Programozás C nyelven 6. ELŐADÁS. Sapientia EMTE

Programozás C nyelven 6. ELŐADÁS Sapientia EMTE 2015-16

ELJÁRÁSOK: void-függvények • Olvassu k be szá ot a bille tyűzetről, és írassuk ki a égyzeteiket a képer yőre. int main(){ int n, i, szam; cin >> n; for( i=1 ; i <= n ; ++i){ cin >> szam; cout << szam*szam << ‘\n’; } return 0; }

3 7 49 11 121 5 25 _

ELJÁRÁSOK: void-függvények void be_szamsor_ki_negyzetsor(int); int main(){ int n; cin >> n; be_szamsor_ki_negyzetsor(n); return 0; } void be_szamsor_ki_negyzetsor(int db){ int i, szam; for( i=1 ; i <= db ; ++i){ cin >> szam; cout << szam*szam << ‘\n’; } }

3 7 49 11 121 5 25 _

ISMÉTLÉS: iteratív vs. rekurzív

PÉLDÁNYOK Kiosztott feladatok

1. 5 fát!

2. 4 fát!

3.

3 fát!

4.

2 fát!

5.

1 fát!

ISMÉTLÉS: iteratív vs. rekurzív • Ha egy függvény azt a feladatot kapja, hogy is ételte végezze el bizo yos űveleteket, akkor két variáns közül választhat: – Ciklus révén felvállalja a sokszori végrehajtást (iteratív módszer); – Csak egyszeri végrehajtást vállal fel, és a többit átruházza egy „kló jára” rekurzív ódszer . • átruházza egy „kló jára”  meghívja önmagát

MIÉRT?

Hanoi tornyai: iteratív vs. rekurzív

void moveDisksBetweenTwoPoles(struct Stack *src, struct Stack *dest, char s, char d){ int pole1TopDisk = pop(src); int pole2TopDisk = pop(dest); void tohIterative(int num_of_disks, struct Stack *src, struct Stack *aux, struct Stack *dest){ if (pole1TopDisk == INT_MIN){ int i, total_num_of_moves; push(src, pole2TopDisk); char s = 'S', d = 'D', a = 'A'; pole2TopDisk); void move(int n, int from, int moveDisk(d, to, int s,via){ if (num_of_disks % 2 == 0){ } if (n > 0) { char temp = d; else if (pole2TopDisk == INT_MIN){ d = a; move(n - 1, from, via,push(dest, to); pole1TopDisk); a = temp; d, pole1TopDisk); cout << from << ‘,’ <<moveDisk(s, to << ‘\n’; } } move(n from); total_num_of_moves = pow(2, num_of_disks) - 1; - 1, via, to, else if (pole1TopDisk > pole2TopDisk){ for (i = num_of_disks; i >= 1; i--) } push(src, pole1TopDisk); ELEGÁNS push(src, i); push(src, pole2TopDisk); } for (i = 1; i <= total_num_of_moves; i++){ moveDisk(d, s, pole2TopDisk); if (i % 3 == 1) } moveDisksBetweenTwoPoles(src, dest, s, d); else{ else if (i % 3 == 2) push(dest, pole2TopDisk); moveDisksBetweenTwoPoles(src, aux, s, a); push(dest, pole1TopDisk); else if (i % 3 == 0) moveDisk(s, d, pole1TopDisk); moveDisksBetweenTwoPoles(aux, dest, a, d); NEHÉZKES } } } }

Ültess fákat: iteratív

Hányszor hívódik meg a függvény

void ultess_fakat(int); int main(){ int n; cin >> n; ultess_fakat(n); return 0; } void ultess_fakat(int db){ int i; for( i=1 ; i <= db ; ++i){ <ültess el egy fát> } }

Hány db/i –nek történik helyfoglalás

Ültess fákat: rekurzív

Hányszor hívódik meg a függvény

void ultess_fakat(int); int main(){ 1. 2. int n; 5 cin >> n; 4 ultess_fakat(n); return 0; } void ultess_fakat(int db){ if (db > 1){ <ültess el egy fát> ultess_fakat(db-1); } else {<ültess el egy fát>} }

3. 3

4.

2

Hány db –nek történik helyfoglalás

5.

1

Rekurzív eljárások: SÉMA (1) void R_E(){ if (){ Rekurzív-ág R_E(<átruházott_feladat_paraméterei>); } Hasonló, else { egyszerűbb; Triviális-ág konvergál a triviális } feladathoz } 1. 5

2. 4

3. 3

4.

2

5.

1

Melyik példány ültet először fát?

Rekurzív eljárások: SÉMA (2) void R_E(){ if (){ R_E(<átruházott_feladat_paraméterei>); } else { } } 1.

5

2.

4

3.

3

4. 2

5. 1

Melyik példány ültet először fát?

Rekurzív void-függvények (1) 3 void REKURZIV_be_szamsor_ki_negyzetsor(int); 7 int main(){ 49 int n; 11 cin >> n; 121 REKURZIV_be_szamsor_ki_negyzetsor(n); 5 25 return 0; _ } void REKURZIV_be_szamsor_ki_negyzetsor(int db){ int szam; Hány db/szam –nak történik helyfoglalás Hányszor if (db > 1){ hívódik cin >> szam; cout << szam*szam << ‘\n’; meg a REKURZIV_be_szamsor_ki_negyzetsor(db-1); függvény } else { 1. 2. 3. cin >> szam; db szam cout << szam*szam << ‘\n’; db szam 3 7 } db szam 2 11 } 1 5

