Tu so zbrane vaje, ki smo jih pri predmetu Računalništvo 2 delali v šolskem letu 2024/25.

Dinamično programiranje

Žabica

1. podnaloga

Žabica se je izgubila v močvari in želi kar se da hitro odskakljati ven. Na srečo močvara vsebuje veliko muh, s katerimi si lahko povrne energijo, kajti utrujena žabica ne skoči daleč.

S funkcijo zabica(mocvara) želimo ugotoviti, kako hitro lahko žabica odskaklja iz močvare. Močvaro predstavimo s tabelo, kjer žabica prične na ničtem polju. Če je močvara dolžine k, je cilj žabice priskakljati vsaj na k-to polje ali dlje (torej prvo polje, ki ni več vsebovano v tabeli).

Energičnost žabice predstavimo z dolžino najdaljšega možnega skoka. Torej lahko žabica z količino energije e skoči naprej za katerokoli razdaljo med 1 in e, in če skoči naprej za k mest ima sedaj zgolj e - k energije. Na vsakem polju močvare prav tako označimo, koliko energije si žabica povrne, ko pristane na polju. Tako se včasih žabici splača skočiti manj daleč, da pristane na polju z več muhami. Predpostavimo, da ima vsako polje vrednost vsaj 1, da lahko žabica v vsakem primeru skoči naprej.

V primeru [2, 4, 1, 2, 1, 3, 1, 1, 5] lahko žabica odskaklja iz močvare v treh skokih, v močvari [4, 1, 8, 2, 11, 1, 1, 1, 1, 1] pa potrebuje zgolj dva.

Minsko polje

1. podnaloga

Robotka moramo prepeljati čez minirano območje, ki je pravokotne oblike in je razdeljeno na $n \times m$ kvadratnih polj. Znano je, kje so mine. Na začetku je robotek parkiran v zgornjem levem polju s koordinatama $(0, 0)$ . Spodnje desno polje ima koordinati $(n-1,m-1)$ . Robotek se lahko v vsakem koraku pomakne bodisi eno polje navzdol bodisi eno polje v desno. Na koliko načinov lahko pride iz začetnega na končno polje? Predpostavite lahko, da na začetnem in končnem polju ni min.

Napišite funkcijo stevilo_poti(n, m, mine), kjer sta n in m dimenziji polja, in mine seznam koordinat, na katerih so mine. Funkcija naj vrne število različnih poti med $(0, 0)$ in $(n-1, m-1)$ , ki se izognejo minam. Zgled:

>>> stevilo_poti(5, 4, [])
35
>>> stevilo_poti(5, 4, [(1, 2), (3, 2)])
9

Namig: najprej zapišimo rekurzivno formulo za funkcijo, ki pove, koliko je poti. Naj bo $S(i,j)$ število poti od polja $(i,j)$ do polja $(n-1, m-1)$ . Tedaj velja:

$S(i,j) = 0$ če je na polju $(i, j)$ mina,
$S(i,j) = S(i+1,j) + S(i,j+1)$ , če na polju $(i,j)$ ni mine in velja $i < n-1$ , $j < m-1$ ,
$S(n-1,m-1) = 1$ ,
$S(n-1,j) = S(n-1, j+1)$ , ker gremo lahko v spodnji vrstici samo desno,
$S(i,m-1) = S(i+1, m-1)$ , ker gremo lahko v desnem stolpcu samo navzdol.

Jajca

Visoka stavba ima več nadstropij. Sprehajamo se od nadstropja do nadstropja ter pri tem iz nekega nadstropja lahko spustimo jajce, ki pada do tal. Jajce se bodisi razbije bodisi ostane celo. Celo jajce lahko poberemo in ga ponovno uporabimo. Če se jajce razbije v nekem nadstropju se razbije tudi v vseh višjih nadstropjih, velja pa tudi obratno. Želimo ugotoviti, katero je najnižje nadstropje v katerem se jajce še razbije. Na voljo imamo $k$ jajc stavba pa ima $n$ nadstropij. Kolikšno je najmanjše število metov jajca, da bomo zagotovo ugotovili katero je ''kritično'' nadstropje.

1. podnaloga

Sestavite funkcijo jajce_rec(n, k), ki vrne najmanje število metov jajca pri k nadstropjih in n jajcih. Funkcija naj bo napisana rekurzivno.

2. podnaloga

Sestavite funkcijo jajce_iter(n, k), ki vrne najmanje število metov jajca pri k nadstropjih in n jajcih. Tokrat naj funkcija nebo napisana rekurzivno

3. podnaloga

Sestavite funkcijo nadstropja(d, n), ki vam pove koliko nadstropij lahko preverite v d metih in z n jajci.

4. podnaloga

Sestavite funkcijo jajca_hitro(n, k) kot v prvih dveh nalogah. Tokrat mora funkcija delovati hitro tudi za večje stavbe z več nadstropji (recimo nad 1000 nadstropji). Namig: uporabite funkcijo nadstropja(d, n).

Vlečenje vrvi

Udeleženci piknika bodo vlekli vrv. So različnih spolov, starosti in mas, zato sprva niso vedeli, kako bi se pravično razdelili v dve skupini. Sklenili so, da je najpravičnejša razdelitev takšna, da bosta imeli obe skupini enako skupno težo, na število članov skupin pa se sploh ne bodo ozirali. Včasih dveh skupin s popolnoma enakima masama ni mogoče sestaviti, zato iščejo takšno razdelitev, da bo razlika med masama skupin čim manjša. Vsak udeleženec nam je zaupal svojo maso v kilogramih in sicer jo je zaokrožil na najbližje celo število.

1. podnaloga

Sestavite funkcijo razdeli(mase), ki dobi seznam mas udeležencev in vrne skupno maso manjše od skupin pri najbolj pravični delitvi. Ta funkcija naj deluje s sestopanjem, torej pregleda vse možnosti. (Katere so vse možnosti in koliko jih je?) Zgled, v katerem je optimalna razdelitev dosežena, ko damo udeleženca z masama 102 in 95 skupaj eno skupino, vse ostale pa v drugo:

>>> razdeli([95, 82, 87, 102, 75])
197

Navodilo: naj bo skupaj skupna masa vseh udeležencev, torej vsota števil v seznamu mase. Definirajmo pomožno funkcijo deli(levi, i), ki sprejme maso levi udeležencev, ki so bili do sedaj razporejeni v levo skupino, ter indeks i naslednjega udeleženca, ki ga moramo še razporediti. Funkcija razdeli potem enostavno pokliče deli(0,0).

Funkcija deli je rekurzivna in pregleduje vse možnosti. Pri tem pazi, da masa levi ne preseže skupaj//2, da se izogne dvakratnemu pregledovanju simetričnih kombinacij. Funkcija vrne maso lažje od obeh skupin:

če je i == len(mase), smo obravnavli vse, in vrnemo levi
če bi dali i-tega na levo in bi s tem leva skupina presegla skupaj//2, potem ga damo na desno
sicer rekurzivno preizkusimo obe možnosti (i-tega damo na levo ali na desno) ter se odločimo za boljšo od obeh možnosti.

2. podnaloga

Če zgornjo rešitev preizkusite na seznamih dolžine 25 ali več, boste ugotovili, da deluje izjemno počasi. Kakšna je njena časovna zahtevnost?

Nalogo bomo rešili še z dinamičnim programiranjem. Gre za tako imenovani problem 0-1 nahrbtnika. Izkoristili bomo dejstvo, da mase ljudi ne morejo biti poljubno velike (največja dokumentirana masa človeka je 635 kg) in da so celoštevilske. Pri sestavljanju skupin lahko dosežemo enako maso na različne načine.

Sestavite funkcijo razdeli_dinamicno(mase), ki naredi isto kot prejšnja funkcija, le da se reševanja tokrat lotite z dinamičnim programiranjem. Zgled:

>>> razdeli_dinamicno([95, 82, 87, 102, 75])
197

Funkcijo preizkusite na seznamu dolžine 50 in na seznamu dolžine 100.

Navodilo: Naj bo skupaj skupna masa vseh udeležencev. Tokrat bomo izračunali množico mozna tako da bo veljalo i ∈ mozna natanko tedaj, ko je možno razdeliti udeležence tako, da ima ena od obeh skupin maso i. To lahko naredimo s preprosto zanko, upoštevajoč:

0 ∈ mozna, če damo vse udeležence v eno skupino
če imamo udeleženca z maso k, ki ga še nismo obravnavali, in je i ∈ mozna, potem velja tudi (i+k) ∈ mozna.

Ko enkrat imamo tabelo mozna, poisčemo največji indeks i, ki je manjši ali enak skupaj//2 in je mozna[i] == True.

3. podnaloga

