ISSN 0351-6652 Letnik 24 (1996/1997) Številka 6 Strani 334-337 Martin Juvan in Katarina Kokalovic: ŠE ENKRAT O FIBONACCIJEVIH ZAPOREDJIH Ključne besede: računalništvo. Elektronska verzija: http://www.presek.si/24/1320-Juvan-Kokalovic.p df © 1997 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo ŠE ENKRAT O FIBONACCIJEVIH ZAPOREDJIH Presek je o Fibonaccijevih zaporedjih v tem letniku že pisal (glej Posplošena Fibonaccijeva zaporedja, Presek 24 (96/97), št. 3, str. 150-152). V prispevku smo obravnavali posplošena Fibonaccijeva zaporedja, to je zaporedja, določena z začetnima Členoma a\ = a in a-i = b ter rekurzivno zvezo Ufc+i = a.k + dk-1 > & > 2. Pri tem smo se omejili na zaporedja s pozitivnima celošte v ilskfrna začetnima členoma a in b. Med takimi zaporedji smo iskali tisto, ki vsebuje število 1000000, hkrati pa je zanj vsota a + b najmanjša. Nalogo smo rešili z "metodo grobe sile", Z rekurzivno zvezo lahko iz dveh zaporednih členov zaporedja izračunamo naslednje, pa tudi prejšnje člene. Ker je bilo Število 1000000 v zaporedju, smo kar preizkusili vse kandidate za prejšnji člen, to so bila Števila od 1 do 999999, in z računanjem nazaj izračunali začetna člena. Tako smo v nekaj sekundah dobili odgovor a ~ 154 in b = 144. Opisana rešitev je bila primerna za zastavljeno nalogo, saj jo je mogoče hitro domisliti in sprogramirati, pa tudi možnosti, da bi se zmotili, ni prav veliko. V nadaljevanju prispevka pa bomo pokazali, kako z nekaj razmišljanja poiščemo še bistveno boljšo rešitev, tako, ki jo bo mogoče uporabiti tudi za računanje s svinčnikom in papirjem (no, tudi žepnega računala se ne bomo branili). Označimo z f\ = /2 = 1, /3 — 2,/4 = 3,... običajna Fibonaccijeva števila. V že omenjenem prispevku smo ugotovili, da za člene posplošenega Fibonaccijevega zaporedja velja — fk-2 ■ a + /t-i ■ b , pri čemer vzamemo /_ 1 = i in /b = 0. Podobno lahko zapišemo tudi formulo za predhodne člene. Recimo, da poznamo člena o.ti in £3rl —.j. Potem za i > 0 velja ««-> (-l)'/;-i ■ an - (-1)'/» ' «n-i ■ (1) Da gornja formula res velja, se prepričamo z matematično indukcijo, seveda pa nama lahko verjamete tudi na besedo. Poglejmo primer računanja predhodnih členov. Recimo, daje v zaporedju število 100, člen pred njim pa je enak 62. Potem z računanjem nazaj, pri tem uporabljamo rekurzivno zvezo an-i = (^-¡+2 - dobimo 100, 62, 38, 24, 14, 10, 4, 6, -2, 8, -10, (2) Seveda nas zaporedje predhodnih členov zanima le toliko časa, dokler so vsi njegovi členi pozitivni. In koliko začetnih členov je pozitivnih? V zgornjem primeru jih je 8. V splošnem pa razmišljajmo takole. Pri računanju predhodnih členov so ti pozitivni toliko časa, dokler je novi predhodni člen strogo manjši od predhodnega člena, izračunanega na prejšnjem koraku. Če je novi predhodni člen večji ali enak prejšnjemu, bo naslednji izračunani predhodni člen enak 0 ali manjši od 0. To pomeni, da se ustavimo pri prvem indeksu i, za katerega velja an-i > a„_i+i . (3) Tedaj ima zaporedje predhodnih členov na začetku natanko i+1 pozitivnih členov. Če v (3) upoštevamo zvezo (1). dobimo (-i)Vi-i ■ o« - (-1)7* - «»-i > (-ir7.'~2 ■ on - (-i rv.-i • , kar nam po preoblikovanju da (-l)7i-a„ > Hl)V<+i an-l - Pogoj, ki nas pri računanju predhodnih Členov zaustavi, je tako (_lfJL>H)i5=i, (4) /i+l an Pomembni so torej količniki zaporednih Fibonaccijevih števil. Zapiširno jih prvih nekaj: 0 1 1 2 3 5 8 13 21 34 55 T' 1' 2' 3' 5' 8' 13' 21' 34' 55' 89' Pokažemo lahko, da se količniki bližajo razmerju zlatega reza, to je vrednosti 0. Prikažimo prvih nekaj količnikov in pripadajoče intervale še na številski premici: 3 6 6 4 2 K-H-HM-H-H n 1 3 2 1 U 2 3 1 Številke nad intervali povedo, s koliko pozitivnimi členi se začne zaporedje predhodnih členov, če je količnik med an-i in «a na izbranem intervalu. Na primer, če c"na~'' 6 [§, §), potem dobimo z računanjem nazaj poieg an in an_i še štiri pozitivne Člene, preden naletimo na prvi nepozitivni člen. Poglejmo še primer (2). Tu je ^^ — Količnik tako leži med jf = || = 0.619 in £ = | = 0.625. Pogoj (4) ni izpolnjen za noben sod indeks i, pri lihih pa ne velja za t = 1,3 in 5. Najmanjši i, za katerega je izpolnjen, je tako 7, zaporedje pa ima na začetku 8 pozitivnih členov. Napoved iz pogoja (4) se torej ujema s številom izračunanih pozitivnih členov v (2). Pričakujemo lahko, da bo vsota zadnjih dveh pozitivnih členov (torej vsota začetnih členov posplošenega Fibonaecijevega zaporedja iz naše naloge) tem manjša, čim več pozitivnih členov bomo naračunali iz an in To predvidevanje potrdi tudi račun. Ce je 1 na intervalu med in pri čemer je interval pri jf^ odprt, pri ^j1- pa zaprt, z računanjem nazaj dobimo (vključno z an in o„_i) i pozitivnih členov. Ce je količnik enak sta zadnja pozitivna člena enaka, njuna vsota pa je Ko pa se s količnikom bližamo drugi meji intervala, številu , se predzadnji pozitivni člen bliža 0, zadnji pa gre proti Vsota obeh se tako od spodaj približuje ■ Za majhne vrednosti indeksa ? so gornje ugotovitve prikazane tudi v spodnji tabeli (pri tem se vrednostim v zadnjem stolpcu lahko le poljubno približamo, ne moremo pa jih doseči); število pozitivnih h interval za vrednost 0 + b členov i količnik najmanjša največja 2 i 2a„ 00 3 2 Ml an On 4 3 ti, i) 3q. 3 «B 5 5 (1 21 V 2 ' sJ Za. n 2 6 S Ls> 3) aj, 4 iLa. 3 7 13 (3 Al U' laJ '¿EJL 13 ¡Lil 5 Še posebej zanimiva je izbira = ip. Tedaj je zaporedje predhodnih Členov sestavljeno iz samih pozitivnih števil, ki padajo proti 0, a te vrednosti nikoli ne dosežejo. Seveda v tem primeru vsaj eden od an ali a„_i ni celo število, saj

0; a2 := an; al := trunc(fi*an); i := 2; { prvi kandidat } write{'an = ',a2,' an-1 = ',al); while al