menu
shopping_cart
0
KOSÁR

16. lecke

Az algoritmus

lightbulb_outlineMegtudjuk mi az az algoritmus és hogyan lehet leírni.

Az algoritmus egy módszer vagy útmutatás egy bizonyos probléma megoládásra.

Az egész életünk algoritmusok köré épül: Amikor reggel felkelünk, akkor a fejünkben lefut egy algoritmus, ami leírja a teendőinket. Az emberek átlagosan 8:00-kor kelnek. 8 előtt senki sem szeret felkelni, így ha reggel fel is ébredtunk addig nem kelünk ki a puha ágyból, amíg el nem hagyta a kismutató a 8-as számot az órán.

Tehát a fejünkben egy vizsgáltot végzünk, ami a kismutató állapotát vizsgálja. Ezután nekiállunk reggelizni. A tányérunkba szórunk egy kis zabpelyhet és amíg el nem fogynak a falatok addig lapátoljuk az arcunkba az ételt, szépen ciklikusan.

A ”reggelinek” nevezett műveletvégzés addig fut amíg a tányér állapota üres nem lesz. Ez is egy fontos mozzanata a reggeli teendőinknek és ha nem is tartjuk számon ilyen hivatalosan a fejünkben, hogy mit is jelent a reggelizés folyamata – azért valahol az agytekervényeinkben a tudatalattink tudja mit kell csinálni.

A programozásban is előkerül az algoritmus fogalma. Problémáink vannak, amit meg kell oldani valahogyan. A megoldás lépésekből áll, valahol vizsgálatot végzünk, valahol ciklikusan ismételünk dolgokat – ugyanúgy mint a való életben. A programjaink egyre bonyolultabbak lesznek, egyre több sorból fognak állni és a probléma megoldását jó lenne emberi nyelven is leírni, hogy komplex programok esetén is könnyen átlássuk, mi programozók az algoritmus lépéseit – és esetleg a programozáshoz nem értő egyének is megértsék a programunk működését.

Eddig egy C programra úgy tekintettünk mint egy dobozra: A doboznak volt bemenete, amit a felhasználó gépelt be, és eredményként a doboz valamit kiköpött a képernyőre.

A doboz tartalma sokféle lehet. Egy programot nem csak egyféleképp lehet megvalósítani. Ahány ember annyi ötlet, annyi megvalósítás. A különböző algoritmusok leírására használhatjuk a pszeudokódot vagy a folyamatábrát

Pszeudokód

Az algritmus leírására használható egyik módszer a pszeudokód.

A pszeudo jelentése: Hamis, ál. Lényegében a pszeudokód nem igazi programkód, nem kapcsolódik semmilyen programozási nyelvhez – hanem csak egy formális leírása az algoritmusnak. Nézzük meg az előbb vázolt reggeli teendők leírását ilyen forámban:

Felfedezhetjük a pszeudokódban mindazokat a programszerkezeteket amit eddig használtunk, péládul kezdésnek itt van az IF-ELSE szerkezet. Ha elmúlt 8 óra fel kell kelni, különben tovább kell aludni. Vannak a pszeudokódban műveletek is, ilyen például a kelj_fel(); vagy az aludj(); vagy a reggeli(); Az első kettő műveletnek nincsenek paraméterei, azok egyszerűen lefutnak – a reggelizés művelete pedig vár egy paramétert, az ételt. Mert ugye nagyon sokféle ételt ehetünk reggelire: zabpelyhet, szendvicset, vagy esetleg kolbászos-zserbót is. :) Éppen ezért ennek a parancsnak a működését pontosítanunk kell paraméter segítségével.

A pszeudokód nem tartalmaz kapcsos zárójeleket, helyette a blokkok kezdetét és végét TABulálással jelölik ki, így is egyszerűsítve az eredeti programkódot. Sokszor nem behúzásokat alkalmaznak, hanem leírják, hogy hol van a blokk kezdete és hol van a vége a ”kezdet” és ”vég” szavakkal.

Nincsenek szabályok, inkább csak szokások, hisz ez nem egy szabványosított programozási nyelv, hanem csak egy emberi nyelven leírt algoritmus.

A pszeudokód nem csak egy részből állhat, hanem sok kis egységből is felépülhet. A reggeli(); és a mosogat(); parancsokat is le lehet írni, ugyanúgy, mint a főprogramot. Ő hozzájuk is tartozik egy kód:

Az ilyen kifejtett parancsokat függvényeknek nevezzük és a későbbiekben részletesen megismerkedünk velük. Az eddig írt C programjainknak csak főprogram része volt, semmi más blokk nem volt benne. Később nem csak main{} blokkunk lesz, hanem mi is írunk saját függvényeket.

