Számábrázolás. Alprogramok

Tömbök

/* 10 elem, tomb[0…9] */
int tomb[10];

for (i=0; i<10; i+=1)
   printf("%d\n", tomb[i]);

• Sorszámozott tároló
• Egyforma típusú elemek
• Adatok ↔ programok: sok elem → tömb, sok művelet → ciklus

Tételek

/* 'E' betűk számlálása */
db=0;
scanf("%c", &betu);
while (betu!='\n') {
   if (betu=='e' || betu=='E')
      db+=1;
   scanf("%c", &betu);
}

• Számlálás, összegzés, keresés…
• Megoldási sémák gyakori, alapvető problémákhoz
• Átalakíthatók egy adott feladathoz

Hajnal Márk rajza

Számítógép, számábrázolás, számrendszerek

Processzor

CPU (central processing unit)

Memória (memory)

Ez tárolja az adatokat és a programokat

Perifériák (peripheral device)

HDD, DVD, megjelenítő, billentyűzet, egér, hangkártya, óra, …

Busz v. sín (bus)

Vezetékek, amelyeken a kommunikáció történik.

CPU működése

• Elemi, egyszerű lépések: gépi utasítások
• A fordítóprogram állítja elő a C forráskódból

x=x+2;

mov   eax, 1055h   x a memóriából a processzorba
add   eax, 2       a processzor hozzáad 2-t
mov   1055h, eax   eredmény a memóriába

Memória működése: számok tárolása

• Karakterek → számok
• Képek → fényesség értékek → számok
• Hang → levegőnyomás értékek → számok
• Gépi utasítások (mov, add) → számok

Érdekesség: A végrehajtott program, és az adatok, amelyeken a program dolgozik, lehetnek külön memóriában is. Az első automatikusan működő számítógépek a programot nem a belső memóriájukban tárolták, hanem papírszalagról vagy lyukkártyáról olvasták be azt futás közben. Ennek egyszerűen az volt az oka, hogy nagyon költséges és bonyolult volt relékből (lásd lent) memóriát csinálni. A tervezők pedig ott spóroltak, ahol tudtak. Ahogyan a technika fejlődött, úgy vált lehetővé, hogy a programot is a központi memóriában tárolják. Ezt az elvet Neumann János (John von Neumann) javasolta kollégáival, és ma Neumann-féle architektúrának nevezzük. Az első ilyen elven működő számítógép az EDVAC nevet viselte. Ez egyben az első kettes számrendszert használó, már nem elektromechanikus, hanem teljesen elektronikus számítógép volt. A külön programmemória elve a fentiek ellenére nem halt ki: ezt ma Harvard architektúrának nevezzük, az EDVAC-nál régebbi régebbi Mark I számítógép nyomán.

A mai számítógépek digitális elven működnek. Csak egész számokkal tudnak dolgozni, amelyeket kettes számrendszerben tárolnak. A kettes számrendszer előnye az, hogy csak két állapot van benne: 0 és 1. Ez elektronikusan könnyen kezelhető (nincs áram, van áram), ezért a működést kapcsolók adják. Bármi, ami kapcsolóként tud működni, az használható számítógép építésére is.

Az alábbi fényképek a számítógépek generációit mutatják. Ezek elvben nem különböznek egymástól, csak a gyakorlatban, méghozzá abból az egyetlen szempontból, hogy milyen elektronikus, vagy esetleg még elektromechanikus eszközt használtak kapcsolónak. Az első három képen lévő eszköz egyetlen kapcsolónak felel meg, míg a jobb alsó képen látható integrált áramkörön már sok millió kapcsoló van. Összehasonlításképp: 3-4000 kapcsoló használatával már egészen jól használható processzor tervezhető, egy Core i7 processzorban viszont már 730 millió darab van.

Relék (relay): az áram hatására a bennük lévő tekercsben (jobb oldalt) mágneses tér keletkezik, és így lehet vezérelni a kapcsolót (bal oldalt). Egy ilyen eszköz kb. 3-4 cm nagy. Manapság is használnak ilyet nagyobb áramok kapcsolására, pl. autókban is.

Elektroncső (tube): a bennük lévő vákuumban repülő elektronok mozgása vezérelhető az elektromos tér változtatásával. Ezek is viszonylag nagyok: 3-4 cm, ráadásul fűteni kell a belsejüket, hogy az elektronok kilépjenek a fémből.

