Tehetséggondozás az informatikában
A lépcsős feladat I.
Az előző szakaszok után joggal vetődik fel a kérdés: mi értelme lehet ilyen
lassú rekurzív függvényeket írni, ha sokkal gyorsabban is megkaphatjuk a
kívánt számeredményeket?
Ahogyan korábban már utaltunk rá, a lassulás végső oka egy exponenciálisan
szélesedő fa bejárása – ennek megfelelően például nincs jobb megoldás akkor,
ha valamiért ténylegesen be kell járnunk a fát. Kézenfekvő módon lehet
szükség erre, ha olyan eseteket kell felsorolnunk, amelyek egy efféle fa
levelein vagy csomópontjain helyezhetőek el.
Ilyen feladat szerepel például a Mozaik Kiadó 11.-es matematikatankönyvének
12. oldalán: hányféleképpen mehetünk fel –mondjuk– egy hatfokú lépcsőn, ha
egyesével vagy kettesével szedjük a fokokat?
Ügyes diák megfelelő előkészítés után megtalálhatja, értelmes diák hamar
megértheti a Fibonacci-számokról szóló választ – az összes eset módszeres
felsorolása azonban egyáltalán nem tűnik könnyűnek.
Lássunk elsőként egy olyan megoldást erre, amely egy listát épít a megtalált
bejárási lehetőségekből. Az algoritmus lényegében csak a lehetséges esetek
számáról szóló állítást, illetve annak bizonyítását formalizálja: egy
lépcsőhöz egyetlen lehetséges út tartozik, két lépcsőhöz a megadott kettő;
minden más esetben tekintsük az eggyel korábbi fokra vezető utak egy
lépéssel megtoldott, továbbá a kettővel korábbi fokra vezető utak kettős
lépéssel megtoldott meghosszabbítását.
def ms_2311_012_01(n):
if n==1:
return ['1']
elif n==2:
return ['11', '2']
else:
l1= ms_2311_012_01(n-1)
for i in range(len(l1)):
l1[i]+= '1'
l2= ms_2311_012_01(n-2)
for i in range(len(l2)):
l2[i]+= '2'
return l1+l2
print(ms_2311_012_01(6))
Az eredményül kapott lista:
['111111', '21111', '12111', '11211', '2211', '11121', '2121', '1221', '11112', '2112', '1212', '1122', '222']