Računalništvo 1

Na vajah bomo reševali problem kovancev v vrsti in problem kovancev v trikotniku, kot jih je profesor opisal na predavanjih. Po izvornih različicah bodo na vrsti zahtevnejše variacije:

Kovanci v vrsti:

• Funkcija naj vrne množico vseh rešitev (indeksi kovancev, ki jih izberejo), ki vrnejo maksimalno vsoto.
• Prilagodi rešitev tako, da bo uporabnik lahko označil maksimalno število kovancev, ki jih lahko izberemo.
• Napišite funkcijo tako, da bo uporabnik lahko izbral katerega od supremumov iščemo (maksimum ali minimum). Najlažje je, da uporabnik kot argument poda kar funkcijo, ki jo želi.
• V izvirniku nobena dva od izbranih kovancev ne smeta biti sosednja. To posplošite tako, da funkcija sprejme parameter k, ki pove najmanj koliko kovancev mora biti med dvema izbrana kovanca (torej k=1 v originalu).

Kovanci v trikotniku:

• Funkcija naj vrne pot, s katero dosežemo največjo izbiro (vrne naj tabelo nizov "levo" in "desno", ki opišejo pot po trikotniku).
• Prilagodite funkcijo tako, da lahko vsako smer izberemo največ dvakrat zapored. Lahko gremo torej levo-levo-desno-levo, neveljavna pa je pot desno-desno-desno-levo.
• Funkcija naj ima dodaten parameter k, s katerim označimo koliko korakov po trikotniku lahko naredimo (torej za k=3 izberemo 3 kovance, tudi če ima trikotnik 6 nivojev).

Poročilo: za vsakega od primerov (v vrsti/v trikotniku) oddate osnovno rešitev in rešitev še ene od različic. Za eno od naprednih različic napišite tudi markdown poročilo (npr. poročilo za kovance v trikotniku kjer vračamo pot). Oddajte tudi rešitev za problem poenostavljenega nahrbtnika.

Opomba: navodila se lahko do začetka vaj še malenkost spremenijo, so pa vaje odprte, da dobite približen občutek, kaj bomo delali.