Prejšnja funkcija nam izračuna maso manjše skupine, nič pa ne izvemo o tem, kdo so udeleženci, ki tvorijo to skupino. Sestavite še funkcijo razdeli_udelezence(mase), ki vrne seznam mas udeležencev, ki bodo manjšo od obeh skupin. Če je rešitev več, lahko funkcija vrne katerekoli rešitev. Zgled:

>>> razdeli_udelezence([95, 82, 87, 102, 75])
[102, 95]

Namig: Spremenite prejšnjo rešitev tako, da bo namesto množice možnih mas skupin mozna izračunala slovar skupine. Ključi v slovarju so možne mase (torej elementi množice mozna), vrednosti pa množice, ki sestavljajo pripadajočo skupino.

Palindromi

1. podnaloga

Sestavi rekurzivno funkcijo palindromsko_podzaporedje(niz), ki vrne dolžino najdaljšega podniza niza niz, ki je palindrom. Za podniz ne zahtevamo, da je strnjen.

Primer:

>>> palindromsko_podzaporedje('BBABCBCAB')
7

Najdaljši podniz niz 'BBABCBCAB', ki je palindrom je 'BABCBAB'.

2. podnaloga

Sestavi funkcijo palindromsko_dinamicno(niz), ki vrne dolžino najdaljšega podniza niza niz, ki je palindrom. Za podniz ne zahtevamo, da je strnjen. Nalogo reši z dinamičnim programiranjem.

Primer:

>>> palindromsko_dinamicno('BBABCBCAB')
7

3. podnaloga

Sestavi funkcijo palindromsko_niz(niz), ki vrne najdaljši podniza niza niz, ki je palindrom. Za podniz ne zahtevamo, da je strnjen. Če je rešitev več, naj vrne prvo izmed njih (tisto, ki se začne najbolj levo). Nalogo reši z dinamičnim programiranjem.

Primer:

>>> palindromsko_niz('BBABCBCAB')
'BABCBAB'
>>> palindromsko_niz('abcABCabcABC')
'aba'

4. podnaloga

Sestavi funkcijo palindromsko_nizi(niz), ki vrne množico vseh najdaljših podnizov niza niz, ki so palindromi. Za podniz ne zahtevamo, da je strnjen. Nalogo reši z dinamičnim programiranjem.

Primer:

>>> palindromsko_nizi('BBABCBCAB')
{'BABCBAB', 'BACBCAB'}

Postavljanje oklepajev

1. podnaloga

Sestavi rekurzivno funkcijo oklepaji(izraz), ki sprejme niz izraz, v katerem nastopajo cela števila in računske operacije seštevanje, odštevanje, množenje in deljenje(števila in operatorji so ločeni s presledkom) ter vrne par '(najvecja, najmanjsa)', kjer 'najvecja' predstavlja največjo vrednost, ki jo lahko dobimo, če v izrazu dodamo oklepaje, 'najmanjsa' pa najmanjšo vrednost, ki jo lahko dobimo, če v izrazu dodamo oklepaje. Primer:

>>> oklepaji('1 + 5 * 6 - 3')
(33, 16)

Največjo vrednost dosežemo z izrazom ((1 + 5) * 6) - 3, najmanjšo pa z '1 + (5 * (6 - 3))'.

Spodaj je že napisan del kode. Ustrezno ga dopolni. Mesta, kjer je potrebno kaj dopisati so označena z ###.

2. podnaloga

Sestavi funkcijo oklepaji_dinamicno(izraz), ki sprejme niz izraz, v katerem nastopajo cela števila in računske operacije seštevanje, odštevanje, množenje in deljenje(števila in operatorji so ločeni s presledkom) ter vrne par '(najvecja, najmanjsa)', kjer 'najvecja' predstavlja največjo vrednost, ki jo lahko dobimo, če v izrazu dodamo oklepaje, 'najmanjsa' pa najmanjšo vrednost, ki jo lahko dobimo, če v izrazu dodamo oklepaje. Nalogo reši z dinamičnim programiranjem. Primer:

>>> oklepaji_dinamicno('1 + 5 * 6 - 3')
(33, 16)

Največjo vrednost dosežemo z izrazom ((1 + 5) * 6) - 3, najmanjšo pa z '1 + (5 * (6 - 3))'.

Spodaj je že napisan del kode. Ustrezno ga dopolni. Mesta, kjer je potrebno kaj dopisati so označena z ###.

3. podnaloga

Sestavi funkcijo oklepaji_izraz(izraz), ki sprejme niz izraz, v katerem nastopajo cela števila in računske operacije seštevanje, odštevanje, množenje in deljenje(števila in operatorji so ločeni s presledkom) ter vrne tisti izraz z oklepaji, kateraga vrednost je največja možna. Nalogo reši z dinamičnim programiranjem. Primer:

>>> oklepaji_izraz('1 + 5 * 6 - 3')
'((1 + 5) * 6) - 3'
>>> oklepaji_izraz('1 + 3')
'1 + 3'

Najbolj zunanjih oklepajev ne izpisuj!

Kode ne piši na novo, ampak preuredi rešitev prejšnje podnaloge.

Poti v matriki

Dano imamo matriko, ki vsebuje števila 1, 0 in -1, kjer -1 predstavlja nevarno celico. Iz prve celice (levo zgoraj) potujemo po matriki in nabiramo točke (1 točka, če obiskana celica vsebuje število 1, 0 točk, če vsebuje število 0), pri tem pa ne smemo obiskati nevarnih celic. Poleg tega nam je dovoljeno potovati samo navzdol ali na levo, če smo v lihi vrstici oz. navzdol in na desno, če smo v sodi vrstici.

Pri reševanju si lahko pomagaš z napisano rešitvijo v C++ ali v Javi, ki jo najdeš na tej spletni strani. Na isti strani je tudi primer matrike s prikazano rešitvijo.

1. podnaloga

Sestavi rekurzivno funkcijo najvrednejsa_pot(matrika), ki vrne največje število točk, ki jih lahko naberemo pri potovanju po matriki po zgoraj napisanih pravilih.

2. podnaloga

Sestavi funkcijo najvrednejsa_pot_dinamicno(matrika), ki vrne največje število točk, ki jih lahko naberemo pri potovanju po matriki po zgoraj napisanih pravilih. Nalogo reši z dinamičnim programiranjem.

3. podnaloga

Sestavi funkcijo najvrednejsa_pot_navodila(matrika), ki vrne seznam z navodili, kako moramo potovati po matriki, da bomo nabrali največje možno število točk. Nalogo reši z dinamičnim programiranjem. Za primer matrike s spletne strani, naj bo rešitev: ['desno', 'dol', 'levo', 'dol', 'desno', 'desno', 'desno', 'dol', 'levo'].

Posode zlata

Dva igralca se igrata naslednjo igro. V vrsti so postavljene posode z različnim številom zlatih kovancev. Igralca, ki vidita, koliko kovancev je v kateri posodi, izmenično izbirata posode, ki jih bosta vzela (ob vsaki potezi igralec vzame celo posodo s kovanci, ne posameznih kovancev iz nje), izbirata pa lahko le med prvo in zadnjo posodo v vrsti. Cilj igre je izbrati čimvečje število kovancev.

1. podnaloga

Sestavi funkcijo najvecji_dobicek(zlato), ki vrne največje število kovancev, ki jih lahko dobi prvi igralec ob predpostavki, da oba igralca igrata optimalno.

Rešitev napiši z dinamičnim programiranjem.

2. podnaloga

Sestavi funkcijo najvecji_dobicek_katere(zlato), ki vrne seznam zaporednih izbir posod, ob kateri prvi igralec dobi največje možno število kovancev ob predpostavki, da oba igralca igrata optimalno.

Rešitev napiši z dinamičnim programiranjem.

Tekmovanje - Nahrbtnik

01 Nahrbtnik

Trgovec želi iz Evrope v Ameriko spravit večjo količino predmetov. Pri tem ima na razpolago tovorno letalo, ki pa lahko prenese le omejeno količino blaga. Predmete predstavimo s seznamom elementov oblike $(c_i, v_i)$ , kjer $c_i$ predstavlja ceno $i$ -tega predmeta, $v_i$ pa njegovo težo.

1. podnaloga

Implementiraj funkcijo optimalni_tovor(predmeti, W), ki vrne največjo skupno ceno predmetov, ki jih lahko trgovec natovori na letalo z maksimalno nosilnostjo W. Na primer:

>>> optimalni_tovor([(2,3), (4,4), (5,4), (3,2), (1,2), (15, 12)], 7)
8

2. podnaloga

Implementiraj funkcijo optimalni_predmeti(predmeti, W), ki vrne seznam predmetov ki dosežejo največjo vrednost, če lahko na letalo natovorimo skupno težo največ W. Če je možnosti več, vrni katerokoli. Na primer:

>>> optimalni_predmeti([(2,3), (4,4), (5,4), (3,2), (1,2), (15, 12)], 7)
[(3, 2), (5, 4)]

3. podnaloga

