Tehetséggondozás az informatikában
Pozitív egész többféle összegként
A lépcsős feladat legutóbb látott átfogalmazásában azt mondtuk, hogy a 6
számot írjuk fel egymást követő 1-esek és/vagy 2-esek összegeként.
Kis változtatással feltehetjük azt a kérdést is: hányféleképpen írható fel
egy pozitív egész szám pozitív egész számok összegeként, ha
megkülönböztetjük azokat az eseteket (is), amelyek csak a tagok sorrendjében
különböznek.
Nem feltétlenül nyilvánvaló, hogy összesen 2
n-1 ilyen lehetőség
van, ahogyan az sem kézenfekvő, hogy hogyan lehet ezek mindegyikét
felsorolni. Erre ad megoldást a következő (meglepően rövid) rekurzív
program.
A megoldás helyességének végiggondolását ezúttal rábízzuk az olvasóra: ha
átesett az algoritmus megértésén, akkor jutalmul ölébe pottyan a lehetőségek
számáról szóló fenti állítás bizonyításának alapgondolata is…
def part(k, n, sum):
if k<n:
part(k+1, n, sum+[1])
part(k+1, n, sum+[sum.pop()+1])
elif k==n:
print(sum, end=' ')
part(1, 5, [1])
print()
Az alább (áttördelve) megjelenített kimenet egyúttal szép illusztráció a
lexikografikus rendezésre is.
[1, 1, 1, 1, 1] [1, 1, 1, 2] [1, 1, 2, 1] [1, 1, 3] [1, 2, 1, 1] [1, 2, 2] [1, 3, 1] [1, 4]
[2, 1, 1, 1] [2, 1, 2] [2, 2, 1] [2, 3] [3, 1, 1] [3, 2] [4, 1] [5]