Tehetséggondozás az informatikában
A lépcsős feladat III.
Megfogalmazhattuk volna úgy is a lépcsős feladatot, hogy írjuk fel a 6-ot
egymást követő 1-esek és/vagy 2-esek összegeként (megkülönböztetve azokat az
eseteket is, amikor csak a tagok sorrendje különbözik).
A fenti megközelítés szerint célszerűbb lehet az utakat az egymást követően
átlépett fokok számával megadni; erre mutatnak példát az alábbi programok.
Első körben különböztessük meg a kétféle lépési lehetőséget: adja meg a
függvény, hogy a k. lépésről 1-et, illetve 2-t lépve milyen utak vezetnek
az n. lépcsőfokra.
A kiindulási lépéssor természetesen most is lehetne az üres string; azért
írtunk ehelyett szóközt, hogy az eredmény szépen igazodjék az előző megoldás
kimenetéhez:
def ms_2311_012_01b(k, f, n, path):
if k<=n:
k+= f
path+= str(f)
if k<n:
ms_2311_012_01b(k, 1, n, path)
ms_2311_012_01b(k, 2, n, path)
elif k==n:
print(path, end=' ')
ms_2311_012_01b(0, 1, 6, ' ')
ms_2311_012_01b(0, 2, 6, ' ')
print()
A két legutóbbi megoldás kimenete egymás alatt:
0123456 012346 012356 012456 01246 013456 01346 01356 023456 02346 02356 02456 0246
111111 11112 11121 11211 1122 12111 1212 1221 21111 2112 2121 2211 222
Végül hagyjuk el a paraméterek közül az átlépett fokok számát megadó
másodikat, s lássunk két lehetséges megfogalmazásra két lehetséges
függvényt.
I. Tudva azt, hogy a k. lépcsőfokra milyen út vezet, írassuk ki az n.
lépcsőfokra vezető utakat: ha k<n, akkor léphetünk egyet vagy kettőt; ha
k=n, akkor készen vagyunk.
def ms_2311_012_01c(k, n, path):
if k<n:
path+= '1'
ms_2311_012_01c(k+1, n, path)
path= path[:-1]+'2'
ms_2311_012_01c(k+2, n, path)
elif k==n:
print(path, end=' ')
ms_2311_012_01c(0, 6, ' ')
print()
II. Tudva azt, hogy a k. lépcsőfokra milyen út vezet, s tudva, hogy még l
lépcsőfok van hátra, írassuk ki a lehetséges utakat: ha l negatív, nincs
teendő; ha l nulla, készen vagyunk; egyébként lépjünk egyet vagy kettőt.
def ms_2311_012_01d(k, l, path):
if l<0:
return
elif l==0:
print(path, end=' ')
return
path+= '1'
ms_2311_012_01d(k+1, l-1, path)
path= path[:-1]+'2'
ms_2311_012_01d(k+1, l-2, path)
ms_2311_012_01d(0, 6, ' ')
print()
A kimenet mindkét esetben ugyanaz, mint legutóbb:
111111 11112 11121 11211 1122 12111 1212 1221 21111 2112 2121 2211 222