Tehetséggondozás az informatikában
A Fibonacci-sorozat
A Fibonacci-sorozat (
A000045) a
legismertebb rekurzív sorozatok egyike; ha máskor nem,
ennek kapcsán érdemes lehet megismerkedni az egész számokból álló sorozatok
címben is hivatkozott enciklopédiájával (
oeis.org).
def fibonacci(n):
if n==1 or n==2:
return 1
else:
return fibonacci(n-2) + fibonacci(n-1)
print('Meghatározzuk a Fibonacci-sorozat n. tagját.')
n= int(input('Hányadik tag értékét számítsuk ki? '))
print('A(z) %d. Fibonacci-szám értéke %d' % (n, fibonacci(n)))
Első látásra meglepő, milyen lassan fut a program. Adott gépen, adott
körülmények között a következő futásidőket jegyeztük föl n faktoriálisának,
illetve az n. Fibonacci-számnak a kiszámítása után (értékek másodpercben,
de ennek nyilván nincs jelentősége):
n értéke |
faktoriális |
Fibonacci |
10 |
<10-3 |
0,0002 |
20 |
<10-3 |
0,0100 |
30 |
<10-3 |
0,4000 |
40 |
<10-3 |
48,0000 |
50 |
<10-3 |
6007,0000 |
Önmagában a számított értékek nagyságrendje egyáltalán nem indokolja a mért
értékek rohamos növekedését: az n. Fibonacci-szám nagyjából 1,6
n
körül van – ennél a faktoriálisok lényegesen gyorsabban nőnek.
A lassulás oka viszonylag könnyen megsejthető, illetve megérthető: az n.
Fibonacci-szám kiszámításához két korábbi Fibonacci-számot határoz meg a
program, és mivel a korábban kiszámolt számokat
nem tároljuk,
azokhoz két-két további számítást (azaz további négy függvényhívást) kell
megvalósítani, és így tovább, (majdnem) mindig kétszerezve: a lépésszám n
értékétől exponenciálisan függ – azért nem mondhatunk állandó kétszerezést,
illetve az ennek megfelelő 2
n-t, mert egyes ágakon hamarabb
elérünk a kezdőtaghoz:
10┬8┬6┬4┬2
│ │ │ └3┬1
│ │ │ └2
│ │ └5┬3┬1
│ │ │ └2
│ │ └4┬2
│ │ └3┬1
│ │ └2
│ └7┬5┬3┬1
│ │ │ └2
│ │ └4┬2
│ │ └3┬1
│ │ └2
│ └6┬4┬2
│ │ └3┬1
│ │ └2
│ └5┬3┬1
│ │ └2
│ └4┬2
│ └3┬1
│ └2
└9┬7┬5┬3┬1
│ │ │ └2
│ │ └4┬2
│ │ └3┬1
│ │ └2
│ └6┬4┬2
│ │ └3┬1
│ │ └2
│ └5┬3┬1
│ │ └2
│ └4┬2
│ └3┬1
│ └2
└8┬6┬4┬2
│ │ └3┬1
│ │ └2
│ └5┬3┬1
│ │ └2
│ └4┬2
│ └3┬1
│ └2
└7┬5┬3┬1
│ │ └2
│ └4┬2
│ └3┬1
│ └2
└6┬4┬2
│ └3┬1
│ └2
└5┬3┬1
│ └2
└4┬2
└3┬1
└2
Ha valaki fogékony az effélére, örömmel fedezheti fel a fenti ábrában sok
fraktálalakzat jellegzetes önhasonlóságát…