i
i
“1298-Juvan-posplosena” — 2010/7/23 — 11:37 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 24 (1996/1997)
Številka 3
Strani 150–152
Martin Juvan:
POSPLOŠENA FIBONACCIJEVA ZAPOREDJA
Ključne besede: matematika, zaporedja, rekurzivne definicije, raču-
nalništvo.
Elektronska verzija: http://www.presek.si/24/1298-Juvan.pdf
c© 1996 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
Računalništvo I
POSPLOŠEN A FIBONACCIJEVA ZAPOREDJA
Gotovo poznate Fibo naccij evo zapo redj e. Njegovi z ačetni čl en i so 1, 1, 2,
3, 5, 8, 13, 21, .. . P ravijo , da je nanj prvi na let el Leonar do (Fibonacci)
iz Pi se (1180?-1250) , ko je opazoval spreminjanje št evila zajcev . Naj bo
dovolj govor ic. Bolj natančno to zapo redje opišemo takole. Začetna člena
It in h st a enaka ena : il = 1 in h = 1; n- ti člen zaporedj a Jn , kjer je
n > 2, paje enak vsoti dveh prejšnj ih členov : Jn = Jn- l+Jn- 2. Definiciji ,
kakršna je pravkar opisa na , prav imo rekurzi vna. P ri njej naslednj i čl en
izračunamo iz nekaj prejšnjih .
Če ohranimo rekurzivno zvezo, začetna člena pa polj ubno spreme-
nim o, dobimo posplo šetio Fibonaccijevo zaporedj e. Za začetna člena al
in a2 to rej vzamem o poljubn i št evili a in b: a l = a in a2 = b; nas lednji
člen i zaporedj a an pa so kot pr ej enaki vsoti dveh prejšnjih členov : an =
= an- l + an- 2. Za a = 1 in b = 4 tako dob im o zaporedj e z začetnimi
člen i 1,4, 5,9 , 14,23,37, . ..
Zapi šimo prvih nekaj členov posplošenega Fibonaccijevega zapo redj a:
a, b, a+ b, a+2b, 2a +3b, 3a+5b, 5a+8b, 8a+ 13b, . . . Hit ro opazimo , da
so koeficienti pred začetnima členoma a in b ravn o člen i običaj nega Fibo-
naceijevega zaporedj a . To seveda ni naklj učj e . Z matematično indukcijo
lahko dokažem o, da za n 2': 3 velj a
an = Jn-2 . a + Jn- l' b .
Sedaj pa je že čas , da si zastavimo nekaj vpraša nj . Pred časom j e
gospo d Kukrika v prilogi Programer revij e Monitor spraševal po t istih
posp lošenih Fibonaccij evih zaporedj ih s poziti vn im a z ačetnima č1enoma
a , b > O, ki vsebujejo število 1000000 in im ajo pri t em čim manjšo vsoto
a + b obeh začetnih členov.
Oglejmo si nalogo nekoliko natančnej e . Naprej bom o pokazali , da
naloga v zgornj i obliki pravzaprav nima prave rešitve, saj lahko poiščemo
posplošena Fib onaccijeva zaporedj a , ki vsebujejo število 1000000 , pr i ka-
t er ih j e vso ta a + b p olj ubno m aj hna . Takole sklepam o . Če n aj štev ilo
1000000 nastopi v zaporedj u , mo ra za neko naravn o šte vilo n velj at i
1000000 = an = Jn- 2 . a + Jn-l ' b .
Zaradi lažj ega računanj a vzemimo a = b. Pot em je
1000000 = Jn- 2 . a + Jn-l ' a = Jn . a .
I Računalništvo
Začetna člena a = b = 1 0~OnO O o to rej rešita nalogo. Ker pa Fibonaccij eva
št evila postanejo z rastočim n poljub no velika, lahko naredimo vsoto a+ b
polj ubno majhno .
Pogoje v nalogi moramo to rej nekoliko zaostriti. Zahtevajmo še, da
sta z ačetna člena a in b naravni števili. Naloga ima potem gotovo rešitev,
saj so možne vrednosti za a in b le št evila med 1 in 999999 . Pregledati
moram o to rej le končno mnogo možn osti. Ker paj e teh možnosti vend arl e
kar precej , preprost e analitične rešitve pa ni pri roki , si bomo pri reševanju
pom agali z računalnikom. Najprej opazimo , da iz dveh zaporednih členov
zaporedja lahko i z računamo vse prejšnj e člene . Če to rej izberemo število,
ki je v iskanem zaporedju pred številom 1000000 , v programu ga bomo
hr anili v spremenij ivki prej , lahko iz njega izračunamo a in b. Ker so
kandidati le št evila od 1 do 999999, teh pa ni preveč , jih preizkusim o s
spodnj im programom. Pri tem člene zaporedja hranimo v sp remenljivkah
t ipa longint , saj imajo običaj na cela št evilo premaj hen obseg .
{ dani člen zaporedja}
{ tr enutno naj m anjša vs o ta a + b }
{ izračun zače tnih členov zaporedja }
{ člen , ki j e v zaporedj u p red členom e1t }
{ členi zaporedja: a3=a2+al }
{ (trenu tno) najbolj ša reši t ev }
pro gram p osp losen i.Fib onacci;
{ Z vzvratnim računanjem poišče začetna člena pospl ošen ega }
{ Fibona ccij evega zaporedja. }
const
elt = 100 0000 j
var
p rej : longint :
a l ,a2,a3 : lon gint ;
min ,amin ,b min ,pmin : lon gin t ;
b egin
min := elt + lj
for prej:=elt-l d ownto 1 d o b egin
a3 := elt ; a 2 := prej; a l := a3 - a 2j
while a l > 0 d o begin
a3 := a2 j a2 := a l j a l := a3 -a2 j
e rrd: { while }
if a 2+a3 < min then b e gin { n ova n ajbolj ,ša I'ditev }
min := a2 + a 3j a m in := a2 j bmin .- a3j pmin ._ p rej ;
e n d ;
e u d , { for }
writeln('Vs ot a : ', m in :8 ,' a = ' ,a m in ,' b = ', b m in ,' ( pr edzadn j i e l en ' ,p min ,' ) ' ) j
read ln ;
e n d.
Kot rešit ev v nekaj seku ndah dobimo št evili a = 154 in b = 144 z
vsoto 298. Pr i te h začetnih člen ih ima zaporedj e naslednj e elemente:
154, 144, 298, 442, 740, 1182, 1922, 3104, 5026, 8130, 13156; 21286,
34442, 55728, 90170, 145898, 236068 , 381966, 618034, 1000000, . ..
Taka, ndcgo wao uspeIino r&Z. Kot neobmmo domab nalogo pa 
lrahh paskuhte ug'na%i Be nasledqja problem& 
.. Po@ tierti posplW FhnaEcjjevri zaporedji z nenegationima z h t -  
nima denoma a, 6 2 0, ki Lof 13. den vsebujeta -10 1996, za 
kateri je vmta a + b 
a) najrnaqjiia, 
b) na,jv&ja 
Naj opoz~rim, da .cmm pri tej ndogi rahwhik ne bo veliko pomqal. 
2. Ta ndog:a je bolj r h M k a .  ~a rmmate gornji program, potem 
vam ga ne; bo Wko epreme;ni+,i talro, d r  bo m&l v pxbpevku obra- 
vhamo nalogo aa &kilo 1998 namesto za gtevilo l(200000. fie pa ee 
vam zdi preMbI potem lahko p d u d t e  na&p ?&ti iie ea MO 
19961996. 
Martin Juvon