Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2012-2013‎ > ‎

8. óra

Néhány szakkörön dinamikus programozással megoldható feladatokat fogunk gyakorolni.

Optimalizálási feladatok gyakran kezelhetők a dinamikus programozásnak nevezett elv segítségével. Ez a következőkből áll:
  1. Meghatározzuk az optimumot egy rekurzív függvény segítségével.
  2. Felgyorsítjuk a rekurziót a következő módon: egy tömbben tároljuk a már kiszámított függvényértékeket, és ha rekurzió egy ága már korábban kiszámított értéket kér, akkor azt a tömbből "vesszük elő", ahelyett, hogy újra meghívnánk a függvényt.
  3. Sok esetben tovább gyorsítható a megoldás, ha a rekurzív hívások valamilyen nyilvánvaló sorrendben történnek (például mindig eggyel kisebb paraméter értékkel). Ilyenkor egy egyszerű ciklussal is feltölthető az a tömb, ami a már kiszámított értékeket tárolja.

Akkor tudjuk a rekurzió lényegesen gyorsítani ezzel a módszerrel, ha sok átfedő részfeladat van, vagyis a "buta" rekurzió sokszor futna rá ugyanazon részprobléma kiszámítására.

Feladatok

3N+1 probléma
Kincsvadász
A fáraó lépcsője