Trgovec je dobil dodatno pošiljko obstoječih predmetov. Tako ima sedaj na razpolago več kot en predmet posameznega tipa. Predmete tako predstavimo s seznamom elementov oblike $(c_i, v_i, z_i)$ , kjer je: * $c_i$ cena * $v_i$ teža * $z_i$ zaloga $i$ -tega predmeta.

Implementiraj funkcijo optimalni_tovor_zaloga(predmeti, W), ki vrne največjo skupno ceno predmetov, ki jih lahko trgovec natovori na letalo z maksimalno nosilnostjo W. Na primer:

>>> optimalni_tovor_zaloga([(2,3, 1), (4,4, 2), (5,4, 4), (3,2, 3), (1,2, 3), (15, 12, 2)], 7))
9

4. podnaloga

Predpostavi, da ima sedaj trgovec na voljo neomejeno zalogo posameznih predmetov. implementiraj funkcijo neomejena_zaloga(predmeti, W), ki vrne najvišjo skupno ceno tovora na letalu z maksimalno nosilnostjo W Na primer:

>>> neomejena_zaloga([(2,3), (4,4), (5,4), (3,2), (1,2), (15, 12)], 23)
33

5. podnaloga

Trgovec je ugotovil, da se mu izplača imeti nekaterih predmetov več na zalogi kot ostalih. Implementiraj funkcijo najboljsa_zaloga(predmeti, W), ki vrne seznam zaloga dolžine len(predmeti), kjer zaloga[i] predstavlja koliko zaloge potrebuje za predmet i, tako da bo skupna vrednost pošiljke na letalu z maksimalno nosilnostjo W čim večja. Na primer:

>>> najboljsa_zaloga([(2,3), (4,4), (5,4), (3,2), (1,2), (15, 12)], 23)
[1, 0, 0, 10, 0, 0]

6. podnaloga

Letalski prevoznik je trgovcu ponudil opcijo, da mu ni treba pošiljati celotnih predmetov. Zapakira jih lahko v manjšo škatlo in jih naloži na letalo. Bolj natančno, za nek predmet $(c_i, v_i)$ lahko na letalo naloži predmet oblike $(c_i/r, v_i/r)$ za $r \in \{1,2,3,4\}$ . Pri tem lahko na letalo naloži le en tip predmeta. Na letalu ne more tako biti recimo $1/2 + 1/3 = 5/6$ nekega predmeta. Implementiraj funkcijo # tovor_rezanje(predmeti, W), ki vrne koliko je sedaj največja skupna cena tovora, če je nosilnost letala največ W. Rezultat vrni zaokrožen na dve decimalni mesti. Na primer:

>>> tovor_rezanje([(2,3), (4,4), (5,4), (3,2), (1,2), (15, 12)], 20)
25.0

7. podnaloga

Trgovec je dobil na razpolago nabor novih izdelkov. Odločiti se mora za enega, ki ga bo vključil v svoje trgovanje. Odloča se na podlagi tega, koliko bo največja skupna cena tovora, ki ga bo lahko poslal z letalom. Pomagaj mu, tako da implementiraš funkcijo tovor_novi_predmet(predmeti, W, novi_predmeti), ki vrne najboljšo skupno ceno tovora, ki ga lahko spravimo na letalo z nosilnostjo najvč W z predmeti iz seznama predmeti ter enim dodatnim predmetom iz seznama novi_predmeti. Pozor: pri testnih primerih je seznam novi_predmeti dolg približno 1000 elementov. Funkcija mora biti tako spisana čim bolje. Na primer:

>>> tovor_novi_predmet([(2,3), (4,4), (5,4), (3,2), (1,2), (15, 12)], 20,[(4,4), (12,11), (2,3), (17, 5), (18,8), (5,6), (7,6), (6,6)])
35

0_1 Nahrbtnik

0/1 nahrbtnik - 1. del

Pri reševanju problema 0/1 nahrbtnika imamo opravka z množicami $S_i$ in $Z_i$ . Predstavili jih bomo s seznami parov, ki so urejeni naraščajoče po prvih komponentah.

Ta sklop se ukvarja le z iskanjem vrendosti opt. rešitve

TODO - poglej lanskeo / predlandsko ... reševanje in prilagodi glede na to - požrešni nahrbtnik - pobiranje podatkov iz datotek - enak problem, a z drugim besedilom

 - 0/n narbrnik optimirati izpis (da res torej dobimo 0/n)

  -. Pogleati Ericsonovenaloge iz =/1 nahrbtnika
  - drugi viri za 0/1

Naloge tipa: * popravi, dopolni, ....

1. podnaloga

Sestavi funkcijo preveri(s), ki za parameter s dobi seznam parov. Funkcija naj ugotovi, ali ta seznam lahko (teoretično) predstavlja neko množico $S$ za nek problem 0/1 nahrbtnika.

>>> preveri([(0,0),(3,7),(4,9),(8,12),(11,17),(20,33)])
True

2. podnaloga

Sestavi funkcijo sestaviZ(s, predmet), ki za neko množico $S_i$ in predmet, podan s parom (velikost, vrednost), sestavi in vrne množico $Z_{i+1}$ .

>>> sestaviZ([(0,0),(1,1),(2,2),(3,3)], (4,4))
[(4,4),(5,5),(6,6),(7,7)]

3. podnaloga

Sestavi funkcijo sestaviS(s, z), ki iz množic $S_i$ in $Z_{i+1}$ sestavi in vrne množico $S_{i+1}$ .

>>> sestaviS([(0,0),(11,6),(40,9),(51,15)], [(16,4),(27,10),(56,13),(67,19)])
[(0,0),(11,6),(27,10),(51,15),(67,19)]

Bi lahko kaj "poenostavil", če bi poznal velikost nahrbtnika?

4. podnaloga

Sestavi funkcijo mnoziceS(predmeti), ki za dani seznam predmetov, pri čemer je vsak predmet predstavljen s parom (velikost, vrednost), sestavi in vrne seznam vseh množic $S$ .

>>> mnoziceS([(2,3),(4,5),(4,7),(6,8)])
[[(0,0)],[(0,0),(2,3)],[(0,0),(2,3),(4,5),(6,8)],[(0,0),(2,3),(4,7),
   (6,10),(8,12),(10,15)],[(0,0),(2,3),(4,7),(6,10),(8,12),(10,15),
   (12,18),(14,20),(16,23)]]

5. podnaloga

Sestavi funkcijo nahrbtnik01(predmeti, velikost), ki reši problem 0/1 nahrbtnika, kjer je predmeti seznam predmetov, predstavljen kot prej, velikost pa velikost nahrtnika. Funkcija naj vrne skupno velikost in vrednost predmetov, ki jih damo v nahrbtnik.

>>> nahrbtnik01([(2,3),(4,5),(4,7),(6,8)], 9)
(8,12)

0/1 nahrbtnik - 2.del

Pri reševanju problema 0/1 nahrbtnika imamo opravka z množicami $S_i$ in $Z_i$ . Predstavili jih bomo s seznami parov, ki so urejeni naraščajoče po prvih komponentah.

V tem sklopu nas zanimajo predmeti, ki sestavljajo opt. rešitevm vse možne rešitve, razširitve na 0/n nahrbtnik ...

TODO:

     - pregledati in izboljšati rešitve 
     - rešitev s tabelo pri omejitvi velikosti na V
     - pred 0/n rešitvijo narediti 0/2 rešitev

1. podnaloga

Sestavi funkcijo resitev01(predmeti, velikost), ki reši problem 0/1 nahrbtnika tako, da vrne seznam ničel in enic, ki določajo, katere predmete moramo izbrati. Če je rešitev več, naj vrne katerokoli izmed njih.

>>> resitev01([(2,3),(4,5),(4,7),(6,8)], 9)
[0, 1, 1, 0]

2. podnaloga

Sestavi funkcijo resitve01(predmeti, velikost), ki reši problem 0/1 nahrbtnika kot pri prejšnji podnalogi, le da vrne seznam vseh možnih rešitev. Vrstni red rešitev v seznamu ni pomemben.

>>> resitve01([(2,4),(4,5),(4,7),(6,8)], 9)
[[0, 1, 1, 0], [1, 0, 0, 1]]

3. podnaloga

Sestavi funkcijo resitev0n(predmeti, velikost), ki reši malo spremenjen problem nahrbtnika. Vzamemo lahko več enakih predmetov, koliko posameznih predmetov imamo na voljo pa je dodano pri opisu posameznega predmeta. Namesto para (velikost, cena) imamo torej trojko (velikost, cena, količina). Funkcija naj vrne seznam celih števil, ki določajo, koliko katerih predmetov moramo vzeti. Če je rešitev več, naj vrne katerokoli izmed njih. Namig: pretvori problem na običajen problem 0/1 nahrbtnika.

>>> resitev0n([(2,3,2),(4,5,3),(4,7,1),(6,8,2)], 15)
[2, 0, 1, 1]

