El akadtam egy program megírásában. Tudnátok segíteni, hogyan tovább?
Van egy beadandó kötprogom, vasárnap éjfélig kell beadni, de teljesen elakadtam benne. Ez nagyon kezdő szint, szóval légyszi ne fikázzatok :D
Az a feladat, hogy van egy n darab lépcsőből álló lépcsősor, amin csak úgy lehet felmenni, hogy egyszerre csak egyet vagy kettőt léphetek. Ki kellene számolni, hogy hányféleképpen lehet felmenni. Mondjuk, ha 4 db lépcsőfokod van, akkor összesen 5 módon juthatsz fel. Na most egy ideig működik is a program, de amint elérek nagyobb n-ekig (kb mondjuk egy 50 lépcsőfokos lépcsőig), nem számolja ki, mert van egy két másodperces időkorlát a feladaton és gondolom tovább tart neki.
Idáig jutottam el:
public static long step(int n) {
if (n<=0) return 0;
if (n==1) return 1;
if (n==2) return 2;
if (n==3) return 3;
return step(n-1)+step(n-2);
}
Tudnátok segíteni abban, hogy ez nagyobb értékekre is működjön?
Előre is köszönöm!
válasza:Mivel nagy számoknál az estek döntő többségében a függvényt 3-nál nagyobb paraméterrel fogod futtatni, érdemes lehet a függvénybe egy if() - else() ágat rakni: mi történik, ha n<4 és mi ha nem, így nem kell 4 kiértékelést elvégezni egy rekurzív lépésben, hanem az esetek nagy részében csak 1-et.
Észre lehet venni azt is, hogy egy csomó értéket többször kiszámolsz ( az n-nél kisebb összes pozitív számra le fug futni a függvény, az n-1-nél kisebbekkre legalább 2-szer). Érdemes lehet kiszámolni külön külön a step() értékeit 0 és n között egyszer, mindig felhasználva az előzőleg kiszámolt értékeket, azokat eltárolni valahogy, és csak lekérdezni az eltárolt értékeket a végén. ( Mondjuk egy n hosszú tömböt feltöltesz a megfelelő értékekkel, felhasználva az addig kiszámolt értékeket)
válasza:Hali!
step(n-1)+step(n-2) Nem emlékeztet ez valamire? :)
Ez a Fibonacci sor képlete 1, 2 kezdőértékekkel.
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!