Tehetséggondozás az informatikában
A Leonardo-számok
Az előző szakaszban utaltunk már a Fibonacci-sorozat vegytisztán rekurzív
számításának lassúságára. Megalapozottabb kijelentéseket tehetünk, ha
megszámoljuk, hogy az n. tag kiszámításához hányszor hívtuk meg a rekurzív
függvényünket, mellesleg kiíratva azt is, hogy éppen hányadik Fibonacci-szám
értékét számítjuk (újra).
def fibonacci(n):
global stps
stps+= 1
if n==1 or n==2:
print('%d ' % (n))
return 1
else:
print('%d ' % (n), end='')
return fibonacci(n-2) + fibonacci(n-1)
stps= 0
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)))
print('A függvényhívások száma %d volt.' % (stps))
Az n. tag kiszámításához szükséges függvényhívások számát a következő
táblázatban foglaljuk össze:
n értéke |
lépésszám |
1 |
1 |
2 |
1 |
3 |
3 |
4 |
5 |
5 |
9 |
… |
… |
Kézenfekvő a szabály: az n. Fibonacci-szám kiszámításához eggyel több lépés
kell, mint az előző kettőéhez összesen (az n.-hez meghívjuk a függvényt,
majd az annyiszor hívja önmagát, mint ahányszor a megelőző két taghoz
együttesen kellett).
A fenti (lépés)számokat nevezik néha Leonardo-számoknak is (
A001595), a belőlük
alkotott sorozat egymást követő tagjainak hányadosa –éppen úgy, mint a
Fibonacci-sorozat esetén– (sqrt(5)+1)/2-höz tart. Ahogyan az oeis.org
oldalon is olvasható, a két sorozatot további tulajdonságok is
összekapcsolják. A lépésszámra vonatkozó összefüggés például úgy is
megfogalmazható, hogy az n-edrendű Fibonacci-fa csomópontjainak számát éppen
a megfelelő Leonardo-szám adja meg.
Végül hogy ebben az évben se maradjon ki, ezúttal is utalunk Edsger Wybe
Dijkstra egy jegyzetére a Fibonacci-, illetve a Leonardo-számok
kapcsolatáról:
EWD-0797.