Tranzisztor (transistor): a félvezető anyagok vezetőképessége (ellenállása) elektromos úton szabályozható, így kapcsolónak is használhatóak. A képen látható tranzisztorban a félvezető szilícium darabka 1 mm-nél is kisebb. A védő fém vagy műanyag tokozás nagyobb, 3-4 mm-es.

Integrált áramkör (integrated circuit): ebben is tranzisztorok vannak, azonban az előzőnél jóval kisebbek. Egy 1 cm² méretű szilícium lapra akár több tízmillió transzisztor integrálható, amelyek egyesével alig néhány tíz nanométeresek (vagyis méretük egy ember hajszál vastagságának ezrede). A fenti processzor mikroszkóp alatt forgatva egy videón is látható.

Római: I, II, III, IV, V, … X, C, D, M

• Egyszerű összeadás: III + VIII = VIIIIII = VVI = XI

  1
 123
+639
────
 762

Hindu-arab: 345, 1203, 2615

• Megjelenik a nulla!
• Számjegyek, helyiértékek – egyszerű a szorzás, osztás is! Minden helyiérték ugyanúgy működik.
• 2615 = 2·10³ + 6·10² + 1·10¹ + 5·10⁰

Szám: _tíz    →    _kettő

Az átalakítás lépései: a számot leosztjuk kettő első olyan hatványával, amely nagyobb nála. Az eredmény egy számjegy, a hányadost pedig felírjuk a következő oszlopba. Így folytatjuk az egyre kisebb hatványokkal, amíg el nem érünk 0-ig. (A legutolsó esetben eggyel osztunk, aminek a maradéka biztosan nulla lesz már.) Az osztások során sehol nem kaphatunk 1-nél nagyobb értéket; ha ilyen történne, akkor kettő egy nagyobb hatványától kell indulnunk.

Szám: _kettő    →    _tíz

Az átalakítás lépései: a szám számjegyeit (alaki értékek) összeszorozzuk kettő megfelelő hatványaival (helyi értékek). Az így kapott számok (valódi értékek) összege adja az eredményt.

A más számrendszerekbe átalakítás ugyanígy működik, csak az ottani alap hatványait kell használni.

Érdekesség: A kettes számrendszernek minden más számrendszernél nagyobb jelentősége van. A 0 és 1 számjegyeket nagyon könnyű automatikusan, elektronikusan kezelni: van áram – nincs áram, világít a lámpa – sötét a lámpa, be van kapcsolva – ki van kapcsolva a kapcsoló. A „binary digit”, azaz bináris számjegy szókapcsolatot eredetileg „bigit” vagy „binit” néven rövidítették. Később a „bit” szót John Tukey, amerikai matematikus javasolta. (Ő találta ki a „software” szót is.)

A szó tudományos írásban először Claude Shannon M.Sc. diplomamunkájában szerepelt, amelynek címe A Symbolic Analysis of Relay and Switching Circuits. Ebben megmutatta, hogy az addig telefonközpontokban használt relék segítségével logikai problémák is megoldhatóak. Pár évvel később megépült az első relékből felépített, kettes számrendszert használó számítógép, a Harvard Mark I. Azóta gyakorlatilag nem készül olyan számítógép, amely nem bináris elven működne.

Bitek és bitcsoportok

bit

Az információ alapegysége: 0 vagy 1.

bájt (byte): bitek csoportja

A memória legkisebb egysége: általában 8 bit.

szó (word): több bájtos adategység

Általában 4 bájt (32 bit), vagy 8 bájt (64 bit).

Előtagok (prefix)

kilobájt (kB) és kibibájt (KiB)

10³=1000 ≈ 2¹⁰=1024 bájt.

megabájt (MB) és mibibájt (MiB)

10⁶=1000000 ≈ 2²⁰=1048576 bájt.

gigabájt (GB, GiB), terabájt (TB, TiB)

10⁹≈2³⁰ és 10¹²≈2⁴⁰ bájt.

