7. házi feladat

A MathWikiből
(Változatok közti eltérés)
13. sor: 13. sor:
 
Adott S pénzösszeg és P = {<math>p_1, ... , p_n</math>} pozitív egészek esetén keresem az összes olyan
 
Adott S pénzösszeg és P = {<math>p_1, ... , p_n</math>} pozitív egészek esetén keresem az összes olyan
 
S = {<math>s_1, ..., s_n </math>} nemnegatív szám n-est, melyre <math>\sum_{x=1}^{n} p_i*s_i</math> egyenlő S-sel.
 
S = {<math>s_1, ..., s_n </math>} nemnegatív szám n-est, melyre <math>\sum_{x=1}^{n} p_i*s_i</math> egyenlő S-sel.
A megoldás osztály a BackTrack-ből legyen leszármaztatva, és írjuk meg az ősosztály virtuális (pass-szal definiált) tagfüggvényeit.
+
A megoldás osztály a BackTrack-ből legyen leszármaztatva, és írjuk meg az ősosztály pass-szal definiált tagfüggvényeit.
  
 
Példa használatra:<br>
 
Példa használatra:<br>

A lap 2011. március 23., 11:52-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 \sum_{x=1}^{n} p_i*s_i egyenlő S-sel. A megoldás osztály a BackTrack-ből legyen leszármaztatva, és írjuk meg 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)

c = Change([1,2,5,10], 72)
c.main()

Kimenet:

Személyes eszközök