Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.6. Az algoritmus megadási módja: a pszeudokód és a folyamatábra.

1.6. Az algoritmus megadási módja: a pszeudokód és a folyamatábra.

Az algoritmust szövegesen adtuk meg a fenti esetekben. Ez egy lehetőség általában az algoritmus lejegyzésére. Elterjedt azonban a pszeudokódos megadás is, mely közelebb viszi a leírást a számítgógépes megvalósításhoz anélkül, hogy elkötelezné magát egy konkrét programozási nyelv mellett. (A programozási nyelvek divatja változik - ma már több programozási nyelv van, mint a beszélt emberi nyelvek száma, - de a már lejegyzett algoritmus lényege nem változik.) Alább ismertetünk néhány pszeudokód konvenciót, megállapodást, amely segít az ilyen módon megadott algoritmusok megértésében.

[1.] Blokkszerkezeteket fogunk használni, amint az sok programozási nyelvben elterjedt. A blokk zárójelezése helyett a bekezdés eltolásának módszerét fogjuk használni.

[2.] Az alábbi strukturális (strukturált vagy kvázistrukturált) utasításokat fogjuk használni:

[3.] Az értékadás jele a jel lesz. Bátran alkalmazzuk tömbök, struktúrák értékadására és többszörös értékadásra is.

[4.] A magyarázatokat, megjegyzéseket // kezdőjellel fogjuk jelezni. Ez lehet egy teljes megjegyzés sor, vagy lehet egy adott sorhoz hozzáfűzött megjegyzés.

[5.] Az eljárásokban használt változók lokálisak lesznek.

[6.] Tömbelemet indexeléssel adunk meg. Lehet egy index (vektor), két index (mátrix), vagy több. Az indexek résztartományát -tal jelöljük. Például jelenti a 3,4,5,6 indexeket.

[7.] Az összetett adatok (objektumok) mezőkkel rendelkeznek, amelyekben az objektum attributumait, tulajdonságait tároljuk. A mezőre a nevével hivatkozunk. A mezőnév mögött szögletes zárójelben feltüntetjük az objektum nevét.

[8.] A tömbök vagy objektumok mutatók révén lesznek megadva. A NIL mutató sehová sem, semilyen objektumra sem mutat. Ha mutat egy objektumra, egy másikra, akkor az értékadás után az is és az is ugyanarra az objektumra mutat, nevezetesen az által jelzettre. Az által korábban mutatott objektum ezáltal elvész, mivel a mutatója eltünt.

[9.] Az eljárások az input paramétereiket érték szerint kapják meg, azaz a paraméterről egy másolat készül (ami a verembe helyeződik el). Az eljárásnak a paramétereken végzett változtatásai a hívó rutinban nem láthatók emiatt, hiszen a veremből ezek a visszatéréskor törlődnek. Objektum paraméter esetén azonban az objektum mutatójának másolata kerül a verembe, nem maga az objektum, ezért az objektum mezőin végzett változtatások a hívó rutinban is láthatóak lesznek a visszatérés után. Nem láthatók viszont magának a mutatónak a megváltozásai. Az input és output paramétereket a paraméterlistán feltüntetjük és megjegyzés sorokban írjuk le azokat. Az output paramétereket a visszatérési RETURN utasításban is megadjuk.

[10.] A pszeudokód nem zárja ki, hogy az algoritmus egyes részeit szöveges módon tüntessük fel.

A fenti iteratív négyzetgyökvonási algoritmus pédául így nézhetne ki. A jobboldalon egy praktikusabb változat látható.

A folyamatábra az algoritmust folyamatában a sík kétdimenziós tulajdonságát kihasználva grafikus szimbólumok felhasználásával teszi szemléletessé. Az alábbi, vízszintes vagy függőleges folyamatvonalak révén egymáshoz kapcsolható szimbólumokat használjuk: A folyamatvonalak összefutását kis körökkel jelöljük.

A folyamatvonalakon a haladás iránya balról-jobbra, vagy fentről-lefelé, hacsak a vonalra kitett nyíl másként nem mutat. Megjegyzést a szimbólumokhoz szaggatott vonallal a szimbólumhoz kapcsolt, megfelelően méretezett kezdő szögletes zárójel jellel lehet hozzákapcsolni. A szöveg a szögletes zárójel mögé kerül.

A négyzetgyökvonás fenti praktikusabb változata folyamatábrával:

A strukturális utasításoknak megfelelő folyamatábra részletek:

Az algoritmusok közül kitűnnek a rekurzív algoritmusok és az iteratív algoritmusok. Mindkét fajta algoritmus hatékonyan realizálható számítógépen. Az iteratív algoritmusok hasonló, vagy azonos műveletek sorozatát ismétlik (a latin iteratio szó ismétlést jelent). A rekurzív algoritmusokban azt ismerjük fel, hogy a probléma mérete redukálható kisebb méretre, majd még kisebb méretre, stb. és a kisebb méretű feladat megoldása után visszatérhetünk (a latin recursio szó visszatérést jelent) a nagyobb méretűnek a megoldásához, amely ezáltal lényegesen egyszerűbbé válik. Iteratív algoritmus volt a Summa algoritmus. és a kézi négyzetgyökvonás algoritmusa. Ugyancsak iteratív algoritmusok az 1.2.1 és 1.2.2 algoritmusok. Rekurzív algoritmus volt a RekSumma és a RekSum algoritmus. A rekurzív algoritmusok mindig átírhatók iteratív formára is. Az említett algoritmusoknak a pszeudokódját az alábbi módon készíthetjük el procedúra formában:

Egy probléma megoldására nem mindig könnyű algoritmust találni még akkor sem, ha ismert, hogy van megoldása a problémának és hogy csak egy megoldása van. (Ha nincs megoldása a problémának, akkor persze nincs értelme algoritmust keresni.) Megemlíthetők azonban általános elvek, amelyek figyelembe vehetők egy-egy algoritmus kidolgozásakor. Ez persze nem jelenti azt, hogy ezen elvek figyelembe vételével biztosan mindig célba is érünk. Az intuíciónak továbbra is korlátlanok a lehetőségei és a szerepe nem csökken. Ilyen általános elvet, algoritmus tervezési stratégiát hármat említünk a könyvben: