Rekurzió. Programozás alapjai C nyelv 9. gyakorlat. Rekurzív algoritmus. Rekurzív algoritmus fajtái. Példa: n! (2) Példa: n!

Rekurzió

Programozás alapjai C nyelv 9. gyakorlat

• A feladat algoritmusa eleve rekurzív formában adott (ld: n!). • A valójában nem rekurzív de valami hasznot húzunk a rekurzióból, pl. sorrend fordítás (ld: számkiíró).

Szeberényi Imre BME IIT

<[email protected]>

Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.14.

-1-

Rekurzív algoritmus

© BME-IIT Sz.I.

-2-

2005.11.14.

– közvetlen (a hívja a-t) – közvetett (a hívja b-t és b hívja a-t)

• Hányszor, hány helyen hívja magát – egyszerű – többszörös

-3-


© BME-IIT Sz.I.

2005.11.14.

-4-

Példa: n! (2) long fakt(int n) { if (n > 1) return(n*fakt(n-1)); return(1); }

• Rekurzívan adott az algoritmus. (Ennek ellenére nem a rekurzió a leghatékonyabb megvalósítás.) • n! = n * (n-1)!, ha n > 1, egyébként 1.

fakt(4) return(4*fakt(3)) return(3*fakt(2)) return(2*fakt(1)) return(1) 2*1 3*2 4*6 24

long fakt(int n) { if (n > 1) return(n*fakt(n-1)); return(1); } © BME-IIT Sz.I.

2005.11.14.

• Hogyan hívja önmagát

Példa: n!


© BME-IIT Sz.I.

Rekurzív algoritmus fajtái.

• Megkeressük azt a legegyszerűbb esetet amiben a megoldás már magától értetődik. • Megkeressük, hogy hogyan vezethető vissza ismételt egyszerűsítésekkel a legegyszerűbb esetre a feladat.



2005.11.14.

-5-


© BME-IIT Sz.I.

2005.11.14.

-6-

1

Példa: számkiíró

Példa: számkiíró (2)

Írjunk ki 3-as számrendszerben: n = an*3n + an-1*3n-1 + .... + a1*31 + a0 • Ha elosztjuk 3-mal akkor a maradék adja az utolsó jegyet. • Gond: ezt a jegyet kellene utoljára kiírni.

void harki(int n) { maradék int e, m;

– lehetne tárolni egy tömbben, de .... }

• 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 jegyek). Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.14.

-7-

Példa: számkiíró (3) harki(34) m ≡ 1

harki(11) m ≡ 2

harki(3) m ≡ 0

0 1

2


© BME-IIT Sz.I.

egészrész

m = n % 3; if (e = n / 3) harki(e); printf(”%d”, m);


csak visszatérés után írunk ki

© BME-IIT Sz.I.

2005.11.14.

-8-

Példa: Hanoi tornyai legenda

void harki(int n) { int e, m = n % 3; if (e = n / 3) harki(e); printf(”%d”, m); }

Feladat:

harki(1) m ≡ 1

?

1

3410=10213 2005.11.14.

-9-

Algoritmus a legenda szerint


© BME-IIT Sz.I.

2005.11.14.

- 10 -

2005.11.14.

- 12 -

Hanoi tornyai folyt.

• „Átviszem a felső 99 korongot az ezüstrúdra, majd a 100. korongot átrakom az aranyrúdra. Ezután átviszem az ezüstrúdon levő korongokat az aranyrúdra.” • „Elég öreg vagyok, ezért inkább a tanítványomra bízom a 99 korong átrakását. Elegendő nekem a 100. korong mozgatása.”


© BME-IIT Sz.I.

2005.11.14.

- 11 -


© BME-IIT Sz.I.

2



© BME-IIT Sz.I.


2005.11.14.

- 13 -



© BME-IIT Sz.I.

2005.11.14.

- 14 -

Hanoi tornyai folyt. void Hanoi(int n, char forras, char cel, char seged) { if (n > 0) { Hanoi(n-1, forras, seged, cel); printf("%d. korongot %c -> %c\n", n, forras, cel); Hanoi(n-1, seged, cel, forras); } }

9

main() { Hanoi(4, 'R', 'A', 'E'); Hanoi(6, 'R', 'A', 'E'); } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.14.

- 15 -


Rekurzió összefoglalása

© BME-IIT Sz.I.

2005.11.14.

2005.11.14.

- 16 -

Fa

• A rekurzív algoritmusok sokszor kézenfekvőnek tűnnek, de nem biztos, hogy rekurzívan kapjuk a leghatékonyabb megoldást. • Rekurzív algoritmus helyességét sokszor egyszerűbb belátni. • A legtöbb rekurzió ciklussá alakítható. • Rekurzív adatszerkezetek Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

i NULL

- 17 -


NULL

© BME-IIT Sz.I.

typedef struct fa_str { int i; struct fa_str *bal; struct fa_str *jobb; } fa_elem, *fa_poi;

2005.11.14.

- 18 -

3

Fa

Fa 22 91 8 31 12 2 20 3 65

15

15 20