Podzaporedja

Najdaljše padajoče podzaporedje

1. podnaloga

Sestavi rekurzivno funkcijo padajoce_podzaporedje_rekurzivno(zaporedje), ki za dano zaporedje vrne dolžino najdaljšega padajočega podzaporedja.

Kako lahko pospešimo delovanje funkcije?

2. podnaloga

Sestavi funkcijo padajoce_podzaporedje_tabela(zaporedje), ki za dano zaporedje vrne dolžino najdaljšega padajočega podzaporedja. Funkcija naj ne bo rekurzivna, temveč naj si delne rešitve shranjuje v tabelo.

3. podnaloga

Sestavi funkcijo padajoce_podzaporedje(zaporedje), ki za dano zaporedje vrne najdaljše padajoče podzaporedje. Podzaporedje naj vrne kot seznam. Če je rešitev več, naj vrne tisto z najmanjšimi indeksi.

4. podnaloga

Sestavi funkcijo vsa_padajoca_podzaporedja(zaporedje), ki za dano zaporedje vrne vsa najdaljša padajoča podzaporedja. Vsako podzaporedje naj bo predstavljeno s terico (tuple), rešitev pa naj bo podana kot množica podzaporedij.

Število najdaljših zaporedij

1. podnaloga

Sestavi funkcijo stevilo_podzaporedij(zaporedje), ki za dano zaporedje vrne število najdaljših naraščajočih podzaporedij.

Problem najkrajših poti

Naloge predpostavljajo, da ima reševalec že na voljo implementacije metod Floyd Warshal, Dijkstra ter Bellman Ford. Opis teh metod in dostop do njih je "tukaj" (TODO!)

Železniške postaje

1. podnaloga

Zaposlili so te v Indijskih železnicah. Tvoja zadolžitev je iskanje najkrajših poti med dvema železniškima postajama. Dan imaš seznam trojk (x, y, d), ki ti pove, da je dolžina dvosmerne povezave med postajama x in y enaka d, in seznam parov (u, v), za katere moraš izračunati najkrajše poti. Sestavi funkcijo najkrajse_poti(povezave, relacije), ki bo vrnila seznam dolžin najkrajših poti med pari postaj podanimi v seznamu relacije. Zgled:

 >>> povezave = [('A', 'B', 10), ('A', 'C', 20), ('B', 'D', 100), ('D', 'C', 50)]
 >>> relacije = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('D', 'C')]
 >>> najkrajse_poti(povezave, relacije)
 [10, 20, 70, 30, 80, 50]

Sherlock

1. podnaloga

Sherlock zelo rad potuje. Tokrat raziskuje London skupaj z Watsonom. Danes je Sherlock razpoložen za igro, zato je Watsona postavil pred izziv. Sherlock bo med dvema krajema A in B potoval po najkrajši poti, Watson pa mora nato za njim po najkrajši poti, ki ne vsebuje nobene povezave po kateri je šel Sherlock.

Pomagaj Watsonu in sestavi funkcijo sherlock(povezave, A, B), ki sprejme seznam povezave, ki vsebuje trojke oblike (x, y, d), kjer je d dolžina povezave z začetkom v x in koncem v y, ter kraja A in B, vrne pa dolžino poti po kateri bo potoval Watson. Če take poti ni, naj funkcija vrne -1. Zgled:

>>> sherlock([('A', 'B', 10), ('A', 'C', 20), ('B', 'D', 100), ('D', 'C', 50)], 'A', 'C')
160

Najkrajše poti in skoki

1. podnaloga

Dan imamo povezan graf z vozlišči od 1 do n. Tvoja naloga je, da potuješ iz vozlišča 1 do vozlišča n po najkrajši poti. Če obstaja več najkrajših poti, moraš izbrati tisto, ki vsebuje manj skokov. Število skokov na poti je število parov dveh sosednjih povezav z dolžinami različne parnosti. Sestavi funkcijo najkrajsa_pot(povezave, n), ki vrne par (dolzina, skoki), kjer je dolzina, dolžina najkrajše poti med vozlišči 1 in n, skoki pa je število skokov na tej poti. Zgled:

>>> najkrajsa_pot([(1, 2, 4), (2, 4, 6), (1, 3, 5), (3, 4, 5), (4, 5, 5)], 5)
(15, 0)

Čokolada

1. podnaloga

Tvoj prijatelj živi v mestu A, ti pa v mestu B. Rad bi dobil posebno čokolado xyz. Ta čokolada je na voljo le v izbranih mestih, med katerimi ni mesta, v katerem živiš. Čokolado hranijo v posebnih hladilnikih, kjer ostane dobra neskončno časa, enkrat ko čokolado vzameš iz hladilnika, pa je dobra le še omejeno časa. Tvoj prijatelj se je ponudil, da ti bo prinesel čokolado. Sestavi funkcijo cokolada(povezave, mesta, A, B, rok), ki sprejme trojice povezav (x, y, d), kjer d predstavlja čas, ki ga potrebujemo za potovanje od mesta x do mesta y, seznam mesta, kjer so shranjena mesta, v katerih je čokolada na voljo, mesti A in B, v katerih živiš ti oz. tvoj prijatelj, ter rok, ki pove, koliko časa je čokolada še dobra, enkrat ko jo vzamemo iz hladilnika, vrne pa minimalni čas, ki ga tvoj prijatelj potrebuje, da pride s čokolado v tvoje mesto. Če tega ne more storiti (ker povezava ne obstaja, ali ker bi se čokolada prej pokvarila), naj vrne -1. Zgled:

>>> cokolada([(1, 2, 4), (2, 4, 6), (1, 3, 5), (3, 4, 5), (4, 5, 5)], [3], 5, 2, 10)
19

Popotnik Xenny

1. podnaloga

Popotnik Xenny je bil na dopustu v AlgoLandu. Želel je potovati iz mesta U v mesto V, to pa je želel storiti tako, da bi potoval deloma po cestah, deloma z vlakom. Xenny bo pot pričel v mestu U, nato bo potoval do nekega mesta Z po cestah, od tam naprej pa bo do mesta V potoval z vlakom ali pa bo pot pričel z vlakom od mesta U do nekega mesta Z in nato do mesta V nadaljeval po cestah. Seveda bo med vsemi takimi potmi izbral najkrajšo možno. Sestavi funkcijo xenny(ceste, zeleznica, u, v), ki sprejme dva seznam cestnih in seznam železniških povezav med mesti, skupaj z njihovimi dolžinami, ter začetno in kočno mesto, vrne pa dolžino najkrajše poti. Zgled:

>>> xenny([(1,2,2), (3,2,4), (3,4,5)], [(1,2,6), (4,3,1), (1,4,7)], 1, 2)
12

Ključno vozlišče

1. podnaloga

Sestavi funkcijo odstrani_element(povezave, A, B), ki izračuna najkrajšo pot med vozliščema A in B ter nato poišče tako vozlišče, da je dolžina najkrajše poti v grafu, kateremu odstanimo to vozlišče, večja od najkrajše poti prvotnega grafa. Če je takih vozlišč več, naj vrne najmanjše vozlišče. Če takega vozlišča ni, naj vrne None. Zgled:

>>> odstrani_element([(1,2,1), (2,5,1), (1,3,1), (3,4,1), (4,5,1)], 1, 5)
2

Luka se igra

1. podnaloga

V vasi, kjer živi Luka, je N hiš, ki so oštevilčene od 1 do N in nekatere med njimi so povezane s potmi. Luka živi v hiši s hišno številko 1. V vseh preostalih hišah živijo njegovi prijatelji, s katerimi se zelo rad igra. Lukova mama je zelo stroga in Luku dovoli iti iz hiše le za K časa. V tem času mora Luka priti do prijateljeve hiše, se igrati in še priti nazaj domov. Sestavi funkcijo obiski(povezave, prijatelji), ki sprejme seznam povezave, ki vsebuje trojke oblike (x, y, d), kjer je d čas, potovanja med hišama x in y in seznam prijatelji, ki vsebuje pare (p, k), kjer je p hišna številka hiše v kateri živi Lukov prijatelj, ki bi ga rad obiskal, k pa koliko časa mu mama dovoli biti zunaj. Funkcija naj vrne seznam, ki za vsak par v seznamu prijatelji vsebuje maksimalni možni čas igranja. Če ima Luka na voljo premalo časa, da bi prišel do prijatelja in nazaj, naj vrne 0. Zgled:

>>> obiski([(1,2,2), (2,3,4), (3,4,5), (4,5,1), (1,4,7)], [(4, 20), (5,21), (3, 5)])
[6, 5, 0]

CryptLand

1. podnaloga

