Információs Technológia

Információs Technológia Rekurzió, Fa adatszerkezet

Fodor Attila Pannon Egyetem Műszaki Informatika Kar Villamosmérnöki és Információs Rendszerek Tanszék [email protected]

2010. november 18.

Rekurzió

Rekurzió

Rekurzió

"Ismételni emberi dolog. Rekurziót írni isteni..." (L. Peter Deutsch)

Fodor A. (Pannon Egyetem)

Információs technológia

2010. november 18.

2 / 41

Rekurzió

Rekurzió

Rekurzió

A feladat algoritmusa eleve rekurzív formában adott Például: n! 4! = 1 * 2 * 3 * 4 3! = 1 * 2 * 3 2! = 1 * 2 1! = 1 A valójában nem rekurzív de egyszerűbb a rekurzió használata Például: sorrend fordítás Megoldás menete: Megkeressük azt a legegyszerűbb esetet amiben a megoldás triviális Megkeressük, hogy hogyan vezethető vissza ismételt egyszerűsítésekkel a legegyszerűbb esetre a probléma



2010. november 18.

3 / 41

Rekurzió

Rekurzió

Rekurzió fajtái, osztályozása

Meghívás módja alapján közvetlen (a függvény hívja a függvényt) közvetett (a függvény hívja b függvényt és b függvény hívja a függvényt)

Meghívás módja és helye alapján (Hányszor, hány helyen hívja meg önmagát) Egyszerű Többszörös



2010. november 18.

4 / 41

Rekurzió

Faktoriális

Faktoriális (n!) Rekurzívan adott az algoritmus. Kiszámítás menete (példa): n! = 1 * 2 * 3 * 4 * ... * n .. . 4! 3! 2! 1!

= = = =

1*2*3*4 1*2*3 1*2 1

Kiszámítása: n! = n * (n-1)! ha n>1 1! = 1 long fakt(int n) { if (n > 1) return n*fakt(n-1); return 1; } Fodor A. (Pannon Egyetem)


2010. november 18.

5 / 41

Rekurzió

Faktoriális

Faktoriális (n!) long fakt(int n) { if (n > 1) return n*fakt(n-1); return 1; }

Kiszámítás lépései: fakt(4) return 4 * fakt(3) return 3 * fakt(2) return 2 * fakt(1) return 1 return 2 * fakt(1) ⇒ 2*1 → 2 return 3 * fakt(2) ⇒ 3*2 → 6 return 4 * fakt(3) ⇒ 4*6 → 24



2010. november 18.

6 / 41

Rekurzió

Szám bináris kiírása

Szám bináris kiírása Kiszámítás módja: Elosztjuk 2-vel a számot, akkor a maradék az utolsó számjegy Probléma: Ezt a bitet kellene utoljára kiírni!!! Probléma megoldása: A biteket egy tömbben kell eltárolni... Megoldás: A rekurzív hívás után írunk ki (a rekurzív hívások során tárolódnak a már kiszámított számjegyek) void binkiir(int n) { int e, m; m = n % 2; if (e = n / 2) binkiir(e); printf("%d", m); }



2010. november 18.

7 / 41

Rekurzió



void binkiir(int n) { int e, m; m = n % 2; if (e = n / 2) binkiir(e); printf("%d", m); }

Kiszámítás lépései: (5 = 22 + 20 Binárisan: 101) binkiir(5) ⇒ m:1 e:2 binkiir(2) ⇒ m:0 e:1 binkiir(1) ⇒ m:1 e:0 printf("%d", 1); → 1 printf("%d", 0); → 0 printf("%d", 1); → 1



2010. november 18.

8 / 41

Rekurzió

Hanoi tornyai

Hanoi tornyai legendája A legenda: Sok ezer évvel ezelőtt Indiában, Fo Hi uralkodása alatt, a benaresi Siva-templom közepén volt egy márványtábla, amelyből három gyémánttű állt ki. Az első tűn 64 vékony aranykorong helyezkedett el, alul a legnagyobb átmérőjű, majd rajta egyre kisebbek. Egyszer Siva isten megparancsolta a templom papjainak, hogy rakják át a korongokat az első tűről a másodikra. Két fontos szabályt azonban be kellett tartaniuk: A korongok igen sérülékenyek, ezért egyszerre csak egyet lehet mozgatni, nem kerülhet a szent korongokból magasabb értékű alacsonyabb értékű fölé