A kettes számrendszerbeli működés miatt a szokásos mértékegységeknek megvan a bináris párja. Bár a kilo- előtag általában ezret jelent, a számítástechnikában inkább 1024-et, azaz 2¹⁰-t. Ezt azért választották meg így, mert a kettő között nagyon kicsi a különbség. Sajnos gyakran keverik is a kettőt. A merevlemezgyártók például előszeretettel használják a kilo=1000 jelölést, mert így nagyobb kapacitást írhatnak rá az eladott merevlemezekre. Hogy ne kelljen mindig hozzátenni, ha pontosak akarunk lenni, hogy a bináris vagy a decimális prefixumról beszélünk, bevezették a kibibájt, mebibájt stb. jelöléseket. Egy DVD kapacitása így 4,7 gigabájt, azaz 4,3 gibibájt.

Túlcsordulás: ha nem fér el az eredmény

 11111111        255    
  
+00000001       +  1    
─────────        ───    
100000000        256 → 0

Ha egy eredmény nem fér el az adott bitszámban, túlcsordulást kapunk. Emiatt 8 biten: 255+1 = 0, és 0-1 = 255.

A biteket az alsó helyiértékektől számozzuk, aszerint, hogy 2 hányadik hatványának felel meg. 2⁰ → 0. bit, 2¹ → 1. bit stb. A helyiértékek matematikából megszokott neve alapján a legkisebb helyiértékű bitet (least significant bit, LSB) legalsónak, a legnagyobb helyiértékűt (most significant bit, MSB) legfelsőnek nevezzük.

Negatív számok tárolása: a kettes komplemens

• Használjuk ki, hogy 11111111_kettő+1 = 0
• Az előjelet a legfelső bit dönti el
• Legfelső bit 0 → nemnegatív szám.
  00000011 → értéke 3_tíz
• Legfelső bit 1 → negatív szám.
  Értéke a többi bit negáltja + 1:
  11111110 →  0000001_kettő + 1 = 2_tíz → a szám −2

A kettes komplemens ábrázolás előnye, hogy a túlcsordulások miatt automatikusan előállnak a helyes pozitív/negatív értékek – nem kell megkülönböztetnie a hardvernek (az áramköröknek) a pozitív és negatív számokkal végzett összeadásokat, kivonásokat. (Egy négy bites példát tekintve 1110+0011=0001, azaz −2+3=1, ami éppen a helyes eredmény.) Ezért mindenhol ezt szokás használni.

Egyébként ugyanez működik tízes alapú számrendszerben is. Pl. 3 számjegyen 17+999=1016, amiből ha eldobjuk a túlcsordulás miatti ezrest, akkor 16-ot kapunk, ami pont 17-1. A témakör a digitális technika tárgyból még fog szerepelni részletesen.

Miért fontos ezt ismerni? Mert így tudjátok, miért adhat a számítógép negatív számot két pozitív összegeként. Mert túlcsordulás történt!

#include <stdio.h>

int main()
{
   unsigned char kicsi;
   int i;
   
   kicsi=1;
   for (i=0; i<20; i+=1) {
      printf("%u\n", kicsi);
      kicsi*=2;
   }
   
   return 0;
}

Típusok, amelyekkel érdemes kipróbálni: unsigned char, signed char, short. Bármekkorával is próbáljuk, előbb-utóbb előjön a probléma. Ha kettővel szorozgatjuk a számot, akkor előbb-utóbb nulla lesz az eredmény, így könnyű tetten érni a hibát. Ha hárommal szorzunk a ciklusban, akkor már kevésbé!

Lebegőpontos ábrázolás (floating point)

± mantissza · 2karakterisztika

• Pl. 4 = 1·2² = 100_kettő, ¼ = 1·2^-2 = 0.01_kettő
• Véges a méret: adott bitszám a mantisszának és a kitevőnek
• Korlátos az ábrázolható számtartomány és a pontosság is:
• A számítások eredménye sokszor nem pontos!
• Az == és != operátorok használata általában értelmetlen, de a többi is adhat váratlan eredményt

a    10000000000000.0000000
b   +             0.0000001
    ───────────────────────
a+b  10000000000000.0000001 → 10000000000000 lesz!

#include <stdio.h>

int main()
{
   double szam;

   printf("%e\n", 
     1.0/2.0 + 1.0/3.0 + 1.0/6.0 - 1);

   printf("%.16f\n", 9.95);
  
   for (szam=0; szam<1; szam+=0.1)
      printf("%f\n", szam);

   return 0;
}

A támogatott típusok itt is eltérnek számítógépenként. A long double gyakran nem létezik, hanem a double szinonímája csak.

