Rendez´esek 8. el˝ oad´as Sergy´an Szabolcs
[email protected] ´ Obudai Egyetem Neumann J´ anos Informatikai Kar
2011. okt´ ober 24.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
1/1
Felhaszn´alt irodalom Szl´avi P´eter, Zsak´o L´aszl´ o: M´ odszeres programoz´as: Programoz´asi t´etelek (Mikrol´ogia 19). ELTE TTK, 2002
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
2/1
Rendez´esi algoritmusok A rendez´esi algoritmusok alapfeladata egy N elem˝ u sorozat nagys´ag szerinti sorba rendez´ese. Sz¨ uks´eges, hogy a sorozat elemei k¨ oz¨ ott ´ertelmezhet˝o legyen a < m˝ uvelet. A rendez´eseket ´altal´aban helyben az eredeti sorozatban hajtjuk v´egre, ´ıgy a rendezetlen sorozatot elvesz´ıtj¨ uk. 5
Sergy´ an (OE NIK)
3
9
1
7
→
AAO 08
1
3
5
7
9
2011. okt´ ober 24.
3/1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
4/1
Egyszer˝u cser´es rendez´es Alap¨otlet Hasonl´ıtsuk ¨ossze a sorozat els˝ o elem´et az ¨ osszes ˝ot k¨ovet˝ovel. Ha egy elem kisebb mint az els˝ o, akkor cser´elj¨ uk meg ˝oket. ´Igy a sorozat els˝o hely´ere a megfelel˝ o (azaz legkisebb) elem ker¨ ul. Ezt k¨ovet˝oen ugyanezt tegy¨ uk meg a m´asodik elemmel, majd az ¨osszes k¨ovetkez˝ovel.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
5/1
Egyszer˝u cser´es rendez´es
Algoritmus
P´elda
Rendez´es(N,X ) Ciklus i := 1-t˝ol N − 1-ig Ciklus j := i + 1-t˝ol N-ig Ha X [i] > X [j] akkor Csere(X [i],X [j]) El´agaz´as v´ege Ciklus v´ege Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 08
i =1
→
i =2
→
i =3
→
i =4
→
5 3 3 1 1 1 1 1 1 1 1 1 1 1
3 5 5 5 5 5 5 3 3 3 3 3 3 3
9 9 9 9 9 9 9 9 9 9 5 5 5 5
1 1 1 3 3 3 3 5 5 5 9 9 9 7
2011. okt´ ober 24.
7 7 7 7 7 7 7 7 7 7 7 7 7 9
6/1
Csere megval´os´ıt´asa K´et sorozatbeli elem megcser´el´es´ehez sz¨ uks´eges egy plusz elem a sorozaton k´ıv¨ ul, melynek t´ıpusa azonos a sorozat elemeinek t´ıpus´aval.
Algoritmus Csere(X [i],X [j]) TEMP := X [i] X [i] := X [j] X [j] := TEMP Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
7/1
Egyszer˝u cser´es rendez´es Hat´ekonys´ag Helyfoglal´as: N + 1 Hasonl´ıt´asok sz´ama:
N(N − 1) 2
Mozgat´asok sz´ama: Legal´abb 0, legfeljebb 3 ·
Sergy´ an (OE NIK)
AAO 08
N(N − 1) 2
2011. okt´ ober 24.
8/1
Rendez´esek o¨sszehasonl´ıt´asa 30 elem˝ u sorozatokat hasonl´ıtottunk ¨ ossze A majdnem rendezett sorozatban k´et elem nem volt a hely´en. A ford´ıtva rendezett sorozat cs¨ okken˝ o sorrendben volt rendezett. A v´eletlen sorozat az els˝ o 30 pozit´ıv eg´esz sz´am egy v´eletlen permut´aci´oja volt.
Egyszer˝ u cser´ es
Sergy´ an (OE NIK)
Majdnem rendezett sorozat Hason. Csere Mozg. 435 29 87
Ford´ıtva rendezett sorozat Hason. Csere Mozg. 435 435 1305
AAO 08
V´ eletlen sorozat Hason. Csere Mozg. 435 231 693
2011. okt´ ober 24.
9/1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
10 / 1
Minimumkiv´alaszt´asos rendez´es Alap¨otlet Az Egyszer˝ u cser´es rendez´es hib´aja, hogy ´altal´aban t´ ul sok cser´et hajt v´egre annak ´erdek´eben, hogy az elemek a megfelel˝o helyre ker¨ uljenek. Ezen jav´ıthatunk, ha az aktu´alis elemet a m¨ og¨ otte ´all´ok minimum´aval cser´elj¨ uk fel, ha egy´altal´an kell cser´elni.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
11 / 1
Minimumkiv´alaszt´asos rendez´es
Algoritmus
P´elda
Rendez´es(N,X ) Ciklus i := 1-t˝ol N − 1-ig MIN := i Ciklus j := i + 1-t˝ol N-ig Ha X [MIN] > X [j] akkor MIN := j El´agaz´as v´ege Ciklus v´ege Csere(X [i],X [MIN]) Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 08
i i i i
=1 =2 =3 =4
→ → → →
5 1 1 1 1
3 3 3 3 3
9 9 9 5 5
1 5 5 9 7
2011. okt´ ober 24.
7 7 7 7 9
12 / 1
Minimumkiv´alaszt´asos rendez´es Hat´ekonys´ag Helyfoglal´as: N + 1 N(N − 1) 2 Mozgat´asok sz´ama: 3 · (N − 1) Hasonl´ıt´asok sz´ama:
A mozgat´asok sz´ama ak´ar t¨ obb is lehet, mint az Egyszer˝ u cser´es rendez´esn´el. Ennek oka, hogy a k¨ uls˝ o ciklusban mindenk´epp cser´el¨ unk, annak ´erdek´eben, hogy ne kelljen mindig egy ¨ osszehasonl´ıt´ast is elv´egezni.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
13 / 1
Rendez´esek o¨sszehasonl´ıt´asa
Egyszer˝ u cser´ es Minimumkiv´ alaszt´ asos
Sergy´ an (OE NIK)
Majdnem rendezett sorozat Hason. Csere Mozg. 435 29 87 435 29 87
Ford´ıtva rendezett sorozat Hason. Csere Mozg. 435 435 1305 435 29 87
AAO 08
V´ eletlen sorozat Hason. Csere Mozg. 435 231 693 435 29 87
2011. okt´ ober 24.
14 / 1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
15 / 1
Bubor´ekos rendez´es Alap¨otlet ¨ Osszehasonl´ ıtjuk egym´assal a szomsz´edos elemeket, s ha a sorrendj¨ uk nem j´o, akkor cser´elj¨ uk meg ˝ oket. A szomsz´edok cser´eje miatt el˝ osz¨ or a legnagyobb elem fog a hely´ere ker¨ ulni, majd ezt k¨ovet˝ oen a m´asodik legnagyobb, ´es ´ıgy tov´abb. Az algoritmusban az elemek u ´gy ker¨ ulnek a sorozatbeli hely¨ ukre a legnagyobbt´ol kezdve, mint a felfel´e sz´all´ o bubor´ekok.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
16 / 1
Bubor´ekos rendez´es
Algoritmus
P´elda
Rendez´es(N,X ) Ciklus i := N-t˝ol 2-ig −1-es´evel Ciklus j := 1-t˝ol i − 1-ig Ha X [j] > X [j + 1] akkor Csere(X [j],X [j + 1]) El´agaz´as v´ege Ciklus v´ege Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 08
i =5
→
i =4
→
i =3
→
i =2
→
5 3 3 3 3 3 3 3 3 3 1 1 1
3 5 5 5 5 5 5 1 1 1 3 3 3
9 9 9 1 1 1 1 5 5 5 5 5 5
1 1 1 9 7 7 7 7 7 7 7 7 7
2011. okt´ ober 24.
7 7 7 7 9 9 9 9 9 9 9 9 9
17 / 1
Bubor´ekos rendez´es Hat´ekonys´ag Helyfoglal´as: N + 1 Hasonl´ıt´asok sz´ama:
N(N − 1) 2
Mozgat´asok sz´ama: Legal´abb 0, legfeljebb 3 ·
Sergy´ an (OE NIK)
AAO 08
N(N − 1) 2
2011. okt´ ober 24.
18 / 1
Rendez´esek o¨sszehasonl´ıt´asa
Egyszer˝ u cser´ es Minimumkiv´ alaszt´ asos Bubor´ ekos
Sergy´ an (OE NIK)
Majdnem rendezett sorozat Hason. Csere Mozg. 435 29 87 435 29 87 435 29 87
Ford´ıtva rendezett sorozat Hason. Csere Mozg. 435 435 1305 435 29 87 435 435 1305
AAO 08
V´ eletlen sorozat Hason. Csere Mozg. 435 231 693 435 29 87 435 231 693
2011. okt´ ober 24.
19 / 1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
20 / 1
Jav´ıtott bubor´ekos rendez´es Alap¨otlet Ha a Bubor´ekos rendez´es bels˝ o ciklus´aban egy´altal´an nincs m´ar csere, akkor az algoritmust k´ar folytatni. Ha volt csere, de az utols´ o csere p´eld´aul a sorozat k¨ozep´en´el volt, akkor az utols´o csere hely´et˝ ol a sorozat v´eg´eig a sorozat m´ar rendezett, teh´at k´ar azzal a r´esszel foglalkozni.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
21 / 1
Jav´ıtott bubor´ekos rendez´es
Algoritmus
P´elda
Rendez´es(N,X ) i := N Ciklus am´ıg i ≥ 2 CS := 0 Ciklus j := 1-t˝ol i − 1-ig Ha X [j] > X [j + 1] akkor Csere(X [j],X [j + 1]) CS := j El´agaz´as v´ege Ciklus v´ege i := CS Ciklus v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 08
i =5
→
i =4
→
i =2
→
5 3 3 3 3 3 3 3 3 3 1
3 5 5 5 5 5 5 1 1 1 3
9 9 9 1 1 1 1 5 5 5 5
1 1 1 9 7 7 7 7 7 7 7
7 7 7 7 9 9 9 9 9 9 9
2011. okt´ ober 24.
22 / 1
Jav´ıtott bubor´ekos rendez´es Helyfoglal´as: N + 1 N(N − 1) 2 N(N − 1) Mozgat´asok sz´ama: Legal´abb 0, legfeljebb 3 · 2 Hasonl´ıt´asok sz´ama: Legal´abb N − 1, legfeljebb
A Bubor´ekos rendez´eshez k´epest szignifik´ans javul´as az ´atlagos v´egrehajt´asi id˝oben van.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
23 / 1
Rendez´esek o¨sszehasonl´ıt´asa
Egyszer˝ u cser´ es Minimumkiv´ alaszt´ asos Bubor´ ekos Jav´ıtott bubor´ ekos
Sergy´ an (OE NIK)
Majdnem rendezett sorozat Hason. Csere Mozg. 435 29 87 435 29 87 435 29 87 254 29 87
Ford´ıtva rendezett sorozat Hason. Csere Mozg. 435 435 1305 435 29 87 435 435 1305 435 435 1305
AAO 08
V´ eletlen sorozat Hason. Csere Mozg. 435 231 693 435 29 87 435 231 693 429 231 693
2011. okt´ ober 24.
24 / 1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
25 / 1
Beilleszt´eses rendez´es Alap¨otlet Egy elem ¨onmag´aban rendezett. A m´asodik elemet tegy¨ uk a hely´ere. A harmadikat ´es az ¨ osszes k¨ ovetkez˝ ot tegy¨ uk a hely´ere.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
26 / 1
Beilleszt´eses rendez´es
Algoritmus
P´elda
Rendez´es(N,X ) Ciklus i := 2-t˝ ol N-ig j := i − 1 Ciklus am´ıg j > 0 ´es X [j] > X [j + 1] Csere(X [j],X [j + 1]) j := j − 1 Ciklus v´ege Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 08
i =2
→
i =3 i =4
→ →
i =5
→
5 3 3 3 3 3 1 1 1
3 5 5 5 5 1 3 3 3
9 9 9 9 1 5 5 5 5
1 1 1 1 9 9 9 9 7
2011. okt´ ober 24.
7 7 7 7 7 7 7 7 9
27 / 1
Beilleszt´eses rendez´es Hat´ekonys´ag Helyfoglal´as: N + 1 N(N − 1) 2 N(N − 1) Mozgat´asok sz´ama: Legal´abb 0, legfeljebb 3 · 2 Hasonl´ıt´asok sz´ama: Legal´abb N − 1, legfeljebb
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
28 / 1
Rendez´esek o¨sszehasonl´ıt´asa
Egyszer˝ u cser´ es Minimumkiv´ alaszt´ asos Bubor´ ekos Jav´ıtott bubor´ ekos Beilleszt´ eses rendez´ es
Sergy´ an (OE NIK)
Majdnem rendezett sorozat Hason. Csere Mozg. 435 29 87 435 29 87 435 29 87 254 29 87 58 29 87
Ford´ıtva rendezett sorozat Hason. Csere Mozg. 435 435 1305 435 29 87 435 435 1305 435 435 1305 435 435 1305
AAO 08
V´ eletlen sorozat Hason. Csere Mozg. 435 231 693 435 29 87 435 231 693 429 231 693 260 231 693
2011. okt´ ober 24.
29 / 1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
30 / 1
Jav´ıtott beilleszt´eses rendez´es Alap¨otlet A Beilleszt´eses rendez´esben t´ ul sok cser´et hajtunk v´egre annak ´erdek´eben, hogy egy elem a hely´ere ker¨ ulj¨ on. Hasznosabb lenne, ha a sz¨ uks´eges elemeket h´atr´abb toln´ank eggyel.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
31 / 1
Jav´ıtott beilleszt´eses rendez´es
Algoritmus
P´elda
Rendez´es(N,X ) Ciklus i := 2-t˝ol N-ig j := i − 1 Y := X [i] Ciklus am´ıg j > 0 ´es X [j] > Y X [j + 1] := X [j] j := j − 1 Ciklus v´ege X [j + 1] := Y Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 08
i =2
→
i =3 i =4
→ →
i =5
→
5 5 3 3 3 3 3 1 1 1
3 5 5 5 5 5 3 3 3 3
9 9 9 9 9 5 5 5 5 5
1 1 1 1 9 9 9 9 9 7
2011. okt´ ober 24.
7 7 7 7 7 7 7 7 9 9
32 / 1
Jav´ıtott beilleszt´eses rendez´es Hat´ekonys´ag Helyfoglal´as: N + 1 N(N − 1) 2 Mozgat´asok sz´ama: Legal´abb 2 · (N − 1), legfeljebb N(N − 1) 2 · (N − 1) + 2 Hasonl´ıt´asok sz´ama: Legal´abb N − 1, legfeljebb
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
33 / 1
Rendez´esek o¨sszehasonl´ıt´asa
Egyszer˝ u cser´ es Minimumkiv´ alaszt´ asos Bubor´ ekos Jav´ıtott bubor´ ekos Beilleszt´ eses rendez´ es Jav´ıtott beilleszt´ eses
Sergy´ an (OE NIK)
Majdnem rendezett sorozat Hason. Csere Mozg. 435 29 87 435 29 87 435 29 87 254 29 87 58 29 87 58 87
Ford´ıtva rendezett sorozat Hason. Csere Mozg. 435 435 1305 435 29 87 435 435 1305 435 435 1305 435 435 1305 435 493
AAO 08
V´ eletlen sorozat Hason. Csere Mozg. 435 231 693 435 29 87 435 231 693 429 231 693 260 231 693 260 289
2011. okt´ ober 24.
34 / 1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
35 / 1
Sz´etoszt´o rendez´es Alap¨otlet Feltessz¨ uk, hogy a rendezend˝ o sorozat elemei strukt´ ur´ak, amelyeknek van olyan kulcsmez˝oje, amely 1 ´es N k¨ oz¨ otti term´eszetes sz´am lehet, ´es nincs k´et azonos kulcs´ u elem. A kulcsmez˝o egy´ertelm˝ uen meghat´arozza azt a helyet, ahova az adott elemnek ker¨ ulnie kell. Nincsen sz¨ uks´eg hasonl´ıt´asra. Kell egy m´asik t¨omb, ahova az eredm´eny ker¨ ul.
Strukt´ura t´ıpus Egy v´altoz´oban t¨obb, ak´ar k¨ ul¨ onb¨ oz˝ o t´ıpus´ u v´altoz´ot z´arhatunk egybe. P´eld´aul: X .sorszam, X .eloado, X .cim, X .szerzo Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
36 / 1
Sz´etoszt´o rendez´es Algoritmus Rendez´es(N,X ,Y ) Ciklus i := 1-t˝ol N-ig Y [X [i].kulcs] := X [i] Ciklus v´ege Elj´ar´as v´ege
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
37 / 1
Sz´etoszt´o rendez´es Hat´ekonys´ag Helyfoglal´as: 2 · N Hasonl´ıt´asok sz´ama: 0 Mozgat´asok sz´ama: N Kulcsmez˝oindexel´es: N
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
38 / 1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
39 / 1
Sz´aml´alva sz´etoszt´o rendez´es Alap¨otlet A kulcsmez˝o indexe nem csak 1 ´es N k¨ oz¨ otti ´ert´ek lehet, hanem N-n´el nagyobb ´ert´eket is felvehet. Jel¨ olj¨ uk a lehet˝o legnagyobb elemet M-mel. T¨obb elemnek is lehet ugyanolyan ´ert´ek˝ u a kulcsmez˝oje. El˝osz¨or megsz´aml´aljuk, hogy melyik kulcs´ert´ekb˝ ol h´any darab van. M´asodj´ara meghat´arozzuk minden kulcs´ert´ekhez a n´ala nemnagyobb kulcs´ert´ek˝ u elemek sz´am´at. Harmadj´ara m´ar minden elemet a hely´ere helyezhet¨ unk.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
40 / 1
Sz´aml´alva sz´etoszt´o rendez´es Algoritmus Rendez´es(N,X ,Y ) DB[1..M] := [0, . . . , 0] Ciklus i := 1-t˝ol N-ig DB [X [i].kulcs] := DB [X [i].kulcs] + 1 Ciklus v´ege Ciklus j := 2-t˝ol M-ig DB[j] := DB[j] + DB[j − 1] Ciklus v´ege Ciklus i := 1-t˝ol N-ig Y [DB [X [i].kulcs]] := X [i] DB [X [i].kulcs] := DB [X [i].kulcs] − 1 Ciklus v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
41 / 1
Sz´aml´alva sz´etoszt´o rendez´es Hat´ekonys´ag Helyfoglal´as: 2 · N + M · ε, ahol ε egy eg´esz t´ıpus´ u v´altoz´o mem´oriabeli m´erete. ε j´ oval kisebb, mint egy ¨ osszetett t´ıpus´ u t¨ombelem m´erete. Hasonl´ıt´asok sz´ama: 0 Mozgat´asok sz´ama: N Kulcsmez˝oindexel´es: 5 · N
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
42 / 1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
43 / 1
Sz´aml´al´o rendez´es Alap¨otlet Sz´amoljuk meg, hogy egy elemn´el h´any kisebb elem van az eg´esz sorozatban, illetve h´any vele egyenl˝ o van az ˝ ot megel˝oz˝o index˝ uek k¨oz¨ott. Az ´ıgy kapott sz´am meghat´arozza, hogy melyik elemnek h´anyadik helyen kell ´allnia a rendezett sorozatban.
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
44 / 1
Sz´aml´al´o rendez´es Algoritmus Rendez´es(N,X ,Y ) DB[1..N] := [1, . . . , 1] Ciklus i := 1-t˝ol N − 1-ig Ciklus j := i + 1-t˝ol N-ig Ha X [i] > X [j] akkor DB[i] := DB[i] + 1 k¨ ul¨onben DB[j] := DB[j] + 1 El´agaz´as v´ege Ciklus v´ege Ciklus v´ege Ciklus i := 1-t˝ol N-ig Y [DB[i]] := X [i] Ciklus v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
45 / 1
Sz´aml´al´o rendez´es Hat´ekonys´ag Helyfoglal´as: 2 · N + N · ε N(N − 1) Hasonl´ıt´asok sz´ama: 2 Mozgat´asok sz´ama: N 2-szeres indexel´es: N
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
46 / 1
Rendez´esek
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
47 / 1
Rendez´es Shell m´odszerrel Alap¨otlet Hasonl´ıtsuk el˝osz¨or ¨ossze az egym´ast´ ol t´avoli elemeket, ´es ha kell cser´elj¨ uk meg ˝oket ´Igy az egyes elemek gyorsan k¨ ozel ker¨ ulnek a v´egleges hely¨ ukh¨oz
Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
48 / 1
Rendez´es Shell m´odszerrel Algoritmus Rendez´es(N,X ) L := L0 Ciklus am´ıg L ≥ 1 Ciklus K := L + 1-t´ ol 2L-ig Ciklus i := K -t˝ ol N-ig L-es´evel j := i − L Y := X [i] Ciklus am´ıg j > 0 ´es X [j] > Y X [j + L] := X [j] j := j − L Ciklus v´ege X [j + L] := Y Ciklus v´ege Ciklus v´ege L :=K¨ ovetkez˝ o(L) Ciklus v´ege Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
49 / 1
Rendez´es Shell m´odszerrel L0 nem l´epheti t´ ul N-t A K¨ovetkez˝o(L) f¨ uggv´eny meghat´aroz´as´ara p´ar p´elda:
2k − 1 alak´u eset K¨ ovetkez˝o(L) K¨ovetkez˝o:=(L + 1)/2 − 1 Elj´ar´as v´ege
Fibonacci sz´am alak´u eset K¨ ovetkez˝o(L) L2 := L − L1 L := L1 L1 := L2 K¨ovetkez˝o:=L1 Elj´ar´as v´ege Sergy´ an (OE NIK)
AAO 08
2011. okt´ ober 24.
50 / 1
