ALGORITMUSOK ÉS PROBLÉMAOSZTÁLYOK (1. előadás) Programozási feladatok megoldásának lépései 1, a feladatok meghatározása -egyértelmű, rövid, tömör, pontos 2, a feladat algoritmusának elkészítése Algoritmus: jól definiált (automatizálható, programozható) számítási eljárás egy meghatározott számítási feladat megoldására, amely bementként bizonyos értékeket kap és kimenetként bizonyos értékeket állít elő. Egy algoritmust helyesnek mondunk, ha minden bemenetre megáll és helyes eredményt ad. A helyes algoritmus megoldja az adott számítási feladatot. Általános feladatok fő részei: - a bemenő adatok bevitele - azokon a szükséges műveletek elvégzése - az eredmények megjelenítése, rögzítése, kiíratása Érdekes az algoritmusok hatékonysága két szempontból is: - felhasznált időben (ezt használjuk rendszerint az algoritmus bonyolultsága mértékeként) - felhasznált memóriában Ugyanannak a feladatnak a megoldására fejlesztett algoritmusok nagy mértékben eltérő hatékonyságot mutathatnak. 3, kódolás - a kész algoritmus valamilyen konkrét programnyelvre való ’lefordítása’ Program: a gép számára érthető formájú meghatározott sorrendű, véges, gépi utasítássorozat. 4, tesztelés 5, dokumentálás: felhasználói dokumentáció és fejlesztői dokumentáció Algoritmusleíró eszközök Céljuk: a megoldás menetének géptől független, szemléletes, a logikai gondolatmenetet, a szerkezeti egységeket világosan tükröző leírása. Legismertebb algoritmusleíró eszközök:
a, folyamatábra b, mondatszerű leírások
1
Folyamatábrák A folyamatábra a feladat megoldási lépéseinek sorrendjét - művelettípusonként különböző geometriai alakzatok felhasználásával - szemléltető ábra. A felhasznált szimbólumok és jelentésük a következő:
START
STOP
-
ún. határszimbólumok, az algoritmus elejét és végét jelzik
-
beolvasó és kiíró művelet
-
értékadás, művelet végrehajtás, aritmetikai kifejezés kiértékelése
-
elágazás. A feladat végrehajtása, egy a rombuszba írt feltétel alapján, egyik vagy másik irányba folytatódik. A rombusznak két kimenete van, amelynek (i, n) jelzéssel vannak ellátva. Az i kimenetet kell folytatni, ha a feltétel teljesül (igaz), különben (hamis esetén) az n kimenetet kell követni.
i
n
-
gyakran találkozhatunk a számlálós ciklus jelölésére a következő szimbólummal is
2
A folyamatábrán az algoritmus haladási irányát nyilakkal jelöljük. Abban az esetben, ha a nyilakat elhagyjuk a folyamatábrát fentről lefelé, illetve balról jobbra kell követni. A folyamatábrák hátránya, hogy elemei nem felelnek meg az algoritmuskészítés során felhasználható, a strukturált programozásra jellemző struktúráknak (szekvencia, elágazás, ciklus). Használatukkal igen könnyen előállíthatók olyan bonyolult szerkezetek is, melyek megértése azután nagyon nagy problémát jelent. Nézzük egy nagyon egyszerű feladat algoritmusát folyamatábrán szemléltetve: FELADAT: Kérjünk be a billentyűzetről N (>0, egész) számot és számoljuk ki az összegüket!
3
ALGORITMUSOK ÉS PROBLÉMAOSZTÁLYOK (2. előadás) Mondatszerű leírások A mondatszerű leírások szemléletesebb módja az, amikor az algoritmus leírására mondatok helyett csak ún. mondatszerű szerkezeteket használjuk. Mondatszerű szerkezetek egymásutánjával írjuk le a feladat megoldását. Ennél a leírási módnál az algoritmus szerkezeti egységeit bekezdéses struktúra segítségével szemléltetjük. Az egyértelműség kedvéért meg kell határozni, milyen műveleteket (utasításokat) tartalmaz az így készített algoritmus leíró nyelv és utasítás fajtánként, hogyan definiáljuk ezeket a mondatszerű szerkezeteket! Beolvasó és kiíró utasítás Formája : Be:
Ki:
// az adatokkal szemben támasztott // követelmények // a kiírás formájára vonatkozó // követelmények
Értékadó utasítás Formája: :=
// Az utasítás hatására a baloldalon álló változó felveszi a jobboldalon álló kifejezés értékét.
Elágazások ( feltételes utasítások) Formája : A, Ha () akkor Ha vége
// Ha az adott feltétel teljesül akkor az // utasítás(ok) kerül(nek) végrehajtásra és a // feladat megoldása a Ha vége után folytatódik. // Ha a feltétel nem teljesül, akkor a feladat a Ha // vége után folytatódik.
B,
Ha () akkor különben Ha vége
// Ha az adott feltétel teljesül akkor az // utasítás(ok)1 kerül(nek) végrehajtásra . Ha a // feltétel nem teljesül, akkor az utasítás(ok)2 // kerül(nek) végrehajtásra. Mindkét esetben a // feladat megoldása a Ha vége után folytatódik.
C,
Elágazás esetén esetén … esetén egyéb esetben Elágazás vége
4
// Sorban vizsgálja a feltételeket. Amikor // megtalálja az első teljesülő feltételt, // a hozzátartozó utasítás(ok) kerül(nek) // végrehajtásra.Ha nem talált egyetlen egy // feltételt sem, amely teljesül, akkor az // egyéb esetben - hez tartozó utasítás(ok) // kerül(nek) végrehajtásra. Minden // esetben a feladat megoldása az // Elágazás vége után folytatódik.
Ciklusszervező utasítások Formája: A,
Ciklus := -től -ig -esével Ciklus vége
// Végrehajtja a ciklusmag utasításait a ciklus-változó kezdőértékével. Ezután növeli a ciklus// változó kezdőértékét a lépésközzel, és az új értékkel hajtja végre a ciklusmag utasításait. Ez // a folyamat addig ismétlődik, amíg a ciklus-változó kisebb vagy egyenlő, mint a végérték. // Ha a ciklus-változó értéke nagyobb, mint a végérték, akkor a feladat megoldása a Ciklus // vége után folytatódik. Ha a kezdőérték nagyobb, mint a végérték, akkor a ciklusmag // utasításai egyszer sem kerülnek végrehajtásra. A lépésköz, 1 esetén, elhagyható. Szokásos // ezt a szerkezetet számlálós ciklusnak nevezni. B,
Ciklus amíg Ciklus vége
// A ciklusmag utasításai addig hajtódnak végre amíg a feltétel igaz, s ha a feltétel hamis // akkor a program végrehajtása a Ciklus vége után folytatódik. Szokásos elnevezés: // elöl tesztelős ciklus. C,
Ciklus amíg Ciklus vége
// A ciklusmag utasításai addig hajtódnak végre amíg a feltétel igaz, s ha a feltétel hamis // akkor a program végrehajtása a Ciklus vége után folytatódik. A ciklusmag utasításai // egyszer mindenképpen végre hajtódnak. Elnevezés: hátul tesztelős ciklus Egyéb jelölések: // kiegészítések , megjegyzések (már használtuk!) : ha egy soron belül több utasítást használunk [ ] - tömbök jelölése ha teljes algoritmust írunk: Algoritmus: Algoritmus vége
ha eljárást( függvényt írunk): <eljárásnév>(<paraméterek>) <eljárás utasításai> <eljárásnév> vége
Eljárás esetén a paraméterek az eljárás bemeneteinek a felsorolása. Az eljárás kimeneteit a Return
5
segítségével adjuk meg, amely a visszatérési értékeket adja vissza és az eljárás végrehajtását fejezi be. A megadott szabály kivétele a tömbök. Ha egy tömb szerepel paraméterként, akkor bemenő és kimenő paraméter is, azaz, ha az eljárásban módosítjuk a tömb paramétert, akkor a módosítások érvényesülnek az eljárás végrehajtása után az eljárást hívó algoritmusban is. Nézzük a szokásos feladat ( N>0 billentyűzetről olvasott egész szám összegének a kiszámítása) mondatszerű leírásának algoritmusát: Bemenet: N (az összeadandó számok száma) Kimenet: Szum (a képzett összeg) Algoritmus: Be: N // N>0 egész Szum:=0 Ciklus i:=1-től N -ig Be: A Szum:= Szum+A Ciklus vége Ki: Szum Algoritmus vége
6
ALGORITMUSOK ÉS PROBLÉMAOSZTÁLYOK (3. előadás) Egyszerű algoritmusok Aki már több programot készített különböző témákban, bizonyára tapasztalta, hogy az egyes problémák, feladatok, részfeladatok tipizálhatóak, megoldásukhoz gyakorlatilag ugyanaz az algoritmus szükséges legfeljebb a ’körítés’ azaz a feladat szövege, a változók, konstansok mások és mások. Ebben a részben most néhány egyszerű, ilyen típus algoritmus következik. Összegzés Adva van egy N elemű számsorozat, és ki kell számolni az elemeinek az összegét! A sorozat elemeit ennél a tételnél és a következőkben is az N elemű A[1..N] vektorban tároljuk. Bemenet: A[1..N] Kimenet: Szum Algoritmus: Szum:=0 Ciklus i := 1-től N-ig Szum:=Szum+A[i] Ciklus vége Algoritmus vége Példa az összegzés alkalmazására: A hét minden egyes napján megmértük egyszer a hőmérsékletet s az értékeket a HOM[7] vektorban tároljuk. Számítsuk ki a heti átlaghőmérsékletet! Algoritmus: Atl:=0 Ciklus i := 1-től 7-ig Atl:=Atl+Hom[i] Ciklus vége Atl:=Atl/7 Algoritmus vége Eldöntés Adva van egy N elemű sorozat, és egy a sorozat tagjain értelmezett T tulajdonság. Olyan algoritmust kell írni, amely eldönti: van-e a sorozat tagjai közt legalább egy T tulajdonságú. Bemenet: A[1..N], T tulajdonság Kimenet: Eredmény (’VAN T tulajdonságú’ vagy ’NINCS T tulajdonságú’) Algoritmus: i:=1 Ciklus amíg i<=N és A[i] nem T tulajdonságú 7
i:=i+1 Ciklus vége Ha( i<=N) akkor Eredmény := ’ VAN T tulajdonságú’ különben Eredmény := ’NINCS T tulajdonságú’ Ha vége Algoritmus vége Példa az eldöntésre: Egy N=20 fős osztály tanulóinak magasságát a Mag[20] elemű vektorban tároljuk. A feladat annak eldöntése, hogy van-e 180 cm-nél magasabb tanuló. Algoritmus: i:=1 Ciklus amíg i<=20 és Mag[i]< =180 i:=i+1 Ciklus vége Ha (i<=20) akkor Eredmény := ’VAN 180-nál magasabb’ különben Eredmény := ’NINCS 180-nál magasabb’ Ha vége Algoritmus vége Kiválasztás Adva van egy N elemű sorozat, és egy a sorozat tagjain értelmezett T tulajdonság. Tudjuk, hogy a sorozat tagjai között van T tulajdonságú. Olyan algoritmust kell írni, amely megadja a sorozat első T tulajdonságú tagjának a sorszámát. Bemenet: A[1..N], T tulajdonság Kimenet: Sorszam Algoritmus: i:=1 Ciklus amíg A[i] nem T tulajdonságú i:=i+1 Ciklus vége Sorszam:=i Algoritmus vége Példa kiválasztásra : Tudjuk, hogy az N=20 tagú osztály tagja Tóth Mihály. Hányadik a rendezett névsorban? Algoritmus
8
i:=1 Ciklus amíg NEV[i] <> 'Tóth Mihály' i:=i+1 Ciklus vége Sorszám:=i Algoritmus vége Lineáris keresés Adva van egy N elemű sorozat, és egy a sorozat tagjain értelmezett T tulajdonság. Olyan algoritmust kell írni amely eldönti, hogy van- e T tulajdonságú elem a sorozatban és ha van hányadik az első T tulajdonságú elem.( előbbi két algoritmus összegzése) Bemenet: A[1..N], T tulajdonság Kimenet: Index (a sorozat első T tulajdonságú elemének sorszáma, ha nincs, akkor 0) Algoritmus: i:=1 Ciklus amíg i<=N és A[i] nem T tulajdonságú i:=i+1 Ciklus vége Ha (i<=N) akkor Index:=i különben Index:=0 Ha vége Algoritmus vége Megszámlálás Adva van egy N elemű sorozat, és egy a sorozat tagjain értelmezett T tulajdonság. Olyan algoritmust kell írni amely megszámlálja a T tulajdonságú elemeket. Bemenet: A[1..N], T tulajdonság Kimenet: DB Algoritmus: DB:=0 Ciklus i:=1-től N-ig Ha (A[i] T tulajdonságú) Ha vége Ciklus vége Algoritmus vége
akkor DB:=DB+1
Példa megszámlálásra: Adott egy N=20 fős osztály matematika eredménye a JEGY[20] vektorban tárolva. Számoljuk össze a bukottakat! Algoritmus:
9
DB:=0 Ciklus i:=1-től 20-ig Ha (JEGY[i] =1 ) Ha vége Ciklus vége Algoritmus vége
akkor DB:=DB+1
Kiválogatás Adva van egy N elemű sorozat, és egy a sorozat tagjain értelmezett T tulajdonság. Olyan algoritmust kell írni, amely a T tulajdonságú elemek sorszámát egy külön B[] vektorba gyűjti. Bemenet: A[1..N], T tulajdonság Kimenet: B[1..M], ahol M az A sorozat T tulajdonságú elemeinek a száma Algoritmus: M:=0 Ciklus i:= 1-től N-ig Ha (A[i] T tulajdonságú) akkor M:=M+1 : B[M]:=i Ha vége Algoritmus vége Példa kiválogatásra: Két hétig naponta megmértük a hőmérsékletet. Válogassuk ki a fagypont alatti napok sorszámát. Algoritmus: j:=0 Ciklus i:=1- től 14-ig Ha (Hom[i] < 0) akkor j:=j+1 : Fagy[j]:=i Ha vége Ciklus vége Algoritmus vége Maximum kiválasztása Adva van egy N elemű sorozat. Meg kell keresni a sorozat legnagyobb elemének a sorszámát. Bemenet: A[1..N], T tulajdonság Kimenet: Maxindex Algoritmus: INDEX:=1 Ciklus i:=2-től N–ig Ha ( A[INDEX] < A[i] ) akkor INDEX:=i
10
Ha vége Ciklus vége Maxindex:= INDEX Algoritmus vége Minimum kiválasztásnál csak a feltételes utasítás feltétele fordul meg. Abban az esetben, ha a kérdést úgy tesszük fel, hogy menyi a legnagyobb érték , akkor egy másik megoldást is kaphatunk : Bemenet: A[1..N], T tulajdonság Kimenet: Maxertek Algoritmus: Ertek:= A[1] Ciklus i:=2-től N-ig Ha ( Ertek < A[i]) akkor Ertek:= A[i] Ha vége Ciklus vége Maxertek:=Ertek Algoritmus vége Megtehetjük azt is , hogy a két eljárást egybeépítjük. Példa maximum kiválasztásra: Készítsünk olyan eljárást, amely N ember magasságának ismeretében megadja a legmagasabb személy magasságát, valamint megjelöl egy ilyen embert ! Legmagasabb(N, A[]) Index:= 1 : Ertek:=A[1] Ciklus i:= 2-től N-ig Ha (Ertek < A[i]) akkor Ertek:=A[i] : Index:=i Ha vége Ciklus vége Maxindex:=Index Maxertek:= Ertek Return Maxindex, Maxertek Legmagasabb vége
11
ALGORITMUSOK ÉS PROBLÉMAOSZTÁLYOK (4. előadás) Rendezés Rendezés közvetlen kiválasztással A rendezendő számok legyenek az A tömb elemei. Az első menetben kiválasztjuk a tömb legkisebb elemét úgy, hogy az A[1]-et összehasonlítjuk az A[2] ….A[N] mindegyikével és akárhányszor A[1]-nél kisebbet találunk megcseréljük a két elemet, így az első kör után biztosan A[1] lesz a vektor legkisebb eleme. Ezt az eljárást A[2]…A[N-1]-gyel folytatjuk. Az A vektor N-1 lépésben rendezett lesz. Bemenet: A[1..N] Kimenet: A[1..N] rendezett Algoritmus: Ciklus i:=1-től N-1-ig Ciklus j:= i+1-től N-ig Ha (A[j] < A[i ])
akkor A:= A[j] A[j]:=A[i] A[i]:=A
Ha vége Ciklus vége Ciklus vége Algoritmus vége A módszer működését véletlenszerűen választott 16 szám esetén a következő táblázat mutatja: Eredeti 1.kör u. 2.kör u. 3. kör u. ……. 15.kör u.
64 3 3 3
56 64 5 5
8 56 64 7
42 42 56 64
5 8 42 56
12 12 12 42
16 16 16 16
40 40 40 40
3 5 8 12
31 31 31 31
47 47 47 47
22 22 22 22
24 24 24 24
33 33 33 33
7 7 7 8
46 46 46 46
3
5
7
8
12
16
22
24
31
33
40
42
46
47
56
64
Az eljárásban megfigyelhető, hogy minden menetben igen sok felesleges csere történik, mely a felesleges cserék kiküszöbölésével javítható. Rendezés minimum kiválasztással A felesleges cserék érdekében bevezetünk két segéd változót. Az 'Ertek' változóban tároljuk a az eddig megtalált legkisebb elemet, az 'Index'-ben pedig a sorozatbeli helyét. A menet végére az 'Ertek'- ben lesz a legkisebb elem, az 'Index'-ben pedig a helye. Csak a menet utolsó lépésében van szükség cserére, amikor is az értékben lévő legkisebb elemet a helyére tesszük. Bemenet: A[1..N] Kimenet: A[1..N] rendezett
12
Algoritmus: Ciklus i:=1-től N-1-ig Index:=i : Ertek:= A[i] Ciklus j:= i+1-től N-ig Ha (Ertek > A[j]) akkor Ertek:= A[j] : Index:= j Ha vége Ciklus vége A[Index] := A[i] A[i]:= Ertek Ciklus vége Algoritmus vége A módszer működését véletlenszerűen választott 16 szám esetén a következő táblázat mutatja: Eredeti 1.kör u. 2.kör u. 3. kör u. ……. 15.kör u.
64 3 3 3
56 56 5 5
8 8 8 7
42 42 42 42
5 5 56 56
12 12 12 12
16 16 16 16
40 40 40 40
3 64 64 64
31 31 31 31
47 47 47 47
22 22 22 22
24 24 24 24
33 33 33 33
7 7 7 8
46 46 46 46
3
5
7
8
12
16
22
24
31
33
40
42
46
47
56
64
Buborékos rendezés A rendezés alapgondolata a szomszédos elemek cseréje. Az első körben a rendezendő tömb végéről indulva az elemeket összehasonlítjuk az előttük levővel s amennyiben rossz sorrendben vannak felcseréljük őket. Az első kör végére a legkisebb elem biztosan a helyére kerül. Minden további körben újra a tömb végéről indulunk ,de egyre rövidülnek a körök mert a tömb eleje fokozatosan rendezetté válik. Bemenet: A[1..N] Kimenet: A[1..N] rendezett Algoritmus: Ciklus i:= 2-től N-ig Ciklus j:= N-től i- ig -1-esével Ha ( A[j-1] > A[j]) akkor
A:= A[j-1] A[j-1]:= A[j] A[j]:= A
Ha vége Ciklus vége Ciklus vége Algoritmus vége A módszer működését véletlenszerűen választott 16 szám esetén a következő táblázat mutatja: Eredeti 1.kör u. 2.kör u.
64 3 3
56 64 5
8 56 64
42 8 56
5 42 8
12 5 42
16 12 7
13
40 16 12
3 40 16
31 7 40
47 31 22
22 47 31
24 22 47
33 24 24
7 33 33
46 46 46
……... ……. 15.kör u.
3
5
7
8
12
16
22
24
31
33
40
42
46
47
56
64
Egyszerű beillesztéses rendezés (beszúrásos rendezés) Úgy végezzük a rendezést, mintha kártyáznánk és kezünkbe egyesével vennénk fel az asztalról a kiosztott lapokat. Az éppen felvett lapnak megkeressük a kezünkben lévő , már rendezett sorozatban a helyét úgy , hogy a nála nagyobbakat egy hellyel elcsúsztatjuk, végül a felvett lapot a neki megfelelő helyre illesztjük. Bemenet: A[1..N] Kimenet: A[1..N] rendezett Algoritmus: Ciklus j:= 2-től N-ig i:= j-1 : A:=A[j] Ciklus amíg i >0 és A
64 56 8 8
56 64 56 42
8 8 64 56
42 42 42 64
5 5 5 5
12 12 12 12
16 16 16 16
40 40 40 40
3 3 3 3
31 31 31 31
47 47 47 47
22 22 22 22
24 24 24 24
33 33 33 33
7 7 7 7
46 46 46 46
3
5
7
8
12
16
22
24
31
33
40
42
46
47
56
64
A most bemutatott rendezés hátránya , hogy elég sok mozgatásra van benne szükség.
14
ALGORITMUSOK ÉS PROBLÉMAOSZTÁLYOK (5. előadás) Rendezés (folytatás) Shell-módszer beszúrással A módszer nem foglalkozik egyszerre minden rendezendő elemmel, csak az egymástól adott távolságra lévőkkel. Minden menet elején meghatározunk egy lépésközt (D), amely azt jelenti, hogy az adott menetben a tömb egymástól (D) távolságra lévő elemeit rendezzük. Adott meneten belül a rendezés több módszer szerint történhet, most beszúrással. Az induló lépésköz meghatározása úgy történik, hogy a rendezéshez szükséges menetek száma kb. log2 N legyen. A további lépésközöket felezéssel kapjuk. Megjegyzés: A továbbiakban a log kifejezés alatt mindig 2-es alapú logaritmust értjük, azaz, számunkra, log N = log2 N, ha külön nem említünk mást. A módszer működését véletlenszerűen választott 16 szám esetén a következő táblázat mutatja: Eredeti D=15 u. D=7 u. D=3 u. D=1 u.
64 46 7 7 3
56 56 3 3 5
8 8 8 8 7
42 42 42 16 8
5 5 5 5 12
12 12 12 12 16
16 16 16 24 22
40 40 40 33 24
3 3 56 22 31
31 31 31 31 33
47 47 47 40 40
22 22 22 46 42
Bemenet: A[1..N] Kimenet: A[1..N] rendezett Algoritmus: D:=2[log(N)] –1 Ciklus i:=1 Ciklus amíg i<=D és i+D<=N Ciklus j:=i+D-től N-ig D-esével A:=A[j] : B:=j-D Ciklus amíg B>0 és A0 Ciklus vége Algoritmus vége
15
24 24 24 42 46
33 33 33 47 47
7 7 46 56 56
46 64 64 64 64
Keresés (folytatás) Logaritmikus keresés Adva van egy N elemű RENDEZETT sorozat és egy keresett elem X. Olyan algoritmust kell írni amely eldönti, hogy van-e X elem a sorozatban és ha van hányadik. Szokás az eljárást intervallum felezéses módszernek is nevezni. Bemenet: A[1..N], X elem Kimenet: Sorszam (az X elem sorszáma az A sorozatban, ill. 0, ha X nincs A-ban) Algoritmus: p:=1 : q:=N Ciklus k:= [(p+q)/2] Ha (A[k] < X) akkor p:=k+1 Ha vége Ha (A[k] > X) akkor q :=k-1 Ha vége amíg p<=q és A[k] <>X Ciklus vége Ha (p <= q) akkor Sorszam:=k különben Sorszam:=0 Ha vége Algoritmus vége A logaritmikus elnevezés onnan származik, hogy evvel a módszerrel az elem megkereséséhez szükséges lépések száma max. log N (log2 N).
16
ALGORITMUSOK ÉS PROBLÉMAOSZTÁLYOK (6. előadás) Rekurzió Rendezés (folytatás) Tervezési módszerek: - Rekurzió: A problémát megoldó algoritmus eljárásaiban alkalmazzuk a leírt eljárásokat, azaz a leírt eljárások közvetlenül vagy közvetve hívják (alkalmazzák) saját magukat. - Oszd meg és uralkodj: A probléma hasonló problémákra való bontása, a részproblémák megoldása, majd a kapott részmegoldásokból a probléma megoldásának az összeállítása. Összefésülő rendezés: Az összefésülő rendezés alkalmazza a fent említett két tervezési módszert. Egy tömb rendezéséhez felbontja azt két résztömbre (első és második fele), majd rendezi a két felet és a kapott részmegoldásokból összeállítja összefésüléssel az eredeti tömb rendezését („Oszd meg és uralkodj” alkalmazása). A felek rendezését az összefésülő rendezés alkalmazásával oldja meg („rekurzió” alkalmazása). Bemenet: A[p..r] Kimenet: A[p..r] rendezettek Összefésülő-rendezés(A, p, r):
//Az A bemenő, p-től r-ig rendezendő tömb és // kimenő, p pozíciótól r pozícióig rendezett tömb
Ha (p < r ) akkor q := [(p + r) / 2] Összefésülő-rendezés(A, p, q) Összefésülő-rendezés(A, q+1, r) Összefésül(A, p, q, r) Ha vége Összefésülő-rendezés vége
// Első fele rendezése // Második fele rendezése // A rendezett felek összefésülése
Az alkalmazott Összefésülés eljárás leírása: Bemenet: A[p..q] és A[q+1..r] rendezettek Kimenet: A[p..r] rendezett Összefésülés(A, p, q, r):
// Az eljárás hívó algoritmus // visszakapja az összefésült A tömböt n1 := q – p + 1 // Az első fél (p-től q-ig) elemeinek száma n2 := r – q // A második fél (q+1-től r-ig) elemeinek száma Ciklus i := 1-től n1-ig // A B tömb feltöltése az első fél elemeivel B[i] := A[p + i – 1] Ciklus vége Ciklus j := 1-től n2-ig // A J tömb feltöltése a második fél elemeivel J[j] := A[q + j] 17
Ciklus vége B[n1 + 1] := ∞ : J[n2 + 1] := ∞
// A két fél végére egy minden lehetséges // elemnél nagyobb elemet teszünk, amely // már nem kerül a rendezett tömbre i := 1 : j := 1 // Mindkét félnél az első elemtől indulunk a visszahelyezésnél Ciklus k := p-től r-ig // Egyenként visszatesszük az elemeket A-ba Ha ( B[i] <= J[j] ) akkor // A soron következő kisebb elem A[k] := B[i] : i := i + 1 // visszahelyezése. A megfelelő különben // pozíció növelése abban a A[k] := J[i] : j := j + 1 // tömbben, ahonnan az elemet Ha vége //visszahelyeztünk Ciklus vége Összefésül vége Példa az Összefésül eljárás működésére: Bemenet: A: 2 4 5 1 3 6 , p = 1, q = 3, r = 6 Összefésül: n1 = 3 n2 = 3 Kezdőértékek beállítása: B: 2 4 5 ∞ J: 1 3 6 ∞ A: 2 4 5 1 3 6 i = 1, j = 1, k = 1 Első lépés: B: 2 4 5 ∞ J: 1 3 6 ∞ B[1] = 2 > J[1] = 1 A: 1 4 5 1 3 6 i = 1, j = 2, k = 2 Második lépés: B: 2 4 5 ∞ J: 1 3 6 ∞ B[1] = 2 < J[2] = 3 A: 1 2 5 1 3 6 i = 2, j = 2, k = 3 Harmadik lépés:
18
B: 2 4 5 ∞ J: 1 3 6 ∞ B[2] = 4 > J[2] = 3 A: 1 2 3 1 3 6 i = 2, j = 3, k = 4 Negyedik lépés: B: 2 4 5 ∞ J: 1 3 6 ∞ B[2] = 4 < J[3] = 6 A: 1 2 3 4 3 6 i = 3, j = 3, k = 5 Ötödik lépés: B: 2 4 5 ∞ J: 1 3 6 ∞ B[3] = 5 < J[3] = 6 A: 1 2 3 4 5 6 i = 4, j = 3, k = 6 Hatodik lépés: B: 2 4 5 ∞ J: 1 3 6 ∞ B[4] = ∞ < J[3] = 6 A: 1 2 3 4 5 6 i = 4, j = 4, k = 7 Vége Példa az Összefésülő-rendezés eljárás működésére: Bemenet: A: 5 2 4 6 1 3 , p = 1, r = 6 Összefésülő-rendezés: q=3 Összefésülő-rendezés(A[5 2 4 6 1 3], 1, 3) Végrehajtás után: A: 2 4 5 6 1 3 Összefésülő rendezés(A[2 4 5 6 1 3], 4, 6) Végrehajtás után: A: 2 4 5 1 3 6 Összefésül(A[2 4 5 1 3 6], 1, 3, 6) // Előző példán láttuk! Végrehajtás után: A: 1 2 3 4 5 6 Vége
19
Gyors rendezés: A gyors rendezés egy tömb rendezéséhez először egy választott elemet a helyére teszi úgy, hogy a tömbben minden a választott elemet megelőző elem nála kisebb vagy egyenlő, minden a választott elemet követő elem nála nagyobb vagy egyenlő. Ezután az így keletkezett két résztömböt, a választott elemet megelőző elemek ill. követő elemek tömbjeit kell rendezi, és megvan az eredeti tömb rendezése. Az eredeti tömb felbontásával az „oszd meg és uralkodj” tervezési módszert alkalmazzuk, azzal pedig, hogy a résztömböket gyors rendezéssel rendezzük, a „rekurzió” tervezési módszert is alkalmazzuk. Bemenet: A[p..r] Kimenet: A[p..r] rendezett Gyors-rendezés(A, p, r):
//Az A bemenő, p-től r-ig rendezendő tömb és // kimenő, p pozíciótól r pozícióig rendezett tömb
Ha (p < r ) akkor q := Feloszt(A, p, r) Gyors-rendezés(A, p, q-1) Gyors-rendezés(A, q+1, r)
// q a választott, helyre került elem helye // A választott elemnél kisebb vagy // egyenlő elemek rendezése // A választott elemnél nagyobb vagy // egyenlő elemek rendezése
Ha vége Gyors-rendezés vége Az alkalmazott Feloszt eljárás leírása (a választott elem a bemenő tömb utolsó eleme) : Bemenet: A[p..r] Kimenet: q, A[p..q-1], A[q+1..r]
// q a választott (utolsó) elem végleges helye // A[p..q-1] a választott elemnél kisebb elemek // A[q+1..r] a választott elemnél nagyobb elemek
Feloszt(A, p, r): // Az A bemenő, p és r pozíciók közötti felosztandó i := p -1 // i – az utolsó megtalált A[r]-nél kisebb elem pozíciója Ciklus j := p-től r-1-ig Ha ( A[j] < A[r] ) akkor // Ha megtalálunk egy A[r]-nél kisebbet, i := i + 1 // akkor helycserével áthelyezzük a tömb S := A[i] : A[i] := A[j] : A[j] := S // elejére, a már megtalált Ha vége // A[r]-nél kisebbek mögé Ciklus vége S := A[i+1] : A[i+1] := A[r] : A[r] := S // A választott (utolsó) elem // áthelyezése a helyére (a nála // kisebbek mögé) Return i+1 // visszaadja a választott elem végleges pozícióját Feloszt vége
20
ALGORITMUSOK ÉS PROBLÉMAOSZTÁLYOK (7. előadás) Algoritmusok hatékonysága Az algoritmusok hatékonyságát főleg két szempont alapján szokták vizsgálni: - felhasznált idő - felhasznált memória A legfontosabb szempont az időigény és ezt használjuk mi rendszerint. Egy algoritmus időigényének a megadásához szükség van a bemenet mértékének a meghatározásához. Ez az általunk eddig látott algoritmusok esetén a tömb elemeinek a száma. Így, ha az A tömb elemeinek a száma n, akkor az időigénye n függvényeként adható meg. Az algoritmusok időhatékonyságának az összehasonlításához szükségünk van a függvények összehasonlítására. Függvények összehasonlítása: 1)
f(n) = Θ(g(n)) : g(n) aszimptotikusan éles korlátja f(n)-nek, ha létezik c1 > 0, c2 > 0, n0 > 0, hogy 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) minden n ≥ n0-ra
2)
f(n) = O(g(n)) : g(n) aszimptotikusan éles felső korlátja f(n)-nek, ha létezik c2 > 0, n0 > 0, hogy 0 ≤ f(n) ≤ c2 g(n) minden n ≥ n0-ra
3)
f(n) = Ω(g(n)) : g(n) aszimptotikusan éles alsó korlátja f(n)-nek, ha létezik c1 > 0, n0 > 0, hogy 0 ≤ c1 g(n) ≤ f(n) minden n ≥ n0-ra
Tétel: f(n) = Θ(g(n)) akkor és csak akkor, ha f(n) = O(g(n)) és f(n) = Ω(g(n)) 4)
f(n) = o(g(n)) : g(n) aszimptotikusan nem éles felső korlátja f(n)-nek, ha
5)
f(n) lim = 0 n → ∞ g(n)
( f(n) ≥ 0, g(n) ≥ 0 )
f(n) = ω(g(n)) : g(n) aszimptotikusan nem éles alsó korlátja f(n)-nek, ha
f(n) lim = ∞ n → ∞ g(n)
( f(n) ≥ 0, g(n) ≥ 0 )
Párhuzam a függvények és a valós számok összehasonlítása kzött: f(n) = O(g(n)) f(n) = Ω(g(n)) f(n) = Θ(g(n)) f(n) = o(g(n)) f(n) = ω(g(n))
a≤b a≥b a=b ab 21
Néhány korábban látott algoritmus időigénye: Összegzés:
Általános: Θ(n)
Eldöntés:
Általános: O(n)
Kiválasztás: Általános: O(n) Lineáris keresés (első megkeresése): Megszámlálás:
Általános: O(n)
Általános: Θ(n)
Kiválogatás (minden előfordulás megkeresése): Általános: Θ(n) Szélsőértékek:
Általános: Θ(n)
Logaritmikus keresés:
Általános: O(log n)
Egyszerű beillesztéses rendezés (beszúrásos rendezés): - legjobb eset: Θ(n) - legrosszabb eset: Θ(n2) Általános: O(n2) Összefésülő rendezés: Általános: Θ(n log n) Gyors rendezés: - legjobb eset: Θ(n log n) - legrosszabb eset: Θ(n2) - az átlagos eset közelít a legjobbhoz Általános: O(n2) A következő példán keresztül szeretnénk rámutatni az időigény vizsgalátának a fontosságára: A számítógép sebessége: 109 művelet/sec Beszúró rendezés: c1 n2 (2 n2 )
B számítógép sebessége: 107 művelet/sec Összefésülő rendezés: c2 n log n (50 n log n)
Rendezendő tömb mérete: 106 elem A tömb rendezésének időigénye: 2.(106)2 művelet = 2000 sec 109 művelet/sec
50 . 106 . log 106 művelet ≈ 100 sec 107 művelet/sec
Az A számítógép100-szor gyorsabb, mint a B, mégis B 20-szor gyorsabban végez, mint A. Nézzük meg most példaként az Összefésülő rendezés időigényének a kiszámítását:
22
Tegyük fel, hogy a rendezendő A tömb mérete n = 2k és a rendezéséhez szükséges idő T(n). Akkor az A tömb rendezéséhez szükséges idő: T(n/2) – az első fele rendezéséhez összefésüléssel T(n/2) – a második fele rendezéséhez összefésüléssel cn – a rendezett felek összefésüléséhez Akkor: T(n)
= 2 T(n/2) + c n = 2 (2 T(n/4) + c n/2) + c n = 4 T(n/4) + 2 c n = 4 (2 T(n/8) + c n/4) + 2 c n = 8 T(n/8) + 3 c n … = 2K T(1) + k c n = n + (log n) c n = n c log n + n = n (c log n + 1)
T(n) = Θ(n log n)
23