6

8

3 2 Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.14.

- 19 -

Fa (elfajuló)

31 20 12 5

2005.11.14.

- 21 -

Vázlat (adatszerkezet)

© BME-IIT Sz.I.


22

© BME-IIT Sz.I.

91 2005.11.14.

- 20 -

2005.11.14.


© BME-IIT Sz.I.

2005.11.14.

- 22 -

2005.11.14.

- 24 -

Vázlat (algoritmus) gyoker = NULL fp = állomány_megnyitása() while folvas(fp, i) gyoker = faepit(gyoker, i) folvas(stdin, i) p = keres(gyoker, i) if (p != NULL) elem_kiirása else nem_találtuk_meg fakir(gyoker)

typedef struct fa_str { int i; /* értek */ int sz; /* számláló */ struct fa_str *bal; /* bal mutató */ struct fa_str *jobb; /* jobb mutató */ } fa_elem, *fa_poi;


12

5

• Olvassunk be a „binfa.txt” állományból file végéig egész számokat. Tároljuk az adatokat bináris fában! • Keressünk meg egy adott elemet, és írjuk ki, hogy hányszor fordult elő! • Írjuk ki nagyság szerint rendezve az adatokat és azok előfordulási számát!

22

© BME-IIT Sz.I.

31

Feladat 1 91


20

6

- 23 -


© BME-IIT Sz.I.

4

Alprogram spec. - faepit

Alprogram spec. - folvas

fa_poi faepit(fa_poi p, int i);

int folvas(FILE *fp, int *n); (≈ olvas 8. ea)

– A paraméterként kapott bináris fába felveszi az integer paraméterként kapott értéket. Azonos érték esetén növeli a számlálót. – bemenet:

– Integer értékű függvény, beolvassa a következő egészet a paraméterként kapott állományból. A nem számjegy karaktereket eldobja. – bemenet:

• fa gyökerére mutató pointer. NULL, ha üres • felveendő érték

• megnyitott állomány pointere • pointer a kimenő adatra

– kimenet:

– kimenet:

• függvényérték: fa gyökerére mutató pointer


© BME-IIT Sz.I.

2005.11.14.

• olvasott egész (pointer paraméter) • függvényérték 1, ha sikerült az olvasás, egyébként 0 - 25 -

Alprogram spec. - keres


© BME-IIT Sz.I.

2005.11.14.

- 26 -

Alprogram spec. - fakir

fa_poi keres(fa_poi p, int i);

void fakir(fa_poi p);

– Függvény, amely a paraméterként kapott bináris fában megkeres egy elemet. – bemenet:

– A paraméterként kapott fa elemeit nagyság szerint kiírja. – bemenet:

• fa gyökerére mutató pointer. NULL, ha üres • keresett érték

• fa gyökerére mutató pointer. NULL, ha üres

– kimenet: standard output

– kimenet: • függvényérték: megtalált elem pointere NULL, ha nincs. Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.14.

- 27 -

Algoritmus - faepit

© BME-IIT Sz.I.

© BME-IIT Sz.I.

2005.11.14.

- 28 -

Algoritmus - faepit

if a_fa_üres then új_elemet_veszünk_fel else érték_azonos then növeljük_a_számlálót else if kisebb_elemet_kell_felvenni then bal_részfát_építjük else jobb_részfát_építjük



2005.11.14.

• Az építés algoritmusa rekurzív, ami nem meglepő, hiszen maga az adatszerkezet is rekurzív. A fa és annak minden részfája

– vagy üres, vagy – egy gyökérelemből és annak bal és jobb oldali részfájából áll.

• Nem feltétlenül rekurzív, de sokkal egyszerűbb. - 29 -


© BME-IIT Sz.I.

2005.11.14.

- 30 -

5

Implementáció - faepit

Implementáció - faepit

• A tömörebb írásmód miatt vezessük be a new makrót, ami megfelelő méretű helyet foglal, és hibát is kezel (visszatér NULL-lal): tárolandó objektum típusa

pointer változó

#define new(p, obj) \ if ((p = malloc(sizeof(obj))) == NULL) return(NULL)


© BME-IIT Sz.I.

2005.11.14.

- 31 -

Algoritmus - keres

© BME-IIT Sz.I.

2005.11.14.

- 33 -

15 20

6

31


5 © BME-IIT Sz.I.

2005.11.14.

- 32 -


© BME-IIT Sz.I.

2005.11.14.

- 34 -

Implementáció - fakir

3 2

© BME-IIT Sz.I.

fa_poi keres(fa_poi p, int i) { if (p == NULL) return(NULL); else if (p->i == i) return(p); else if (p->i > i) return(keres(p->bal, i)); else return(keres(p->jobb, i)); }

Algoritmus - fakir if fa_nem_üres then begin kiírjuk_a_bal_részfát kiírjuk_az_elemet kiírjuk_a_jobb_részfát end


Implementáció - keres

if a_fa_üres then nincs_meg_az_elem else érték_azonos then megtaláltuk else if a_keresett_elem_kisebb then bal_részfában_keresünk else jobb_részfában_keresünk


