Algoritmusok Hogyan csináljam?
1
Az algoritmus fogalma Algoritmusnak olyan pontos előírást nevezünk, amely megmondja, hogy bizonyos feladat megoldásakor milyen műveleteket milyen meghatározott sorrendben kell elvégeznünk. Az elnevezés Mohamed ibn Musza Abu Abdallah al-Hvárizmi al-Madzsúszi alKutrubulli perzsa-arab tudós (800-850) nevének latinos formájából (Algorismus) alakult ki. 2
Az algoritmusok haszna Egy összetett feladat megoldását általában nagy tudású emberek tudják elvégezni. Ha valaki elkészíti egy adott folyamat algoritmusát, a megfelelő utasítások alapján kisebb képességű egyének is végre tudják hajtani a feladatokat.
3
Az algoritmusok szerkezete Az algoritmus műveletekből és vezérlő szerkezetekből épül fel. A művelet egy olyan átalakítás (transzformáció) amely az adatok aktuális értékeit felhasználva előállítja az adatok új értékeit. Például: egy változó értékének növelése eggyel, az adatok sorbarendezése, stb. 4
Vezérlő szerkezetek A vezérlő szerkezetek a feladat műveletekre bontását, és ezek végrehajtási sorrendjét írják le. Vezérlő szerkezetek: szekvencia (műveletsor), szelekció (kiválasztás, döntés), iteráció (ismétlés, ciklus) 5
Algoritmusok a programozásban A program a számítógép „nyelvére” lefordított algoritmus. A program fejlesztése során hasznos dolog az ember számára érthető módon leírni a megfelelő algoritmust.
6
Az algoritmus leírásának módjai Mondatszerű leírás Grafikus ábrázolás Folyamatábra Struktogram Jackson-ábra
7
Példa Írjunk algoritmust két szám hányadosának kiszámítására!
8
Mondatszerű leírás Be: x,y (osztandó, osztó) Ha y≠0 akkor z = x /y Ki: z Különben Ki: Nincs megoldás! Vége 9
Struktogram Be: x,y Igen z = x /y Ki: z
y ≠0
Nem Ki: Nincs megoldás
10
Jackson-ábra Osztás Be: x,y
y≠0
Igen
Nem
Jó eset o
Rossz eset o
z = x/y
Ki: z
Ki: Hiba 11
Folyamatábra Start Be: x,y y≠0 i z=x/y Ki: z End
n
Be: Hiba
12
A folyamatábra elemei Adatbevitel, kiírás (input, output) Tevékenység (szekvencia) Alprogram (eljárás, függvény) Választás (szelekció) Algoritmus eleje és vége Kapcsolódási pont
13
A feladat megoldásának lépései A feladat leírása, megértése Az algoritmus felállítása Az algoritmus megvalósítása (programírás) A program ellenőrzése (tesztelés)
14
A feladat elemzése Részletes, pontos leírás Bemenő adatok (input) Kimenő eredmények (output) A feladat modellezése (képletek)
15
Az algoritmus tervezése Megoldáskeresés Folyamatábra vagy más módszer Helyességvizsgálat – az algoritmus elemzése
16
Az algoritmus megvalósítása A programozási nyelv kiválasztása (C++) A program megírása az adott nyelven.
17
A program tesztelése A logikai és programozói hibák keresése Egyes hibákat a fordító program jelez. Logikai hibák – a program tervezése közben jöttek létre – a fordító nem jelzi őket. Hibakereső program – debuger A program tesztelése fiktív és valós bemenő adatokkal. 18
Vezérlő szerkezetek Az utasítások sorrendjét adják meg. Bármely feladat megoldásához elegendő a következő három vezérlő szerkezet: Lineáris szerkezet (szekvencia) Elágazás (szelekció) Ismétlés (iteráció, ciklus)
19
Lineáris algoritmusok Műveletsor A vezérlés az előző utasításról a következőre helyeződik. Szaggatott vonal – a lineáris struktúra elemei egységet képeznek.
U1 U2
Un
20
Elágazásos algoritmus (szelekció) Egyes utasítások elvégzése feltételhez kötött. Két fajta elágazás: Ha feltétel akkor utasítás Ha feltétel akkor utasítás_1 különben utasítás_2 A feltétel logikai eredményt ad: igaz, hamis 21
Ha ... akkor ...
Feltétel Igaz Utasítás
Hamis
Napsütés
Hamis
Igaz Strand
22
Ha ... akkor ... különben ....
Feltétel
Hamis
Igaz Utasítás_1
Napsütés
Hamis
Igaz Utasítás_2
Strand
TV
23
Ciklus (iteráció) Egy adott feladatot többször végzünk el. Az ismétlést egy feltétel vezérli. A ciklus teste (magja): az ismétlődő utasítások. Két ciklusfajta: elöltesztelős hátultesztelős ciklus. 24
Elöltesztelős ciklus Ha a feltétel igaz, ismételd, különben hagyd abba. Feltétel
Hamis
Igaz Utasítás
25
Hátultesztelős ciklus Ismételd, és vizsgáld meg a feltételt: ha hamis, hagyd abba. Utasítás
Igaz
Feltétel
Hamis 26
