Kezdőoldal » Számítástechnika » Programozás » El akadtam egy program megírás...

El akadtam egy program megírásában. Tudnátok segíteni, hogyan tovább?

Figyelt kérdés

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!



2018. okt. 4. 13:49
 1/2 anonim ***** 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)

2018. okt. 4. 15:07
Hasznos számodra ez a válasz?
 2/2 Progresszor ***** 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.


[link]

2018. okt. 5. 09:56
Hasznos számodra ez a válasz?

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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!