7. házi feladat
16. sor: | 16. sor: | ||
Példa használatra:<br> | Példa használatra:<br> | ||
− | (amikor még 72 Ft volt egy kőrözöttes szendvics)<br><br> | + | (amikor még 72 Ft volt egy kőrözöttes szendvics az E-ben)<br><br> |
c = Change([1,2,5,10], 72)<br> | c = Change([1,2,5,10], 72)<br> |
A lap 2011. március 23., 17:51-kori változata
- LKR megszerkesztése:
Az előadáson bemutatott lkr.py módosítása úgy, hogy az LKR hossza mellett határozzunk meg egy konkrét közös részsorozatot, melynek hossza maximális. Ez történhet például úgy, hogy a c[i][j] értékek meghatározásakor feljegyezzük egy kétdimenziós tömbben, hogy a legjobb értéket honnan kaptuk. Miután c-t kitöltöttük, visszafelőlről meghatározható egy LKR.
- Backtrack alkalmazása pénzváltásra:
A 8 vezér probléma megoldása alapján alkalmazzuk a backtrack algoritmust a pénzváltás problémára. A probléma a következő:
Adott S pénzösszeg és P = {p1,...,pn} pozitív egészek esetén keresem az összes olyan S = {s1,...,sn} nemnegatív szám n-est, melyre egyenlő S-sel. A megoldás osztály a BackTrack-ből legyen leszármaztatva, és írjuk felül az ősosztály pass-szal definiált tagfüggvényeit.
Példa használatra:
(amikor még 72 Ft volt egy kőrözöttes szendvics az E-ben)
c = Change([1,2,5,10], 72)
c.main()
Kimenet: