Tehetséggondozás az informatikában
A lépcsős feladat II.
Az előző megoldás az n-fokú lépcsőre vezető utak számát
visszavezette az (n-1)-fokú, valamint az (n-2)-fokú lépcsőre vezető
utak számára (azok összegére).
E
deduktív megközelítéssel szemben
induktív szemlélettel
is hozzáláthatunk a megfelelő program megírásához: ha már tudjuk, hogy a
lépcső aljától a k. lépcsőfokra elvezet egy út, akkor ebből
levezethetünk egy-egy utat a (k+1)., továbbá a (k+2). lépcsőfokra:
az előző úthoz értelemszerűen a következő, illetve az arra rákövetkező
lépcsőfok sorszámát kell hozzáilleszteni.
A következő példákban nem tároljuk, csak kiírjuk a képernyőre lehetséges
utakat; a kiírás mellett/helyett nyilván építhetnénk ezekből például egy
listát.
A függvény hívásakor azt kérjük, hogy a 0. lépcsőfoktól a 6.-ig vezető
utakat írja ki a program; a kiindulási lépéssort értelemszerűen az üres
string határozza meg.
def ms_2311_012_01a(k, n, path):
if k<=n:
path+= str(k)
if k<n:
ms_2311_012_01a(k+1, n, path)
ms_2311_012_01a(k+2, n, path)
else:
print(path, end=' ')
ms_2311_012_01a(0, 6, '')
print()
A kimenet:
0123456 012346 012356 012456 01246 013456 01346 01356 023456 02346 02356 02456 0246