Ha valós szám kell, legtöbbször double-t használunk.

Figyeljünk arra, hogy a printf()-nek és a scanf()-nek adott formátumkód a double esetében nem ugyanaz. A kiíráshoz ennél %f kell, a beolvasáshoz %lf. Ennek mélyebb, történelmi okai vannak, amelyek itt nem lényegesek.

A tizenhatos számrendszer

• Kettes számrendszer: túl sok számjegy
• Tizenhatos (hexadecimal) számrendszer kényelmesebb
• 4-es csoportokban (nibble) átalakíthatóak
• Pl. 10011111_kettő = 9f_tizenhat
• A 10…15 alaki értékek jelölésére az a…f vagy A…F betűket használjuk

Használhatnánk a nyolcas számrendszert is azzal a céllal, hogy spóroljunk a számjegyekkel. Azzal azonban van egy kis probléma. Manapság szinte mindegyik számítógépen nyolc bites a bájt. Ha egy ilyet nyolcas számrendszerben írunk le, akkor 2-3-3 bites csoportok adódnak: 10'101'111_kettő=257_nyolc. Ezzel önmagában nem is lenne probléma, azonban ha egy két bájtos, azaz 16 bites számot szeretnénk átírni, akkor az egymás mellé tett bájtok nyolcas átírása eltér attól, mint a két bájtté külön. Ha az előző bitsorozatot kétszer egymás mellé írjuk, annak átírása: 1'010'111'110'101'111_kettő=127657_nyolc, nem pedig 257257_nyolc, ahogyan a két nyolcas számrendszerbeli egymás után írása miatt gondolnánk. A tizenhatos számrendszerrel nincs ilyen probléma, mert ott nem három, hanem négy bit van egy csoportban, és egy bájt nyolc bitje pontosan két csoportot ad. A négybites csoportok angol neve a nibble (esetleg nybble).

Számok megadása C-ben (numerikus literálisok)

• 23: egész szám
  • Kettes számrendszerben megadott konstans nincsen!
  • 012 = 12_nyolc (0-val kezdődik), 0xFCE2 = FCE2_tizenhat (0x-szel kezdődik)
  • Ritkán: 12U, 12u – unsigned, 12L, 12l – long
• 3.14: valós (van benne . vagy e)
  • .45 = 0,45 (a legelső 0 elhagyható)
  • 6.022e23 = 6,022·10²³
  • Ritkán: 12.3F – float, 12.3L – long double

Bitműveletek

A Boole-féle algebrában a változóknak két értékük lehet: HAMIS és IGAZ, vagy bitekben gondolkodva 0 és 1. A sokféle művelet közül a fontosabbak a következők.

NEM
(NOT)

0	1
1	0

ÉS
(AND)

	0	1
0	0	0
1	0	1

VAGY
(OR)

	0	1
0	0	1
1	1	1

KIZÁRÓ VAGY
(XOR)

	0	1
0	0	1
1	1	0

• NOT: mindig az ellenkezője
• AND: akkor 1, ha mindkettő 1 (0, ha a bármelyik 0)
• OR: akkor 1, ha bármelyik 1 (0, ha mindkettő 0)
• XOR: akkor 1, ha nem egyformák (0, ha egyformák)

Ez a művelet két szám bitjeit hozza VAGY kapcsolatba páronként, vagyis az egyik szám 0. bitjét a másik szám 0. bitjével, 1. bitet az 1. bittel stb. A VAGY műveletnél „az eredmény 1, ha bármelyik 1”. Ezt adott bitek 1-be állítására szokás használni.

Feladat: állítsuk egy szám 5. bitjét 1-be!

• Olyan maszk (mask) kell, amiben az 5. bit 1-es, többi 0
• Ez a szám az 1<<5:
  00000001 1
00100000 1<<5
  
• x = x | 1<<5; vagy egyszerűbben: x |= 1<<5;

A két operandusának ugyanolyan sorszámú bitjeit hozza KIZÁRÓ VAGY kapcsolatba. Mivel a kizáró VAGY műveletnél az eredmény akkor 0, ha egyformák a bemeneti bitek, és akkor 1, ha nem egyformák, ezt adott bitek negálására szokás használni.

Feladat: negáljuk egy szám 3. és 4. bitjét!