Folyamatábra

A programjaink másik leírási módszere a folyamatábra.

A folyamatábra dobozokból és nyilakból áll. A dobozok vagy programszerkezeteket jelölnek, vagy parancsokat – a nyilak pedig megmutatják a vezérlés irányát. Legutóbb az IF és IF-ELSE programszerkezettel foglalkoztunk, lássuk ezek folyamatábráját:

Az egyszerű IF feltételnek csak 1 darab {} kapcsos zárójeles része van, ezért is látunk az első folyamatábra igaz ágában egy "parancsok" nevű dobozt. Az IF-ELSE feltétel 2 darab {} kapcsos zárójeles részből áll, ez a jobb oldali folyamatábrán is látszik: Vannak parancsok a hamis ágon is és az igaz ágon is.

A parancsok végrehajtása a programkódban fentről lefele történik, ezért a folyamatábrába is felül kell belépni és a nyilat követni. A folyamatábrákon a feltételek vizsgálatát egy rombusz alakzattal jelöljük. A vizsgált feltétel lehet igaz vagy hamis, ezért az IF folyamatábrája 2 szálra ágazik szét: lesz egy olyan ág amibe akkor lépünk, ha feltétel igaz lett, és lesz egy olyan amikor hamis.

Egyszerre csak egy ágba léphetünk, mivel csak egy darab vezérjelünk (hivatalos nevén vezérlési token-ünk) van, ami végigfut a szálakon. (Párhuzamos programozás alkalmazásakor lenne több tokenünk, amik egymástól függetlenül szaladgálhatnának a szálakon, de mi most csak az egyszálas vezérlésnél maradunk.)

Később szuper izgalmas programozási trükköket tanulunk, amiket ezekkel a folyamatábra alakzatokkal tudunk majd lerajzolni:

A programunk rajza egy lekerekített sakrú START dobozzal kezdődik. A programot a STOP alakzattal kell zárni. A folyamatábra feltételek vizsgálatakor több szálra bomlik. Ezeket a szálakat valamikor egyesíteni kell, erre való a csomópont alakzat. Adatokat vihetünk be, és írhatunk ki, ezeket jelezni kell – sőt van nekünk a ciklikus programfolyamatok lerajzolásához is egy alakzatunk.

Egyre bonyolultabb programokkal fogunk találkozni, amihez jól jön ez a leírási módszer. A jegyzet későbbi részében itt-ott előkerülnek folyamatábrák, pszeudokódok amivel algoritmusokat írhatunk le.

Na de mégis hogyan lehet egy probléma megoládsának algoritmusát meghatározni?

A válasz: sehogy. Egy probléma megoldására nincs általános módszer. Egy programozási feladat lekódolásához nem lehet általános iránymutatást adni, mivel minden megoldás, minden algoritmus más és más. (Ezért lehet egyesek számára nehéz programozni, mivel hozzászoktak a magoláshoz és a feldatokat már megoldott feladattípusokhoz próbálják hasonlítani, ami itt nem célravezető.)

Segítség, most mitévő legyek?

Keress szabályosságokat, keress építőelemeket. A programozás olyan mint a pázli. Vannak építőelemeink és ezeket össze kell kapcsolni valahogyan. A legfontosabb pázlidarabok amiből kettőt már ismersz:

A változókban adatokat tárolhatunk, az IF-fel vizsgálhatjuk őket, a FOR-ral, amit a következő fejezetben ismersz meg pedig ciklikusan ismételgetheted a parancsokat. Ezekből lehet építkezni.

Az építkezés során nem árt tervet készíteni. A terv a következő részekből áll:

  1. adatszerkezet megtervezése

  2. algoritmus megtervezése

Az adat és a program elkülönül. Egyelőre csak egyszerű adattípusokat ismerünk, mint például az egész szám, valós szám és a karakter – de már a karakter típusból összeraktunk egy nagyobb egységet: a karakterláncot, ami sok karakter egymás után. A későbbiekben megismerünk más adatszerkezeteket is.

Az algoritmust megtervezni nem egyszerű feladat, nagyon sok gyakorlás kell hozzá, de egyszer csak ráérez az ember. Egy jó módszer, ha a leprogramozandó feladatot összehasonlítjuk a való életbeli megoldásával. Gondoljuk meg hogyan csinálnánk az életben/ fejben és keressünk analógiát a programozáshoz, keressünk szabályosságokat ami fel lehet használni.