A szerzetesek természetesen használhatták a harmadik tűt is a rakodás közben. Amikor az utolsó korong a helyére kerül, a templom porrá omlik össze, és a világ véget ér. Fodor A. (Pannon Egyetem)


2010. november 18.

9 / 41

Rekurzió

Hanoi tornyai

Hanoi tornyai Megoldás lépései 3 korong esetén

Hét áthelyezést adja a leggyorsabb megoldást 3 korong esetén Demo: http://www.irt.org/games/js/hanoi/index.htm?d=5 Fodor A. (Pannon Egyetem)


2010. november 18.

10 / 41

Rekurzió

Hanoi tornyai

Hanoi tornyai

Felírható a következő képlet: L=L’+1+L’, ahol L’ a lépések száma K-1 korong esetén. Az összeadás három tagja a megoldás három lépését jelöli: (1) K-1 korong az első tűről a harmadikra (L’ lépés) (2) Legnagyobb korong a helyére rekása (1 lépés) (3) a K-1 korong vissza a másodikra (L’ lépés)

Lépések száma: L = 2K − 1 (K: korongok száma) A szerzeteseknek tehát 264 − 1 áthelyezést kell végrehajtaniuk. Ha feltesszük, hogy egy korongot átlagosan egy másodperc alatt tesznek át akkor több mint 590 000 000 000 évig tartana!



2010. november 18.

11 / 41

Rekurzió

Hanoi tornyai