V CryptLandu so mesta povezana s cestami in metroji. Nekatere cene potovanja med mesti so vnaprej znane. Za potovanje po cesti morajo prebivalci plačati vladi, če pa potujejo z metrojem, jim vlada podari denar in tako spodbujajo uporabo javnih prevoznih sredstev. Sestavi funkcijo cryptLand(povezave, relacije), ki sprejme trojice povezav (x, y, d) v seznamu povezave, kjer d predstavlja čas, potreben za potovanje od mesta x do mesta y in seznam relacije, ki vsebuje pare (u, v). Funkcija vrne seznam, ki za vsak par iz seznama relacije vrne najkrajšo pot od u do v. Če pot med u in v ne obstaja, naj vrne 'Ni povezave'. Zgled:

>>> cryptLand([(1,2,2), (2,3,-1), (3,1,4), (3,4,2), (3,5,-3), (6,4,1), (6,5,-4)], [(1,3), (1,2), (3,6), (4,6), (2,5)])
[1, 2, 'Ni povezave.', 'Ni povezave.', -4]

Iskanje najkrajših poti

Podan imamo graf z vozlišči in povezavami graf ter eno izmed njegovih vozlišč s. Za vsako vozlišče v v grafu graf želimo poiskati dolžino najkrajše poti od s do v. Graf graf predstavimo kot slovar, katerga ključi so posamezna vozlišča. Vsakemu vozlišču v pripada slovar, katerega ključi so sosedi vozlišča v, vrednosti pa njihove razdalje do v. Na primer, graf mest s predavanj predstavimo kot:

graf_predavanja = {
    'Ljubljana': {
        'Maribor': 127,
        'Kranj': 26
    },
    'Maribor': {
        'Ljubljana': 127
    },
    'Koper': {
        'Ljubljana': 97,
        'Kranj': 105
    },
    'Kranj': {
        'Maribor': 140,
        'Koper': 105
    }
}

Nalogo bomo rešili z Dijkstrovim algoritmom. Dijkstrov algoritem okvirno deluje na sledeč način:

funkcija Dijsktra(graf, s):
    za vsako vozlišče x:
        razdalja[x] <- ∞
    razdalja[s] <- 0

    dokler ne obiščemo vseh vozlišč:
        x <- vozlišču s trenutno najbližje vozlišče
        za vsakega soseda y vozlišča x, ki ga še nismo obiskali:
            do_y_skozi_x <- razdalja[x] + povezava(x, y)
            če do_y_skozi_x < razdalja[y]:
                razdalja[y] <- do_y_skozi_x
        vozlišče x označimo kot obiskano
    vrni razdalja

Pomožna funkcija povezava(x, y) nam s pomočjo slovarja graf izračuna razdaljo med vozliščema x in y. Če x in y nista povezana, vrne ∞.

1. podnaloga

Sestavi funkcijo dijkstra(graf, s), ki s pomočjo Dijkstrovega algoritma poišče dolžine najkrajših poti med s ter vsemi ostalimi vozlišči v grafu graf.

Nasvet: za vrednost ∞ uporabi float("inf").

>>> dijkstra(graf_predavanja, "Ljubljana")
{'Ljubljana': 0, 'Kranj': 26, 'Maribor': 127, 'Koper': 131}
>>> dijkstra(graf_wiki, '1')
{'6': 11, '5': 20, '1': 0, '4': 20, '3': 9, '2': 7}

graf_predavanja je graf mest s predavanj kot zgoraj, graf_wiki pa graf z Wikipedije.

2. podnaloga

Poleg dolžin najkrajših poti bi bilo koristno vedeti tudi katera vozlišča se na poteh nahajajo. Najkrajše poti bomo shranjevali na premeten način. Namesto da bi poti shranjevali kot slovar seznamov, jih bomo shranili kot slovar predhodnih vozlišč predhodnik. Tako pot od s do v izračunamo kot predhodnik[v], predhodnik[predhodnik[v]], predhodnik[predhodnik[predhodnik[v]]], itn., dokler ne zadanemo vozlišča s. Pot od s do s, tj., predhodnik[s] nastavimo na None.

Sestavi funkcijo dijkstra_s_potmi(graf, s), ki poleg slovarja najkrajših poti, kot v prejšnji nalogi, vrne še slovar predhodnik, kot je opisano zgoraj.

>>> dijkstra_s_potmi(graf_predavanja, "Ljubljana")
({'Koper': 131, 'Maribor': 127, 'Kranj': 26, 'Ljubljana': 0}, {'Koper': 'Kranj', 'Maribor': 'Ljubljana', 'Kranj': 'Ljubljana', 'Ljubljana': None})
>>> dijkstra_s_potmi(graf_wiki, '1')
({'1': 0, '5': 20, '2': 7, '4': 20, '3': 9, '6': 11}, {'1': None, '5': '6', '2': '1', '4': '3', '3': '1', '6': '3'})

Iskalno drevo

Ena od možnih implementacij iskalnega drevesa

Iskalna drevesa

Razred IskalnoDrevo je podoben razredu Drevo. Njegov konstruktor __init__ sprejme iterator in sestavi drevo, ki ga dobimo, če elemente seznama po vrsti vstavljamo v iskalno drevo.

Razredu smo dodali tudi metodo pravilno, ki vrne True, če je drevo res iskalno (torej, če so v levem poddrevesu vsi podatki manjši, v desnem pa vsi večji od podatka v korenu).

1. podnaloga

Sestavite metodo dodaj(self, podatek), ki v iskalno drevo vstavi nov podatek. Konstruktor kliče metodo dodaj; konstruktor ne bo deloval, dokler ne napišete pravilne implementacije metode dodaj. Zgled:

>>> d = IskalnoDrevo([6, 9, 4, 7, 5, 1, 3])
>>> d
IskalnoDrevo(6,
    levo = IskalnoDrevo(4,
                levo = IskalnoDrevo(1,
                                levo = IskalnoDrevo(),
                                desno = IskalnoDrevo(3)),
                desno = IskalnoDrevo(5)),
    desno = IskalnoDrevo(9,
                    levo = IskalnoDrevo(7),
                    desno = IskalnoDrevo()))

2. podnaloga

Sestavite metodo poisci(self, podatek), ki v iskalnem drevesu poišče podatek. Vrne naj drevo, ki ga vsebuje v korenu, oziroma None, če ga ni v drevesu. Zgled:

>>> d = IskalnoDrevo([6, 9, 4, 7, 5, 1, 3])
>>> d.poisci(9)
IskalnoDrevo(9,
      levo = IskalnoDrevo(7),
      desno = IskalnoDrevo())
>>> d.poisci(11) is None
True

3. podnaloga

Sestavite generator po_vrsti(self), ki našteje vse podatke v drevesu od najmanjšega do največjega. Generator naj vrača vrednosti. Zgled:

>>> d = IskalnoDrevo([6, 9, 4, 7, 5, 1, 3])
>>> [x for x in d.po_vrsti()]
[1, 3, 4, 5, 6, 7, 9]

Iskalna drevesa - vse naloge

Implementacija

1. podnaloga

Ko boste odprli datoteko, bo spodaj napisana implementacija dvojiškega iskalnega drevesa. V implementaciji metoda vstavi ne stori nič. Popravi jo, da bo na ustrezno mesto vstavila nov ključ. Primer:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> d
Vozlisce(6,
    levo = Vozlisce(4,
                levo = Vozlisce(1,
                                levo = Vozlisce(),
                                desno = Vozlisce(3)),
                desno = Vozlisce(5)),
    desno = Vozlisce(9,
                    levo = Vozlisce(7),
                    desno = Vozlisce()))

Iskanje podatkov

1. podnaloga

Sestavite funkcijo vrni(drevo, podatek), ki v iskalnem drevesu drevo poišče podatek. Vrne naj drevo, ki ga vsebuje v korenu, oziroma None, če ga ni v drevesu. Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> vrni(d, 9)
Vozlisce(9,
      levo = Vozlisce(7),
      desno = Vozlisce())
>>> vrni(d, 11)
None

2. podnaloga

Sestavite funkcijo maksimum(drevo), ki v iskalnem drevesu poišče in vrne največji ključ. Če je drevo prazno naj vrne niz "Drevo je prazno." Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> mmaksimum(d)
9

>>> d = IskalnoDrevo()
>>> maksimum(d)
"Drevo je prazno."

3. podnaloga

Sestavite funkcijo minimum(drevo), ki v iskalnem drevesu poišče in vrne najmanjši ključ. Če je drevo prazno naj vrne niz "Drevo je prazno." Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> minimum(d)
1

>>> d = IskalnoDrevo()
>>> minimum(d)
"Drevo je prazno."

Prednik, ...

1. podnaloga

Sestavite funkcijo prednik(drevo, kljuc), ki v iskalnem drevesu poišče in vrne prednika vozlisca z vrednostjo kljuc. Če prednika ni, naj vrne None. Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> prednik(d, 7)
6
>>> prednik(d, 1)
None

2. podnaloga