• A maszk: 1<<3 | 1<<4
• Így: x = x ^ (1<<3 | 1<<4);
• Vagy másképpen: x = x ^ 1<<3 ^ 1<<4;

Az x=x^y kifejezés rövidítve is írható: x^=y, vagyis a fenti példa rövid változata: x ^= 1<<3 | 1<<4;

A két operandusának ugyanolyan sorszámú bitjeit hozza ÉS kapcsolatba.

Feladat: ellenőrizzük, egyes-e a szám 3. bitje!

• Vágjuk ki csak azt a bitet, minden másikat nullázva
• A maszk: 1<<3
• if ((x & 1<<3) != 0) …
• A zárójelezés a műveletek erőssége (precedenciája) miatt szükséges. Különben 1<<(3!=0)-t jelentené a kifejezés jobb oldala.

A ~ operátor a bitenkénti negálás jele C-ben. Ezt egy szám vagy változó neve elé írva olyan számot kapunk, amelyben minden bit ellenkezőjére (negáltjára) van váltva.

Feladat: állítsuk egy szám 3. bitjét 0-ba!

• ÉS: „az eredmény 0, ha bármelyik 0”
• Maszk, amelyben csak a 3. bit 0: ~(1<<3)
• x = x & ~(1<<3);
• Vagy rövidebben: x &= ~(1<<3);

Függvények

Számoljuk meg, hány prímszám van 2 és 1000 között!

int sz, db;
db=0;
for (sz=2; sz<=1000; sz+=1)
   if (… sz egy prím …)  !
      db+=1;

int oszt, van;
van=0;
oszt=2;
while (oszt<sz && !van) {
   if (sz%oszt==0)
      van=1;
   oszt+=1;
}

int sz, db, oszt, van;

db=0;
for (sz=2; sz<=1000; sz+=1) {
   van=0;
   oszt=2;
   while (oszt<sz && !van) {
      if (sz%oszt==0)
         van=1;
      oszt+=1;
   }
   if (!van)
      db+=1;
}

printf("%d prím.\n", db);

Az előző előadáson azzal a megállapítással zártuk ezt a feladatot, hogy a két egymástól független programrész összedolgozása által egy nehezen értelmezhető program keletkezett. Nagyban rontotta az áttekinthetőségét az, hogy az egyik algoritmust bele kellett építenünk a másikba, kettévágva azt. Megírni is nehezebb egy ilyet, hiszen egyszerre több dolgon kell gondolkozni.

Tegyük fel, hogy van egy programrész, amely megmondja egy adott számról, hogy prím-e, vagy nem. Ez a programrész egy ún. függvény. Ahogyan a sin() is, amely kap egy szöget, és megadja annak szinuszát, ez kap egy egész számot, és meghatározza annak prím vagy nem prím voltát. Ha van egy ilyen, akkor a prímek számlálása feladat nagyon egyszerű: a kékkel jelölt „… sz egy prím …” programrész helyére csak annyit kell írnunk, hogy prim_e(sz). Mint az lent is látható, ilyet a C-ben lehet csinálni.

Alprogram (subprogram), szubrutin (subroutine)

Az egész programunk együttműködő alprorgamokból épülhet fel!

if (… sz egy prím …)
   db+=1;

if (prim_e(sz))
   db+=1;

Ezekhez is tartozik specifikáció: bemenet → kimenet összefüggése.

C-ben a nevük: függvény (function)

double negyzet(double x) // x: bemenet
{
   return x*x;           // x²: kimenet
}

A részfeladatokat külön függvényben írhatjuk meg. Így egy nagyobb program áttekinthetőbb, kezelhetőbb lehet. Sőt a gyakran ismétlődő programrészeket is így csak egyszer kell majd megírnunk. A programok így kisebbek, hatékonyabbak lehetnek. Egy feladat elvégzéséhez szükséges programrész kódja csak egyszer fog szerepelni a memóriában, mindenhol máshol csak hivatkozunk rá! A printf() függvényt is egyszer megírta valaki, és mindenhol használhatjuk.

int main()
{
  int db, sz;

  db=0;
  for (sz=2; sz<=1000; sz+=1)
    if (prim_e(sz)) // prím?
      db+=1;
    
  printf("%d db.\n", db);
  
  return 0;
}

int prim_e(int szam) // prím?
{
  int oszt, van;

  van=0; oszt=2;
  while (oszt<szam && !van) {
    if (szam%oszt==0)
      van=1;
    oszt+=1;
  }
   
  return !van;
}