Hanoi tornyai lépéseit kiszámoló függvény Függvény kódja: void Hanoi_tornyai(int korong, char honnan, char hova, char seged) { if (korong > 0) { Hanoi_tornyai(korong-1, honnan, seged, hova); printf("%d. korong %c --> %c\n", korong, honnan, hova); Hanoi_tornyai(korong-1, seged, hova, honnan); }

Meghívása: ... Hanoi_tornyai(3, ’A’, ’B’, ’T’); Hanoi_tornyai(4, ’A’, ’B’, ’T’); ...



2010. november 18.

12 / 41

Rekurzió

Hanoi tornyai

Hanoi tornyai lépései 3 korong esetén

1. 2. 1. 3. 1. 2. 1.

korong korong korong korong korong korong korong

A A B A T T A

--> --> --> --> --> --> -->

B T T B A B B



2010. november 18.

13 / 41

Rekurzió

Hanoi tornyai

Hanoi tornyai lépései 6 korong esetén 1. 2. 1. 3. 1. 2. 1. 4. 1. 2. 1. 3. 1. 2. 1. 5. 1. 2. 1. 3. 1. 2. 1. 4. 1. 2. 1. 3. 1. 2. 1. 6.

korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong Fodor A.

A --> T A --> B T --> B A --> T B --> A B --> T A --> T A --> B T --> B T --> A B --> A T --> B A --> T A --> B T --> B A --> T B --> A B --> T A --> T B --> A T --> B T --> A B --> A B --> T A --> T A --> B T --> B A --> T B --> A B --> T A --> T A --> B (Pannon Egyetem)

1. 2. 1. 3. 1. 2. 1. 4. 1. 2. 1. 3. 1. 2. 1. 5. 1. 2. 1. 3. 1. 2. 1. 4. 1. 2. 1. 3. 1. 2. 1.

korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong korong

T T B T A A T T B B A B T T B T A A T A B B A A T T B T A A T

--> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> -->

B A A B T B B A A T T A B A A B T B B T A T T B B A A B T B B


2010. november 18.

14 / 41

Rekurzió

A rekurzió átalakítása

Rekurzió A rekurzív algoritmusok sokszor egyszerűbbnek tűnnek, de nem biztos, hogy a rekurzív megoldás a legoptimálisabb Rekurzív algoritmus bizonyos esetekben egyszerűbb felépítéssű (könyebben megérthető) A rekurzió ciklussá alakítható A ciklus rekurzív algorítmussá is alakítható Rekurzív adatszerkezetek Rekurzív görbék (fraktálok) (Koch görbe, Mandelbrot halmaz)



2010. november 18.

15 / 41

Rekurzió

A rekurzió átalakítása

Rekurzió-ciklus átalakítás

Minden rekurzió megvalósítható ciklussal és segédváltozókkal A megoldás bizonyos esetekben nem egyszerű!



2010. november 18.

16 / 41

Rekurzió

A rekurzió átalakítása, Fibonacci

Fibonacci sorozat

Megadása: 0, ha n=0 1, ha n=1 fib(n-1)+fib(n-2), ha n>1 A sorozat rekurzív alakban adott Sorozat elemei: 0-0 1-1 2 - fib(0)+fib(1) = 0+1 = 1 3 - fib(1)+fib(2) = fib(1)+[fib(0)+fib(1)] = 1+[0+1] = 2 4 - fib(2)+fib(3) = [fib(0)+fib(1)]+[fib(1)+fib(2)] = [fib(0)+fib(1)]+[fib(1)+[fib(0)+fib(1)]] = [0+1]+[1+[0+1]] = 3



2010. november 18.

17 / 41

Rekurzió


Fibonacci sorozatot kiszámoló rekurzív függvény Függvény kódja: long fib(int n) { if (n < 0) return -1; if (n <= 1) return n; else return fib(n-1) + fib(n-2); }

Meghívása: ... for(i=0; i<20; i++) printf("fib( %d ) = %d \n", i, fib(i)); ...



2010. november 18.

18 / 41

Rekurzió


Fibonacci sorozatot kiszámoló NEM rekurzív függvény (1.) Hátulról számolva (n értékét folyamatosan csökkenti) Függvény kódja: long fib_cikl_hatul(long n) { long x,y,z; if (n < 0) return -1; if (n == 0) return 0; x=0; y=1; z=1; while (n > 1) { z=x+y; x=y; y=z; n=n-1; } return z; }

Meghívása: for(i=0; i<20; i++) printf("fib_cikl_hatul( %d ) = %d \n", i, fib_cikl_hatul(i)); ... Fodor A. (Pannon Egyetem) Információs technológia

2010. november 18.

19 / 41

Rekurzió


Fibonacci sorozatot kiszámoló NEM rekurzív függvény (1.)(tömörebben) Hátulról számolva (n értékét folyamatosan csökkenti) Függvény kódja: long fib_cikl_hatul_for(long n) { long x,y,z; if (n < 0) return -1; if (n == 0) return 0; for(x=0, y=1, z=1; n > 1; n=n-1) { z=x+y; x=y; y=z; } return z; }

Meghívása: ... for(i=0; i<20; i++) printf("fib_cikl_hatul_for( %d ) = %d \n", i, fib_cikl_hatul_for(i)); ... Fodor A. (Pannon Egyetem)


2010. november 18.

20 / 41

Rekurzió


Fibonacci sorozatot kiszámoló NEM rekurzív függvény (2.) Elölről számolva (n értékét folyamatosan növeli) Függvény kódja: long fib_cikl_elol(long n) { long x,y,z,i; if (n < 0) return -1; if (n == 0) return 0; x=0; y=1; z=n; for(i=1; i < n; i++) { z=x+y; x=y; y=z; } return z; }

Meghívása: ... for(i=0; i<20; i++) printf("fib_cikl_elol( %d ) = %d \n", i, fib_cikl_elol(i)); ... Fodor A. (Pannon Egyetem) Információs technológia

2010. november 18.

21 / 41

Rekurzió


Fibonacci sorozat tagjai fib( 0 ) = 0 fib( 1 ) = 1 fib( 2 ) = 1 fib( 3 ) = 2 fib( 4 ) = 3 fib( 5 ) = 5 fib( 6 ) = 8 fib( 7 ) = 13 fib( 8 ) = 21 fib( 9 ) = 34 fib( 10 ) = 55 fib( 11 ) = 89 fib( 12 ) = 144 fib( 13 ) = 233 fib( 14 ) = 377 fib( 15 ) = 610 fib( 16 ) = 987 fib( 17 ) = 1597 fib( 18 ) = 2584 fib( 19 ) = 4181 fib( 20 ) = 6765 fib( 21 ) = 10946 fib( 22 ) = 17711 fib( 23 ) = 28657 fib( 24 ) = 46368 fib( 25 ) = 75025 fib( 26 ) = 121393 fib( 27 ) = 196418 fib( 28 ) = 317811 fib( 29 ) = 514229 fib( 30 ) = 832040 fib( 31 ) = 1346269 fib( 32 )A.= (Pannon 2178309 Egyetem) Fodor

fib_cikl_hatul( fib_cikl_hatul( fib_cikl_hatul( fib_cikl_hatul( fib_cikl_hatul( fib_cikl_hatul( fib_cikl_hatul( fib_cikl_hatul( fib_cikl_hatul( fib_cikl_hatul(

0 1 2 3 4 5 6 7 8 9

) ) ) ) ) ) ) ) ) )

= = = = = = = = = =

0 1 1 2 3 5 8 13 21 34

-------------------fib_cikl_elol( 0 ) = 0 fib_cikl_elol( 1 ) = 1 fib_cikl_elol( 2 ) = 1 fib_cikl_elol( 3 ) = 2 fib_cikl_elol( 4 ) = 3 fib_cikl_elol( 5 ) = 5 fib_cikl_elol( 6 ) = 8 fib_cikl_elol( 7 ) = 13 fib_cikl_elol( 8 ) = 21 fib_cikl_elol( 9 ) = 34


2010. november 18.

22 / 41

Fa adatszerkezet

Fa adatszerkezet

Fa adatszerkezet

A keresés gyorsítása érdekében a láncolt adatszerkezetet fába rendeztük Fa: az adatszerkezet az egyes elemeknél elágazhat Kétfelé ágazó fákat bináris fának nevezzük A bináris fa és annak minden részfája vagy üres, vagy a gyökérelemből és annak bal és jobboldali részfájából áll Levél: Egy elemnek nincs utódja Kiegyensúlyozott fa: az összes levél azonos szinten van Rekurzív adatszerkezet rekurzív algoritmusokkal egyszerűbb kezelni A keresés az elemek 2-es alapú logaritmusával arányos műveletet igényel



2010. november 18.

23 / 41

Fa adatszerkezet

Fa adatszerkezet

Fa adatszerkezet

Adatszerkezetnek tartalmaznia kell: adat jobb oldali fa címe bal oldali fa címe struct faelem { int adat; struct faelem *bal, *jobb; };



2010. november 18.

24 / 41

Fa adatszerkezet

Fa felépítése

Fa felépítése 2. adat elhelyezése

3. adat elhelyezése



2010. november 18.

25 / 41

Fa adatszerkezet

Fa felépítése

Fa felépítése 4. adat elhelyezése




2010. november 18.

26 / 41

Fa adatszerkezet

Fa felépítése

Fa felépítése




2010. november 18.

27 / 41

Fa adatszerkezet

Fa felépítése

Fa felépítése Fa adatszerkezetbe való rendezett beszúrást végző függvény kódja: void beszur(faelem **ppfa, int ertek) { if( !*ppfa ) { *ppfa = (faelem*) malloc(sizeof(faelem)); (*ppfa)->adat = ertek; (*ppfa)->bal = (*ppfa)->jobb = NULL; } else if ( (*ppfa)->adat != ertek ) if ((*ppfa)->adat > ertek) beszur( &(*ppfa)->bal, ertek); else beszur( &(*ppfa)->jobb, ertek); }



2010. november 18.

28 / 41

Fa adatszerkezet

Fa felépítése

Fa felépítése

Fa adatszerkezetbe való beszúrást végző függvény meghívása: void main(void) { faelem *fa; fa = NULL; beszur(&fa, beszur(&fa, beszur(&fa, beszur(&fa, beszur(&fa, beszur(&fa, }


4); 1); 3); 6); 2); 5);


2010. november 18.

29 / 41

Fa adatszerkezet

Fa felépítése

A függvényhívások után felépített fa

Beszúrt adatok: 4, 1, 3, 6, 2, 5



2010. november 18.

30 / 41

Fa adatszerkezet

Fa felépítése

Fa bejárása

Több startégia van Stratégiak közötti kölönbség, hogy mikor dolgozzuk fel az adatot. Preorder Először feldogozom az adatot, bejárom a bal faágat, bejárom a jobb oldali faágat Inorder Bejárom a bal faágat, feldolgozom az adatot, bejárom a jobb oldali faágat Postorder Bejárom a bal faágat, bejárom a jobb oldali faágat, feldolgozom az adatot



2010. november 18.

31 / 41

Fa adatszerkezet

Fa bejárása

Preorder bejárás

Először feldogozom az adatot, bejárom a bal faágat, bejárom a jobb oldali faágat void preorder(faelem *fa) { if (fa) { printf("%d\n", fa->adat); preorder(fa->bal); preorder(fa->jobb); } }



2010. november 18.

32 / 41

Fa adatszerkezet

Fa bejárása

Preorder bejárás eredménye Először feldogozom az adatot, bejárom a bal faágat, bejárom a jobb oldali faágat Eredmény: 4 1 3 2 6 5 void preorder(faelem *fa) { if (fa) { printf("%d\n", fa->adat); preorder(fa->bal); preorder(fa->jobb); } }



2010. november 18.

33 / 41

Fa adatszerkezet

Fa bejárása

Inorder bejárás

Bejárom a bal faágat, feldolgozom az adatot, bejárom a jobb oldali faágat void inorder(faelem *fa) { if (fa) { inorder(fa->bal); printf("%d\n", fa->adat); inorder(fa->jobb); } }



2010. november 18.

34 / 41

Fa adatszerkezet

Fa bejárása

Inorder bejárás eredménye Bejárom a bal faágat, feldolgozom az adatot, bejárom a jobb oldali faágat Eredmény: 1 2 3 4 5 6 Rendezetten adja vissza az adatokat void inorder(faelem *fa) { if (fa) { inorder(fa->bal); printf("%d\n", fa->adat); inorder(fa->jobb); } }



2010. november 18.

35 / 41

Fa adatszerkezet

Fa bejárása

Postorder bejárás

Bejárom a bal faágat, bejárom a jobb oldali faágat, feldolgozom az adatot void postorder(faelem *fa) { if (fa) { postorder(fa->bal); postorder(fa->jobb); printf("%d\n", fa->adat); } }



2010. november 18.

36 / 41

Fa adatszerkezet

Fa bejárása

Postorder bejárás eredménye Bejárom a bal faágat, bejárom a jobb oldali faágat, feldolgozom az adatot Eredmény: 2 3 1 5 6 4 void postorder(faelem *fa) { if (fa) { postorder(fa->bal); postorder(fa->jobb); printf("%d\n", fa->adat); } }



2010. november 18.

37 / 41

Fa adatszerkezet

A fa adatszerkezet egyéb tulajdonságai

Műveletek a fa adatszerkezettel Beszúrás Törlése Bejárás Keresés Fa diagnosztizálása Mélység Kiegyensúlyozottság Van-e jobb/bal ága



2010. november 18.

38 / 41

Fa adatszerkezet


Bináris fa Adattagjai: adat 2 ág (jobb-bal)

Megvalósítás: struct binfaelem { int adat; struct binfaelem *bal, *jobb; };



2010. november 18.

39 / 41

Fa adatszerkezet


Nem bináris fa Adattagjai: adat 2...n ág

Megvalósítás: #define N 6 struct nembinfaelem { int adat; struct nembinfaelem *faagak[ N ]; } ;



2010. november 18.

40 / 41

Fa adatszerkezet


Elfajult fa

A fa valamely ága sokkal nagyobb mélységű, mint a többi Az építés során keletkezhetnek a gondok Például: (1 6 20 24 30)



2010. november 18.

41 / 41

Információs Technológia

Recommend Documents