Rekurz´ıv algoritmusok 11. el˝ oad´as Sergy´an Szabolcs
[email protected] ´ Obudai Egyetem Neumann J´ anos Informatikai Kar
2011. november 14.
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
1 / 32
Rekurz´ıv algoritmusok 1
Faktori´alis
2
Fibonacci sz´amok
3
Binomi´alis egy¨ utthat´ok
4
Ackermann f¨ uggv´eny
5
Egyszer˝ u feladatok
6
Keres´esek
7
Rekurz´ıv rendez´es
8
Hanoi tornyai
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
2 / 32
Faktori´alis Matematikai defin´ıci´o Az n ∈ N faktori´alisa (jel¨ ol´es: n!) alatt az els˝ o n darab pozit´ıv term´eszetes sz´am szorzat´at ´ertj¨ uk, n = 0 eset´en pedig 1-et. ha n = 0, 1, n Q n! = i, ha n ≥ 1. i=1
¨ Megval´os´ıt´as az Osszegz´ es t´etellel fakt(N, R) R := 1 Ciklus i := 1-t˝ol N-ig R := R ∗ i Ciklus v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 11
2011. november 14.
3 / 32
Rekurz´ıv faktori´alis Matematikai defin´ıci´o A faktori´alis rekurz´ıv m´odon is defini´alhat´ o: 1, ha n = 0, n! = n · (n − 1)!, ha n ≥ 1.
F¨uggv´ennyel le´ırva fakt(n) =
1, ha n = 0, n · fakt(n − 1), ha n ≥ 1.
¨ Osszetev˝ ok A rekurz´ıv defin´ıci´onak k´et r´esze van: Alapeset (itt most az n = 0 eset) Indukci´os l´ep´es: visszavezetj¨ uk a probl´em´at kisebb sz´amok eset´ere. Sergy´ an (OE NIK)
AAO 11
2011. november 14.
4 / 32
Rekurz´ıv faktori´alis
Rekurz´ıv algoritmus
Ki´ert´ekel´es fakt(5) =
fakt(N) Ha N = 0, akkor return(1) K¨ ul¨ onben return(N · fakt(N − 1)) El´agaz´as v´ege F¨ uggv´eny v´ege
Sergy´ an (OE NIK)
AAO 11
5 · fakt(4) 5 · 4 · fakt(3) 5 · 4 · 3 · fakt(2) 5 · 4 · 3 · 2 · fakt(1) 5 · 4 · 3 · 2 · 1 · fakt(0) 5·4·3·2·1·1 5·4·3·2·1 5·4·3·2 5·4·6 5 · 24 120
2011. november 14.
5 / 32
Rekurzi´o megval´os´ıt´asa Probl´em´ak Ugyanabb´ol a f¨ uggv´enyb˝ ol egyszerre t¨ obb is fut? El˝ oz˝ o p´eld´aban a fakt f¨ uggv´enyb˝ ol egyszerre 6 is futott.
A f¨ uggv´enyen bel¨ uli lok´alis v´altoz´ ok ´ert´eke fel¨ ul´ır´ odik? El˝ oz˝ o p´eld´aban honnan lehet tudni, hogy N ´ert´eke ´eppen mennyi?
Megold´as Minden megh´ıvott f¨ uggv´eny m´as, csak a nev¨ uk azonos. A mem´ori´aban elt´aroljuk, hogy honnan h´ıvtunk egy f¨ uggv´eny, majd ide lehet visszat´erni k´es˝ obb. A lok´alis v´altoz´ok minden egyes f¨ uggv´enyben k¨ ul¨ on-k¨ ul¨on l´etrej¨onnek. Azonos nev˝ u, de k¨ ul¨onb¨ oz˝ o v´altoz´ okr´ ol van sz´ o, hiszen a f¨ uggv´enyek is k¨ ul¨onb¨oz˝oek. Az ezen c´elra fenntartott mem´ oria t´ ulcsord´ ulhat t´ ul sok f¨ uggv´enyh´ıv´as eset´en. Sergy´ an (OE NIK)
AAO 11
2011. november 14.
6 / 32
Rekurzi´o megval´os´ıt´asa R :=fakt(5) Ha 5 = 0, akkor ... K¨ ul¨ onben R := 5 · fakt(4) El´ agaz´ as v´ ege F¨ uggv´ eny v´ ege
→
R :=fakt(4) Ha 4 = 0, akkor ... K¨ ul¨ onben R := 4 · fakt(3) El´ agaz´ as v´ ege F¨ uggv´ eny v´ ege
←
R :=fakt(1) Ha 1 = 0, akkor ... K¨ ul¨ onben R := 1 · fakt(0) El´ agaz´ as v´ ege F¨ uggv´ eny v´ ege
→
R :=fakt(3) Ha 3 = 0, akkor ... K¨ ul¨ onben R := 3 · fakt(2) El´ agaz´ as v´ ege F¨ uggv´ eny v´ ege
←
R :=fakt(2) Ha 2 = 0, akkor ... K¨ ul¨ onben R := 2 · fakt(1) El´ agaz´ as v´ ege F¨ uggv´ eny v´ ege
↓ R :=fakt(0) Ha 0 = 0, akkor R := 1 K¨ ul¨ onben ... El´ agaz´ as v´ ege F¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
7 / 32
Rekurz´ıv algoritmusok 1
Faktori´alis
2
Fibonacci sz´amok
3
Binomi´alis egy¨ utthat´ok
4
Ackermann f¨ uggv´eny
5
Egyszer˝ u feladatok
6
Keres´esek
7
Rekurz´ıv rendez´es
8
Hanoi tornyai
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
8 / 32
Fibonacci sz´amok Nyulak szaporod´as´anak vizsg´alata Fibonacci a nyulak szaporod´as´at vizsg´alta, ´es a k¨ ovetkez˝oket tapasztalta: Minden ny´ ulp´ar - amikor szaporodik -, akkor k´et ut´oddal j´arul hozz´a a n´epess´eghez. A nyulak a sz¨ ulet´es¨ uket k¨ ovet˝ oen k´et egym´as ut´ani id˝opontban szaporodnak. Vizsg´aljuk, hogy adott id˝ opontban h´any u ´j ny´ ulp´ar sz¨ uletik.
Matematikai le´ır´as Jel¨ olje Fib(n), hogy az n-edik szaporod´askor h´any u ´j ny´ ulp´ar sz¨ uletik. Kezdetben van egy ny´ ulp´ar: Fib(0) = 1 K¨ovetkez˝o szaporod´askor ez a p´ar szaporodik: Fib(1) = 1 Minden m´as szaporod´askor az el˝ oz˝ o ´es az azt megel˝oz˝o szaporod´askor sz¨ uletett nyulak j´arulnak hozz´a a szaporod´ashoz (m´egpedig egy-egy ny´ ulp´arral). Teh´at: Fib(n) = Fib(n − 1) + Fib(n − 2) Sergy´ an (OE NIK)
AAO 11
2011. november 14.
9 / 32
Fibonacci sz´amok Rekurz´ıv algoritmus Fib(N) Ha N ≤ 1 akkor return(1) K¨ ul¨onben return(Fib(N − 1) + Fib(N − 2)) El´agaz´as v´ege F¨ uggv´eny v´ege
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
10 / 32
Fibonacci sz´amok Az algoritmus megval´os´ıthat´ o rekurzi´ o n´elk¨ ul is.
Iterat´ıv algoritmus Fib(N) a := 1 e := 1 Ciklus i := 1-t˝ol N − 1-ig temp := a + e e := a a := temp Ciklus v´ege return(a) F¨ uggv´eny v´ege
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
11 / 32
Rekurz´ıv algoritmusok 1
Faktori´alis
2
Fibonacci sz´amok
3
Binomi´alis egy¨ utthat´ok
4
Ackermann f¨ uggv´eny
5
Egyszer˝ u feladatok
6
Keres´esek
7
Rekurz´ıv rendez´es
8
Hanoi tornyai
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
12 / 32
Binom´alis egy¨utthat´ok Matematikai defin´ıci´o 1, n n−1 = + k k 1,
n−1 k−1
ha k = 0 , ha 0 < k < n ha k = n
Algoritmus Bin(N, K ) Ha (K = 0) vagy (K = N) akkor return(1) K¨ ul¨onben return(Bin(N − 1, K ) + Bin(N − 1, K − 1)) El´agaz´as v´ege F¨ uggv´eny v´ege
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
13 / 32
Rekurz´ıv algoritmusok 1
Faktori´alis
2
Fibonacci sz´amok
3
Binomi´alis egy¨ utthat´ok
4
Ackermann f¨ uggv´eny
5
Egyszer˝ u feladatok
6
Keres´esek
7
Rekurz´ıv rendez´es
8
Hanoi tornyai
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
14 / 32
Ackermann f¨uggv´eny Matematikai defin´ıci´o ha m = 0, n + 1, A(m − 1, 1), ha m > 0 ´es n = 0, A(m, n) = A (m − 1, A(m, n − 1)) , ha m > 0 ´es n > 0.
Algoritmus Ackermann(M, N) Ha M = 0 akkor return(N + 1) K¨ ul¨onben Ha (M > 0) ´es (N = 0) akkor return(Ackermann(M − 1, 1)) K¨ ul¨onben return(Ackermann(M − 1, Ackermann(M, N − 1))) El´agaz´as v´ege El´agaz´as v´ege F¨ uggv´eny v´ege Sergy´ an (OE NIK)
AAO 11
2011. november 14.
15 / 32
Rekurz´ıv algoritmusok 1
Faktori´alis
2
Fibonacci sz´amok
3
Binomi´alis egy¨ utthat´ok
4
Ackermann f¨ uggv´eny
5
Egyszer˝ u feladatok
6
Keres´esek
7
Rekurz´ıv rendez´es
8
Hanoi tornyai
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
16 / 32
Sz¨oveg megford´ıt´asa Feladat Az X v´altoz´oban adott egy N hossz´ us´ag´ u sz¨ oveg. Feladat, hogy a karakterek sorrendj´et megford´ıtsuk. P´eld´aul: abcdef → fedcba
Rekurz´ıv megval´os´ıt´as Ford´ıt´as(X , N) Ha N = 1 akkor return(X ) k¨ ul¨onben return(Ford´ıt´as(X [2..N], N − 1) + X [1]) El´agaz´as v´ege F¨ uggv´eny v´ege
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
17 / 32
Palindrom Feladat Egy N-jegy˝ u sz´am palindrom, ha az i-edik sz´amjegye megegyezik az (N + 1 − i)-edik sz´amjegy´evel. P´eld´aul: 9876543456789. Egy sz´am sz´amjegyeit t´aroljuk az N elem˝ u X t¨ ombben. Egy egyjegy˝ u sz´am palindrom. Ha a k´et sz´els˝o sz´amjegy azonos, akkor vizsg´aljuk a sz´els˝ok n´elk¨ uli sz´amot.
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
18 / 32
Palindrom Rekurz´ıv megval´os´ıt´as Palindrom e(X , N) Ha N <= 1 akkor return(Igaz) K¨ ul¨onben Ha X [1] = X [N] akkor return(Palindrom e(X [2..N − 1], N − 2)) K¨ ul¨onben return(Hamis) El´agaz´as v´ege El´agaz´as v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
19 / 32
Hatv´anyoz´as Az a pozit´ıv eg´esz sz´am n-edik hatv´any´at kisz´am´ıthatjuk az al´abbi m´odon:
Algoritmus Hatv´any(a, n) temp := 1 Ciklus i := 1-t˝ol n-ig temp := temp ∗ a Ciklus v´ege return(temp) F¨ uggv´eny v´ege
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
20 / 32
Hatv´anyoz´as ¨ Otlet n
a =
an/2 · an/2 , ha n p´aros (n−1)/2 (n−1)/2 a ·a · a, ha n p´aratlan
Rekurz´ıv megval´os´ıt´as Hatv´any(a, n) Ha n = 0 akkor return(1) K¨ ul¨onben Ha n p´aros, akkor return(Hatv´any(a, n/2)*Hatv´any(a, n/2)) K¨ ul¨onben return(Hatv´any(a, (n − 1)/2)*Hatv´any(a, (n − 1)/2)*a) El´agaz´as v´ege El´agaz´as v´ege F¨ uggv´eny v´ege Sergy´ an (OE NIK)
AAO 11
2011. november 14.
21 / 32
Rekurz´ıv algoritmusok 1
Faktori´alis
2
Fibonacci sz´amok
3
Binomi´alis egy¨ utthat´ok
4
Ackermann f¨ uggv´eny
5
Egyszer˝ u feladatok
6
Keres´esek
7
Rekurz´ıv rendez´es
8
Hanoi tornyai
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
22 / 32
Line´aris keres´es ¨ Otlet a rekurz´ıv megval´os´ıt´ashoz Tegy¨ uk fel, hogy nem rendezett a sorozatunk Ha az X sorozat els˝ o eleme nem egyezik meg a keresett Y -nal, akkor h´ıvjuk meg ism´et a f¨ uggv´enyt, de m´ar csak a m´asodikt´ol az N-edik elemig terjed˝o r´eszsorozattal. E jel¨olje a vizsg´aland´ o r´eszsorozat els˝ o elem´enek index´et, U pedig az utols´o elem index´et A f¨ uggv´eny visszat´er´esi ´ert´eke legyen 0, ha Y nincs benne X -ben, egy´eb esetben pedig az X -beli indexe annak az elemnek, amely ´ert´eke egyenl˝o Y -nal
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
23 / 32
Line´aris keres´es Rekurz´ıv megval´os´ıt´as Keres´es(X , E , U, Y ) Ha E > U akkor return(0) K¨ ul¨onben Ha X [E ] = Y akkor return(E ) K¨ ul¨ onben return(Keres´es(X , E + 1, U, Y )) El´agaz´as v´ege El´agaz´as v´ege F¨ uggv´eny v´ege
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
24 / 32
Logaritmikus keres´es Ebben az esetben tegy¨ uk fel, hogy n¨ ovekv˝ o m´ odon rendezett a sorozatunk.
Rekurz´ıv megval´os´ıt´as Keres´es(X , E , U, Y ) Ha E > U akkor return(0) K¨ ul¨ onben
K := (E + U)/2 El´ agaz´ as X [K ] = Y eset´en return(K ) X [K ] < Y eset´en return(Keres´es(X , K + 1, U, Y )) X [K ] > Y eset´en return(Keres´es(X , E , K − 1, Y )) El´ agaz´ as v´ege El´ agaz´ as v´ege F¨ uggv´eny v´ege Sergy´ an (OE NIK)
AAO 11
2011. november 14.
25 / 32
Rekurz´ıv algoritmusok 1
Faktori´alis
2
Fibonacci sz´amok
3
Binomi´alis egy¨ utthat´ok
4
Ackermann f¨ uggv´eny
5
Egyszer˝ u feladatok
6
Keres´esek
7
Rekurz´ıv rendez´es
8
Hanoi tornyai
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
26 / 32
Quicksort Alap¨otlet V´alogassuk sz´et u ´gy a rendezend˝ o X t¨ omb elemeit, hogy az els˝o elemn´el kisebb ´ert´ek˝ u elemek az els˝ o elem el´e, a nagyobbak pedig m¨og´e ker¨ uljenek. V´egezz¨ uk el ezt a sz´etv´alogat´ast az els˝ o elemn´el kisebbekre, illetve nagyobbakra k¨ ul¨on-k¨ ul¨ on. Ez az elj´ar´as az Oszd meg ´es uralkodj! elvet haszn´alja.
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
27 / 32
Quicksort Sz´etv´alogat´o elj´ar´as Sz´etv´ alogat(X , E , U, K ) K := E ; L := U; A := X [K ] Ciklus am´ıg K < L Ciklus am´ıg (K < L) ´es (X [L] ≥ A) L := L − 1 Ciklus v´ege Ha K < L akkor X [K ] := X [L]; K := K + 1 Ciklus am´ıg (K < L) ´es (X [K ] ≤ A) K := K + 1 Ciklus v´ege Ha K < L akkor X [L] := X [K ]; L := L − 1 El´ agaz´ as v´ege El´ agaz´ as v´ege Ciklus v´ege X [K ] := A Elj´ ar´ as v´ege Sergy´ an (OE NIK)
AAO 11
2011. november 14.
28 / 32
Quicksort Rekurz´ıv h´ıv´as Quick(X , E , U) Sz´etv´alogat(X , E , U, K ) Ha K − E > 1 akkor Quick(X , E , K − 1) El´agaz´as v´ege Ha U − K > 1 akkor Quick(X , K + 1, U) El´agaz´as v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
29 / 32
Rekurz´ıv algoritmusok 1
Faktori´alis
2
Fibonacci sz´amok
3
Binomi´alis egy¨ utthat´ok
4
Ackermann f¨ uggv´eny
5
Egyszer˝ u feladatok
6
Keres´esek
7
Rekurz´ıv rendez´es
8
Hanoi tornyai
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
30 / 32
Hanoi tornyai Feladat Az egyik sz´els˝o r´ udr´ ol ´at kell pakolni a korongokat a m´asik sz´els˝o r´ udra. Seg´ıts´eg¨ ul a k¨oz´eps˝o r´ ud is haszn´alhat´ o. Egyszerre egyetlen korong mozgathat´ o. Csak fel¨ ul l´ev˝o korongot lehet mozgatni egyik r´ udr´ol a m´asikra. Egy korong nem rakhat´ o n´ala kisebb m´eret˝ u korongra.
Sergy´ an (OE NIK)
AAO 11
2011. november 14.
31 / 32
Hanoi tornyai Megold´asi o¨tlet Ha N − 1 korongot ´at tudn´ank mozgatni a k¨ oz´eps˝o r´ udra, akkor az N-edik korong ezut´an m´ar ´attehet˝ o a jobbsz´els˝ o r´ udra, majd a k¨oz´eps˝ o r´ udr´ol kell az N − 1 korongot a jobbsz´els˝ore tenni. Ez egy rekurz´ıv gondolat! A rekurzi´o biztos le´all, mert a legkisebb korong mindig fel¨ ul van, ´es b´arhonnan b´arhova mozgathat´ o.
Algoritmus Hanoi(N, Forras, Cel, Seged) Ha N > 0 akkor Hanoi(N − 1, Forras, Seged, Cel) Ki: N, Forras, Cel Hanoi(N − 1, Seged, Cel, Forras) El´agaz´as v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 11
2011. november 14.
32 / 32
