Tehetséggondozás az informatikában
A binomiális együtthatók
Nem meglepő, hogy a binomiális együtthatók (rekurzív) számolása éppen úgy
lassul, mint a Fibonacci-számoké: ebben az esetben is két korábbi érték
(újbóli és újbóli) kiszámítása teszi exponenciálissá a megoldás időigényét.
def sub(n, k):
global stps
stps+= 1
if k==0 or k==n:
print('(%d %d)' % (n, k))
return 1
else:
print('(%d %d)' % (n, k), end='')
return sub(n-1, k-1) + sub(n-1, k)
stps= 0
print('Meghatározzuk az n alatt k binomiális együttható értékét.')
n= int(input('Mennyi legyen a binomiális együtthatóban n értéke? '))
k= int(input('Mennyi legyen a binomiális együtthatóban k értéke? '))
print('%d alatt %d értéke %d' % (n, k, sub(n, k)))
print('A függvényhívások száma %d volt.' % (stps))
Néhány binomiális együttható kiszámításához a függvényhívások számát,
illetve a futásidő (másodpercben mért) értékeit a következő táblázatban
foglaljuk össze:
n értéke |
k értéke |
lépésszám |
futásidő |
10 |
5 |
503 |
<10-3 |
20 |
10 |
369511 |
0,2 |
30 |
15 |
310235039 |
112,0 |
40 |
20 |
? |
>86400 |
… |
… |
… |
… |
A lépésszámokat kézenfekvő módon a Pascal-háromszöghöz hasonló módon
határozhatjuk meg: a széleken ezúttal is 1-esek állnak, de a köztes
értékeket a fölöttük lévő két szám eggyel növelt összegeként kaphatjuk meg:
1
1 1
1 3 1
1 5 5 1
1 7 11 7 1
1 9 19 19 9 1
Az egyes sorokban álló számok összegét most 2
n helyett (a hasonló
növekedési ütemet mutató) 1, 2, 5, 12, 27, 58, … sorozat tagjai adják meg
(
A000325).