fa_poi faepit(fa_poi p, int i) p csak itt { változik if (p == NULL) { new(p, fa_elem); p->bal = p->jobb = NULL; p->i = i; p->sz = 1; bal részfán } else if (p->i == i) tovább p->sz++; else if (p->i > i) p->bal = faepit(p->bal, i); else a változást p->jobb = faepit(p->jobb, i); visszaírjuk (!) return(p); }

22 2005.11.14.

91 - 35 -

void fakir(fa_poi p) { if (p != NULL) { fakir(p->bal); /* bal részfa */ printf(”%5d%6d\n”, p->i, p->sz); fakir(p->jobb); /* jobb részfa */ } } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.14.

- 36 -

6

Implementáció - olvas

Implementáció - program #include <stdio.h> #include <stdlib.h>

int olvas(FILE *fp, int *i) { int r ;

typedef struct fa_str { int i; int sz; struct fa_str *bal; struct fa_str *jobb; } fa_elem, *fa_poi;

while ((r = fscanf(fp, ”%d”, i)) == 0) fscanf(fp, ”%*c”); return(r != EOF); }

… alprogramok …


© BME-IIT Sz.I.

2005.11.14.

- 37 -

Implementáció - program

© BME-IIT Sz.I.

2005.11.14.

- 39 -

Algoritmus - keres

© BME-IIT Sz.I.

2005.11.14.

- 38 -


© BME-IIT Sz.I.

2005.11.14.

- 40 -

Implementáció - keres2 fa_poi keres2(fa_poi p, int i) ciklus { elhagyása, mert while (p != NULL) { megtaláltuk if (p->i == i) break; if (p->i > i) p = p->bal; else megtaláltuk, p = p->jobb; vagy NULL } return(p); }

if a_fa_üres then nincs_meg_az_elem else érték_azonos then megtaláltuk else if a_keresett_elem_kisebb then bal_részfában_keresünk else jobb_részfában_keresünk


© BME-IIT Sz.I.

• Keressünk a fában nem rekurzív algoritmussal! (A legtöbb esetben a rekurzió ciklussá alakítható.) • „Rajzoljuk” ki a fát!

if ((fp = fopen(”binfa.txt”, ”r”)) == NULL) printf(”A binfa.txt nem olvasható\n”), exit(-1); while (olvas(fp, &i)) gyoker = faepit(gyoker, i); olvas(stdin, &i); p = keres(gyoker, i); if (p != NULL) printf(”%d:%10d\n”, p->i, p->sz); else printf(”Sajnos nincs meg!\n”); fakir(gyoker);



Feladat 2

main () { fa_poi gyoker = NULL, p; FILE *fp; int i;

}

/* értek */ /* számláló */ /* bal mutató */ /* jobb mutató */

2005.11.14.

- 41 -


© BME-IIT Sz.I.

2005.11.14.

- 42 -

7

Alprogram spec. - farajz

Algoritmus - farajz

void farajz(fa_poi p, int m);

if fa_nem_üres then begin növeljük_a_margót kiírjuk_a_jobb_részfát kiírjuk_a_margót kiírjuk_az_elemet kiírjuk_a_bal_részfát csökkentjük_a_margót end

– A paraméterként kapott bináris fát „kirajzolja” a paraméterként kapott margóval. – bemenet: • fa gyökerére mutató pointer. NULL, ha üres • margó

– kimenet: • 90 fokkal elforgatott „rajz” a fa elemeiről.


© BME-IIT Sz.I.

2005.11.14.

- 43 -

Implementáció - farajz


Input: (file) 20 30 25 10 7 8 5 4 31 20 30 9 7 7 7 7 Input: (standard) 7

a szintet

© BME-IIT Sz.I.

2005.11.14.

- 45 -

Összefoglalás

© BME-IIT Sz.I.


7: 4 5 7 8 9 10 20 25 30 31

5 1 1 5 1 1 1 2 1 2 1

© BME-IIT Sz.I.

31 30 25 20 10 9 8 7 5 4 2005.11.14.

- 46 -

Összefoglalás (2) • Ha egy elemnek nincs utódja, akkor azt levélelemnek nevezzük. • Ha az összes levél azonos szinten van, akkor a fa kiegyensúlyozott. • 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.

• 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. Programozás alapjai I. (C nyelv, gyakorlat)

- 44 -

2005.11.14.

Próbafuttatás eredménye

void farajz(fa_poi p, int m) { növeljük if (p != NULL) { a szintet (m-1)*5 szóköz m++; farajz(p->jobb, m); /* jobb részfa */ printf(”%*s%5d\n”, (m-1)*5, ””, gy->i); farajz(p->bal, m); /* bal részfa */ m--; } csökkentjük } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.14.

- 47 -


© BME-IIT Sz.I.

2005.11.14.

- 48 -

8

Rekurzió. Programozás alapjai C nyelv 9. gyakorlat. Rekurzív algoritmus. Rekurzív algoritmus fajtái. Példa: n! (2) Példa: n!

Recommend Documents