Sestavite funkcijo naslednik(drevo, kljuc), ki v iskalnem drevesu poišče in vrne naslednika vozlisca z vrednostjo kljuc. Če naslednika ni, naj vrne None. Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> naslednik(d, 7)
9
>>> naslednik(d, 9)
None

3. podnaloga

Sestavite funkcijo floor(drevo, podatek), ki v iskalnem drevesu poišče in vrne največji ključ, ki je manjši ali enak danemu številu podatek. Če takega števila ni, naj funkcija vrne inf. Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> floor(d, 2)
1
>>> floor(d, 0)
inf

4. podnaloga

Sestavite funkcijo ceil(drevo, podatek), ki v iskalnem drevesu poišče in vrne najmanjsi ključ, ki je večji ali enak danemu številu podatek. Če takega števila ni, naj funkcija vrne -inf. Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> ceil(d, 2)
3
>>> ceil(d, 10)
-inf

Brisanje

1. podnaloga

Sestavite funkcijo izbrisi_minimum(drevo), ki v iskalnem drevesu izbriše najmanjši ključ. Če je drevo prazno, naj funkcija ne naredi ničesar. Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> izbrisi_minimum(d)
>>> d
Vozlisce(6,
    levo = Vozlisce(4,
                levo = Vozlisce(3),
                desno = Vozlisce(5)),
    desno = Vozlisce(9,
                    levo = Vozlisce(7),
                    desno = Vozlisce()))

2. podnaloga

Sestavite funkcijo izbrisi_maksimum(drevo), ki v iskalnem drevesu izbriše največji ključ. Če je drevo prazno, naj funkcija ne naredi ničesar. Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> izbrisi_maksimum(d)
>>> d
Vozlisce(6,
    levo = Vozlisce(4,
                levo = Vozlisce(1,
                                levo = Vozlisce(),
                                desno = Vozlisce(3)),
                desno = Vozlisce(5)),
    desno = Vozlisce(7))

3. podnaloga

Sestavite funkcijo izbrisi(drevo, podatek), ki v iskalnem drevesu izbriše ključ podatek po Hibbardovemu algoritmu. Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> izbrisi(d, 6)
>>> d
IskalnoDrevo(7,
    levo = IskalnoDrevo(4,
                levo = IskalnoDrevo(1,
                                levo = IskalnoDrevo(),
                                desno = IskalnoDrevo(3)),
                desno = IskalnoDrevo(5)),
    desno = IskalnoDrevo(9))

Sestavi iskalno drevo

1. podnaloga

Sestavite funkcijo visina(drevo), ki vrne višino drevesa drevo. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> visina(d)
 4

2. podnaloga

Sestavite funkcijo sestavi_drevo(podatki), ki vrne iskalno drevo najmanjše možne višine s podatki podanimi v urejeni tabeli podatki. Zgled:

 >>> d = sestavi_drevo([1,2,3,4,5,6,7])
 >>> d
 IskalnoDrevo(4,
       levo = IskalnoDrevo(2,
                    levo = IskalnoDrevo(1),
                    desno = IskalnoDrevo(3)),
       desno = IskalnoDrevo(6,
                    levo = IskalnoDrevo(5),
                    desno = IskalnoDrevo(7)))
 >>> visina(d)
 3

Izpiši

1. podnaloga

Sestavite generator izpisi_narascajoce(drevo), ki vrača ključe v drevesu drevo v naraščajočem vrstnem redu. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> [x for x in izpisi_narascajoce(d)]
 [1, 2, 4, 5, 6, 10]

2. podnaloga

Sestavite generator izpisi_padajoce(drevo), ki vrača ključe v drevesu drevo v padajočem vrstnem redu. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> [x for x in izpisi_padajoce(d)]
 [10, 6, 5, 4, 2, 1]

3. podnaloga

Sestavite generator kljuci(drevo, a, b), ki vrača ključe večje ali enake a in manjše ali enake b v drevesu drevo. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> [x for x in kljuci(d, 3, 5)]
 [4, 5]

Rang

1. podnaloga

Sestavite funkcijo stevilo_vozlisc(drevo), ki vrne število vozlišč v drevesu drevo. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> stevilo_vozlisc(d)
 6

2. podnaloga

Sestavite funkcijo rang(drevo, kljuc), ki vrne rang ključa, tj. kateri po vrsti je dani kljuc, če ključe drevesa zložimo v naraščajočem vrstnem redu. Predpostavimo, da dani ključ v drevesu obstaja. Šteti začnemo z 0! Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> rang(d, 6)
 4

3. podnaloga

Sestavite funkcijo k_ti(drevo, k), vrne ključ ranga k. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> k_ti(d, 4)
 6

Najmanjši skupni prednik

1. podnaloga

Najmanjši skupni prednik dveh vozlišč a in b je najnižje vozlišče, ki ima dani vozlišči za potomca. Privzeli bomo, da je vozlišče tudi potomec samega sebe. Sestavite funkcijo najmanjsi_skupni_prednik(drevo, a, b), ki vrne tisti ključ v drevesu, ki je skupni prednik podatkov a in b. Zgled:

 >>>d = IskalnoDrevo()
 >>>for x in [20,8,22,4,12,10,14]:
 >>>    d.vstavi(x)
 >>>najmanjsi_skupni_prednik(d, 10, 14)
 12
 >>> najmanjsi_skupni_prednik(d, 14, 8)
 8

Iskalna drevesa

Implementacija

1. podnaloga

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> d
Vozlisce(6,
    levo = Vozlisce(4,
                levo = Vozlisce(1,
                                levo = Vozlisce(),
                                desno = Vozlisce(3)),
                desno = Vozlisce(5)),
    desno = Vozlisce(9,
                    levo = Vozlisce(7),
                    desno = Vozlisce()))

Iskanje podatka

1. podnaloga

Sestavite funkcijo vrni(drevo, podatek), ki v iskalnem drevesu drevo poišče podatek. Vrne naj drevo, ki ga vsebuje v korenu, oziroma None, če ga ni v drevesu. Zgled:

>>> d = IskalnoDrevo()
>>> for x in [6, 9, 4, 7, 5, 1, 3]:
>>>     d.vstavi(x)
>>> vrni(d, 9)
Vozlisce(9,
      levo = Vozlisce(7),
      desno = Vozlisce())
>>> vrni(d, 11)
None

Izpiši

1. podnaloga

Sestavite generator kljuci(drevo, a, b), ki vrača ključe večje ali enake a in manjše ali enake b v drevesu drevo. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> [x for x in kljuci(d, 3, 5)]
 [4, 5]

Rang

1. podnaloga

Sestavite funkcijo stevilo_vozlisc(drevo), ki vrne število vozlišč v drevesu drevo. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> stevilo_vozlisc(d)
 6

2. podnaloga

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> rang(d, 6)
 4

3. podnaloga

Sestavite funkcijo k_ti(drevo, k), vrne ključ ranga k. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> k_ti(d, 4)
 6

Najmanjši skupni prednik

1. podnaloga

 >>>d = IskalnoDrevo()
 >>>for x in [20,8,22,4,12,10,14]:
 >>>    d.vstavi(x)
 >>>najmanjsi_skupni_prednik(d, 10, 14)
 12
 >>> najmanjsi_skupni_prednik(d, 14, 8)
 8

AVL drevesa

Ravnotežnostni faktor

1. podnaloga

Sestavite funkcijo ravnoteznostni_faktor(vozlisce), vrne ravnotežnostni faktor drevesa, ki ima vozlisce za koren. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> ravnoteznostni_faktor(d.koren)
 1

2. podnaloga

Sestavite funkcijo je_uravnotezeno(vozlisce), ki preveri ali je drevo, ki ima vozlisce za koren, uravnoteženo po višini. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> je_uravnotezeno(d.koren)
 False

3. podnaloga

Sestavite funkcijo najvecji_ravnoteznostni_faktor(vozlisce), ki vrne poddrevo drevesa, ki ima vozlisce za koren, z najveščim ravnotežnostnim faktorjem po absolutni vrednosti. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> najvecji_ravnoteznostni_faktor(d.koren)
 Vozlisce(4,
       levo = Vozlisce(2,
                    levo = Vozlisce(1),
                    desno = Vozlisce()),
       desno = Vozlisce())

4. podnaloga

Sestavite funkcijo je_avl(vozlisce), ki preveri ali je drevo, ki ima 'vozlisce' za koren, AVL drevo. Zgled:

 >>> d = IskalnoDrevo()
 >>> for x in [5, 6, 4, 2, 1, 10]:
 >>>     d.vstavi(x)
 >>> je_avl(d.koren)
 False

Implementacija

V tem sklopu nalog bomo dopolnjevali že delno napisano implementacijo AVL drevesa, ki jo najdete tukaj

1. podnaloga

Sestavite metodo leva_rotacija(self), ki na drevesu izvede rotacijo v levo. Zgled:

