V_18 (kovanci in datoteke) (J)

Due: Thursday, 17 March 2022, 8:00 PM
Glavnino vaj bomo tokrat posvetili reševanju problema pobiranja kovancev, ki ste ga spoznali na predavanjih, ter njegovim izpeljankam. Drugi del vaj bo namenjen spoznavanju z datotekami preko nalog na Tomu.


1. Pobiranje kovancev

Osnovna rešitev problema kovancev

Na predavanjih ste spoznali problem pobiranja kovancev in ga rešili na tri načine:

  • z uporabo grobe sile (preverimo vse možne kombinacije)
  • z rekurzijo
  • z rekurzijo in slovarjem za hranjenje vmesnih rezultatov
Za vsak način napišite ustrezno funkcijo ter preverite, da vse delujejo pravilno (pripravite si nekaj primerov, za katere rešitev izračunate na roko, nato pa preverite, če vaše funkcije vračajo pravilno rešitev).
Izmerite čas izvajanja vsake izmed funkcij in jih primerjajte med seboj (spomnite se, kako smo čas z uporabo modula time merili pri nekaterih nalogah na začetku leta - recimo podnaloga Metak mrzkog neprijatelja naloge Mirko in Slavko na https://www.projekt-tomo.si/problem_set/2260/). Kaj se dogaja s časom, ko povečujete število kovancev? Za kako velike tabele še lahko izračunate rešitev v eni minuti z vsako izmed napisanih funkcij? Ugotovitve v nekaj stavkih predstavite v poročilu.

Nadgradnja problema kovancev

Rešitev problema kovancev nadgradite tako, da

  • vrne optimalno kombinacijo
  • vrne najkrajšo (z najmanj števili) optimalno kombinacijo
  • vrne najdaljšo (z največ števili) optimalno kombinacijo
  • vrne vse optimalne kombinacije
  • vrne optimalno kombinacijo z največjo vsoto vseh števk števil, ki jih izberemo
  • funkcija sprejme dodaten parameter k, ki pove, koliko kovancev moramo preskočiti (pri k=1 torej rešujemo klasičen problem kovancev, ker mora biti med dvema izbranima kovancema vsaj en kovanec)
Izberite si vsaj eno izmed nadgradenj in jo implementirajte. V poročilu na kratko komentirajte, kaj ste v kodi spremenili. Navedite tudi vsaj tri primere, na katerih ste svojo rešitev testirali (vsaj en mora biti netrivialen). Oddajte tudi kodo, ki naj sledi smernicam za lepo programiranje (jasna imena spremenljivk, ustrezni komentarji, kjer so potrebni).

2. Datoteke

Na Tomu si v sklopu Uvod v datoteke oglejte video z razlago, nato pa rešite vsaj tri podnaloge v tem sklopu.

=============

Poročilo naj vključuje:
  • komentarje in odgovore, zahtevane pri nalogi s kovanci
  • posnetek semaforjev za nalogo Datoteke

Rok za oddajo poročil je 17. 3. ob 20:00.

Za te vaje lahko pridobite Jollija, če poleg ostalih zahtev:
  • prikažete graf(e) meritev časa - pri tem lahko uporabite poljubno orodje
  • naredite vsaj tri nadgradnje problema s kovanci, oddate njihovo kodo in jih ustrezno predstavite v poročilu