Egyszerű algoritmusok
Az algoritmusban megadjuk egy feladat véges számú lépésben végrehajtható megoldását.
A lineáris, vagyis egyszerű algoritmus, elemi lépések egymás után végrehajtott sorozatából áll. Egy lineáris algoritmus tervezésénél mindig törekedni kell arra, hogy a lehető legkevesebb lépésből oldjuk meg a feladatot.
Először a feltétlenül végrehajtandó lépéseket kell megvizsgálni. Egy problémamentes lépéssorozat kialakítása során, úgy vesszük, hogy a probléma megoldásának megvalósulását semmilyen tényező nem befolyásolja, csak a legszükségesebb műveletek elvégzése a cél.
Például a probléma: elfogyott otthon a kenyér. A megoldás egyszerű, lineáris lépései: lemegyünk a boltba, levesszük a kenyeret a polcról, kifizetjük, majd hazavisszük. Ebben az esetben nem merülnek fel a következő problémák: van-e nálunk pénz? Van-e a boltban kenyér? Ha többféle kenyér van, melyiket válasszuk? Bármely problémára adott lépéssorozatnak van problémamentes, egyszerű változata.
A tervezést általában egy lineáris algoritmus összeállításával kezdjük, majd megvizsgáljuk, hogy mely lépéseknél merülhetnek fel problémák, feltételek. Ezt követően az egyes lépéseket rögzítjük valamilyen formában, például folyamatábrával. Az egyszerű lineáris algoritmus folyamatábrával ábrázolva egymás alatti téglalapokból, azaz általános utasítások sorozatából áll.
Feltételes algoritmusok
Az algoritmus lépések egymás utáni sorozata, melyek végrehajtása egy probléma megoldásához vezet. A problémák nagy része egyszerű, lineáris algoritmus segítségével nem valósítható meg. Néhány lépésnél előre nem látható feltételek léphetnek föl, amelyek eredményétől függ a továbblépés. Ilyen esetekben az elemi lépések közé feltételeket, más néven elágazásokat kell beépítenünk.
Feltételes algoritmus esetén a feltétel minden lehetséges eredményét meg kell határoznunk, és fel kell használnunk a folyamatban. Például: ha hideg van, pulóvert veszünk fel, ha nem, akkor pólót. Ebben az esetben az öltözködés lépésénél új információra, azaz a hőmérsékletre van szükség a továbblépéshez, vagyis ahhoz, hogy mit vegyek fel.
Az elágazás
Az algoritmus lépések sorozata, mely elvezet egy probléma megoldásához. Az algoritmus tartalmazhat feltételt, más néven elágazást.
Az elágazásnak több fajtája ismert. Egy feltétel után a következő lépés kétfelé vagy kettőnél többfelé folytatódhat. Az előbbit nevezzük kétfelé ágazásnak, az utóbbit többfelé ágazásnak. Kétfelé ágazás esetén a feltétel, egy állítás eldöntése. Az állítás logikai értékétől függően, ha az állítás igaz, akkor az egyik irányban, egyik ágon folytatódik az algoritmus, ha hamis, akkor a másikon. Például, telefonon szeretnénk megbeszélni, elintézni valamit. Ha a hívott fél felveszi, beszélünk vele, ha nem akkor letesszük a telefont.
Többfelé ágazás esetén a feltétel egy kifejezés vagy tartomány. A tartományon belül eső értékek irányában többfelé folytatódhat az algoritmus. Ha az egyik értékre teljesült a feltétel, akkor nem kell tovább vizsgálódni, mert a több lehetőség közül egyszerre csak egy teljesülhet.
Egyszerű példa erre a köszönés algoritmusa, ha a napszaknak megfelelően akarunk üdvözölni valakit.
Ha az időpont 6 és 9 óra között van, akkor a köszönés „Jó reggelt.”.
Ha az időpont 9 és 18 óra között van, akkor a köszönés „Jó napot.”.
Ha az időpont 18 és 22 óra között van, akkor a köszönés „Jó estét.”.
Ha az időpont 22 és 6 óra között van, akkor a köszönés „Jó éjszakát.”.
Az algoritmusok leírására mi mondatszerű leírást, folyamatábrát vagy struktogramot használunk. Mondatszerű leírásban az elágazás jelölése:
- Ha feltétel Akkor tevékenység1,
- Egyébként tevékenység2,
- Elágazás vége.
Az elágazást a folyamatábrában rombusszal, struktogramban ferde vonallal jelöljük.
Ciklusok
A problémák lépéssorozattal megadott megoldása az algoritmus. Egy feladat megoldásánál felmerülhet, hogy néhány műveletet többször is végre kell hajtanunk. Az ilyen ismétlődést tartalmazó adatszerkezetet ciklusnak nevezzük. Az ismétlődő utasítások alkotják a ciklusmagot. A ciklusoknak három csoportját különböztetjük meg.
A számlálóciklus esetében pontosan tudjuk és megadjuk, hogy a ciklusmagban lévő műveleteket hányszor ismételjük meg. Például egy napirendet leíró algoritmusban szerepelhet a fogmosás művelete, amit háromszor kell megismételnünk. Általános formája mondatszerű leírással:
- Ciklus n-szer
- Ciklusmag (műveletek, amiket ismételünk)
- Ciklus vége.
Az előbbi példa esetében:
- Ciklus 3-szor
- Fogmosás
- Ciklus vége.
A számláló ciklusban betűvel is jelölhető ciklusváltozókat is megadhatunk az ismétlés számának leírására. Amikor azt tervezzük, hogy a hét minden napján futunk, akkor egy hetirendben a futást, mint ciklusmagot hétszer fogjuk végrehajtani. Például, ha algoritmust készítünk arra, hogy születésnapunkra tíz barátunknak írjunk meghívót, akkor a ciklusváltozó kezdőértéke 1 lesz és egyesével nő 10-ig. Tehát ebben az esetben a ciklus 10-szer fut végig. Általános formája mondatszerű leírással:
- Ciklus ciklusváltozó:= kezdőértéktől végértékig
- Ciklusmag
- Ciklusváltozó növelése
- Ciklus vége
Az előbbi példát tekintve:
- Ciklus i:=1-től 10-ig
- Meghívó írása
- i növelése
- Ciklus vége
Egyes algoritmusok megoldásánál több változót is kell használnunk. Ha a ciklusmag végrehajtása egy feltételtől függ, és ezt a feltételvizsgálatot a ciklus utasításai előtt értékeljük ki, akkor előltesztelős ciklusról beszélünk. Általános formája mondatszerű leírással:
- Ciklus amíg feltétel (igaz esetén)
- Ciklusmag
- Ciklus vége
Ha például nagyon szeretjük a cseresznyét és sok van otthon, mondhatjuk, hogy addig esszük, amíg jól nem lakunk belőle.
Ha a feltétel nem teljesül, akkor a ciklus nem hajtódik végre.
A ciklusok harmadik csoportját hátultesztelős ciklusnak hívjuk. Ebben az esetben a ciklusmag utasításait addig ismételjük, míg a ciklus végén lévő feltétel nem teljesül. Mivel a feltétel a ciklus végén helyezkedik el, a ciklusmag legalább egyszer végrehajtódik. Általános formája mondatszerű leírással:
- Ciklus
- Ciklusmag
- Amíg feltétel igaz
- Ciklus vége
Ha például szeretünk korcsolyázni, és lehetőségünk van rá, mert van a közelben jég és jó a korcsolyánk, mondhatjuk, hogy addig minden nap kimegyünk korcsolyázni, amíg van rá lehetőségünk, vagyis jó a jég.
21. századi közoktatás - fejlesztés, koordináció (TÁMOP-3.1.1-08/1-2008-0002)