>>> d = AVLDrevo()
>>> for x in [3, 5, 7]:
>>>      d.vstavi(x)
>>> d.leva_rotacija()
>>> d
AVLDrevo(5,
      levo = AVLDrevo(3),
      desno = AVLDrevo(7))

2. podnaloga

Sestavite metodo desna_rotacija(self), ki na drevesu izvede rotacijo v desno. Zgled:

>>> d = AVLDrevo()
>>> for x in [7, 5, 3]:
>>>      d.vstavi(x)
>>> d.desna_rotacija()
>>> d
AVLDrevo(5,
      levo = AVLDrevo(3),
      desno = AVLDrevo(7))

3. podnaloga

Sestavite metodo popravi_visine(self), ki ponovno izračuna višine vozlišč. Zgled:

>>> d = AVLDrevo()
>>> for x in [7, 5, 3]:
>>>      d.vstavi(x)
>>> d.desna_rotacija()
>>> d.popravi_visine()
>>> d.visina
1

4. podnaloga

Sestavite metodo popravi_ravnotezja(self), ki ponovno izračuna ravnotežne faktorje vozlišč. Zgled:

>>> d = AVLDrevo()
>>> for x in [7, 5, 3]:
>>>      d.vstavi(x)
>>> d.desna_rotacija()
>>> d.popravi_visine()
>>> d.popravi_ravnotezja()
>>> d.ravnotezje
0

5. podnaloga

Sestavite metodo popravi(self), ki preveri, če se globini levega in desnega poddrevesa preveč razlikujeta, in drevo ustrezno popravi. Ko boste pravilno implementirali metodo popravi, bo metoda vstavi pravilno delovala. Zgled:

>>> d = AVLDrevo()
>>> for x in range(1,7):
>>>      d.vstavi(x)
>>> d
AVLDrevo(4,
      levo = AVLDrevo(2,
                   levo = AVLDrevo(1),
                   desno = AVLDrevo(3)),
      desno = AVLDrevo(5,
                   levo = AVLDrevo(),
                   desno = AVLDrevo(6)))

Globina listov

1. podnaloga

Sestavite funkcijo min_globina(drevo), ki vrne najmanjšo med globinami listov v AVL drevesu. Zgled:

>>> d = AVLDrevo()
>>> for x in range(5):
>>>     d.vstavi(x)
>>> d
AVLDrevo(1,
      levo = AVLDrevo(0),
      desno = AVLDrevo(3,
                    levo = AVLDrevo(2),
                    desno = AVLDrevo(4)))
>>> min_globina(d)
2

2. podnaloga

Sestavite funkcijo max_globina(drevo), ki vrne največjo med globinami listov v AVL drevesu. Zgled:

>>> d = AVLDrevo()
>>> for x in range(5):
>>>     d.vstavi(x)
>>> d
AVLDrevo(1,
      levo = AVLDrevo(0),
      desno = AVLDrevo(3,
                    levo = AVLDrevo(2),
                    desno = AVLDrevo(4)))
>>> max_globina(d)
3

3. podnaloga

Sestavite funkcijo povprecna_globina(drevo), ki vrne povprecje globin listov v AVL drevesu zaokroženo na dve decimalni mesti. Namig: najprej sestavite pomožni funkciji, ki izračunata vsoto globin listov in število listov v drevesu. Zgled:

>>> d = AVLDrevo()
>>> for x in range(5):
>>>     d.vstavi(x)
>>> d
AVLDrevo(1,
      levo = AVLDrevo(0),
      desno = AVLDrevo(3,
                    levo = AVLDrevo(2),
                    desno = AVLDrevo(4)))
>>> povprecna_globina(d)
2.67

4. podnaloga

Sestavite funkcijo opt_min_globina(s), ki vrne minimalno globino listov v popolnoma uravnoteženem drevesu s s vozlišči. Zgled:

>>> opt_min_globina(9)
3

5. podnaloga

Sestavite funkcijo opt_max_globina(s), ki vrne maksimalno globino listov v popolnoma uravnoteženem drevesu s s vozlišči. Zgled:

>>> opt_max_globina(9)
4

6. podnaloga

Sestavite funkcijo opt_povprecna_globina(s), ki vrne povprecno globino listov v popolnoma uravnoteženem drevesu s s vozlišči. Zgled:

>>> opt_povprecna_globina(9)
3.4

7. podnaloga

Sestavite funkcijo odstopanja(drevo), ki vrne trojico števil (min, max, povp). Število min pove, za koliko odstotkov (zaokroženo na celi del) se minimalna globina listov razlikuje od optimalne minimalne globine drevesa z enakim številom vozlišč kot drevo. Podobno za max in povp. Zgled:

>>> d = AVLDrevo()
>>> for x in [8, 5, 11, 3, 6, 10, 12, 2, 4, 7, 9, 13, 1]:
>>>     d.vstavi(x)
>>> odstopanja(d)
(33, 25, 9)

Kopica

Naslednje naloge reši z uporabo kopic. Za osnovo vzemi implementacijo, ki jo najdeš na spletni učilnici in jo po potrebi dopolni.

Sestavljanje kopice

1. podnaloga

Sestavi funkcijo sestavi_in_vrni(navodila), ki bo po danih navodilih sestavljala kopico in vrnila zahtevani seznam števil rezultat. navodila so podana v obliki seznama, ki ga interpretiramo na naslednji način:

če naletimo na število 1, v kopico vstavimo naslednji element v seznamu,
če naletimo na število 2, iz kopice odstranimo naslednji element v seznamu, če tega števila ni, v rezultat dodamo -1
če naletimo na število 3, v rezultat vstavimo največji element v kopici,
če naletimo na število 4, v rezultat vstavimo najmanjši element v kopici.

Primer: navodila = [1, 5, 1, 9, 1, 6, 3, 2, 1] V kopico vstavimo števila 5, 9 in 6, nato v rezultat dodamo število 9, ki je trenutno največje število v kopici, nato izbrišemo število 1 iz kopice, ker pa tega števila v kopici ni, v rezultat dodamo -1. Zgled:

 >>> sestavi_in_vrni([1, 5, 1, 9, 1, 6, 3, 2, 1])
 [9, -1]

Nogometna tekma

1. podnaloga

Mihec zelo rad spremlja nogometne tekme. Njegov najljubši klub je Manchester United, ki je prišel v finale Lige prvakov, ki bo potekal na stadionu Wembley v Londonu. Mihec se je odločil, da bo si bo tekmo ogledal v živo. Ko je prišel do stadiona, je videl, da v vrsti za nakup vstopnic stoji veliko navijačev. Vedel je, da je na stadionu M vrst z različnim številom sedežev. Cena vstopnice je odvisna od izbire vrste. Če je v vrsti še K praznih sedežev, potem je cena vstopnice K evrov. Vstopnice navijačem v vrsti prodajajo eno po eno.

Sestavi funkcijo max_dobicek(n, kapacitete), ki glede na dane kapacitete vrne največji možni dobiček od prodaje n vstopnic. kapacitete so podane v obliki seznama, kjer i-to število predstavlja število prostih sedežev v i-ti vrsti. Zgled:

 >>> max_dobicek(4, [1, 2, 4])
 11

Priljubljene teme

1. podnaloga

Franček poskuša razviti pripomoček, ki prikazuje priljubjene tematike (podobno kot Facebook). Iz baze podatkov je zbral seznam N tem (njihovih IDjev) in njihove priljubljenosti. Vsak dan se priljubljenost začne šteti z 0 in se spreminja v skladu z naslednjimi pravili: Vsaka objava na določeno temo, temi priljubljenost poveča za 50, vsak "všeček" priljubljenost poveča za 5, komentar poveča priljubljenost za 10, deljenje objave pa priljubljenost poveča za 20. Priljubljene teme se določajo glede na spremembo priljubljenosti. Tema z največjim prirastkom priljubljenosti velja za najbolj priljubljeno temo. Če imata dve temi enak prirastek priljubljenosti, jih uredi glede na ID (višji ID ima prednost).

Franček potrebuje pomoč pri pisanju algoritma, ki bo poiskal top 5 tem. Pomagajte mu in napišite funkcijo popularni(podatki), ki prejme seznam s podatki oblike (ID, trenutna_priljubljenost, število_objav, število_všečkov, število_komentarjev, število_delitev) in vrne seznam parov (ID, nova_priljubljenost) za top 5 tem. Zgled:

 >>> popularni([(1003, 100, 4, 0, 0, 0), (1002, 200, 6, 0, 0, 0), (1001, 300, 8, 0, 0, 0), (1004, 100, 3, 0, 0, 0),
     (1005, 200, 3, 0, 0, 0), (1006, 300, 5, 0, 0, 0), (1007, 100, 3, 0, 0, 0), (999, 100, 4, 0, 0, 0)])
 [(1003, 200), (1002, 300), (1001, 400), (999, 200), (1007, 150)]

