Programozási modellek

1. Hétköznapi algoritmusok

1.2. Italautomata használati algoritmusa

Az előző példában egy olyan algoritmust láttunk, ahol elemi tevékenységeket kellett végrehajtani, mindegyiket végre kellett hajtani, s adtunk hozzá egy egyértelmű végrehajtási sorrendet.

Egy italautomata használatának menetén keresztül most azt vizsgáljuk, hogy elemi lépéseket hogyan, milyen sorrendben lehet végrehajtani.

Ebben az algoritmusban a várakozás az előző fejezetbelivel szemben egy nem pontosan definiált tevékenység. Módosítsuk az algoritmust!

Itt megjelent egy újdonság: elemi tevékenység többszöri végrehajtása. A végrehajtás számát egy feltételtől tettük függővé: addig kell várni, amíg megtelik a pohár. Az egymás után végrehajtandó elemi tevékenységek is különbözőek. Például a Vedd ki a poharat! és az Idd meg az italt! nevű tevékenységet csak ilyen sorrendben lehet elvégezni, fordítva nem, s egyszerre sem. Ugyanakkor a Válaszd ki a megfelelő italt! és a Dobj be egy 100 Ft-ost! tevékenységek sorrendje tetszőleges lehet, sőt akár egyszerre is végezhetjük őket.

Tehát, ha elemi tevékenységek mindegyikét végre kell hajtani, akkor a végrehajtás sorrendjére három szabály is alkalmazható: Adott sorrendben egymás után kell végrehajtani, tetszőleges sorrendben lehet egymás után végrehajtani, lehet párhuzamosan, egyszerre végrehajtani őket.

A bevezetőben arról volt szó, hogy az algoritmus végrehajtása nem feltétlenül véges. Ez persze a legtöbb esetben (mint most is) hiba. Ezért, amikor elemi tevékenységek ismétlését írjuk le, akkor mindig meg kell gondolni, hogy az ismétlés befejeződik-e.

Most például elképzelhető a végtelenség, ha az automata csak félig adja a poharat. Módosítsuk az ismétlés feltételét!

Persze elképzelhető, hogy a pohár megtelik, s az ital tovább folyik. Érdemes ezen is elgondolkodni, de most mi más úton fogunk továbbhaladni.

Nézzünk egy másik problémát! Mit tehetünk, ha nincs 100 Ft-osunk és az automata elfogad 20 Ft-osokat is?

Újdonság itt az, hogy most megadtunk két tevékenységet (Dobj be 5 db 20 Ft-ost!, valamint Dobj be egy 100 Ft-ost!), de közülük csak az egyiket kell elvégezni, azaz választani kell közülük.

A megoldás nem tartalmazza azt a lehetőséget, amikor nincs sem 20, sem 100 Ft-osunk. Ugyanakkor, ha van 5 db 20 Ft-os és van 100 Ft-os is, akkor a fenti két lehetőségből bármelyiket választhatjuk.

Tehát újdonságként megjelent a több lehetőségből való választás, amelyben ráadásul a választás nem is egyértelmű.

Nézzük meg, mit tehetünk, ha egyáltalán nem folyik ital!

Most egy olyan utasítást is be kellett vezetnünk, amely azt szervezi meg, hogy valamit vagy végre kell hajtani, vagy nem. Fölbukkant egy újabb fajta ismétlés is, ebben csak az után nézzük meg, hogy kell-e még ismételni, miután az ismétlődő utasítás(oka)t egyszer már végrehajtottuk.

A 20 Ft-osokat persze egyenként kell bedobni, s nem egyszerre. Ezért a megoldás kicsit precízebben így fogalmazható meg:

Harmadik fajta ismétlést láthatunk ebben a megoldásban: megmondtuk pontosan, hogy hányszor kell az ismétlendőt megismételni.

Nézzük meg, hogy az összetett algoritmusainkat milyen módon bontottuk elemibbekre!

• (1) Az összetett algoritmus több elemi algoritmusból áll, és mindegyiket végre kell hajtani.
• (a) A végrehajtási sorrend adott, s egyszerre csak egyet lehet végrehajtani.
• (b) A végrehajtási sorrend tetszőleges, s egyszerre csak egyet lehet végrehajtani.
• (c) A végrehajtási sorrend tetszőleges, akár egyszerre is végre lehet hajtani az összeset.
• (2) Az összetett algoritmus egy vagy több elemi algoritmusból áll, és ezek közül csak legfeljebb az egyiket kell végrehajtani.
• (a) Egy elemi algoritmust vagy végrehajtunk, vagy nem.
• (b) Kettő elemi algoritmus közül egyértelműen választanunk kell az egyiket.
• (c) Sok elemi algoritmus közül egyértelműen választanunk kell az egyiket.
• (d) Sok elemi algoritmusok közül választanunk kell az egyiket, de a választás nem egyértelműen definiált.
• (3) Az összetett algoritmus 1 elemi algoritmus ismétléséből áll.
• (a) Tudjuk, hogy pontosan hányszor kell végrehajtani.
• (b) Tudunk mondani egy feltételt, aminek teljesülése esetén még végre kell hajtani.
• (c) Tudunk mondani egy feltételt, aminek teljesülése esetén még végre kell hajtani, de a feltétel vizsgálatához az ismétlendőt egyszer már végre kellett hajtani, azaz legalább egyszer lefut az ismétlendő.

Az 1/b és az 1/c megvalósítható az 1/a segítségével, a 2/d pedig a többi 2-es valamelyikével, így ezekkel külön nem foglalkozunk.

Az 1. megvalósítását a programozásban egymás utáni végrehajtásnak, szekvenciának nevezzük, a 2.-at választásnak vagy elágazásnak, a 3.-at pedig ismétlésnek vagy ciklusnak.

Az 1/b és a 2/d hozná be a programozásba az ún. nemdeterminisztikusságot, az 1/c pedig a párhuzamosságot.

Vissza a tartalomjegyzékhez