visszatérési_típus függvénynév(paraméterlista)
{
   … függvénytörzs …
   
   return visszatérési_érték;
}

double teglalap_kerulet(double a, double b)
{
   return 2*(a+b);
}

printf("%f", teglalap_kerulet(2, 3.4)); // a=2, b=3.4

Formális paraméter (formal p.): a neveik a függvény fejlécében.

• Szimbolikus paraméternek is nevezik (symbolic parameter)
• A függvényen belüli szerep szerint kell elnevezni

Aktuális paraméter (actual p.): a hívás helyén adott érték.

• Híváskor a megadás sorrendje számít
• Nem csak változó lehet, hanem konstans is
• Automatikusan inicializált lokális változók. Ugyanúgy megszűnnek!

Fontos, hogy a paraméterlista megadásánál minden egyes paraméter elé oda kell írni annak típusát. Akkor is, ha azok egyformák. Ezért van a fenti függvény fejlécében double a, double b, és nem pedig double a,b, ami helytelen szintaktikailag.

#include <stdio.h>

void szamol(int a, int b, int osszeg)
{
   osszeg=a+b;  /* el fog veszni! */
}

int main()
{
   int szum;
   
   szum=0;
   printf("előtte: %d\n", szum);

   szamol(5, 6, szum);
   printf("utána: %d\n", szum);

   return 0;
}

double kerulet(double a, double b); // deklaráció/prototípus

int main()
{
   printf("%f", kerulet(2, 3.4));
   return 0;
}

/* kiszámolja egy a,b oldalú téglalap kerületét */
double kerulet(double a, double b)  // definíció
{
   return 2*(a+b);
}

• A fordítónak a main()-nél tudnia kell, mit jelent a kerulet
• Nevét, paraméterek számát és típusát, visszatérés típusát
• Vagyis deklarálni kell; definiálni ráér később is
• A deklaráció kihagyása hiba!

/* kiszámolja egy a,b oldalú téglalap kerületét */
double kerulet(double a, double b)  // definíció
{
   return 2*(a+b);
}

int main()
{
   printf("%f", kerulet(2, 3.4));
   return 0;
}

int beolvas_szam(void)
{
   int sz;
   scanf("%d", &sz);
   return sz;
}

void kiir_szam(int szam)
{
   printf("%d", szam);

   return;
}

• Ha a függvénynek nincs paramétere, azt a void szóval jelöljük
• Ha nincs visszatérési értéke, azt is
  • Ilyenkor a return önmagában áll: return;
  • Vagy el is hagyható

x=beolvas_szam(); // A híváshoz ilyenkor is kell a ( )
kiir_szam(x);

int negyzet(int szam)
{
   return szam*szam;
}

void szam_kiir(int szam)
{
   printf("%d", szam);
}

Általában igyekszünk olyan függvényeket írni, amelyeknek csak főhatása vagy csak mellékhatása van. Ennek az elvnek neve is van: command-query separation. Eszerint kétféle függvény van. Az egyik fajta a parancsfüggvény (command), amelyet azért használunk, hogy hatása legyen. A másik fajtának kérdéseket teszünk fel (query), amely kiszámol valamit, de mellékhatása nincs. Ha ez a kettő keveredik, az könnyen összevisszasághoz, átláthatatlan programfelépítéshez és nehezen megtalálható hibákhoz vezet.

Fontos: ha a specifikáció nem kéri a kiírást, akkor kifejezetten hibának számít, ha a függvény mégis ilyet tesz! Például kiírja a képernyőre az eredményt ahelyett, hogy visszatérne vele. Hadd döntse el a hívó, mit szeretne csinálni vele!

int fakt(int mie);

printf("%d\n", fakt(6));
printf("%d\n", fakt(6));
printf("%d\n", fakt(6));

720
720
720

#include <stdlib.h>

printf("%d\n", rand());
printf("%d\n", rand());
printf("%d\n", rand());

8311623
2141262
16641798

• Ha a függvény értéke csak a paramétereitől függ, mindig ugyanaz kell legyen az eredmény.
• Ha van mellékhatása, ez nem biztos! Valahol valaminek történnie kell, hogy a rand() mindig mást ad…

Funkcionális dekompozíció