Tekmovanje

1. podnaloga

Kralj duhcev je zelo razočaran, ker so se jih ljudje na Zemlji prenehali bati. Kralj ve, zakaj je prišlo do tega. Duhci so postali preleni in ljudi ne strašijo več. Zato se je odločil, da bo duhce spodbudil s tekomovanjem. Tekmovanje bo trajalo N dni, tekmovalo pa bo `M˙ duhcev, za katere velja:

najmlajši je star 1 leto,
najstarejši je star M let,
nobena dva duhca nista iste starosti,
starost vsakega duhca je pozitivno celo število.

Vsak dan tekmovanja, morajo duhci obiskati Zemljo in strašiti ljudi. Na koncu vsakega dne je duhcu, ki je prestrašil največ ljudi v tistem dnevu, podeljen naslov "Duhec dneva". Ko je podeljen naslov, duhcu, ki je do tega dne prejel ta naslov največkrat, kralj podeli še pokal za konsistenco. Če je več duhcev z največjim številom naslovov, je pokal podeljen najstarejšemu izmed njih.

Sestavi funkcijo nagrajenci(m, zmagovalci), ki vrne seznam parov (starost, naslovi), kjer i-ti par predstavlja starost duhca, ki je i-ti dan prejel pokal, in število naslovov, ki jih je do tega dne prejel. Število ´m´predstavlja število duhcev, ki tekmuje, zmagovalci pa je seznam dolžine N, kjer i-to število predstavlja starost prejemnika naslova "Duhec dneva" na i-ti dan. Zgled:

 >>> nagrajenci(5, [1, 3, 1, 3, 2, 2, 2])
 [(1, 1), (3, 1), (1, 2), (3, 2), (3, 2), (3, 2), (2, 3)]

Nov sklop

Uvod

Vlečenje vrvi

1. podnaloga

>>> razdeli([95, 82, 87, 102, 75])
197

če je i == len(mase), smo obravnavli vse, in vrnemo levi
če bi dali i-tega na levo in bi s tem leva skupina presegla skupaj//2, potem ga damo na desno
sicer rekurzivno preizkusimo obe možnosti (i-tega damo na levo ali na desno) ter se odločimo za boljšo od obeh možnosti.

2. podnaloga

Če zgornjo rešitev preizkusite na seznamih dolžine 25 ali več, boste ugotovili, da deluje izjemno počasi. Kakšna je njena časovna zahtevnost?

Sestavite funkcijo razdeli_dinamicno(mase), ki naredi isto kot prejšnja funkcija, le da se reševanja tokrat lotite z dinamičnim programiranjem. Zgled:

>>> razdeli_dinamicno([95, 82, 87, 102, 75])
197

Funkcijo preizkusite na seznamu dolžine 50 in na seznamu dolžine 100.

0 ∈ mozna, če damo vse udeležence v eno skupino
če imamo udeleženca z maso k, ki ga še nismo obravnavali, in je i ∈ mozna, potem velja tudi (i+k) ∈ mozna.

Ko enkrat imamo tabelo mozna, poisčemo največji indeks i, ki je manjši ali enak skupaj//2 in je mozna[i] == True.

3. podnaloga

Prejšnja funkcija nam izračuna maso manjše skupine, nič pa ne izvemo o tem, kdo so udeleženci, ki tvorijo to skupino. Sestavite še funkcijo razdeli_udelezence(mase), ki vrne seznam mas udeležencev, ki sestavljajo manjšo od obeh skupin. Če je rešitev več, lahko funkcija vrne katerekoli rešitev. Zgled:

>>> razdeli_udelezence([95, 82, 87, 102, 75])
[102, 95]

Maksimalna neodvisna podmnožica

Pot

1. podnaloga

Definiraj funkcijo maks_podmnozica_pot(pot), ki vrne največjo neodvisno množco za podano pot. Seznam števil `pot predstavlja vrednosti na posameznih vozliščih poti. Vozlišča so povezana v vrstnem redu v katerem se pojavljajo v seznamu. For example:

>>> maks_podmnozica_pot([1, 2])
2
>>> maks_podmnozica_pot([1, 0, -2, 4, 5, 2])
7

2. podnaloga

Definiraj funkcijo maks_podmnozica_cikel(cikel), ki vrne največjo neodvisno množco za podan cikel. Seznam števil cikel predstavlja vrednosti na posameznih vozliščih cikla. Vozlišča so povezana v vrstnem redu v katerem se pojavljajo v seznamu, dodatno pa je prvo vozlišče povezano z zadnjim For example:

>>> maks_podmnozica_cikel([1, 2])
2
>>> maks_podmnozica_cikel([1, 2, 3, 1])
4

3. podnaloga

Definiraj funkcijo maks_podmnozica_lestev(zgornji, spodnji), ki vrne največjo neodvisno množco za podan graf lestev, ki jo predstavljata seznama števil zgornji in spodnji. Lestev je graf, ki ga sestavljata dve vzporedni (disjunktni) poti, dodatno pa so med seboj povezana istoležeča vozlišča. Uteži na lestvi so predstavljene s seznamom zgornji, ki predstavlja uteži na zgornji poti, ter seznamom spodnji, ki predstavlja uteži na spodnji poti. Na primer:

>>> maks_podmnozica_lestev([1], [2])
2
>>> maks_podmnozica_lestev([1, 2], [2, 1])
4

4. podnaloga

Definiraj funkcijo rekonstrukcija_maks_podmnozica_pot(pot), ki vrne največjo neodvisno množico za podano pot. Rezultat naj bo seznam indeksov elementov, ki jih vključimo v množico. Indeksi naj bodo v naraščajočem vrstnem redu For example:

>>> rekonstrukcija_maks_podmnozica_pot([1, 2])
[1]
>>> rekonstrukcija_maks_podmnozica_pot([1, 0, -2, 4, 5, 2])
[0, 3, 5]

5. podnaloga

Definiraj funkcijo stevilo_maks_podmnozic_pot(pot), ki vrne število maksimalnih neodvisnih podmnožic v poti For example:

>>> stevilo_maks_podmnozic_pot([1, 2])
1
>>> stevilo_maks_podmnozic_pot([1, 0, -2, 4, 5, 2, 1])
2

6. podnaloga

Ob stranici pravokontnega travnika želimo posaditi jablane. Ob celotnem robu travnika smo izvedli meritve zemlje ter drugih pogojev iz česar smo dobilo neko številko, ki nam predstavlja ustreznost za rast jablan. Lahko se tudi zgodi, da so pogoji za rast jablane preslabi. V tem primeru zabeležimo None. Naš cilj je posaditi jablane na mestih, kjer se nam najbolj splača. Meritve smo izvedli na vsak meter stranice travnika. Vendar pa jablane ne morejo rasti tako blizu. Med dvema jablanama mora biti vsaj 2 metra razdalje.

Definiraj funkcijo posadi_jablane(pogoji), ki vrne lokacije, kjer se nam najbolj splača posaditi jablane za danimi pogoji pogoji. For example:

>>> posadi_jablane([0.5, 2, 1.3])
[1]
>>> posadi_jablane([0.8, 1, None, 1.5, 4])
[1, 4]

Računalništvo 2 VAJE

Matija LOKAR

2024-2025

Dinamično programiranje

Žabica

1. podnaloga

Minsko polje

1. podnaloga

Jajca

1. podnaloga

2. podnaloga

3. podnaloga

4. podnaloga

Vlečenje vrvi

1. podnaloga

2. podnaloga

3. podnaloga

Palindromi

1. podnaloga

2. podnaloga

3. podnaloga

4. podnaloga

Postavljanje oklepajev

1. podnaloga

2. podnaloga

3. podnaloga

Poti v matriki

1. podnaloga

2. podnaloga

3. podnaloga

Posode zlata

1. podnaloga

2. podnaloga

Tekmovanje - Nahrbtnik

01 Nahrbtnik

1. podnaloga

2. podnaloga

3. podnaloga

4. podnaloga

5. podnaloga

6. podnaloga

7. podnaloga

0_1 Nahrbtnik

0/1 nahrbtnik - 1. del

1. podnaloga

2. podnaloga

3. podnaloga

4. podnaloga

5. podnaloga

0/1 nahrbtnik - 2.del

TODO:

1. podnaloga

2. podnaloga

3. podnaloga

Podzaporedja

Najdaljše padajoče podzaporedje

1. podnaloga

2. podnaloga

3. podnaloga

4. podnaloga

Število najdaljših zaporedij

1. podnaloga

Problem najkrajših poti

Železniške postaje

1. podnaloga

Sherlock

1. podnaloga

Najkrajše poti in skoki

1. podnaloga

Čokolada

1. podnaloga

Popotnik Xenny

1. podnaloga

Ključno vozlišče

1. podnaloga

Luka se igra

1. podnaloga

CryptLand

1. podnaloga

Iskanje najkrajših poti