Hogyan lehet ezt a feladatot megoldani, lehetőleg pythonban?
Van egy lista számokkal (intiger), meg egy maximum, hogy mmekkorát lehet lépni. A lista elemei lényegében lépcsőfokot jelentenek és az értékük mutassa, hogy milyen magasak. Hány féleképpen lehet felmenni a tetejére, ha nulláról kezdünk, egy lépcsőfokot mindenképp kell lépni de lehet egyszerre többet is de akkor oda kell figyelni, hogy a lépcsődokok értéke ne halagya meg a megadott maximum értéket. PL
maximum= 100
lépcsők=[0,20,30,50,30]
Ennek a megoldása 6, mert 0-1-2-3-4[0,20,30,50,30], 0-1-2-4[0,20,30,50+30], 0-1-3-4[0,20,30+50,30], 0-2-3-4[0,20+30,50,30], 0-2-4[0,20+30,50+30] és 0-3-4[0,20+30+50,30]. De a 0-4 már nem jó mert 20+30+50+30=130 ami több mint 100.
válasza:Pythont nem ismerem, de erre rekurziót adnék meg.
Kilépési feltétel az, ha felért, vagy ha nem tud lépni a következőre.
A rekurzión belül meg egy ciklust lehet futtatni, ami a hátralévő összes lépcsőt megnézni következőnek.
válasza:Sikerült?
Az a 0 lépcsőmagasság az hogy van ott?
0+20,... meg 0+20+20,... 0,... lehetőségek nem is játszanak?
válasza:Lehet ez nem hatekony:
Step 1) Epitsunk fel egy grafot, hogy melyik lepcsorol melyikre lehet kozvetlenul eljutni, pl szamoljuk ki a cumulative sum-jat a lepeseknek:
A: 0
B: 0+20=20
C: 20+30=50
D: 20+30+50=100
E: 20+30+50+30=130
Ket lepcso kozott van kozvetlen lepes ha a cumul. sum kozott a kulonbseg max 100 (de pozitiv).
Nezzuk sorba a lepcsoket A: el lehet jutni a B,C,D-re, E-re mar nem; B: el lehet jutni a C es D-re ... Ez n*(n-1)/2 osszehasonlitas
Step 2) Ezen a grafon (iranyitott), hanyfelekeppen lehet A-bol E-be jutni?
Pl [link]
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!