avagy
procedurális programozás
avagy
top-down tervezés

Ernesto Cesàro (olasz matematikus): válasszunk ki véletlenszerűen két egész számot. Annak a valószínűsége, hogy ezek relatív prímek, 6/π².

Feladat: írjunk programot, amely megbecsüli a π értékét!

A következőképpen nézhet ki. Először is, rendezzük az egyenletet:

  6       6
P=─  → π²=─
  π²      P

int main()
{
    double pi = sqrt(6/valoszinuseg());
    
    printf("%f", pi);
    
    return 0;
}

A keresett valószínűséget majd a függvény megmondja.

Hogyan számoljuk ki a valószínűséget? Adott egy kísérletünk, legyen ez kiserlet(). Térjen ez a függvény vissza igazzal, ha a kísérlet sikerült! Végezzük el ezerszer! A sikeres kísérletek számát 1000-rel osztva megkapjuk a becsült valószínűséget.

/* P meghatározása kísérletezéssel */
double valoszinuseg()
{
    int i, db;
    
    db=0;
    for (i=1; i<=1000; i+=1)
        if (kiserlet())     // elvégzi a kísérletet
            db+=1;
    return db/1000.0;   /* egész osztás elkerülése! */
}

Mi a kísérlet? Az, hogy két véletlenszám relatív prím. Gyártsunk ehhez 1 és 1000 között véletlenszámokat, és hasonlítsuk a legnagyobb közös osztójukat 1-hez:

/* A kísérlet: a legnagyobb közös osztójuk 1? */
int kiserlet()
{
    return lnko(rand()%1000+1, rand()%1000+1)==1;
}

És hogyan számolunk legnagyobb közös osztót? Euklidész módszerét megnézhetjük a Wikipédián is. A pszeudokódot csak át kell írni C-be:

/* visszatér a két szám legnagyobb közös osztójával. */
int lnko(int a, int b)
{
    while (b!=0) {
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}

Érdekesség: Donald Knuth amerikai programozó. Leghíresebb műve a „Számítógépprogramozás művészete” (The Art of Computer Programming) című többkötetes könyv. Az ő nevéhez fűződik a TeX nevű szövegszedő program kifejlesztése is, amelynek különféle változatait most is használják könyvek, folyóiratok szerkesztéséhez, szedéséhez. Az elterjedt irodai programcsomagokkal készített dokumentumok külleme meg sem közelíti azt, ami a TeX segítségével elérhető!

Az eredmény

3.131121
_

A funkcionális dekompozíció (functional decomposition) egy tervezési elv. A másik neve a felülről lefelé (top-down) elv. Lényege, hogy a problémát részfeladatokra bontjuk. Az egész rendszert, programot úgy tervezzük meg, hogy közben a részfeladatokat megoldottnak tekintjük. Az egyes részfeladatok megoldása közben így nem kell a többi részleteivel bajlódni. A részfeladatok ugyanúgy specifikálhatóak, mintha egy teljes programról lenne szó.

A funkcionális dekompozíció céljai:

• Felülről lefelé tervezés (top-down design)
• Tervezés egyszerűsítése: „oszd meg és uralkodj”
• A programrészek közötti csatolások csökkentése

Érdekesség: Gerald Jay Sussman amerikai programozó, matematikus, aki legtöbbet a mesterséges intelligenciával foglalkozik. Az ő nevéhez is fűződik a Structure and Interpretation of Computer Programs című könyv megírása is, amelyhez egy programozás alapjait bemutató tárgy is tartozott az MIT egyetemen. A fenti idézet az egyik előadásáról származik. A tárgyat egyébként a saját maguk által kifejlesztett programozási nyelvvel tanították, amelynek a neve Scheme.

A top-down tervezést „wishful thinking” néven mutatta be (kb. ábrándozó gondolkodás). Hiszen éppen ez a lényege: „Bárcsak lenne egy olyan függvény, amelyik megmondja egy számról, hogy prímszám-e… Mert ha igen, akkor milyen egyszerű lenne a feladatunk!” Sokszor ezzel a gondolkodásmóddal tudjuk szétválasztani a részfeladatokat.

A fenti feladat a felülről lefelé (top-down) tervezést szemlélteti. Azt kell látni, hogy minden lépésben csak egy kicsit lépünk a megoldás felé; a következő lépést pedig mindig megoldottnak tekintjük.