7. házi feladat

A MathWikiből
(Változatok közti eltérés)
 
(egy szerkesztő 4 közbeeső változata nincs mutatva)
1. sor: 1. sor:
LKR megszerkesztése:
+
Az alábbi két feladat közül lehet választani:
 +
 
 +
* 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
 
Az előadáson bemutatott lkr.py módosítása úgy, hogy az LKR hossza mellett határozzunk meg egy konkrét
5. sor: 7. sor:
 
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
 
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.
 
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 = {<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.
 +
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:<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.main()<br><br>
 +
 +
Kimenet:
 +
*[http://info.ilab.sztaki.hu/~kisstom/info2_2011/7het/hazi/out change_out]
 +
<nowiki>Insert non-formatted text here</nowiki>

A lap jelenlegi, 2011. március 27., 15:01-kori változata

Az alábbi két feladat közül lehet választani:

  • 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 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:

Insert non-formatted text here

Személyes eszközök