Rekurzív void-függvények (2) 3 7 11 5 25 121 49 _

void REKURZIV_be_szamsor_ki_negyzetsor(int); int main(){ int n; cin >> n; REKURZIV_be_szamsor_ki_negyzetsor(n); return 0; } void REKURZIV_be_szamsor_ki_negyzetsor(int db){ int szam; if (db > 1){ cin >> szam; REKURZIV_be_szamsor_ki_negyzetsor(db-1); cout << szam*szam << ‘\n’; } else { 1. 2. 3. cin >> szam; cout << szam*szam << ‘\n’; db szam db szam } 3 7 db szam 2 11 } 1 5

Rekurzív void-függvények (3) void REKURZIV_be_szamsor_ki_negyzetsor(int); 3 int main(){ 7 int n; 49 11 cin >> n; 121 REKURZIV_be_szamsor_ki_negyzetsor(n); 5 return 0; 25 } _ void REKURZIV_be_szamsor_ki_negyzetsor(int db){ int szam; Hány db/szam –nak Hányszor if (db > 0){ történik helyfoglalás hívódik cin >> szam; cout << szam*szam << ‘\n’; meg a REKURZIV_be_szamsor_ki_negyzetsor(db-1); függvény } 1. 2. 3. 4. else {;} } db szam 3

7

db szam

2 11

db szam

1

5

db szam

0

?

Rekurzív valódi-függvények (1) Írj rekurzív függvényt, amely visszatéríti a paraméterként kapott természetes szám számjegyei szorzatát!

1. KÉRDÉS: Hogyan vezethető vissza a feladat hasonló, egyszerűbb részfeladatra? x számjegyszorzata (52437)

x/10 számjegyszorzata (5243)


2. KÉRDÉS: Mikor tekintem úgy, hogy a feladat triviálissá redukálódott? Ha elfogyott a szám (52437)

(5243)

(524)

(52)

(5)

()


int szamjegyszorzat(int x){ if (x > 0){ Rekurzív-ág ooo } Triviális-ág else{ ooo } }


int szamjegyszorzat(int x){ if (x > 0){ ooo } Triviális részfeladat else{ return 1; } nyilvánvaló } megoldásának return-elése


int szamjegyszorzat(int x){ if (x > 0){ int t = szamjegyszorzat(x/10); ooo Rekurzív hívás révén kérem } tálcán az else{ return 1; } átruházott rész megoldását }


int szamjegyszorzat(int x){ if (x > 0){ int t = szamjegyszorzat(x/10); return t * x%10; } A bevállalt szorzás else{ return 1; } }

Rekurzív valódi-függvények int szamjegyszorzat(int); int main(){ 324 int szam; 24_ cin >> szam; cout << szamjegyszorzat(szam); return 0; } int szamjegyszorzat(int x){ if (x > 0){ 1. int t = szamjegyszorzat(x/10); x t return t * x%10; 324 324 ? } else{ return 1; } 32 }

24

324 6 * *

2.

3.

x

t

32 ? 3

32 3 6

4.

*

x

t

3

?

0

0

3 3

1

*

x

1

Összefoglalás (1) • Mi de jele tősebb feladat egoldása részfeladatok ismételt elvégzését feltételezi. – Ha ciklus-utasítás révén valósítjuk meg az ismétlést, akkor iteratív implementációról beszélünk. – Egy ásik lehetőség a rekurzív egvalósítás.

• A rekurzív eljárások/függvények sajátossága, hogy meghívják önmagukat. – Olyan, mintha klónoznának magukból további példányokat. • Úgy is mondhatnánk, hogy a rekurzivitás mechanizmusa révé , az illető eljárásból/függvé yből példá yok sora jö létre, amelyek között szétosztódik a megoldandó feladat.

Összefoglalás (2) • Mindegyik példány bevállal egy adott részt a kapott feladatból, a maradék részfeladatot pedig egy következő példá yra ruházza át.

– Mivel az átruházás egy klónra történik, ezért a kapott feladatnak és az átruházott részfeladatnak hasonlónak kell lennie.

• A rekurzív implementálás kulcskérdése tehát az, hogy iké t vezethető vissza a kapott feladat egoldása haso ló, egyre egyszerűbb részfeladatok egoldására. – E redukálási folya at révé végül a yira leegyszerűsödik a feladat, hogy a sorvégi példány egészében be tudja vállalni.

Összefoglalás (3) • Minden eljárás/függvény-példány hasonló feladatot kap, hogy megoldjon; • A kapott feladat éretétől függ, hogy a kurre s példány rekurzívan fog viselkedni, vagy bevállalja a teljes megoldást; – Rekurzívan viselkedni azt jelenti, hogy önmaga meghívása által, a kapott feladat oroszlánrészét haso ló, egyszerűbb részfeladatot átruházza egy következő példá yra a fe aradt részt bevállalja ;

• Egyszerűsített, általá os forgatókö yv a kurre s példányra megfogalmazva:

Gyakori hibák (ID)

Gyakori hibák (ID)

Gyakori hibák (ID)

Gyakori hibák (ID)

Gyakori hibák (ID)

Gyakori hibák (ID)

Gyakori hibák (ID)

Gyakori hibák (ID)

Programozás C nyelven 6. ELŐADÁS. Sapientia EMTE

Recommend Documents