Ponovitev - OOP

Za utrjevanje znanja iz OOP. Nobena od nalog ne bi smela delati težav! Predlagam, da se o reševanju pogovarjamo tudi v Forumu predmeta!

Kako razširimo razrede

V sledečih nalogah definiramo razred v prvi podnalogi, nato pa ga tekom nadaljnih podnalog razširimo z dodatnimi metodami. Standardni pristop k reševanju takšnih nalog na Tomotu je, da v prvi podnalogi definiramo:

class MojRazred:

    def metoda(...):
        ...

V nadaljnih podnalogah pa razred ponovno definiramo, vendar kot:

class MojRazred(MojRazred):

    def nova_metoda(...):
        ...

Takšna definicija ustvari nov razred (zato ga lahko razširimo), vendar skopira vse definicije metod iz prejšnih podnalog.

1. podnaloga

Na hitro preiskusite zgoraj navedeni postopek, tako da definirate razred TestniRazred in zanj definirajte __init__ metodo, ki nastavi lastnost vrednost na 123. Zgled:

>>> TestniRazred().vrednost
123

2. podnaloga

Sedaj razred razširite z metodo spremeni_vrednost(self, x), ki spremeni vrednost elementa razreda TestniRazred. Zgled:

>>> a = TestniRazred()
>>> a.vrednost
123
>>> a.spremeni_vrednost(321)
>>> a.vrednost
321

Geometrija

Pri tej vaji bomo razvili razrede Vektor, Tocka in Premica, ki predstavljajo vektor, točko in premico v evklidski ravnini. Nekaj metod je že napisanih, nekaj pa jih boste napisali sami.

Najprej si oglejte kodo razredov, ki je prenešena, ko datoteko odprete.

1. podnaloga

Razredu Vektor dodajte metodo __repr__(self). Zgled:

>>> v = Vektor(3, 2)
>>> v
Vektor(3, 2)

Opomba: Če v interaktivni konzoli pokličemo nek objekt, se izpiše niz, ki ga vrne klic metode __repr__ na tem objektu. Priporočilo je, da je niz, ki ga vrne metoda __repr__, veljavna programska koda v Pythonu, ki ustvari identično kopijo objekta.

2. podnaloga

Razredu Vektor dodajte metodo __str__(self). Zgled:

>>> v = Vektor(3, 2)
>>> print(v)
(3, 2)

Opomba: Funkcija print na svojem argumentu pokliče metodo __str__ in izpiše niz, ki ga ta metoda vrne. Metoda __str__ običajno vrne razumljiv opis objekta, ki naj bi ga razumeli tudi ne-programerji.

3. podnaloga

Razredu Vektor dodajte metodo __abs__(self), ki naj vrne dolžino (normo) vektorja. Zgled:

>>> v = Vektor(1, 3)
>>> abs(v)
3.1622776601683795

4. podnaloga

Razredu Vektor dodajte metodo __sub__(self, other), ki vrne razliko vektorjev. Zgled:

>>> v = Vektor(-1, 3)
>>> u = Vektor(2, 1)
>>> u - v
Vektor(-3, 2)

5. podnaloga

V razredu Vektor sestavite metodo __truediv__(self, skalar), ki vrne produkt vektorja self s skalarjem 1 / skalar. Zgled:

>>> Vektor(-1, 3) / 2
Vektor(-0.5, 1.5)

6. podnaloga

V razredu Vektor sestavite metodo sta_pravokotna(self, other), ki vrne True, če sta vektorja self in other pravokotna, in False sicer. Zgled:

>>> v = Vektor(-1, 3)
>>> u = Vektor(2, 1)
>>> v.sta_pravokotna(u)
False

7. podnaloga

V razredu Vektor sestavite metodo rotacija(self, alpha), ki vrne rotacijo vektorja self za kot alpha (v radianih). Zgled:

>>> Vektor(1, 0).rotacija(math.pi/4)
Vektor(0.7071067811865476, 0.7071067811865475)

8. podnaloga

Zunaj vseh razredov sestavite funkcijo projekcija(tocka, premica), ki vrne pravokotno projekcijo točke tocka na premico premica. Zgled:

>>> p = Premica(Tocka(1, 1), Vektor(0, 1))
>>> projekcija(Tocka(3, 0), p)
Tocka(3, 1)

9. podnaloga

Sestavite funkcijo presek(premica1, premica2), ki vrne točko, ki je presek dveh premic. Zgled:

>>> p = Premica(Tocka(3, 4), Vektor(2, -1))
>>> q = Premica(Tocka(0, 1), Vektor(1, 2))
>>> presek(p, q)
Tocka(1.2, 0.4)

10. podnaloga

Sestavite funkcijo zrcali_cez_premico(tocka, premica), ki vrne zrcalno sliko točke tocka čez premico premica. Zgled:

>>> p = Premica(Tocka(1, 1), Vektor(0, 1))
>>> zrcali_cez_premico(Tocka(3, 4), p)
Tocka(3, -2)

Datumi

Koledar, ki ga trenutno uporabljamo v zahodnem svetu, se imenuje gregorijanski koledar. Pri tej nalogi bomo implementirali razred Datum, ki bo omogočal predstavitev datumov v gregorijanskem koledarju in računanje z njimi.

1. podnaloga

Sestavite funkcijo je_prestopno(leto), ki preveri, ali je dano leto prestopno (po gregorijanskem koledarju). Zgled:

>>> je_prestopno(2004)
True
>>> je_prestopno(1900)
False

2. podnaloga

Sestavite funkcijo stevilo_dni(leto), ki vrne število dni v danem letu. Zgled:

>>> stevilo_dni(2015)
365
>>> stevilo_dni(2016)
366

Nasvet: Uporabite funkcijo je_prestopno.

3. podnaloga

Sestavite funkcijo dolzine_mesecev(leto), ki vrne seznam dolžine 12, ki ima za elemente števila dni po posameznih mesecih v danem letu. Zgled:

>>> dolzine_mesecev(2015)
[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

4. podnaloga

Definirajte razred Datum, s katerim predstavimo datum. Najprej sestavite konstruktor __init__(self, dan, mesec, leto). Nastali objekt naj ima atribute dan, mesec in leto. Zgled:

>>> d = Datum(8, 2, 1849)
>>> d.dan
8
>>> d.mesec
2
>>> d.leto
1849

5. podnaloga

Sestavite metodo __str__(self), ki predstavi datum v obliki 'dan. mesec. leto'. Zgled:

>>> d = Datum(8, 2, 1849)
>>> print(d)
8. 2. 1849

6. podnaloga

Sestavite še metodo __repr__(self), ki vrne niz oblike 'Datum(dan, mesec, leto)'. Zgled:

>>> d = Datum(8, 2, 1849)
>>> d
Datum(8, 2, 1849)

7. podnaloga

Sestavite metodo je_veljaven(self), ki preveri, ali je datum veljaven. Zgled:

>>> d1 = Datum(8, 2, 1849)
>>> d1.je_veljaven()
True
>>> d2 = Datum(5, 14, 2014)
>>> d2.je_veljaven()
False

8. podnaloga

Sestavite metodo __lt__(self, other), ki datum primerja z drugim datumom (metoda naj vrne True, če je prvi datum manjši, in False, če ni).

Ta metod omogoča, da lahko datume primerjamo kar z operatorjema < in >. Na primer:

>>> Datum(31, 12, 1999) < Datum(1, 1, 2000)
True

9. podnaloga

Sestavite metodo __eq__(self, other), ki datum primerja z drugim datumom (metoda naj vrne True, če sta datuma enaka, in False, če nista).

Ta metoda omogoča, da lahko datume primerjamo kar z operatorjema == in !=. Na primer:

>>> Datum(31, 12, 1999) != Datum(1, 1, 2000)
True

10. podnaloga

Sestavite metodo dan_v_letu(self), ki izračuna, koliko dni je minilo od začetka leta do danega datuma. Zgled:

>>> d = Datum(1, 11, 2014)
>>> d.dan_v_letu()
305

Nasvet: Ali si lahko kako pomagate s funkcijo dolzine_mesecev?

11. podnaloga

Sestavite metodo razlika(self, other), ki kot argument dobi še en objekt razreda Datum in vrne število dni med datumoma. Dobra rešitev deluje brez uporabe zanke po vseh letih med danima datuma (ima časovno zahtevnost $O(1)$). Zgled:

>>> d1 = Datum(1, 11, 2014)
>>> d2 = Datum(14, 10, 2014)
>>> d1.razlika(d2)
18

Namig: Najprej sestavite pomožno metodo dni_od_zacetka(self), ki izračuna, koliko dni je minilo od "začetka štetja" (leto==0, mesec=1, dan=1). Razliko v dnevih med self in other lahko nato preprosto izračunate z metodo dni_od_zacetka.

Opomba: Gregorijanski koledar seveda ni bil v veljavi leta 0, ampak za potrebe računanja se lahko pretvarjamo, da ga je uporabljal tudi Julij Cezar.

12. podnaloga

Sestavite metodo dan_v_tednu(self), ki vrne številko dneva v tednu (1 = ponedeljek, 2 = torek, …, 7 = nedelja). Lahko si pomagate z Zellerjevim obrazcem. Druga možnost je, da izračunate razliko med datumom self in nekim fiksnim datumom, za katerega že poznate dan v tednu. Zgled:

>>> d = Datum(1, 11, 2014)
>>> d.dan_v_tednu()
6

13. podnaloga

Sestavite statično metodo dan_v_letu_stat(leto, dan), ki za parametra dobi leto in zaporedno številko dneva v letu ter sestavi in vrne ustrezen datum. Zgled:

>>> Datum.dan_v_letu_stat(2014, 305)
Datum(1, 11, 2014)

Koti

1. podnaloga

Sestavi razred Kot z začetno metodo __init__(self, st, m, sek), ki predstavlja kot podane velikosti. Podatke shranite v atribute stopinje, minute in sekunde, pri tem pa minute in sekunde večje od 60 ustrezno pretvorite.

Primer:

>>> a = Kot(15, 65, 100)
>>> a.sekunde
40
>>> a.minute
6
>>> a.stopinje
16

2. podnaloga

Razredu Kot dodaj metodo __str__, ki kot predstavi v berljivi obliki kot° minute' sekunde''.

Primer:

>>> a = Kot(15, 65, 100)
>>> print(a)
16° 6' 40''

3. podnaloga

Razredu dodaj metodo __repr__, ki vrne predstavitev razreda kot niz oblike Kot(st, m, s), kjer so st, m in s stopinje, minute in sekunde kota.

Primer:

>>> a = Kot(15, 65, 100)
>>> a
Kot(16, 6, 40)

4. podnaloga

Razredu dodaj metodo __lt__(self, other), ki primerja dva kota med seboj. Metoda naj vrne True, če je prvi kot manjši od drugega. Kota lahko nato primerjamo z operatorjem <.

Primer:

>>> a = Kot(15, 65, 100)
>>> b = Kot(10, 20, 30)
>>> a < b
False

5. podnaloga

Razredu dodaj metodo __eq__(self, other), ki vrne True, če sta dva kota enaka.

Primer:

>>> a = Kot(15, 65, 100) == Kot(16, 6, 40)
True

6. podnaloga

Razredu dodaj metodo __add__(self, other), ki sešteje dva kota.

Primer:

>>> a = Kot(15, 65, 100)
>>> b = Kot(10, 20, 30)
>>> a + b
Kot(26, 27, 10)

7. podnaloga

Razredu dodaj metodo get(self), ki vrne trojko (st, m, sek).

Primer:

>>> Kot(15, 65, 100).get()
(16, 6, 40)

8. podnaloga

Zunaj razreda sestavi funkcijo suplementaren(kot), ki vrne trojko (stopinje, minute, sekunde) kota, ki je suplementaren danemu kotu. Podatke kota kot pridobi s klicem metode get. Če je dani kot večji od 180°, naj funkcija vrne None

Primer:

>>> a = Kot(10, 20, 30)
>>> suplementaren(a)
(169, 39, 30)

9. podnaloga

Našemu razredu bi radi dodali še metodo povecaj in pomnozi, ki naš kot spremeni (ne vrne novega kota, ampak ustrezno spremeni atribute začetnega kota). Pri obeh metodah bi morali posebej obravnavati primere, ko dobimo prevelike minute ali sekunde. Da bo računanje enostavneje sestavi nov razred Kot2. Začetna metoda __init__(self, st, m, sek) stopinje in minute spremeni v sekunde in celotno vrednost shrani v atribut sekunde.

Primer:

>>> a = Kot2(15, 15, 15)
>>> a.sekunde
54915

10. podnaloga

Razredu Kot2 dodaj metodi povecaj(self, st, m, sek) in pomnozi(self, stevilo). Metoda povecaj naj dani kot poveča za st stopinj, m minut in sek sekund, metoda pomnozi pa naj dani kot pomnozi z danim številom.

Primer:

>>> a = Kot2(15, 15, 15)
>>> a.povecaj(10, 20, 30)
>>> a.sekunde
92145
>>> a.pomnozi(2)
>>> a.sekunde
184290

11. podnaloga

Razredu Kot2 dodaj metodo get, ki naj vrne enako predstavitev kota kot v razredu Kot. Ko bo metoda dodana, bo funkcija suplementaren delovala tudi za kote iz razreda Kot2.

Primer:

>>> a = Kot2(15, 15, 15)
>>> a.get()
(15, 15, 15)
>>> suplementaren(Kot2(115, 5, 40))
(64, 54, 20)

Uporaba dekoratorja 'property'

Pri preprostih razredih pogosto upravljamo direktno z lastnostmi objektov. Če želimo točko s koordinatama x in y premakniti za vektor (1, 0) to storimo tako, da popravimo koordinati. V mnogih primerih pa imajo lastnosti objektov omejitve, ali pa preprosto želimo abstrakcijo implementacije.

V teh primerih do lastnosti ne dostopamo direktno (takšne lastnosti predznačimo z _), temveč za njih spišem posebne metode za dostop. Za lažje delo v Pythonu uporabljamo dekorator @property, ki ga bomo spoznali v naslednjih podnalogah.

1. podnaloga

Točko v polarnih koordinatah podamo s kotom in razdaljo od izhodišča. Pri tem je razdalja nujno pozitivna, kot pa leži na intervalu $[0, 2\pi)$.

Definirajte razred SlabaPolarnaTocka, za katero definirajte metodo __init__(self, r, phi), ki ustvari. Če je razdalja r negativna, jo nastavimo na 0, na kot phi pa gledamo modulo $2\pi$.

>>> a = SlabaPolarnaTocka(-10, 4)
>>> a.r
0
>>> a.phi

2. podnaloga

Napišite primer pokvarjena_tocka, ki pripada razredu SlabaPolarnaTocka ampak ima razdaljo r negativno.

Namig: Ustvarite poljubno točko, in jo pokvarite.

>>> pokvarjena_tocka.r < 0
True

3. podnaloga

Napišite razred BoljsaPolarnaTocka, ki ima namesto lastnosti r lastnost _r (podrčtaj označuje, da je uporabnik ne sme direktno spreminjati). Za dostop do razdalje definirajte metodi nastavi_r(self, r) in vrednost_r(self), ki pravilno upravljata z lastnostjo _r. Metoda __init__ naj že uporablja ti dve metodi za kreacijo točke.

Opomba: Za kot točke se trenutno ne zmenimo (lahko ga tudi izpustite).

>>> a = BoljsaPolarnaTocka(-10, 0)
0
>>> a.nastavi_r(5)
>>> a.vrednost_r()
5

4. podnaloga

Uporaba dodatnih metod za dostop do lastnosti je naporna, zato problem rešimo z dekoratorjem @property. Razred PolarnaTocka ze uporablja @property za razdaljo, vaša naloga pa je, da ta pristop uporabite še za kot.

Če lastnosti definiramo na takšen način, jih lahko uporabljamo kot običajno.

Opomba: Metoda za prikaz vrednosti lastnosti uporablja dekorator @property, metoda za nastavljanje vrednosti pa @ime_lastnosti.setter.

>>> a = PolarnaTocka(-5, 10)
>>> a.phi
0.5752220392306207
>>> a.phi = -2
>>> a.phi
1.1415926535897931

Neusmerjen graf

Naj bo $V$ končna neprazna množica in $E$ družina dvoelementnih podmnožic množice $V$. Paru $G = (V, E)$ pravimo graf na množici vozlišč $V$ in z množico povezav $E$. Pri tej nalogi bomo sestavili razred NeusmerjenGraf za delo z enostavnimi (ni zank in ni vzporednih povezav) neusmerjenimi grafi.

1. podnaloga

Definirajte razred NeusmerjenGraf in sestavite konstruktor __init__, ki sprejme seznam parov seznam_povezav (vsak par predstavlja eno povezavo). Konstruktor naj objektu pripne atribut sosedje, ki naj bo slovar, katerega ključi so oznake vozlišč, vrednost ključa pa je množica sosedov te točke. Zgled:

>>> g = NeusmerjenGraf([(1, 2), (2, 3), (3, 1), (1, 4)])
>>> g.sosedje
{1: {2, 3, 4}, 2: {1, 3}, 3: {1, 2}, 4: {1}}

2. podnaloga

Sestavite metodo slovar_stopenj, ki vrne slovar, katerega ključi so oznake vozlišč, vrednosti pa so njihove stopnje. Zgled:

>>> g = NeusmerjenGraf([(1, 2), (2, 3), (3, 1), (1, 4)])
>>> g.slovar_stopenj()
{1: 3, 2: 2, 3: 2, 4: 1}

3. podnaloga

Sestavite metodo dodaj_vozlisce(self, u), ki v graf doda vozlišče z oznako u. Če vozlišče s to oznako že obstaja, naj metoda ne naredi ničesar. Zgled:

>>> g = NeusmerjenGraf([(1, 2), (2, 3), (3, 1)])
>>> g.dodaj_vozlisce(4)
>>> g.sosedje
{1: {2, 3}, 2: {1, 3}, 3: {1, 2}, 4: set()}}

4. podnaloga

Sestavite metodo odstrani_vozlisce(self, u), ki iz grafa odstrani vozlišče z oznako u in vse povezave, ki imajo u za krajišče. Predpostavi, da je vozlišča u zagotovo v grafu. Zgled:

>>> g = NeusmerjenGraf([(1, 2), (2, 3), (3, 1)])
>>> g.odstrani_vozlisce(3)
>>> g.sosedje
{1: {2}, 2: {1}}

5. podnaloga

Sestavite metodo dodaj_povezavo(self, e), ki v graf doda povezavo e (par vozlišč). Če ta povezava že obstaja, naj metoda ne naredi ničesar. V primeru, če katero od krajišč povezave manjka, še njega dodajte v graf (s klicem metode dodaj_vozlisce). Zgled:

>>> g = NeusmerjenGraf([(1, 2), (2, 3), (3, 1)])
>>> g.dodaj_povezavo((1, 4))
>>> g.sosedje
{1: {2, 3, 4}, 2: {1, 3}, 3: {1, 2}, 4: {1}}

6. podnaloga

Sestavite še metodo odstrani_povezavo(self, e), ki iz grafa odstrani povezavo e (par vozlišč). Predpostavi, da je povezava e zagotovo v grafu. Zgled:

>>> g = NeusmerjenGraf([(1, 2), (2, 3), (3, 1)])
>>> g.odstrani_povezavo((1, 2))
>>> g.sosedje
{1: {3}, 2: {3}, 3: {1, 2}}

Bitni cekini

Trenutno je na spletu zelo popularna digitalna valuta Bitcoin. Osnova za pošteno uporabo take valute so zapleteni kriptografski protokoli, mi pa bomo ubrali malo bolj poenostavljeno različico ter sestavili razred BitniCekin, s katerim bomo predstavili račun nekega lastnika te valute.

1. podnaloga

Sestavite razred BitniCekin s konstruktorjem __init__(self, stanje), ki sprejme začetno stanje na računu (v valuti Bitcoin). Atribut, v katerega shranite stanje, naj bo poimenovan _stanje.

Parameter konstruktorja stanje naj bo neobvezen in v primeru, ko ni podan, naj bo začetno stanje enako nič.

2. podnaloga

Sestavite metodo __str__(self), ki predstavi stanje na računu v obliki: 'Število bitnih cekinov na računu: ...'

Zgled:

>>> racun = BitniCekin(6)
>>> print(racun)
Število bitnih cekinov na računu: 6

3. podnaloga

Sestavite metodi dvig(self, koliko) in polog(self, koliko), ki dvigneta oz. položita ustrezno količino bitnih cekinov na račun. Predpostavimo, da bo vrednost argumenta koliko vedno nenegativno celo število.

Pri metodi dvig upoštevajte, da stanje na računu ne sme biti negativno. V takšnem primeru se dvig ne sme izvesti.

Metoda dvig naj vrne True, če je dvig uspel in False, če ni. Metoda polog naj spremeni stanje in vrne stanje na računu po pologu.

4. podnaloga

Sestavite funkcijo prenesi(racun1, racun2, koliko), ki iz računa racun1 prenese koliko cekinov na račun racun2. Funkcija prenesi naj ne bo znotraj razreda BitniCekin, saj ni objektna metoda, ampak je čisto običajna funkcija. Spremenljivki racun1 in racun2 sta seveda objekta tipa BitniCekin, kar ni potrebno preverjati!

Če na računu racun1 ni dovolj denarja, se transakcija ne sme izvršiti, torej mora stanje na obeh računih ostati nespremenjeno. Funkcija naj vrne uspešnost transakcije (True, če je transakcija uspela, in False, če ni).

Redki vektorji

Vektorjem, ki vsebujejo veliko število ničelnih elementov, pravimo redki vektorji. Namesto običajne predstavitve, pri kateri navedemo vse elemente vektorja, lahko uporabimo bolj kompaktno predstavitev, kjer ničelne elemente izpustimo, za neničelne pa si zapomnimo, na katerih mestih so.

Na primer, vektor

a = [1, 0, 0, 0, 0, 5, 1, 0, 0, 0, 4, 0, 0]

lahko namesto v obliki dolgega seznama z veliko ničlami zapišemo v kompaktni obliki kot slovar, kjer so ključi indeksi neničelnih elementov iz dolgega zapisa:

r = {0: 1, 10: 4, 5: 5, 6: 1}

Vrstni red indeksov seveda ni pomemben, saj imamo slovar. Ničelni vektor predstavimo kar s praznim slovarjem {}.

1. podnaloga

Napišite funkcijo stisni(vektor), ki sprejme vektor kot seznam števil ter vrne redko obliko vektorja, tj. slovar, v katerem so ključi indeksi neničelnih vrednosti, vrednosti pa te neničelne vrednosti.

Primer:

>>> stisni([1, 0, 0, 0, 0, 5, 1, 0, 0, 0, 4])
{0: 1, 10: 4, 5: 5, 6: 1}
>>> stisni([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 99])
{0: 1, 15: 99}

2. podnaloga

Definirajte razred Vektor, s katerim bomo predstavili redke vektorje. Sestavite konstruktor, ki kot parameter sprejme vektor v stisnjeni obliki (slovar) ter ga priredi atributu elementi.

Sestavite še metodo __len__, ki vrne število neničelih elementov redkega vektorja. Metoda nima argumentov (razen obveznega argumenta self, ki pove, da gre za metodo danega razreda). Metoda __len__ se bo izvedla, kadar bomo na objektu tipa Vektor uporabili Pythonovo vgrajeno funkcijo len, kot je prikazano v spodnjem primeru.

Primer:

>>> a = Vektor({0: 1, 10: 4, 5: 5, 6: 1})
>>> a.elementi
{0: 1, 10: 4, 5: 5, 6: 1}
>>> len(a)
4

3. podnaloga

Definirajte metodi __add__ in __sub__, s katerima boste definirali operatorja + in - nad objekti tipa Vektor. Gre za običajno seštevanje in odštevanje vektorjev, le da morate upoštevati, da seštevamo oz. odštevamo redki obliki, ki sta predstavljeni s slovarjema.

Vsaka od metod sprejema en argument in sicer drugi vektor, ki nastopa v aritmetični operaciji, vrne pa naj nov objekt tipa Vektor, ki je vsota oz. razlika danih vektorjev.

Nasvet: Upoštevajte, da so v rezultatu lahko neničelne vrednosti le na tistih indeksih, pri katerih je neničeln vsaj en od obeh operandov – pomagajte si z unijo obeh množic indeksov.

Primer:

>>> a = Vektor({0: 1})
>>> b = Vektor({0: 1, 3: 1})
>>> c = a + b
>>> c.elementi
{0: 2, 3: 1}

4. podnaloga

Definirajte še metodo razsiri, ki vrne običajno (dolgo) obliko vektorja. Pri tem se razširjena oblika ne sme končati z 0, saj drugače razširitev ni enolična (glej drugi primer!).

Primer:

>>> a = Vektor(stisni([1, 0, 0, 0, 0, 0, 0, 0, 9]))
>>> a.elementi
{0: 1, 8: 9}
>>> a.razsiri()
[1, 0, 0, 0, 0, 0, 0, 0, 9]
>>> Vektor(stisni([1, 0, 0, 0])).razsiri()
[1]

Polinomi

Definirajte razred Polinom, s katerim predstavimo polinom v spremenljivki $x$. Polinom predstavimo s seznamom njegovih koeficientov, kjer je $k$-ti element seznama koeficient pri $x^k$. Na primer, polinom $x^3 + 2 x + 7$ predstavimo s Polinom([7, 2, 0, 1]). Razmislite, kaj predstavlja Polinom([]). Zadnji koeficient v seznamu mora biti neničelen.

1. podnaloga

Sestavite začetno metodo __init__(self, koef), ki nastavi tabelo koeficientov. ta naj bo v lastnosti _koef.

2. podnaloga

Razred Polinom dopolnite z metodo stopnja, ki vrne stopnjo polinoma. Stopnja ničelnega polinoma je v matematiki po dogovoru $-\infty$, pri nas pa bo $-1$.

3. podnaloga

Sestavite metodo __eq__ za primerjanje polinomov.

4. podnaloga

Sestavite metodo __add__ za seštevanje polinomov. Pozor: pri seštevanju se lahko zgodi, da se nekateri začetni koeficienti pokrajšajo: $(x^3 + 2 x + 7) + (- x^3 - 2 x + 10) = 17$

5. podnaloga

Sestavite metodo __mul__ za množenje polinomov.

6. podnaloga

Sestavite metodo __str__, ki predstavi polinom v čitljivi obliki.

>>> print(Polinom([1, -2, 3, -1]))
-x^3 + 3 x^2 - 2 x + 1
>>> print(Polinom([-1, 0, 0, 1]))
x^3 - 1

Bakterije

1. podnaloga

Definirajte razred Bakterija, s katerim bomo predstavili bakterije. Sestavite konstruktor, ki kot parameter sprejema niz, ki opisuje genski zapis bakterije in ta niz priredi atributu DNA.

Preveriti pa morate, če je dani genski zapis veljaven, se pravi, da vsebuje samo črke 'A','G','C','T' (okrajšave za Adenin, Gvanin, Citozin in Timin). Če niz ni veljaven, naj atribut DNA postane prazen niz. Konstruktor mora narediti tudi atribut generacija, ki naj dobi začetno vrednost 0.

Primer:

>>> a = Bakterija('GAAATCGGT')
>>> a.DNA
'GAAATCGGT'
>>> a.generacija
0

Primer z neveljavnim genskim zapisom:

>>> a = Bakterija('ABCDEFGH')
>>> a.DNA
''

2. podnaloga

Bakterije se zelo rade delijo. Običajne bakterije se delijo tako, da iz ene nastaneta dve novi, naše bakterije pa so posplošene bakterije, ki se lahko delijo na poljubno število novih bakterij. Pri tem se njihov genski zapis prekopira, poveča pa se števec generacije.

Definirajte metodo __floordiv__, s katero je definirana operacija // (celoštevilčno deljenje). Metoda sprejema le en parameter (delitelj), ki pove, koliko bakterij dobimo po delitvi. Metoda mora vrniti tabelo novih bakterij, ki imajo isti DNA kot začetna bakterija, imajo pa povečan števec generacije. Pri tem morate upoštevati še, da se bakterije s praznim genskim zapisom ne morejo deliti. V takšnem primeru naj metoda vrne prazno tabelo.

Primer:

>>> a = Bakterija('GAAATCGGT')
>>> nove_bakterije = a//3
>>> len(nove_bakterije)
3
>>> print(nove_bakterije)
[<__main__.Bakterija object at 0x7ffd41edac50>, <__main__.Bakterija object at 0x7ffd41edab90>, <__main__.Bakterija object at 0x7ffd41edab50>]
>>> nove_bakterije[0].generacija
1
>>> nove_bakterije[0].DNA
'GAAATCGGT'

3. podnaloga

Bakterije se lahko tudi združujejo. Pri tem nastane nova bakterija, katere genski zapis je kombinacija genskih zapisov obeh bakterij, ki nastopata v združevanju. Zapis se združuje po takšnem pravilu: izmenično se jemlje po eno črko iz obeh genskih zapisov, ko pa pridemo do konca krajšega genskega zapisa, se preostanek daljšega doda na konec novega zapisa. Tako bi na primer pri združevanju zapisov ACT in GCTATGCCC dobili AGCCTTATGCCC.

Definirajte metodo __add__, s katero je definirana operacija + (seštevanje). To pomeni, da bomo bakterije lahko združevali kar z uporabo operatorja +. Metoda naj vrne novo bakterijo, ki ima združen genski zapis ter za ena večji števec generacije kot starejša od obeh bakterij, ki nastopata v združevanju.

Primer:

>>> a = Bakterija('ACT')
>>> b = Bakterija('GCTATGCCC')
>>> c = a + b
>>> c.DNA
'AGCCTTATGCCC'
>>> c.generacija
1

4. podnaloga

Bakterije lahko tudi mutirajo, pri čemer se jim spremeni genski zapis. Na primer, podzaporedje AAG se pri mutaciji spremeni v podzaporedje AAT. Pri mutaciji se vedno spremenijo vse pojavitve danega podzaporedja, če pa genski zapis bakterije takšnega podzaporedja ne vsebuje, se med mutacijo DNA seveda ne spremeni.

Napišite metodo mutacija, ki sprejme dva parametra, ki povesta, v kaj se pri mutaciji spremeni dano podzaporedje genskega zapisa. Metoda naj vrne novo bakterijo, ki ima mutiran genski zapis in za ena večji števec generacije. Upoštevajte, da se mutacije genskega zapisa vedno odvijajo v smeri od leve proti desni (običajna smer v katero naraščajo indeksi).

Upoštevajte tudi, da bakterije brez genskega zapisa ne morejo mutirati. V takšnem primeru naj metoda vrne isto, nespremenjeno bakterijo (nasvet: self).

Nasvet: pomagajte si z metodo replace!

Primer:

>>> a = Bakterija('GAAATCGGT')
>>> m = a.mutacija('AAT', 'CAT')
>>> m.DNA
'GACATCGGT'
>>> m.generacija
1

Zajec

Jože goji zajce. V zadnjih letih so se tako namnožili, da si Jože enostavno ne more več zapomniti vseh. Zato potrebuje primeren informacijski sistem. V pomoč mu sestavite razred, ki bo vseboval vse potrebne podatke o vsakem zajcu.

1. podnaloga

Sestavite razred Zajec s konstruktorjem __init__(self, teza, starost), ki predstavlja zajca z dano težo in starostjo. Lastnosti teza in starost naj bodo definirane kot property, saj zajci z negativno težo in starostjo ne obstajajo. Takšnim zajcom nastavite težo oz. starost na 0 (in se pretvarjajte, da obstajajo zajci brez teže).

2. podnaloga

Sestavite metodo nahrani(self, hrana), kjer je argument hrana teža hrane, ki jo damo zajcu. Pri hranjenju se teža zajca poveča za 30 % teže hrane, ki jo zajec poje. Zgled:

>>> z = Zajec(5, 2)
>>> z.nahrani(2)
>>> z.teza
5.6

3. podnaloga

Sestavite metodo __str__(self), ki vrne predstavitev razreda Zajec z nizom oblike 'Zajec težak X kg, star Y let.'.

Primer:

>>> z = Zajec(5, 2)
>>> print(z)
'Zajec težak 5 kg, star 2 let.'

Opomba: Funkcija print na svojem argumentu pokliče metodo __str__ in izpiše niz, ki ga ta metoda vrne. Metoda __str__ običajno vrne razumljiv opis objekta, ki naj bi ga razumeli tudi ne-programerji.

4. podnaloga

Sestavite še metodo __repr__, ki vrne predstavitev razreda Zajec kot niz oblike 'Zajec(X, Y)', kjer je X teža, Y pa starost zajca.

Primer:

>>> z = Zajec(5, 2)
>>> z
Zajec(5, 2)

Opomba: Če v interaktivni konzoli pokličemo nek objekt, se izpiše niz, ki ga vrne klic metode __repr__ na tem objektu. Priporočilo je, da je niz, ki ga vrne metoda __repr__, veljavna programska koda v Pythonu, ki ustvari identično kopijo objekta.

5. podnaloga

Sestavite metodo __lt__(self, drugi), ki dva zajca primerja med sabo. Metoda naj vrne True, če je prvi zajec manjši od drugega in False sicer.

Manjši zajec je tisti, ki je lažji. Če pa imata zajca enako maso, je manjši tisti, ki je mlajši (tj. ima manjše število let).

>>> Zajec(5, 3) < Zajec(6, 2)
True
>>> Zajec(3, 1) < Zajec(2, 2)
False
>>> Zajec(4, 3) < Zajec(4, 2)
False

6. podnaloga

Sestavite funkcijo uredi(teze, starosti). Argumenta teze in starosti sta enako dolga seznama števil, kjer $i$-ti element predstavlja težo oz. starost $i$-tega zajca. Funkcija uredi naj ne bo znotraj razreda Zajec, saj ni objektna metoda, ampak je čisto običajna funkcija.

Funkcija naj ustvari seznam ustreznih primerkov razreda Zajec, ga uredi po velikosti glede na zgoraj opisano relacijo in ta seznam vrne kot rezultat.

Namig: metodo __lt__ ste že definirali, torej jo Python lahko uporablja v svojih funkcijah.

>>> l = uredi([5, 4, 4], [3, 2, 3])
>>> for z in l:
...     print(z)
...
Zajec težak 4 kg, star 2 let.
Zajec težak 4 kg, star 3 let.
Zajec težak 5 kg, star 3 let.

Kvadratni polinomi

1. podnaloga

Sestavimo razred KvPol, ki ga bomo uporabili za predstavitev kvadratnih polinomov. , torej za "zadeve" oblike $ax^2 + bx + c$. Za dostop do koeficientov pa bomo imeli tri lastnosti, ki jih bomo poimenovali koefA, koefB, koefC. Polinom $2x^2 - 3x + 10$ bomo ustvarili z KvPol(2, -3, 10)

V razredu naj bosta še osnovni metodi za prikaz polinoma v obliki niza, ki se obnašata kot kaže zgled

  >>> kv = KvPol(2, -3, 10)
  >>> kv.koefA = 3
  >>> repr(kv)
  'KvPol(3, -3, 10)'
  >>> str(kv)
  3x**2 + -3x + 10

2. podnaloga

Razred KvPol dopolni, tako, da bomo lahko seštevali polinome

   >>> pol1 = KvPol(2, 1, 3)
   >>> pol2 = KvPol(1, -1, 2)
   >>> pol1 + pol2
   'KvPol(3, 0, 5)'

3. podnaloga

Razred KvPol dopolni tako, da bomo lahko polinome množili s faktorjem

   >>> pol1 = KvPol(2, 1, 3)
   >>> pol2 = KvPol(2, 1, 2)
   >>> 2 * pol1
   'KvPol(4, 2, 6)'
   >>> pol2 * 1.5
   'KvPol(3, 1.5, 3)'

4. podnaloga

Razred KvPol dopolni z metodo vrednost, ki izračuna vrednost polinoma za dani x.

   >>> pol1 = KvPol(2, 1, 3)
   >>> pol1.vrednost(0)
   3
   >>> pol1.vrednost(1)
   6

Kompleksna števila (osnova)

1. podnaloga

Sestavljen je razred KompleksnoStevilo z metodama __init__(self, re, im) in prikazi(self). Realni del kompleksnega števila je shranjen v atributu _re, imaginarni pa v _im. Metoda prikazi(self) predstavi kompleksno število z nizom oblike KompleksnoStevilo(re, im). V kodi sta dve napaki, popravite ju.

Zgled:

>>> u = KompleksnoStevilo(3, 4)
>>> u.prikazi()
KompleksnoStevilo(3, 4)

2. podnaloga

Razredu dodaj metodo v_niz(self), ki kompleksno stevilo predstavi z nizom oblike npr. 3 + 4i Pri tem bodi pozoren da:

• Če je realni ali imaginarni del števila enak 0, naj bo v nizu njegov člen izpuščen (npr. namesto 2 + 0i pišemo samo 2).
• Če je imaginarni del števila enak 1, namesto 1i pišemo samo i. Če je enak -1namesto -1i pišemo -i.
• Če je imaginarni del števila negativen, njegov predznak zamenja +. Torej, namesto 2 + (-3)i pišemo kar 2 – 3i. Če je realni del enak 0 med predznakom - in nadaljevanjem ni presledka. Torej namesto - 3i pišemo -3i.

Zgled:

>>> u = KompleksnoStevilo(3, 4)
>>> print(u.v_niz())
3 + 4i
>>> v = KompleksnoStevilo(2, 0)
>>> print(v.v_niz())
2
>>> w = KompleksnoStevilo(0, -4)
>>> print(w.v_niz())
-4i
>>> w = KompleksnoStevilo(0, 1)
>>> print(w.v_niz())
i
>>> y = KompleksnoStevilo(-2, -6)
>>> print(y.v_niz())
-2 - 6i
>>> z = KompleksnoStevilo(0, 0)
>>> print(z.v_niz())
0

Opozorilo: To in vse ostale podnaloge začnite s class KompleksnoStevilo(KompleksnoStevilo), ali pa iz prejšnjih nalog skopirajte razred KompleksnoStevilo z vsemi prej definiranimi metodami.

3. podnaloga

Sestavite metodo polarni_zapis(self), ki vrača par (r, fi). Podatek r je oddaljenost kompleksnega števila od izhodišča, fi pa kot (argument) v radianih. Kot fi naj bo element intervala [0, 2*pi). Oba podatka se bosta preverjala na 5 decimalnih mest natančno.

Zgled:

>>> z = KompleksnoStevilo(1, 1)
>>> z.polarni_zapis()
(1.41421356237, 0.78539816339)

Zaradi preverjanja je že definirana (izven razreda) funkcija zaokrozi! Funkcije ne uporabi, saj se bo uporabila avtomatsko pri preverjanju.

 def zaokrozi(par):
     zaokrozen_r = round(float(par[0]), 5)
     zaokrozen_fi = round(float(par[1]), 5)
     return(zaokrozen_r, zaokrozen_fi)

Kompleksna števila II

1. podnaloga

Sestavljen je razred KompleksnoStevilo z metodama __init__(self, re, im), lastnostima im inre terrepr(self). Realni del kompleksnega števila je shranjen v spremenljivki_re, imaginarni pa v_im. Metodarepr(self)predstavi kompleksno število z nizom oblikeKompleksnoStevilo(re, im)`.

Zgled:

>>> u = KompleksnoStevilo(3, 4)
>>> u
KompleksnoStevilo(3, 4)

Žal so se vrstice v kodi zamešale. uredi jih v pravilni vrstni red. Razen spreminanja vrstnega reda ne naredi nobene druge spremembe

2. podnaloga

Razredu dodaj metodo __str__(self), ki kompleksno stevilo predstavi z nizom oblike npr. 3 + 4i Pri tem bodi pozoren da: ◦ Če je realni ali imaginarni del števila enak 0, naj bo v nizu njegov člen izpuščen (npr. namesto 2 + 0i pišemo samo 2). ◦ Če je imaginarni del števila enak 1, namesto 1i pišemo samo i. Če je enak -1namesto -1i pišemo -i. ◦ Če je imaginarni del števila negativen, njegov predznak zamenja +. Torej, namesto 2 + (-3)i pišemo kar 2 – 3i. Če je realni del enak 0 med predznakom - in nadaljevanjem ni presledka. Torej namesto - 3i pišemo -3i.

Zgled:

>>> u = KompleksnoStevilo(3, 4)
>>> print(u)
3 + 4i
>>> v = KompleksnoStevilo(2, 0)
>>> print(v)
2
>>> w = KompleksnoStevilo(0, -4)
>>> print(w)
-4i
>>> w = KompleksnoStevilo(0, 1)
>>> print(w)
i
>>> y = KompleksnoStevilo(-2, -6)
>>> print(y)
-2 - 6i
>>> z = KompleksnoStevilo(0, 0)
>>> print(z)
0

Opozorilo: To in vse ostale podnaloge začnite s class KompleksnoStevilo(KompleksnoStevilo)

3. podnaloga

Razširite razred tako, da podpira seštevanje dveh kompleksnih števil. Zgled:

 >>> KompleksnoStevilo(3, -2) + KompleksnoStevilo(2, 1)
 KompleksnoStevilo(5, -1)

4. podnaloga

Razširite razred tako, da podpira seštevanje kompleksnih števil z decimalnimi in celimi števili. Zgled:

 >>> str(KompleksnoStevilo(3, -2) + KompleksnoStevilo(2, 1))
 5 - i
 >>> str(KompleksnoStevilo(3, 2) + 4.5)
 7.5 + 2i
 >>> str(5 + KompleksnoStevilo(3, -2))
 8 - 2i
 >>> str("bla" + KompleksnoStevilo(3, -2))
 ...TypeError('Kompleksnih števil ne znamo seštevati z objekti tipa str')

5. podnaloga

Sestavite metodo __mul__(self, other), ki vrne produkt dveh kompleksnih števil. Množenec na levi bo vedno tipa KompleksnoStevilo, množenec na desni pa je lahko tudi navadno število tipa float ali int.

Zgled:

>>> KompleksnoStevilo(3, 4) * 2
KompleksnoStevilo(6, 8)
>>> KompleksnoStevilo(3, 4) * KompleksnoStevilo(2, -1)
KompleksnoStevilo(10, 2)

6. podnaloga

Omogočite, da lahko med sabo poljubno množimo kompleksna, cela in decimalna števila.

Zgled:

>>> d1 = KompleksnoStevilo(3, 4)
>>> d2 = KompleksnoStevilo(2, -1)
>>> d1 * d2
KompleksnoStevilo(10, 2)
>>> d1 * 3
KompleksnoStevilo(9, 12)
>>> 2.2 * d2
KompleksnoStevilo(4.4, -2.2)
>>> 7 * 3
21

7. podnaloga

Izven razreda KompleksnoStevilo sestavite funkcijo vsota_kompleksnih, ki sprejme tabelo kompleksnih števil in vrne vsoto številv tabeli.

>>> kompleksna = [KompleksnoStevilo(0, 0), KompleksnoStevilo(3, 4), KompleksnoStevilo(2, 2)]
>>> vsota_kompleksnih(kompleksna)
KompleksnoStevilo(5, 6)

Ponovitev - rekurzija

Za utrjevanje znanja iz rekurzije. Nobena od nalog ne bi smela delati težav! Predlagam, da se o reševanju pogovarjamo tudi v Forumu predmeta!

Ogrevanje: Vsote potenc

1. podnaloga

Sestavite rekurzivno funkcijo vsota_prvih(n), ki vrne vsoto prvih n naravnih števil.

2. podnaloga

Sestavite rekurzivno funkcijo vsota_prvih_kvadratov(n), ki vrne vsoto kvadratov prvih n naravnih števil.

3. podnaloga

Sestavite rekurzivno funkcijo vsota_prvih_potenc(n, k), ki vrne vsoto k-tih potenc prvih n naravnih števil. Argument k naj bo neobvezen in naj ima privzeto vrednost 1.

Koši

1. podnaloga

Če je ekipa na košarkarski tekmi dosegla m točk, na koliko načinov so lahko padali koši. Na primer: 3 točke se da doseči na 4 načine: 1 + 1 + 1, 1 + 2, 2 + 1, 3.

Sestavite funkcijo kosi(n), ki pove, na koliko načinov je ekipa lahko dosegla n točk. Na primer:

>>> kosi(2)
2
>>> kosi(3)
4
>>> kosi(4)
7
>>> kosi(20)
121415

Binomski simbol

1. podnaloga

Ena najbolj znanih formul za binomski simbol je $$\binom{n}{k} = \frac{n!}{k! \cdot (n - k)!}$$ Definirajte funkcijo binomski_fakulteta(n, k), ki s pomočjo te formule izračuna binomski simbol. Ne pozabite si definirati tudi funkcije fakulteta.

2. podnaloga

Seveda to ni edini način za izračun binomskega simbola. Lahko ga izračunamo tudi kot: $$\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}$$ pri čemer je treba upoštevati, da velja $\binom{n}{0} = \binom{n}{n} = 1$. Definirajte funkcijo binomski_rekurzija(n, k), ki binomski simbol definira po tej formuli.

3. podnaloga

Bolj učinkovit način za izračun binomskega simbola pa je: $$\binom{n}{k} = \frac{n - k + 1}{k} \binom{n}{k - 1}$$ pri čemer je treba upoštevati, da velja $\binom{n}{0} = 1$. Definirajte še funkcijo binomski_ucinkovit(n, k), ki binomski simbol definira po tej formuli. Pri tem pazite, da za rezultat vrnete celo število.

Collatzovo zaporedje

Collatzovo zaporedje tvorimo na sledeč način. Začnemo z nekim naravnim številom $n$, ki ga nato delimo z $2$, če je sodo, ali pa pomnožimo s $3$ in prištejemo $1$, če je liho. Postopek ponavljamo, dokler ne pridemo do števila $1$ (v tem primeru stvar ni več zanimiva, saj se začno ponavljati števila $1, 4, 2, 1, 4, 2, 1, \ldots$). Primer zaporedja, ki se začne z $6$ je tako $6, 3, 10, 5, 16, 8, 4, 2, 1$. Collatzova domneva, ki trdi, da za poljubno naravno število njegovo Collatzovo zaporedje sčasoma doseže $1$, je še vedno nerešena.

1. podnaloga

Sestavite funkcijo naslednji_clen(n), ki izračuna člen, ki v Collatzovemu zaporedju sledi številu n.

2. podnaloga

Sestavite funkcijo dolzina_zaporedja(n), ki izračuna dolžino Collatzovega zaporedja, ki se začne s številom n.

3. podnaloga

Sestavite funkcijo najvecji_clen(n), ki izračuna največji člen v Collatzovem zaporedju, ki se začne s številom n.

4. podnaloga

Sestavite funkcijo najdaljse_zaporedje(m, n), ki vrne dolžino najdaljšega zaporedja med vsemi tistimi Collatzovimi zaporedji, ki se začnejo s števili med (vključno) m in n.

SSCŠ

Seznam seznamov celih števil (SSCŠ) je seznam, katerega elementi so bodisi cela števila bodisi seznami seznamov celih števil. Da bo enostavneje, recimo, da je tudi prazen seznam SSCŠ. Nekaj primerov:

[-1, 2, -3]
[1, [2], 3, [2, 3, 4]]
[[[[2]], 1], [2, [[-3], [4]]]]

1. podnaloga

Sestavi funkcijo prestej_stevila(sscs), ki prešteje, koliko je v sscs celih števil. Za primere od zgoraj so rezultati:

3
6
5

2. podnaloga

Sestavi funkcijo prestej_negativna_stevila(sscs), ki prešteje, koliko je v seznamu seznamov negativnih celih števil. Za primere od zgoraj so rezultati:

2
0
1

3. podnaloga

Sestavi funkcijo sestej_stevila(sscs), ki sešteje vsa cela števila v seznamu seznamov celih števil. Za primere od zgoraj so rezultati:

-2
15
6

4. podnaloga

Sestavi funkcijo je_SSCS(sscs), ki preveri (vrne True oz. False), če je dan seznam res seznam seznamov celih števil.

POZOR: Python pravi, da je isinstance(True, int) enako True, pa tudi isinstance(False, int) enako True, zato se "znebi" napačnih logičnih vrednosti z isinstance(True, bool)

5. podnaloga

Sestavi funkcijo splosci(sscs), ki "splošči" seznam seznamov celih števil, torej vrne navaden seznam celih števil, ki so vsebovana v SSCŠ (v istem vrstnem redu). Za primere od zgoraj so rezultati:

[-1, 2, -3]
[1, 2, 3, 2, 3, 4]
[2, 1, 2, -3, 4]

Veliki šef in njegovi podrejeni

V nekem uspešnem podjetju ima skoraj vsak zaposleni svojega šefa. Seveda imajo tudi šefi svoje šefe in ti spet svoje šefe itn. Dobili smo podatke o hierarhiji v podjetju in ugotovili, da velja naslednje:

• Vsaka oseba ima kvečjemu enega šefa.
• En šef ima lahko pod seboj več zaposlenih.
• Vsem, ki so nad nami (naš šef, šef našega šefa itd.), pravimo nadrejeni.
• Vsem, ki so pod nami (sami smo njihov šef, ali pa smo šef njihovega šefa itd.), pravimo podrejeni.
• Nihče ni sam svoj šef in nihče ni samemu sebi podrejen.

Napisali bomo nekaj funkcij, s katerimi bomo preučili razmere v podjetju.

1. podnaloga

Podatke smo dobili v obliki tabele parov oblike (uslužbenec, šef). Vsi uslužbenci so predstavljeni z nizi (ki so običajno njihova imena oz. priimki). Zgled:

[('Mojca', 'Tilen'), ('Andrej', 'Tilen'), ('Tilen', 'Zoran')]

Komentar: Tilen ima pod seboj dva podrejena (Andreja in Mojco), njegov šef pa je Zoran. Zoran nima šefa, vsi ostali pa so njegovi podrejeni.

Napišite funkcijo slovar_sefov(tabela), ki bo iz zgoraj opisane tabele zgradila slovar šefov. Ključi v slovarju naj bodo uslužbenci, vrednosti pa njihovi šefi. Zgled:

>>> slovar_sefov([('Mojca', 'Tilen'), ('Andrej', 'Tilen'), ('Tilen', 'Zoran')])
{'Andrej': 'Tilen', 'Mojca': 'Tilen', 'Tilen': 'Zoran'}

2. podnaloga

Napišite funkcijo neposredno_podrejeni(tabela), ki bo iz zgoraj opisane tabele sestavila slovar neposredno podrejenih. Vrednost pri vsakem ključu naj bo množica tistih uslužbencev, ki imajo le-ta ključ za svojega šefa. Zgled:

>>> neposredno_podrejeni([('Mojca', 'Tilen'), ('Andrej', 'Tilen'), ('Tilen', 'Zoran')])
{'Zoran': {'Tilen'}, 'Tilen': {'Andrej', 'Mojca'}}

Zoranu je torej neposredno podrejen le Tilen, Tilnu pa sta podrejena tako Andrej kot Mojca.

3. podnaloga

Sestavite funkcijo veriga_nadrejenih(usluzbenec, slovar), ki kot prvi argument dobi uslužbenca, kot drugi argument pa dobi slovar šefov (v obliki kot ga vrne funkcija slovar_sefov). Funkcija naj sestavi tabelo, ki po vrsti vsebuje: šefa osebe usluzbenec, šefa od njegovega šefa itn. (dokler končno ne pridemo do osebe, ki nima šefa). Zgled:

>>> veriga_nadrejenih('Mojca', {'Andrej': 'Tilen', 'Mojca': 'Tilen', 'Tilen': 'Zoran'})
['Tilen', 'Zoran']

Mojci je nadrejen Tilen, kateremu je nadrejen Zoran, torej sta Mojčina šefa Tilen in Zoran.

4. podnaloga

Sestavite funkcijo mnozica_podrejenih(usluzbenec, slovar), ki kot prvi argument dobi ime uslužbenca, kot drugi argument pa slovar neposredno podrejenih (v obliki kot ga vrne funkcija neposredno_podrejeni). Funkcija naj sestavi in vrne množico vseh tistih oseb, ki so (posredno ali neposredno) podrejeni osebi usluzbenec. Zgled:

>>> mnozica_podrejenih('Zoran', {'Zoran': {'Tilen'}, 'Tilen': {'Andrej', 'Mojca'}, 'Mojca' : {'Urša'}})
{'Andrej', 'Mojca', 'Tilen', 'Urša'}

Zoranju je neposredno podrejen Tilen, torej sta mu podrejena tudi Tilnova podrejena Andrej in Mojca, ter Urša, ker je ta podrejena Mojci.

5. podnaloga

Tistemu uslužbencu, za katerega velja:

• da nima nadrejenih;
• je zadnji v verigi nadrejenih vseh ostalih uslužbencev (razen seveda samega sebe);

pravimo big boss. Sestavite funkcijo big_boss(slovar), ki kot argument dobi slovar nadrejenih in vrne ime osebe, ki je big boss v podjetju oz. vrednost None, če to podjetje nima big boss-a. Zgled:

>>> big_boss({'Andrej': 'Tilen', 'Mojca': 'Tilen', 'Tilen': 'Zoran'})
'Zoran'

Rodovniki

Ukvarjali se bomo z rodovniki (Celjskih grofov in drugih). Rodovnik imamo podan kot slovar, kjer je ključ ime "glave rodbine" vrednost pa tabela imen otrok. Recimo:

rodovnik =
 {'Ulrik I.': ['Viljem'], 'Margareta': [], 'Herman I.': ['Herman II.', 'Hans'],
  'Elizabeta II.': [], 'Viljem': ['Ana Poljska'], 'Elizabeta I.': [],
  'Ana Poljska': [], 'Herman III.': ['Margareta'], 'Ana Ortenburška': [],
  'Barbara': [], 'Herman IV.': [], 'Katarina': [], 'Friderik III.': [],
  'Herman II.': ['Ludvik', 'Friderik II.', 'Herman III.', 'Elizabeta I.', 'Barbara'],
  'Ulrik II.': ['Herman IV.', 'Jurij', 'Elizabeta II.'], 'Hans': [], 'Ludvik': [],
  'Friderik I.': ['Ulrik I.', 'Katarina', 'Herman I.', 'Ana Ortenburška'],
  'Friderik II.': ['Friderik III.', 'Ulrik II.'], 'Jurij': []}
 rodovnik['Friderik II.']

nam torej vrne

  ['Friderik III.', 'Ulrik II.']

1. podnaloga

Število otrok

Sestavi funkcijo koliko_otrok(ime, rodovnik), ki za dano ime in rodovnik vrne število otrok te osebe, oz None, če osebe ni v rodovniku.

2. podnaloga

Število potomcev

Sestavi funkcijo koliko_potomcev(ime, rodovnik), ki za dano ime in rodovnik vrne število potomcev te osebe. Če osebe ni v rodovniku, vrni vrednost None.

3. podnaloga

Je v rodbini?

Sestavi funkcijo je_v_rodbini(ime, glava_rodbine, rodovnik), ki ugotovi, ali je oseba z imenom ime v rodbini osebe glava_rodbine.

4. podnaloga

Kdo se podpisuje najdlje časa?

Sestavi funkcijo najdaljsi_podpis(glava_rodbine, rodovnik), ki ugotovi, kdo v rodbini osebe glava_rodbine ima najdaljše ime za podpis (torej kompletno ime). Če imata dve osebi enako dolg podpis, naj vrne starejšega.

5. podnaloga

Globina rodbine

"Globino" rodbine definiramo tako: če nekdo nima otrok, je globina njegove rodbine 1. Če ima otroka, ta pa nima vnukov (ali celo več otrok, ti pa nimajo vnukov), je globina rodbine 2. Če nekdo ima vnuke, vendar nobenega pravnuka, je globina njegove rodbine 3.

Sestavi funkcijo globina(glava_rodbine, rodovnik), ki vrne globino rodbine osebe glava_rodbine v rodovniku rodovnik

Podrejeni

Rekurzija se lahko pojavi tudi brez ustavitvenega pogoja, če primer le prevedemo na manjši primer.

1. podnaloga

V podjetju SLED vodijo evidenco svojih zaposlenih tako, da se vedno ve, kdo je glavni. Za vsakega zaposlenega v tabelo zaposleni vpišejo vse njegove neposredno podrejene. Če bi imeli štiri zaposlene, kjer bi bil Janez šef, Liza in Katja njegovi podrejeni, poleg tega pa bi Luka bil podrejen Lizi, bi tabela zaposleni izgledala tako:

  [('Janez', 'Liza'),('Janez', 'Katja'), ('Liza', 'Luka')]

Uredite vrstni red vrstic kode spodaj, da bo funkcija podrejeni(ime, zaposleni), ki sprejme ime delavca ime in tabelo zaposleni in vrne število vseh podrejenih (tudi posredno podrejenih) delavcu z imenom ime, delovala pravilno. Poleg tega ima ena vrstica napako, ena pa je odveč.

      """Prešteje uslužbence, podrejene delavcu ime."""
      return podrejenih
      podrejenih = 0
      if sef == ime:
      def podrejeni(ime, zaposleni):
      for (sef, usluzbenec) in zaposleni:
      podrejenih += podrejeni(usluzbenec, zaposleni)
      return 0

2. podnaloga

Sestavite še funkcijo glavni(zaposleni), ki vrne množico vseh glavnih šefov. Glavni šef je tisti, ki nima nobenega nadrejenega.

Naloga je rešljiva s pomočjo rekurzije, vendar je precej težka, tako da lahko rešite tudi brez rekurzije, oglejte pa si uradno rešitev z rekurzijo, tam se boste še kaj novega naučili.

Tabele tabel nizov I

Tabela tabel nizov je tabela, katere elementi so bodisi nizi bodisi tabele tabel nizov.

1. podnaloga

Sestavi funkcijo skupna_dolzina(ttn), ki bo vrnila skupno dolžino vseh nizov v tabeli tabel nizov ttn.

>>> skupna_dolzina(['sonce', [['dez', 'veter'], 'sneg'], [[[['mavrica']]]]])
24

2. podnaloga

Sestavi funkcijo max_dolzina(ttn), ki bo vrnila dolžino najdaljšega niza v tabeli tabel nizov ttn.

>>> max_dolzina(['sonce', [['dez', 'veter'], 'sneg'], [[[['mavrica']]]]])
7

3. podnaloga

Sestavi funkcijo max_dolzina_zadnji(ttn), ki bo vrnila najdaljši niz v tabeli tabel nizov ttn. Če je takih nizov več, naj vrne zadnjega.

>>> max_dolzina_zadnji(['sonce', [['dez', 'veter'], 'sneg'], [[[['oblak']]]]])
'oblak'

4. podnaloga

Sestavi funkcijo max_dolzina_vsi(ttn), ki bo vrnila množico vseh najdaljših nizov v tabeli tabel nizov ttn.

>>> max_dolzina_vsi(['sonce', [['dez', 'veter'], 'sneg'], [[[['oblak']]]]])
{'sonce', 'oblak', 'veter'}

Kovanci v vrsti

1. podnaloga

Čestitam! V nagradni igri si bil izžreban za dobitnika nagrade. Kolikšna bo nagrada, pa je odvisno od tvoje iznajdljivosti. Za nagrado si lahko izbereš poljubne kovance iz podane vrste kovancev (ki so lahko vsi različni ali pa tudi ne). Edini pogoj pri izbiranju je, da nikoli ne izbereš dveh sosednjih kovancev. Da se boš prepričal, da si boš izbral največjo možno nagrado, sestavi funkcijo nagrada(kovanci), ki bo za dane kovance vrnila največjo možno vsoto, ki jo lahko izbereš.

>>> nagrada([5, 6, 4, 8, 1, 2, 1, 1])
17
>>> nagrada([2, 2, 2])
4
>>> nagrada([1, 3, 1])
3
>>> nagrada([1, 3, 1, 4, 6])
9
>>> nagrada([3, 2, 1, 4, 6])
10
>>> nagrada([10, 2, 8, 16, 14, 2, 10, 4, 5, 7])
49
>>> nagrada([10, 2, 8, 16, 14, 10, 4, 5, 7])
43

2. podnaloga

Za izplačilo nagrade ni dovolj povedati, kakšno vsoto lahko dobiš, ampak s katerimi kovanci prideš do te vsote. Sestavi funkcijo kateri(kovanci), ki vrne tabelo z izbranimi kovanci, urejeno v naraščajočem vrstnem redu.

>>> kateri([5, 6, 4, 8, 1, 2, 1, 1])
[1, 2, 6, 8]

3. podnaloga

Predsednik komisije za nagradno igro pa s funkcijo kateri ni najbolj zadovoljen, saj mora sedaj, če želi ugotoviti znesek, poklicati funkcijo nagrada ali pa sešteti rezultat funkcije kateri. Zato želi funkcijo, ki vrne par - prva je maksimalna vrednost, druga vrednost pa tabela kovancev.

A pozor! Nalogo reši "od začetka", torej pri rešitvi nikakor ne uporabi funkcij nagrada in kateri.

  >>> naj_vsota([10, 2, 8, 16, 14, 10, 4, 5, 7])
  (43, [4, 7, 8, 10, 14])
  >>> naj_vsota([10, 2, 8, 16, 14, 2, 10, 4, 5, 7])
  (49, [7, 8, 10, 10, 14])
  >>> naj_vsota([3, 2, 1, 4, 6])
  (10, [1, 3, 6])
  >>> naj_vsota([1, 3, 1])
  (3, [3])
  >>> naj_vsota([2, 2, 2])
  (4, [2, 2])

4. podnaloga

Blagajnik komisije za nagradno igro pa pravi, da je predsednik malo čuden in si z njegovo funkcijo nima kaj pomagati. Želi bolj "vizualen" rezultat. Kakšne, je razvidno iz primerov!

  >>> naj_vsota_kako([10, 2, 8, 16, 14, 10, 4, 5, 7])
  (43, [10, '_', 8, '_', 14, '_', 4, '_', 7])
  >>> naj_vsota_kako([10, 2, 8, 16, 14, 2, 10, 4, 5, 7])
  (49, [10, '_', 8, '_', 14, '_', 10, '_', '_', 7])
  >>> naj_vsota_kako([3, 2, 1, 4, 6])
  (10, [3, '_', 1, '_', 6])
  >>> naj_vsota_kako([1, 3, 1])
  (3, ['_', 3, '_'])
  >>> naj_vsota_kako([2, 2, 2])
  (4, [2, '_', 2])

Dvobarvne ogrlice

Takrat, ko je upokojenki Tini dolgčas, vzame svoji dve posodici z belimi in rdečimi kroglicami ter začne nizati ogrlice. Te ogrlice bomo predstavili z nizi, sestavljenimi iz znakov B in R.

Na primer: 'BBRBBRB' in 'RRBBBBB' sta dve izmed 21 možnih ogrlic, sestavljenih iz petih belih in dveh rdečih kroglic.

1. podnaloga

Sestavite funkcijo je_ogrlica(niz, b, r), ki preveri, ali niz predstavlja ogrlico iz b belih in r rdečih kroglic. Na primer:

>>> je_ogrlica('BBRBBRB', 5, 2)
True
>>> je_ogrlica('RRBBBBB', 5, 2)
True
>>> je_ogrlica('BBRBBRB', 2, 5)
False
>>> je_ogrlica('BBRBBRBBB', 5, 2)
False
>>> je_ogrlica('BBRBBRBXY', 5, 2)
False

2. podnaloga

Z $O(b, r)$ označimo število različnih ogrlic, sestavljenih iz natanko $b$ belih in $r$ rdečih kroglic. Če je eno od števil $b$ ali $r$ enako nič, potem je $O(b, r) = 1$. Na primer, $O(5, 0) = 1$, saj iz petih belih kroglic lahko sestavimo le ogrlico 'BBBBB'.

V nasprotnem primeru pa velja $O(b, r) = O(b - 1, r) + O(b, r - 1)$, saj se vsaka izmed ogrlic iz $b$ belih in $r$ rdečih kroglic:

• bodisi začne z belo kroglico, preostalih $b - 1$ belih in $r$ rdečih kroglic pa lahko sestavimo na $O(b - 1, r)$ načinov,
• bodisi začne z rdečo kroglico, preostalih $b$ belih in $r - 1$ rdečih kroglic pa lahko sestavimo na $O(b, r - 1)$ načinov.

Sestavite funkcijo stevilo_ogrlic(b, r), ki izračuna število vseh možnih ogrlic, sestavljenih iz natanko b belih in r rdečih kroglic. Na primer:

>>> stevilo_ogrlic(5, 0)
1
>>> stevilo_ogrlic(5, 2)
21
>>> stevilo_ogrlic(4, 2)
15
>>> stevilo_ogrlic(5, 1)
6

3. podnaloga

Sestavite funkcijo ogrlice(b, r), ki generira vse nize, ki predstavljajo ogrlice, sestavljene iz b belih in r rdečih kroglic. Funkcija naj nize vrača v abecednem vrstnem redu.

Primer:

>>> ogrlice(2, 2)
['BBRR', 'BRBR', 'BRRB', 'RBBR', 'RBRB', 'RRBB']

Tabele tabel nizov II

Tabela tabel nizov je tabela, katere elementi so bodisi nizi bodisi tabele tabel nizov.

1. podnaloga

Sestavi funkcijo max_presledki_prvi(ttn), ki bo vrnila niz v tabeli tabel nizov ttn, ki vsebuje največ presledkov.Če je takih nizov več, naj vrne prvega.

>>> max_presledki_prvi(['s o n c e', [['  dez  ', 'veter   '], 'sneg'], [[[['o bla k']]]]])
's o n c e'

2. podnaloga

Sestavi funkcijo max_stevk_vsi(ttn), ki bo vrnila po abecedi urejeno tabelo vseh nizov v tabeli tabel nizov ttn, ki vsebujejo največje število števk.

>>> max_stevk_vsi(['a123', [['00', 'abcdef'], 'a1b2c3'], [[[['386']]]]])
['386', 'a123', 'a1b2c3']

3. podnaloga

Sestavi funkcijo globina(ttn), ki bo vrnila par (niz, globina), ki pove na kateri največji globini je niz v tabeli tabel nizov ttn. Če je takih nizov več, vrni tistega z največ števkami. Če pa je tudi teh več, pa tistega, ki je najdaljši . Tak je zagotovo največ en!

>>> globina(['a123', [['00', 'abcdef'], [[['a1b2c3']]], [[['3677']]]])
('a1b2c3', 4)
>>> globina(['a123', ['00', 'abcdef']])
('00', 2)
>>> globina(['a123', [['00', 'abcdef'], [[[['a1b2c3']]]], [[[['36']]]]])
('a1b2c3', 5)
>>> globina(['a123', '100', 'abcdef'])
('a123', 1)

4. podnaloga

Sestavi funkcijo globina_nizov(ttn), ki bo vrnila obratno po abecedi urejeno tabelo parov (niz, globina), ki za vsak niz pove, na kateri globini je.

>>> globina_nizov(['a123', [['00', 'abcdef'], [[['a1b2c3']]]])
[('abcdef', 3), ('a1b2c3', 4), ('a123', 1), ('00', 3)]
>>> globina_nizov(['a123', '00', 'abcdef'])
[('abcdef', 1), ('a123', 1), ('00', 1)]

Sklad - osnovne vaje

Pri nalogah boste potrebovali razred Sklad. Njegovo implementacijo najdete tukaj ali pa tukaj.

Janezek preverja sklad

1. podnaloga

Janezek je želel preveriti delovanje razreda Sklad. V ta namen je napisal program, ki v sklad vstavi nekaj števil, jih nato prebere nazaj ter izpiše na zaslon. Ima pa nekaj manjših napak. Program si oglejte ter ga popravite tako, da bo deloval pravilno.

Vstavljanje iz tabele v sklad

1. podnaloga

Sestavite funkcijo vstavi_vec(s, tabela), ki bo v sklad s po vrsti vstavila vse elemente iz seznama tabela, začenši z elementom na mestu 0. Zgled:

>>> s = Sklad()
>>> s.vstavi(5)
>>> s.vstavi(3)
>>> print(s)
DNO : 5 : 3 : VRH
>>> vstavi_vec(s, [11, 2, 5])
>>> print(s)
DNO : 5 : 3 : 11 : 2 : 5 : VRH

Preštej: popravi obstoječo kodo

1. podnaloga

V datoteki je funkcija prestej_elemente(s), ki bi morala izračunati in vrniti število podatkov v skladu s. Funkcija ima več napak. Popravi jih. Sklad s mora ostati nespremenjen. Zgled:

>>> s = Sklad()
>>> s.vstavi(6)
>>> s.vstavi(3)
>>> s.vstavi(1)
>>> prestej_elemente(s)
3

Podvoji sklad

1. podnaloga

Sestavi funkcijo podvoji_sklad(s), ki kot argument dobi sklad s in sestavi ter vrne nov sklad, kjer se vsak element iz sklada s pojavi dvakrat zaporedoma v enakem vrstnem redu kot se pojavijo v skladu s. Na koncu mora biti sklad s v enakem stanju kot na začetku. Zgled:

>>> s = Sklad()
>>> s.vstavi(1)
>>> s.vstavi(3)
>>> s.vstavi(5)
>>> podvojen = podvoji_sklad(s)
>>> print(s)
DNO : 1 : 3 : 5 : VRH
>>> print(podvojen)
DNO : 1 : 1 : 3 : 3 : 5 : 5 : VRH

Razmnoži sklad

1. podnaloga

V datoteki je napisana funkcija "razmnozi_sklad", ki sprejme sklad in seznam iste dolžine ter bi morala vrniti nov sklad, v katerem se vsak element prvotnega sklada pojavi tolikokrat, kolikor je istoležeče število v seznamu. $i$-to število v seznamu tako pove število ponovitev $i$-tega elementa v skladu. Funkcija ima dve napaki. Popravi ju. Na koncu morata biti prvotni sklad in seznam enaka kot na začetku. Predpostaviš lahko, da bosta sklad in seznam vedno iste dolžine ter da bo seznam vseboval le nenegativna cela števila.

Zgled:

>>> s = Sklad()
>>> s.vstavi(1)
>>> s.vstavi(3)
>>> s.vstavi(5)
>>> seznam = [2, 0, 3]
>>> razmnozen = razmnozi_sklad(s, seznam)
>>> print(s)
DNO : 1 : 3 : 5 : VRH
>>> print(razmnozen)
DNO : 1 : 1 : 5 : 5 : 5 : VRH

Odstrani največjega

Sestavili bomo tri funkcije, ki spremenijo sklad celih števil tako, da v njem odstranijo največji podatek. Seveda je potrebno uporabljati le metode nad skladom, na koncu mora pa biti vrstni red elementov (tistih, ki ostanejo v skladu) nespremenjen. Če je v skladu le en največji podatek, se vse tri funcije obnašajo enako. Če pa sta dva ali celo več enakih največjih elementov, lahko postopamo na več možnih načinov:

• odstranimo le najstarejšega (tistega, ki smo ga prvega vstavili v sklad) največjega;
• odstranimo vse največje;
• odstranimo le najmlajšega največjega.

Obstoječo implementacijo sklada bomo razširili - torej začnemo z

class Sklad(Sklad):

1. podnaloga

Sestavite metodo odstrani_najvecje(self), ki iz sklada odstrani vse največje elemente. Sklad

DNO : 8 : 6 : 14 : 10 : 14 : 13 : VRH

metoda spremeni v

DNO : 8 : 6 : 10 : 13 : VRH

Zgled:

>>> s = Sklad()
>>> for x in [8, 6, 14, 10, 14, 13]:
...     s.vstavi(x)
>>> print(s)
DNO : 8 : 6 : 14 : 10 : 14 : 13 : VRH
>>> s.odstrani_najvecje()
>>> print(s)
DNO : 8 : 6 : 10 : 13 : VRH

2. podnaloga

Sestavite metodo odstrani_najstarejsega_najvecjega(self), ki iz sklada odstrani najstarejši največji element. Zgled:

>>> s = Sklad()
>>> for x in [8, 6, 14, 10, 14, 13]:
...     s.vstavi(x)
>>> s.odstrani_najstarejsega_najvecjega()
>>> print(s)
DNO : 8 : 6 : 10 : 14 : 13 : VRH

3. podnaloga

Sestavite metodo odstrani_najmlajsega_najvecjega(self), ki iz sklada odstrani najmlajši največji element. Zgled:

>>> s = Sklad()
>>> for x in [8, 6, 14, 10, 14, 13]:
...     s.vstavi(x)
>>> s.odstrani_najmlajsega_najvecjega()
>>> print(s)
DNO : 8 : 6 : 14 : 10 : 13 : VRH

Sklad - uporaba

Pri nalogah boste potrebovali razred Sklad. Njegovo implementacijo najdete tukaj ali pa tukaj.

Gnezdenje oklepajev: ustvari funkcijo

Oklepaji so pravilno gnezdeni, če uklepaji in zaklepaji istega tipa nastopajo v parih in število zaklepajev nikoli ne preseže števila uklepajev, ko jih štejemo od leve proti desni.

1. podnaloga

Sestavite funkcijo oklepaji(niz), ki bo preverila, ali so v danem nizu oklepaji pravilno gnezdeni. Na ostale znake naj se funkcija ne ozira. Poznamo naslednje tipe oklepajev:

oklep = {
    '(': ')',
    '{': '}',
    '[': ']',
    '<': '>'
}

Zgled:

>>> oklepaji('(a + b)^2 = ({[a^2] + 2ab} + b^2)')
True
>>> oklepaji('[])({}')
False

2. podnaloga

Definirana je funkcija max_globina(niz), ki bi morala poiskati globino najbolj globoko gnezdenega para oklepajev v izrazu niz. Funkcija vsebuje več napak. Najprej jo dopolni do funkcije iz prejšnje naloge, nato pa odpravi še preostale napake. Končna funkcija naj torej v primeru pravilno gnezdenih oklepajev vrne največjo globino, v nasprotnem primeru pa False. Zgled:

>>> max_globina('(a + b)^2 = ({[a^2] + 2ab} + b^2)')
3
>>> max_globina('[])({}')
False

Seznam skladov: popravi obstoječo funkcijo

1. podnaloga

V datoteki je definirana funkcija locevanje(sklad), ki kot argument dobi sklad celih števil sklad, vrniti bi pa morala seznam desetih skladov, pri čemer $i$-ti sklad ($i = 0, 1, \ldots, 9$) vsebuje tista števila s sklada sklad, ki dajo ostanek $i$ pri deljenju z 10. Funkcija vsebuje več napak. Odpravi jih. Zgled:

>>> s = Sklad()
>>> s.vstavi(2)
>>> s.vstavi(13)
>>> s.vstavi(5)
>>> s.vstavi(4)
>>> s.vstavi(3)
>>> s.vstavi(14)
>>> s.vstavi(23)
>>> r = locevanje(s)
>>> all([r[0].prazen(), r[1].prazen(), r[6].prazen(), r[7].prazen(), r[8].prazen(), r[9].prazen()])
True
>>> print(r[2])
DNO : 2 : VRH
>>> print(r[3])
DNO : 13 : 3 : 23 : VRH
>>> print(r[4])
DNO : 4 : 14 : VRH
>>> print(r[5])
DNO : 5 : VRH

Matrično množenje

Naj bo $A$ matrika velikosti $n \times m$ in naj bo $B$ matrika velikosti $p \times r$. Če je $m = p$, potem lahko matriki zmnožimo. Matrika $AB$ je velikosti $n \times r$. Da jo dobimo potrebujemo $nmr$ množenj. Če je $m \neq p$, matrik $A$ in $B$ ne moremo zmnožiti.

1. podnaloga

Sestavite funkcijo stevilo_mozenj(izraz, velikost), ki kot argumenta dobi niz izraz in slovar velikost. Izraz vsebuje le znake ( in ) ter velike črke angleške abecede, ki predstavljajo matrike, npr. ((A((BC)D))(EF)). Predpostaviš lahko, da je izraz smiseln in da so v njem zapisani vsi oklepaji, tudi če niso potrebni. Slovar velikost za vsako matriko vsebuje njene dimenzije (ključ je ime matrike, vrednost pa par oblike (število vrstic, število stolpcev)). Funkcija naj vrne skupno število množenj, ki jih je potrebno narediti, da izračunamo dani matrični izraz. Funkcija naj vrne None, če množenje ni možno. Zgled:

>>> stevilo_mnozenj('((AB)C)', {'A': (10, 5), 'B': (5, 20), 'C': (20, 3)})
1600

Vlak

1. podnaloga

Na neki vaški železniški postaji imamo poleg glavnega tira še en slepi tir, s pomočjo katerega lahko spremenimo vrstni red vagonov. Slepi tir lahko sprejme poljubno število vagonov. Na primer, vlak 321 s tremi vagoni pripelje z leve in nadaljuje z vožnjo proti desni. Če vagonov ne bi prerazporejali, bi vožnjo nadaljevali kot 321. Lahko pa vagon 1 preusmerimo na slepi tir, vagon 2 spustimo naprej, s slepega tira spustimo 1 in nazadnje mimo spustimo še vagon 3, s čimer dobimo zaporedje 312. Vseh zaporedij se na tak način ne da dobiti. Na primer, če bi želeli dobiti zaporedje 213, bi morali vagona 1 in 2 zadržati na slepem tiru ter mimo najprej spustiti vagon 3. To bi še šlo, vendar bi potem morali najprej spustiti vagon 2, saj je na slepi tir zapeljal za vagonom 1 in mu tako zapira pot.

Napišite funkcijo vagoni(prihod, odhod), ki dobi dva seznama z opisom vagonov in vrne True, če jih lahko ustrezno permutiramo s pomočjo slepega tira, in False sicer. Zgled:

>>> vagoni('321', '312')
True
>>> vagoni('321', '213')
False

Nadomestni upor

Kot je dobro znano iz elektrotehnike, nadomestni upor dveh zaporedno vezanih upornikov izračunamo po formuli $R = R_1 + R_2$, nadomestni upor dveh vzporedno vezanih upornikov pa je $1/R = 1/R_1 + 1/R_2$.

1. podnaloga

Napišite funkcijo nadomestni_upor(r1, r2, tipV), ki kot argumenta dobi dve števili r1 in r2 (tj. upor obeh upornikov) in tip vezave tipV, ki je bodisi znak 'V' bodisi znak 'Z'. Funkcija naj vrne nadomestni upor vezja. Pozor: nekateri uporniki so vezani kratkostično in imajo upor 0. (Upor dveh vzporedno vezanih upornikov, od katerih ima vsaj en upor 0, je 0.)

>>> nadomestni_upor(3, 5, 'Z')
8
>>> nadomestni_upor(3, 0, 'V')
0
>>> nadomestni_upor(2, 5, 'V')
1.875

2. podnaloga

Sestavite funkcijo upor_vezja(niz), ki izračuna nadomestni upor vezja. Vezje je podano kot niz v "RPN notaciji": operandom (tj. vrednosti uporov) sledi operator (tj. način vezave, 'V' ali 'Z').

Analizirajmo vezje '3 5 Z 0 V 3 2 Z V': Niz '3 5 Z' tako pomeni, da sta zaporedno vezana upornika z upornostma 3 in 5 (ki ju lahko nadomestimo z enim upornikom z upornostjo 8). Skratka, dobimo vezje '8 0 V 3 2 Z V'. V tem novem vezju niz '8 0 V' pomeni, da sta vzporedno vezana upornika z upornostma 8 in 0. Vzporedna vezava, ki vsebuje kratkostični upornik, je kratkostična, zato je 0 nadomestni upor vezja '8 0 V'. Skratka, dobimo vezje '0 3 2 Z V'. Niz '3 2 Z' pomeni, da sta zaporedno vezana upornika z upornostma 3 in 2 (in torej z nadomestno upornostjo 5). Če upoštevamo še to, potem dobimo vezje '0 5 V', kar na koncu da rezultat 0.

>>> upor_vezja('3 5 Z 0 V 3 2 Z V')
0

Predpostavite lahko, da v nizu niz nastopajo (poleg znakov 'V', 'Z' in ' ') le nenegativna cela števila.

3. podnaloga

Napišite še funkcijo sestavi_racun(niz), ki namesto da izračuna nadomestni upor vezja, sestavi račun, ki ga je potrebno izračunati, da dobimo nadomestni upor vezja.

>>> sestavi_racun('3 5 Z 0 V 3 2 Z V')
'(1/(1/(3 + 5) + 1/0)^-1 + 1/(3 + 2))^-1'

Namig: Ali lahko nalogo rešite tako, da malenkost predelate rešitev prejšnje naloge?

4. podnaloga

Stari električarski mački si račun poenostavijo na sledeč način: če je upor $R_a$ več kot 10-krat večji kot upor $R_b$, potem za nadomestni upor zaporedne vezave upornikov $R_a$ in $R_b$ vzamejo kar $R_a$, kot nadomestni upor vzporedne vezave pa kar upor $R_b$. Seveda pa pravilno razumejo vezavo, če je kakšen upor enak 0.

Sestavite funkcijo stari_macki(niz), ki bo nadomestni upor vezja izračunala po "metodi starih mačkov".

>>> stari_macki('2 30 Z 20 V 3 2 Z V')
3.5294117647058822

Sklad (dodatne vaje)

Pri nalogah boste potrebovali razred Sklad. Njegovo implementacijo najdete tukaj ali pa tukaj.

RPN kalkulator

Ko z enostavnim kalkulatorjem želimo izračunati malo zapletenejši račun, vedno nastanejo težave z zapisom oklepajev. Izkaže pa se, da se lahko uporabi oklepajev v celoti izognemo z obrnjenim poljskim zapisom (reverse Polish notation oz. na krajše RPN).

V tem zapisu operacij ne pišemo med argumenti, temveč za njimi. Tako namesto 4 + 5 pišemo 4 5 +. Če želimo izračunati (2 + 4) * 3, pa napišemo 2 4 + 3 *. Ko napišemo 2 4 +, je to isto, kot če bi napisali 6, in ko temu dodamo še 3 *, dobimo iskani rezultat 18.

V splošnem števila dajemo na sklad, z operacijo pa s sklada poberemo dve vrhnji števili, nanj pa vstavimo rezultat operacije.

1. podnaloga

Sestavite funkcijo izracunaj(a, b, op), ki dobi niza a in b, ki predstavljata celi števili, in operacijo op, ki je bodisi znak '+' (seštevanje) bodisi znak '*' (množenje). Funkcija naj vrne niz, ki predstavlja rezultat operacije na argumentih a in b.

>>> izracunaj('10', '5', '+')
'15'
>>> izracunaj('5', '3', '*')
'15'

2. podnaloga

Sestavite funkcijo vrednost_rpn(niz), ki dobi niz z veljavnim RPN izrazom ter izračuna in vrne njegovo vrednost.

>>> vrednost_rpn('10 5 + 3 7 * +')
36

Namig: Pri izračunu si pomagajte s skladom. Niz razbijte po presledkih, nato pa po vrsti preglejte vse dele. Če pridete do števila, ga dajte na sklad, če pa pridete do operacije, s sklada vzemite vrhnji dve števili, izračunajte rezultat, ter ga postavite nazaj na sklad. Ko pridete do konca seznama, bi na skladu moralo ostati le eno število, ki predstavlja rezultat.

3. podnaloga

Sestavite funkcijo obicajni_zapis(izraz), ki sprejme izraz v RPN in vrne niz z istim izrazom v običajni obliki. Da ne bo težav z oklepaji, jih postavite okoli vsake uporabe operacije.

>>> obicajni_zapis('2 4 +')
'(2 + 4)'
>>> obicajni_zapis('2 4 + 3 *')
'((2 + 4) * 3)'
>>> obicajni_zapis('10 5 + 3 7 * +')
'((10 + 5) + (3 * 7))'

Namig: Ali lahko nalogo rešite tako, da minimalno predelate funkcijo vrednost_rpn?

Dijkstrov algoritem odstavnega tira

Na predavanjih ste spoznali algoritem za izračun vrednosti aritmetičnega izraza, ki uporablja dva sklada: enega za vrednosti, drugega za operacije. Z nekaj prilagoditvami lahko ta algoritem pretvorimo v Dijkstrov algoritem odstavnega tira, ki upošteva tudi prednost operacij, zato nam v aritmetičnem izrazu ni treba pisati vseh oklepajev.

V spodnjih nalogah bomo aritmetične izraze predstavili z nizi, v katerih bodo členi ločeni z vsaj enim presledkom, operacije pa bomo omejili na +, * in **.

1. podnaloga

Najprej potrebujemo dve pomožni funkciji:

• cleni_izraza(izraz), ki niz izraz po presledkih razbije na člene, ter

• izracunaj(a, op, b), ki operacijo op uporabi na številih a in b.

  cleni_izraza(' ( 2 + 4 ) + 6 ') ['(', '2', '+', '4', ')', '+', '6'] izracunaj(2, '+', 4) 6 izracunaj(2, '**', 4) 16

2. podnaloga

Pogost korak pri algoritmu je, da s sklada operacij poberemo operacijo (predstavljeno z nizom), s sklada vrednosti dve vrednosti (predstavljeni s števili), nato pa na sklad vrednosti vrnemo vrednost izračuna (prestavljeno s številom). Sestavite funkcijo izvedi_racun(sklad_operacij, sklad_vrednosti), ki izvede zgornji korak.

>>> sklad_operacij = Sklad()
>>> sklad_vrednosti = Sklad()
>>> sklad_vrednosti.vstavi(1)
>>> sklad_vrednosti.vstavi(2)
>>> sklad_vrednosti.vstavi(3)
>>> sklad_operacij.vstavi('+')
>>> sklad_operacij.vstavi('*')
>>> print(sklad_operacij)
DNO : + : * : VRH
>>> print(sklad_vrednosti)
DNO : 1 : 2 : 3 : VRH
>>> izvedi_racun(sklad_operacij, sklad_vrednosti)
>>> print(sklad_operacij)
DNO : + : VRH
>>> print(sklad_vrednosti)
DNO : 1 : 6 : VRH
>>> izvedi_racun(sklad_operacij, sklad_vrednosti)
>>> print(sklad_operacij)
DNO : VRH
>>> print(sklad_vrednosti)
DNO : 7 : VRH

3. podnaloga

Za začetek si oglejmo enostaven primer, ko so vsi podizrazi v oklepajih in dvoma glede vrstnega reda operacij ni. Sestavite funkcijo vrednost_z_vsemi_oklepaji(izraz), ki izračuna in vrne vrednost izraza, predstavljenega z nizom izraz, zapisanega v običajni obliki z vsemi oklepaji. Pri tem sledite algoritmu s predavanj.

>>> vrednost_z_vsemi_oklepaji('( 2 + 4 )')
6
>>> vrednost_z_vsemi_oklepaji('( ( 10 + 5 ) * ( 3 + 7 ) )')
150

4. podnaloga

Glavna razlika med zgornjim in Dijkstrovim algoritmom je, da račune izvedemo tudi takrat, ko naletimo na operator, ki nima prednosti.

Sestavite funkcijo sklad_ima_prednost(sklad_operacij, op), ki vrne True, kadar je na skladu operacij operacija, ki ima prioriteto višjo ali enako operatorju op. V primeru, da sta operacija na skladu in operator op oba **, naj funkcija vrne False.

>>> sklad_operacij = Sklad()
>>> print(sklad_ima_prednost(sklad_operacij, '+'))
>>> False
>>> sklad_operacij.vstavi('*')
>>> print(sklad_ima_prednost(sklad_operacij, '*'))
>>> True
>>> print(sklad_ima_prednost(sklad_operacij, '**'))
>>> False
>>> sklad_operacij.vstavi('**')
>>> print(sklad_ima_prednost(sklad_operacij, '+'))
>>> True
>>> print(sklad_ima_prednost(sklad_operacij, '**'))
>>> False

5. podnaloga

Sestavite funkcijo vrednost(izraz), ki izračuna in vrne vrednost izraza, predstavljenega z nizom izraz. Pri tem lahko sledite algoritmu, opisanemu na https://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail.

>>> vrednost('( 2 + 4 ) * 3')
18
>>> vrednost('2 + 4 * 3')
14
>>> vrednost('2 * 4 + 3')
11

Janezek in sklad

1. podnaloga

Janezek je želel preveriti delovanje razreda Sklad. V ta namen je napisal program, ki v sklad vstavi nekaj števil, jih nato prebere nazaj ter izpiše na zaslon. Ima pa nekaj manjših napak. Program si oglejte ter ga popravite tako, da bo deloval pravilno.

2. podnaloga

Premislite, kaj vse bi bilo pri razredu Sklad še potrebno preveriti, da bi bili prepričani, da deluje pravilno. Za rešitev te podnaloge napišite program za testiranje sklada.

(Ta podnaloga nima testnih primerov, saj avtomatično preverjanje ni možno.)

Preštej: ustvari funkcijo

Implementacijo razreda Sklad lahko dobite tukaj.

1. podnaloga

Sestavite funkcijo prestej_elemente(s), ki izračuna in vrne število podatkov v skladu s. Sklad s mora ostati nespremenjen. Zgled:

>>> s = Sklad()
>>> s.vstavi(6)
>>> s.vstavi(3)
>>> s.vstavi(1)
>>> prestej_elemente(s)
3

Gnezdenje oklepajev: popravi obstoječo kodo

Oklepaji so pravilno gnezdeni, če uklepaji in zaklepaji istega tipa nastopajo v parih in število zaklepajev nikoli ne preseže števila uklepajev, ko jih štejemo od leve proti desni.

Implementacijo razreda Sklad lahko dobite tukaj.

1. podnaloga

V datoteki je definirana funkcija oklepaji(niz), ki bi morala preveriti, ali so v danem nizu oklepaji pravilno gnezdeni. Funkcija ima več napak. Odpravi jih. Na ostale znake naj se funkcija ne ozira. Poznamo naslednje tipe oklepajev:

oklep = {
    '(': ')',
    '{': '}',
    '[': ']',
    '<': '>'
}

Zgled:

>>> oklepaji('(a + b)^2 = ({[a^2] + 2ab} + b^2)')
True
>>> oklepaji('[])({}')
False

2. podnaloga

V datoteki je definirana funkcija max_globina(niz), ki bi morala poiskati globino najbolj globoko gnezdenega para oklepajev v izrazu niz. Funkcija ima več napak. Najprej jo dopolni do funkcije iz prejšnje podnaloge, nato pa odpravi še preostale napake. Končna funkcija naj torej v primeru pravilno gnezdenih oklepajev vrne največjo globino, v nasprotnem primeru pa False. Zgled:

>>> max_globina('(a + b)^2 = ({[a^2] + 2ab} + b^2)')
3
>>> max_globina('[])({}')
False

Seznam skladov: ustvari funkcijo

Implementacijo razreda Sklad lahko dobite tukaj.

1. podnaloga

Sestavite funkcijo locevanje(sklad), ki kot argument dobi sklad celih števil sklad in vrne seznam desetih skladov, pri čemer $i$-ti sklad ($i = 0, 1, \ldots, 9$) vsebuje tista števila s sklada sklad, ki dajo ostanek $i$ pri deljenju z 10. Zgled:

>>> s = Sklad()
>>> s.vstavi(2)
>>> s.vstavi(13)
>>> s.vstavi(5)
>>> s.vstavi(4)
>>> s.vstavi(3)
>>> s.vstavi(14)
>>> s.vstavi(23)
>>> r = locevanje(s)
>>> all([r[0].prazen(), r[1].prazen(), r[6].prazen(), r[7].prazen(), r[8].prazen(), r[9].prazen()])
True
>>> print(r[2])
DNO : 2 : VRH
>>> print(r[3])
DNO : 13 : 3 : 23 : VRH
>>> print(r[4])
DNO : 4 : 14 : VRH
>>> print(r[5])
DNO : 5 : VRH

Vrsta

Datoteko vrsta.py s predstavitvijo APS Vrsta najdete tukaj. Predstavitev je razširjena še s tem, da Vrsta([1, 2, 3]) ustvari vrsto, v kateri so že podatki 1, 2 in 3. Na začetku vrste je 1, na koncu pa 3!

Delo z vrsto: popravi obstoječo kodo

1. podnaloga

V datoteki je definirana funkcija prestej_elemente(v), ki kot argument dobi vrsto v in vrne število elementov v vrsti. V definiciji je več napak. Odpravi jih. Ko funkcija konča delo, mora biti vrsta v enakem stanju kot na začetku.

Zgled:

>>> v = Vrsta([4, 5, 6])
>>> v.vstavi(7)
>>> prestej_elemente(v)
4
>>> v
Vrsta([4, 5, 6, 7])

2. podnaloga

V datoteki je definirana funkcija prestej_pogojno(v, p), ki kot argument dobi vrsto v in funkcijo p (funkcija p dobi en argument in vrne logično vrednost) ter prešteje, koliko je takih elementov v vrsti, za katere funkcija p vrne True. V definiciji je več napak. Odpravi jih. Ko funkcija konča, mora biti vrsta v enakem stanju kot na začetku.

Zgled:

>>> v = Vrsta([1, 2, 3, 4, 5, 6, 7, 8])
>>> prestej_pogojno(v, lambda x: x % 2 == 0)
4

3. podnaloga

V datoteki je definirana funkcija odstrani_ntega(v, n), ki kot argumenta dobi vrsto v in celo število n. Definicija ima več napak. Odpravi jih. Funkcija naj iz vrste v odstrani $n$-ti zaporedni element (šteti začnemo pri 0). Če vrsta ne vsebuje $n$-tega elementa (ker je prekratka), naj je funkcija ne spremeni.

Primer:

>>> v = Vrsta([1, 2, 3, 4, 5, 6, 7])
>>> odstrani_ntega(v, 3)
>>> v
Vrsta([1, 2, 3, 5, 6, 7])

4. podnaloga

V datoteki je definirana funkcija odstrani_pogojno(v, p), ki kot argumenta dobi vrsto v in funkcijo p (funkcija p dobi en argument in vrne logično vrednost) ter odstrani tiste elemente v vrsti, za katere funkcija p vrne True. Definicija ima več napak. Odpravi jih.

Primer:

>>> v = Vrsta([1, 2, 3, 4, 5, 6, 7, 8])
>>> odstrani_pogojno(v, lambda x: x % 2 == 0)
>>> v
Vrsta([1, 3, 5, 7])

5. podnaloga

V datoteki je defenirana funkcija obrni(v), ki obrne vrsto v. Definicija ima več napak. Odpravi jih. Pri tem si pomagajte s skladom (implementacija).

Zgled:

>>> v = Vrsta([1, 2, 3, 4, 5])
>>> obrni(v)
>>> v
Vrsta([5, 4, 3, 2, 1])

Družabna vrsta

1. podnaloga

V zelo popularno menzo hodijo na kosilo ljudje iz različnih ustanov. Vljudno bi bilo, če bi se vsak, ki pride, postavil na konec vrste. Ampak v praksi se izkaže, da to ne drži. Prišlek namreč v vrsti poišče zadnjega, ki prihaja iz iste ustanove kot on, in se z njim zaplete v pogovor. Klepet izkoristi za to, da se vrine v vrsto za zadnjega iz svoje skupine. Sestavite razred DruzabnaVrsta, ki naj ima naslednje metode:

• __init__(self), ki ustvari prazno vrsto;
• dodaj_prisleka(self, ime, skupina), ki doda osebo z imenom ime, ki pripada skupini skupina;
• ime_prvega(self), ki vrne ime osebe, ki je trenutno prva v vrsti;
• postrezi(self), ki iz vrste odstrani prvega (ta dobi svoje kosilo in gre sedet k mizi).

Primer:

>>> menza = DruzabnaVrsta()
>>> menza.dodaj_prisleka('Marjan', 'FMF')
>>> menza.dodaj_prisleka('Petra', 'FKKT')
>>> menza.dodaj_prisleka('Borut', 'FDV')
>>> menza.dodaj_prisleka('Tanja', 'FMF')
>>> menza.dodaj_prisleka('Boris', 'FKKT')
>>> menza.ime_prvega()
'Marjan'
>>> menza.postrezi()
>>> menza.ime_prvega()
'Tanja'
>>> menza.postrezi()
>>> menza.ime_prvega()
'Petra'
>>> menza.postrezi()
>>> menza.ime_prvega()
'Boris'

Razred DruzabnaVrsta naj uporablja vrsto iz modula Vrsta.

Zavetišče

1. podnaloga

V nekem živalskem zavetišču sprejemajo pse in mačke (bolj eksotičnih živali pa ne sprejemajo). Pravila zavetišča določajo, da dobi posvojitelj vedno tisto žival, ki je najdlje časa varovanec zavetišča. Pri tem lahko izbira med psom in mačko, lahko pa mu je vseeno glede vrste. Sestavite razred Zavetisce, ki bo upravniku v pomoč pri vodenju zavetišča.

Razred naj ima naslednje metode:

• __init__(self), ki ustvari prazno zavetišče;
• sprejmi(self, ime, vrsta), ki evidentira novo žival z imenom ime, ki je pripadnik vrste vrsta (ta ima lahko vrednost 'pes' ali 'mačka');
• oddaj_psa(self), ki vrne ime psa, ki je na vrsti za posvojitev (in ga tudi odstrani iz evidence);
• oddaj_macko(self), ki deluje podobno kot oddaj_psa, vendar za mačke;
• oddaj_zival(self), ki deluje podobno kot oddaj_psa in oddaj_macko, vendar vrne žival tiste vrste, ki je prva na vrsti za posvojitev.

Metode oddaj_psa, oddaj_macko in oddaj_zival naj vrnejo None, če ustrezne živali ni na voljo. Primer:

>>> z = Zavetisce()
>>> z.sprejmi('Taček', 'pes')
>>> z.sprejmi('Šarki', 'pes')
>>> z.oddaj_macko()
None
>>> z.sprejmi('Tom', 'mačka')
>>> z.oddaj_psa()
'Taček'
>>> z.sprejmi('Nyan', 'mačka')
>>> z.oddaj_zival()
'Šarki'

Namig: Uporabite dve vrsti, tako da v eni hranite pse, v drugi pa mačke. V vrsti hranite pare, ki vsebujejo ime in čas prihoda, npr. ('Taček', 1).

2. podnaloga

Zavetišče je obiskala informacijska pooblaščenka, ki je prepovedala hranjenje časa prihoda živali. Zdaj morate napisati nov razred ZavetiscePoPredpisih, ki naj deluje enako kot Zavetisce, le da ne hrani časov prihoda živali.

Namig: Živali hranite v eni sami vrsti, ki naj vsebuje pare podatkov in sicer ime živali ter vrsto, npr. ('Taček', 'pes').

Sladoled

1. podnaloga

Pred kioskom v ravni vrsti stojijo otroci, ki kupujejo sladoled. Za vsakega otroka vemo, kako močan je. Večja številka pomeni, da je otrok močnejši. Ko pride nek otrok na vrsto, najprej pogleda, če v vrsti stoji še kdo, ki je močnejši. V tem primeru se ustraši in se vljudno umakne na konec vrste, sicer pa si kupi sladoled.

Denimo, da je na začetku vrsta takšna:

KIOSK 2 1 3 2 3 1 3

Otrok, ki je prvi na vrsti, opazi, da je za njim močnejši, zato se umakne na konec:

KIOSK 1 3 2 3 1 3 2

Otrok, ki je zdaj prvi v vrsti, se tudi vljudno umakne na konec, saj za njim stoji močnejši otrok. Novo stanje je takšno:

KIOSK 3 2 3 1 3 2 1

Otrok, ki je zdaj na začetku vrste, kupi sladoled in gre, v vrsti pa ostanejo:

KIOSK 2 3 1 3 2 1

Tako nadaljujejo, dokler vsi otroci ne dobijo sladoleda.

Sestavite funkcijo kdaj_pridem_na_vrsto(otroci), ki kot argument dobi seznam moči otrok in vrne nov seznam, ki vsebuje števila od 1 naprej. Pri tem naj $i$-to število v izhodnem seznamu pomeni, kateri po vrsti kupi sladoled otrok, ki je bil na začetku $i$-ti v vrsti. Zgled:

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

Namig: V vrsti lahko hranite pare dveh števil, kjer je prvo število zaporedna številka otroka (kje je stal na začetku), drugo pa je njegova moč. Če vam je lažje, si definirajte pomožno funkcijo, ki kot argument dobi vrsto, vrne pa moč najmočnejšega otroka v vrsti. Pri tem naj vrste ne spremeni.

Zamenjava elementov

1. podnaloga

Napišite funkcijo zamenjaj_elementa(v, k), ki kot argumenta dobi vrsto v celo število k ter vrne vrsto, v kateri sta k-ti in k + prvi element med seboj zamenjana. Elemente začnemo šteti pri 1. Vrsta v naj bo na koncu enaka kot na začetku. Če je število k neustrezno, naj funkcija sproži napako. Da bo lažje, je ta del funkcije že napisan. Namig: Pomagajte si s funkcijo prestej_elemente(v).

Zgled:

>>> v = Vrsta([4, 5, 6, 7, 8])
>>> v_nova = zamenjaj(v, 3)
>>> v_nova
Vrsta([4, 5, 7, 6, 8])
>>> v
Vrsta([4, 5, 6, 7, 8])

Urejanje vrste

1. podnaloga

Sestavite funkcijo uredi_z_zlivanjem(v), ki vrsto v uredi z algoritmom urejanja z zlivanjem: funkcija naj vrsto razdeli na dva (prb. enako velika) dela in nato vsakega rekurzivno uredi. Ko imamo dve urejeni vrsti, ju združimo tako, da v novo vrsto vedno vstavimo tistega izmed obeh prvih elementov, ki je manjši. Funkcija naj vrne novo, urejeno vrsto (urejeno od najmanjšega proti največjemu). Prvotna vrsta naj bo na koncu enaka kot na začetku. Pomagajte si s funkcijo prestej_elemente(v) iz prve naloge.

Zgled:

>>> v = Vrsta([7, 2, 5, 3])
>>> v_urejena = uredi_z_zlivanjem(v)
>>> v_urejena
Vrsta([2, 3, 5, 7])
>>> v
Vrsta([7, 2, 5, 3])

2. podnaloga

Sestavite funkcijo hitro_uredi(v), ki vrsto v uredi z algoritmom hitrega urejanja: funkcija naj izbere poljuben element vrste (pivot; kateri element točno bo funkcija izbrala, je prepuščeno vam) ter preostale elemente vrste razdeli na dva dela: v enem naj bodo elementi, manjši ali enaki pivotu, v drugem pa elementi, večji od pivota. Funkcija naj nato vsak del rekurzivno uredi. Ko imamo dve urejeni vrsti, ju združimo tako, da v novo vrsto najprej vstavimo del z manjšimi elementi, nato pivot in na koncu še del z večjimi elementi. Funkcija naj vrne novo, urejeno vrsto (urejeno od najmanjšega proti največjemu). Prvotna vrsta naj bo na koncu enaka kot na začetku. Pomagajte si s funkcijo prestej_elemente(v) iz prve naloge.

Zgled:

>>> v = Vrsta([7, 2, 5, 3])
>>> v_urejena = hitro_uredi(v)
>>> v_urejena
Vrsta([2, 3, 5, 7])
>>> v
Vrsta([7, 2, 5, 3])

3. podnaloga

Sestavite funkcijo uredi_z_mehurcki(v), ki vrsto v uredi z algoritmom urejanja z mehurčki: funkcija se zapelje čez celotno vrsto. Na vsakem koraku trenutni element zamenja z naslednjim, če je trenutni element večji od naslednjega. Ko funkcija prehodi vso vrsto, se postopek ponovi, le da se funkcija tokrat ustavi na elementu prej. Funkcija naj vrne novo, urejeno vrsto (urejeno od najmanjšega proti največjemu). Prvotna vrsta naj bo na koncu enaka kot na začetku. Pomagajte si s funkcijo prestej_elemente(v) iz prve naloge.

Zgled:

>>> v = Vrsta([7, 2, 5, 3])
>>> v_urejena = uredi_z_mehurcki(v)
>>> v_urejena
Vrsta([2, 3, 5, 7])
>>> v
Vrsta([7, 2, 5, 3])

Vrsta (dodatne vaje)

Delo z vrsto: definiraj funkcije

1. podnaloga

Napišite funkcijo prestej_elemente(v), ki kot argument dobi vrsto v in vrne število elementov v vrsti. Ko funkcija konča, mora biti vrsta v enakem stanju kot na začetku.

Zgled:

>>> v = Vrsta([4, 5, 6])
>>> v.vstavi(7)
>>> prestej_elemente(v)
4
>>> v
Vrsta([4, 5, 6, 7])

2. podnaloga

Sestavite funkcijo prestej_pogojno(v, p), ki kot argument dobi vrsto v in funkcijo p (funkcija p dobi en argument in vrne logično vrednost) ter prešteje koliko je takih elementov v vrsti, za katere funkcija p vrne True. Ko funkcija konča, mora biti vrsta v enakem stanju kot na začetku.

Zgled:

>>> v = Vrsta([1, 2, 3, 4, 5, 6, 7, 8])
>>> prestej_pogojno(v, lambda x: x % 2 == 0)
4

3. podnaloga

Sestavite funkcijo odstrani_ntega(v, n), ki kot argumenta dobi vrsto v in celo število n. Funkcija naj iz vrste v odstrani $n$-ti zaporedni element (šteti začnemo pri 0). Če vrsta ne vsebuje $n$-tega elementa (ker je prekratka), naj je funkcija ne spremeni.

Primer:

>>> v = Vrsta([1, 2, 3, 4, 5, 6, 7])
>>> odstrani_ntega(v, 3)
>>> v
Vrsta([1, 2, 3, 5, 6, 7])

4. podnaloga

Sestavite funkcijo odstrani_pogojno(v, p), ki kot argumenta dobi vrsto v in funkcijo p (funkcija p dobi en argument in vrne logično vrednost) ter odstrani tiste elemente v vrsti, za katere funkcija p vrne True.

Primer:

>>> v = Vrsta([1, 2, 3, 4, 5, 6, 7, 8])
>>> odstrani_pogojno(v, lambda x: x % 2 == 0)
>>> v
Vrsta([1, 3, 5, 7])

5. podnaloga

Sestavite funkcijo obrni(v), ki obrne vrsto v. Pri tem si pomagajte s skladom.

Zgled:

>>> v = Vrsta([1, 2, 3, 4, 5])
>>> obrni(v)
>>> v
Vrsta([5, 4, 3, 2, 1])

Zamenjava elementov

1. podnaloga

Napišite funkcijo zamenjaj_elementa(v, k), ki kot argumenta dobi vrsto v celo število k ter vrne vrsto, v kateri sta k-ti in k + prvi element med seboj zamenjana. Elemente začnemo šteti pri 1. Vrsta v naj bo na koncu enaka kot na začetku. Če je število k neustrezno, naj funkcija sproži napako. Da bo lažje, je ta del funkcije že napisan. Namig: Pomagajte si s funkcijo prestej_elemente(v).

Zgled:

>>> v = Vrsta([4, 5, 6, 7, 8])
>>> v_nova = zamenjaj(v, 3)
>>> v_nova
Vrsta([4, 5, 7, 6, 8])
>>> v
Vrsta([4, 5, 6, 7, 8])

Veriga vozlov

Veriga vozlov

Ena najpogostejših predstavitev seznama uporablja verigo vozlov, od katerih vsak vsebuje podatek in kaže na morebitni naslednji vozel v verigi. Verigo vozlov bomo predstavili s pomočjo razreda Vozel:

class Vozel:
    """
    Osnovni sestavni del verige vozlov.
    """

    def __init__(self, podatek, naslednji=None):
        self.podatek = podatek
        self.naslednji = naslednji

    def __str__(self):
        if self.naslednji is not None:
            return '{} -> {}'.format(self.podatek, self.naslednji)
        else:
            return '{} -> X'.format(self.podatek)

Zadnji vozel v verigi ima za atribut .naslednji vrednost None. Prav tako z None predstavimo prazno verigo.

>>> v = Vozel(1, Vozel(2, Vozel(3)))
>>> print(v)
1 -> 2 -> 3 -> X

1. podnaloga

Sestavite funkcijo vrni_seznam(prvi), ki vrne seznam vseh podatkov v verigi vozlov, ki se prične z vozlom prvi. Ne pozabite na prazno verigo! Zgled:

>>> vrni_seznam(Vozel('petek', Vozel('sobota', Vozel('nedelja'))))
['petek', 'sobota', 'nedelja']

2. podnaloga

Sestavite funkcijo dodaj_na_zacetek(prvi, x), ki doda nov vozel na začetek verige vozlov, ki se začne z vozlom prvi, ter vrne referenco na novi začetni vozel. Zgled:

>>> v = Vozel('nedelja')
>>> v = dodaj_na_zacetek(v, 'sobota')
>>> v = dodaj_na_zacetek(v, 'petek')
>>> vrni_seznam(v)
['petek', 'sobota', 'nedelja']

3. podnaloga

Sestavite funkcijo dodaj_na_konec(prvi, x), ki doda nov vozel na konec verige vozlov, ki se začne z vozlom prvi, ter vrne referenco na prvi vozel v verigi. Ne pozabite na primer, ko je veriga prazna! Zgled:

>>> v = Vozel('petek')
>>> v = dodaj_na_konec(v, 'sobota')
>>> v = dodaj_na_konec(v, 'nedelja')
>>> vrni_seznam(v)
['petek', 'sobota', 'nedelja']

4. podnaloga

Sestavite funkcijo iz_seznama(seznam), ki sestavi novo verigo, ki kot podatke v vozlih zaporedoma vsebuje elemente seznama seznam, ter vrne referenco na prvi vozel v tej verigi. Zgled:

>>> v = iz_seznama(['torek', 'sreda', 'četrtek', 'petek'])
>>> v = dodaj_na_konec(v, 'sobota')
>>> vrni_seznam(v)
['torek', 'sreda', 'četrtek', 'petek', 'sobota']

Branje verig vozlov

Za spodnje naloge morate uvoziti vse definicije iz naloge Veriga vozlov. To storite z:

from veriga_vozlov import Vozel, dodaj_na_konec, dodaj_na_zacetek, vrni_seznam, iz_seznama

1. podnaloga

Sestavite funkcijo dolzina(prvi), ki vrne število vozlov v verigi vozlov, ki se začne z vozlom prvi. Zgled:

>>> v = Vozel('sobota')
>>> v = dodaj_na_konec(v, 'nedelja')
>>> v = dodaj_na_zacetek(v, 'petek')
>>> dolzina(v)
3

2. podnaloga

Sestavite funkcijo zadnji_vozel(prvi), ki vrne referenco na zadnji vozel v verigi vozlov, ki se začne z vozlom prvi. Zgled:

>>> v = iz_seznama(['sreda', 'četrtek', 'petek', 'sobota'])
>>> zadnji_vozel(v).podatek
'sobota'

3. podnaloga

Sestavite funkcijo seznam_sodih(prvi), ki vrne seznam vseh sodih elementov v verigi vozlov, ki se začne z vozlom prvi. Predpostavite lahko, da so vsi podatki cela števila. Zgled:

>>> v = iz_seznama([3, 4, 5, 6, 7, 8, 9, 10, 11])
>>> seznam_sodih(v)
[4, 6, 8, 10]

4. podnaloga

Sestavite funkcijo pogojni_seznam(prvi, pogoj), ki kot argument dobil verigo vozlov, ki se začne z vozlom prvi, ter funkcijo pogoj, ki sprejme en element in vrne logično vrednost. Funkcija pogojni_seznam naj sestavi in vrne seznam vseh podatkov, pri katerih funkcija pogoj vrne True. Zgled:

>>> v = iz_seznama(['sreda', 'četrtek', 'petek', 'sobota'])
>>> pogojni_seznam(v, lambda s: s.endswith('ek'))
['četrtek', 'petek']

5. podnaloga

Sestavite funkcijo je_urejen(prvi), ki vrne True, če so podatki v verigi vozlov urejeni naraščajoče in False, če niso. Zgled:

>>> v = iz_seznama([1, 2, 4, 7, 8])
>>> je_urejen(v)
True
>>> v = iz_seznama([1, 2, 4, 3, 7])
>>> je_urejen(v)
False
>>> v = iz_seznama([1, 2, 3, 3, 7])
>>> je_urejen(v)
True

Sestavljanje verig vozlov

Za spodnje naloge morate uvoziti vse definicije iz naloge Veriga vozlov. To storite z:

from veriga_vozlov import Vozel, dodaj_na_konec, dodaj_na_zacetek, vrni_seznam, iz_seznama

Funkciji vrni_seznam ter iz_seznama sta namenjeni predvsem testiranju funkcij, zato se nanju raje ne zanašajte preveč.

1. podnaloga

Sestavite funkcijo stevilska_veriga(a, b), ki vrne referenco na prvi vozel v verigi, ki zaporedoma vsebuje števila od a do b. Predpostavite, da velja a <= b. Zgled:

>>> v = stevilska_veriga(3, 7)
>>> vrni_seznam(v)
[3, 4, 5, 6, 7]

2. podnaloga

Sestavite funkcijo sodi_in_lihi(v), ki kot argument prejme referenco na vozel ter vrne dve verigi, ki jih dobi tako, da v eno zloži vozle, ki vsebujejo sode podatke, v drugo pa vozle, ki vsebujejo lihe podatke. Funkcija naj vrne par in sicer referenci na začetna vozla v obeh verigah. Na primer:

>>> v = iz_seznama([7, 5, 2, 1, 3, 4, 9, 8])
>>> v1, v2 = sodi_in_lihi(v)
>>> vrni_seznam(v1)
[2, 4, 8]
>>> vrni_seznam(v2)
[7, 5, 1, 3, 9]

3. podnaloga

Sestavite funkcijo podvoji_verigo(prvi), ki naj sestavi in vrne novo, identično kopijo verige, stare pa naj ne spreminja. Zgled:

>>> v = iz_seznama([2, 3, 4, 5])
>>> v2 = podvoji_verigo(v)
>>> v2.podatek = 11
>>> vrni_seznam(v)
[2, 3, 4, 5]
>>> vrni_seznam(v2)
[11, 3, 4, 5]

4. podnaloga

Sestavite funkcijo stakni_verigi(v1, v2), ki kot argumenta prejme referenci na dva vozla in sestavi novo verigo, ki jo dobi tako, da stakne obe verigi. Na primer:

>>> v1 = iz_seznama([1, 2, 3])
>>> v2 = iz_seznama([4, 5, 6])
>>> v = stakni_verigi(v1, v2)
>>> vrni_seznam(v)
[1, 2, 3, 4, 5, 6]

5. podnaloga

Sestavite funkcijo na_zadrgo(v1, v2), ki kot argumenta prejme referenci na dva vozla. Funkcija naj vrne verigo, ki jo dobi tako, da "na zadrgo" združi obe verigi. Funkcija naj vrne referenco na prvi vozel tako dobljene verige. Funkcija naj ne ustvarja novih vozlov.

Na primer:

>>> v1 = iz_seznama([7, 5, 2])
>>> v2 = iz_seznama([1, 3, 4, 9, 8])
>>> v = na_zadrgo(v1, v2)
>>> vrni_seznam(v)
[7, 1, 5, 3, 2, 4, 9, 8]

6. podnaloga

Sestavite funkcijo odpni_zadrgo(v), ki kot argument prejme referenco na vozel ter vrne dve verigi, ki jih dobi tako, da "odpne zadrgo", tj. vozle naj razdeli med dve verigi. Funkcija naj vrne par in sicer referenci na začetna vozla v obeh verigah. Funkcija naj ne ustvarja novih vozlov.

Na primer:

>>> v = iz_seznama([7, 5, 2, 1, 3, 4, 9, 8])
>>> v1, v2 = odpni_zadrgo(v)
>>> vrni_seznam(v1)
[7, 2, 3, 9]
>>> vrni_seznam(v2)
[5, 1, 4, 8]

Spreminjanje verig vozlov: popravi obstoječo kodo

Za spodnje naloge morate uvoziti vse definicije iz naloge Veriga vozlov. To storite z:

from veriga_vozlov import Vozel, dodaj_na_konec, dodaj_na_zacetek, vrni_seznam, iz_seznama

1. podnaloga

V datoteki je definirana funkcija vstavi_na_mesto(prvi, n, x), ki na n-to mesto v verigi vozlov, ki se začne z vozlom prvi, vstavi vozel s podatkom x. V definiciji funkcije je več napak. Odpravi jih. Funkcija naj vrne referenco na prvi vozel v spremenjeni verigi vozlov. Če veriga vozlov ni dovolj dolga, dodajte ustrezno število vozlov, ki imajo kot podatek None. Zgled:

>>> v = iz_seznama(['sreda', 'četrtek', 'sobota'])
>>> v = vstavi_na_mesto(v, 2, 'petek')
>>> vrni_seznam(v)
['sreda', 'četrtek', 'petek', 'sobota']

2. podnaloga

V datoteki je definirana funkcija vstavi_v_urejenega(prvi, x), ki podatek x vstavi na primerno mesto v urejeno verigo vozlov, ki se začne z vozlom prvi. V definiciji je več napak. Odpravi jih. Funkcija naj vrne začetni vozel spremenjene verige. Zgled:

>>> v = iz_seznama([1, 2, 4, 7, 8])
>>> v = vstavi_v_urejenega(v, 3)
>>> vrni_seznam(v)
[1, 2, 3, 4, 7, 8]

3. podnaloga

V datoteki je definirana funkcija odstrani(v, x), ki kot argumenta prejme referenco na vozel ter element x. Funkcija mora verigo popraviti, tako da odstrani vozle, ki kot podatek vsebujejo element x. A definicija vsebuje več napak. Odpravi jih. Funkcija naj vrne referenco na začetni vozel verige. Na primer:

>>> v = iz_seznama([7, 5, 2, 5, 3, 5])
>>> v = odstrani(v, 5)
>>> v.vrni_seznam()
[7, 2, 3]

4. podnaloga

V datoteki je definirana funkcija multipliciraj_verigo(v, n), ki kot argumenta prejme referenco na vozel in naravno število n ter verigo spremeni tako, da iz vsakega vozla naredi n zaporednih kopij. V definiciji je več napak. Odpravi jih. Funkcija naj vrne referenco na prvi vozel. Na primer:

>>> v = iz_seznama([7, 5, 2])
>>> v = multipliciraj_verigo(v, 3)
>>> v.vrni_seznam()
[7, 7, 7, 5, 5, 5, 2, 2, 2]

Preurejanje verig vozlov: ustvari funkcije

Za spodnje naloge morate uvoziti vse definicije iz naloge Veriga vozlov. To storite z:

from veriga_vozlov import Vozel, dodaj_na_konec, dodaj_na_zacetek, vrni_seznam, iz_seznama

1. podnaloga

Sestavite funkcijo preuredi_parnost(v), ki kot argument prejme referenco na vozel ter verigo vozlov tako preuredi, da postavi vse vozle, ki vsebujejo lih podatek na začetek, vozle, ki vsebujejo sod podatek pa na konec. Funkcija naj vrne referenco na začetek preurejene verige. Na primer:

>>> v = iz_seznama([7, 5, 2, 1, 3, 4, 9, 8])
>>> v = preuredi_parnost(v)
>>> v.vrni_seznam()
[7, 5, 1, 3, 9, 2, 4, 8]

2. podnaloga

Pepi je sestavil verigo vozlov in ugotovil, da je elemente nizal v seznam v napačnem vrstnem redu. Zdaj je treba seznam obrniti, tako da obstoječih vozlov ne brišemo in ne dodajamo novih. Sestavite funkcijo obrni_na_mestu(v), ki dobi verigo vozlov in jo obrne na mestu. Funkcija mora vrniti referenco na prvi vozel. Zgled:

>>> v = iz_seznama([7, 5, 2, 1])
>>> v = obrni_na_mestu(v)
>>> v.vrni_seznam()
[1, 2, 5, 7]

3. podnaloga

Napišite funkcijo uredi_z_izbiranjem(v), ki verigo vozlov uredi z izbiranjem. Funkcija naj deluje tako, da najprej ustvari novo prazno verigo. V seznamu v naj poišče največji element ter ga prestavi na začetek nove verige. To naj ponavlja, doker v seznamu v ne zmanjka elementov. Funkcija naj vrne referenco na prvi vozel v urejeni verigi. Zgled:

>>> v = iz_seznama([4, 7, 3, 6, 5, 2, 1])
>>> v = uredi_z_izbiranjem(v)
>>> vrni_seznam(v)
[1, 2, 3, 4, 5, 6, 7]

Verižni seznam

Verižni seznam

Verižni seznam predstavimo z verigo vozlov ter kazalcema, ki kažeta na začetni in končni vozel v tej verigi. Za osnovo si bomo vzeli razred Vozel, kot ga poznamo že od prej:

class Vozel:
    """
    Razred, ki predstavlja posamezen vozel s podatkom v verižnem seznamu.
    """
    def __init__(self, podatek, naslednji=None):
        self.podatek = podatek
        self.naslednji = naslednji

ter razred VerizniSeznam:

class VerizniSeznam:
    """
    Razred, ki predstavlja verižni seznam z začetkom in koncem.
    """
    def __init__(self):
        self._zacetek = None
        self._konec = None

    def __str__(self):
        niz = ''
        vozel = self._zacetek
        while vozel is not None:
            niz += '{} -> '.format(repr(vozel.podatek))
            vozel = vozel.naslednji
        return niz + '•'

Pozorni bodite, da se imeni atributov, v katerih sta shranjena kazalca na začetek in konec verige vozlov, začneta s podčrtajem, s čimer želimo povedati, da naj uporabnik podatkovne strukture do njih ne dostopa direktno. V ta namen bomo raje malo kasneje definirali metodi zacetek in konec.

1. podnaloga

Dopolnite obstoječi razred VerizniSeznam tako, da dopišete še metodo vstavi_na_zacetek(self, podatek), ki podatek vstavi na začetek seznama (pazite pri vstavljanju v prazen seznam).

2. podnaloga

Dopišite še metodo zacetek(self), ki vrne podatek na začetku verižnega seznama. Če je seznam prazen, naj metoda sproži izjemo IndexError('Verižni seznam je prazen').

3. podnaloga

Dodajte še metodo izbrisi_zacetek(self), ki izbriše element na začetku verižnega seznama (pazite na seznam dolžine 1). Če je seznam prazen, naj metoda sproži izjemo IndexError('Verižni seznam je prazen').

4. podnaloga

Razred VerizniSeznam naj sedaj pozna še metodo vstavi_na_konec(self, podatek), ki podatek vstavi na konec seznama (pazite pri vstavljanju v prazen seznam).

5. podnaloga

Dopišite še metodo konec(self), ki vrne podatek na koncu verižnega seznama. Če je seznam prazen, naj metoda sproži izjemo IndexError('Verižni seznam je prazen').

6. podnaloga

Sestavite metodo izbrisi_konec(self), ki izbriše element na koncu verižnega seznama (pazite na seznam dolžine 1). Če je seznam prazen, naj metoda sproži izjemo IndexError('Verižni seznam je prazen').

7. podnaloga

Definicijo razreda VerizniSeznam zaključimo z metodo je_prazen(self), ki vrne True, če je verižni seznam prazen, in False, če ni.

Verižni seznami z dolžino

Verižni seznam lahko nadgradimo tako, da hkrati hrani tudi svojo dolžino. Če pogosto potrebujemo dolžino seznama, hkrati pa uporabljamo zelo obsežne sezname, je hranjenje dolžine učinkovitejše kot računanje.

1. podnaloga

Dopolnite definicijo verižnega seznama z metodami (kot so opisane v nalogi Verižni seznam):

• vstavi_na_zacetek
• zacetek
• izbrisi_zacetek
• vstavi_na_konec
• konec
• izbrisi_konec
• prazen
• dolzina: dodatna metoda, ki vrne dolžino seznama

Namig: prekopirajte vašo rešitev naloge Verižni seznam in metode primerno popravite.

2. podnaloga

Definirajte metodo filtriraj(self, f), ki iz verižnega seznama pobriše vse elemente za katere funkcija f vrne False. Za boljšo prostorsko učinkovitost, naj metoda ne uporablja pomožnega seznama.

Namig: pri znani dolžini lahko kot "pomožni" seznam uporabimo kar self.

3. podnaloga

Definirajte metodo __lt__ za primerjanje verižnih seznamov, kjer je manjši seznam tisti, ki je krajši, pri seznamih enake dolžine pa jih primerjamo leksikografsko (po vrsti vsebino vozlov). Pazite, da metoda ne spremeni začetnih seznamov.

Hitri problemčki s seznami

Za reševanje potrebujete implementacijo iz naloge Verižni seznam.

1. podnaloga

Napišite funkciji:

• obrnjen(vs), ki vrne nov seznam z obrnjenim vrstnim redom podatkov. Pri tem ne spremeni izvornega seznama.
• obrni(vs), ki verižni seznam obrne na mestu.

2. podnaloga

Napišite funkcijo filtriraj(vs, f), ki filtrira elemente verižnega seznama vs glede na funkcijo f. V seznamu vs pusti elemente, za katere funkcija vrne True, hkrati pa vrne verižni seznam vseh izločenih elementov.

3. podnaloga

Napišite funkcijo razdrobi_glede_na_enke(vs), ki razdrobi verižni seznam celih števil v več verižnih seznamov. Funkcija vrne tabelo (poimenujmo jo t) za katero velja, da t[i] vsebuje verižni seznam vseh števil iz vs, ki vsebujejo natanko i enk. Vrstni red elementov v verižnih seznamih t[i] naj bo tak, kot si števila sledijo v vs. Funkcija je lahko destruktivna (torej ne rabi ohraniti izvornega seznama).

>>> vs = VerizniSeznam()
>>> vs.vstavi_na_zacetek(0)
>>> vs.vstavi_na_zacetek(10)
>>> vs.vstavi_na_zacetek(210)
>>> vs.vstavi_na_zacetek(11210)
>>> [str(s) for s in razdrobi_glede_na_enke(vs)]
['0 -> •', '210 -> 10 -> •', '•', '11210 -> •']

Verižni seznam (dodatne vaje)

Spreminjanje verig vozlov: ustvari funkcije

Za spodnje naloge morate uvoziti vse definicije iz naloge Veriga vozlov. To storite z:

from veriga_vozlov import Vozel, dodaj_na_konec, dodaj_na_zacetek, vrni_seznam, iz_seznama

1. podnaloga

Sestavite funkcijo vstavi_na_mesto(prvi, n, x), ki na n-to mesto v verigi vozlov, ki se začne z vozlom prvi, vstavi vozel s podatkom x. Funkcija naj vrne referenco na prvi vozel v spremenjeni verigi vozlov. Če veriga vozlov ni dovolj dolga, dodajte ustrezno število vozlov, ki imajo kot podatek None. Zgled:

>>> v = iz_seznama(['sreda', 'četrtek', 'sobota'])
>>> v = vstavi_na_mesto(v, 2, 'petek')
>>> vrni_seznam(v)
['sreda', 'četrtek', 'petek', 'sobota']

2. podnaloga

Sestavite funkcijo vstavi_v_urejenega(prvi, x), ki podatek x vstavi na primerno mesto v urejeno verigo vozlov, ki se začne z vozlom prvi. Funkcija naj vrne začetni vozel spremenjene verige. Zgled:

>>> v = iz_seznama([1, 2, 4, 7, 8])
>>> v = vstavi_v_urejenega(v, 3)
>>> vrni_seznam(v)
[1, 2, 3, 4, 7, 8]

3. podnaloga

Sestavite funkcijo odstrani(v, x), ki kot argumenta prejme referenco na vozel ter element x. Funkcija naj verigo popravi, tako da odstrani vozle, ki kot podatek vsebujejo element x. Funkcija naj vrne referenco na začetni vozel verige. Na primer:

>>> v = iz_seznama([7, 5, 2, 5, 3, 5])
>>> v = odstrani(v, 5)
>>> v.vrni_seznam()
[7, 2, 3]

4. podnaloga

Sestavite funkcijo multipliciraj_verigo(v, n), ki kot argumenta prejme referenco na vozel in naravno število n ter verigo spremeni tako, da iz vsakega vozla naredi n zaporednih kopij. Funkcija naj vrne referenco na prvi vozel. Na primer:

>>> v = iz_seznama([7, 5, 2])
>>> v = multipliciraj_verigo(v, 3)
>>> v.vrni_seznam()
[7, 7, 7, 5, 5, 5, 2, 2, 2]

Preurejanje verig vozlov: popravi obstojeco kodo

Za spodnje naloge morate uvoziti vse definicije iz naloge Veriga vozlov. To storite z:

from veriga_vozlov import Vozel, dodaj_na_konec, dodaj_na_zacetek, vrni_seznam, iz_seznama

1. podnaloga

V datoteki je definirana funkcija preuredi_parnost(v), ki kot argument prejme referenco na vozel ter verigo vozlov tako preuredi, da postavi vse vozle, ki vsebujejo lih podatek na začetek, vozle, ki vsebujejo sod podatek pa na konec. V definiciji funkcije je nekaj napak. Odpravi jih. Funkcija naj vrne referenco na začetek preurejene verige. Na primer:

>>> v = iz_seznama([7, 5, 2, 1, 3, 4, 9, 8])
>>> v = preuredi_parnost(v)
>>> v.vrni_seznam()
[7, 5, 1, 3, 9, 2, 4, 8]

2. podnaloga

Pepi je sestavil verigo vozlov in ugotovil, da je elemente nizal v seznam v napačnem vrstnem redu. Zdaj je treba seznam obrniti, tako da obstoječih vozlov ne brišemo in ne dodajamo novih. V datoteki je že definirana funkcija obrni_na_mestu(v), ki dobi verigo vozlov in jo obrne na mestu. V definiciji funkcije so vrstice med seboj pomešane. Razvrsti jih v pravi vrstni red. Funkcija mora vrniti referenco na prvi vozel. Zgled:

>>> v = iz_seznama([7, 5, 2, 1])
>>> v = obrni_na_mestu(v)
>>> v.vrni_seznam()
[1, 2, 5, 7]

3. podnaloga

V datoteki je definirana funkcija uredi_z_izbiranjem(v), ki verigo vozlov uredi z izbiranjem, a ima nekaj napak. Funkcija mora delovati tako, da najprej ustvari novo prazno verigo. V seznamu v naj poišče največji element ter ga prestavi na začetek nove verige. To naj ponavlja, doker v seznamu v ne zmanjka elementov. Funkcija naj vrne referenco na prvi vozel v urejeni verigi. Zgled:

>>> v = iz_seznama([4, 7, 3, 6, 5, 2, 1])
>>> v = uredi_z_izbiranjem(v)
>>> vrni_seznam(v)
[1, 2, 3, 4, 5, 6, 7]

Preurejanje verig vozlov: ustvari funkcije

Za spodnje naloge morate uvoziti vse definicije iz naloge Veriga vozlov. To storite z:

from veriga_vozlov import Vozel, dodaj_na_konec, dodaj_na_zacetek, vrni_seznam, iz_seznama

1. podnaloga

Sestavite funkcijo preuredi_parnost(v), ki kot argument prejme referenco na vozel ter verigo vozlov tako preuredi, da postavi vse vozle, ki vsebujejo lih podatek na začetek, vozle, ki vsebujejo sod podatek pa na konec. Funkcija naj vrne referenco na začetek preurejene verige. Na primer:

>>> v = iz_seznama([7, 5, 2, 1, 3, 4, 9, 8])
>>> v = preuredi_parnost(v)
>>> v.vrni_seznam()
[7, 5, 1, 3, 9, 2, 4, 8]

2. podnaloga

Pepi je sestavil verigo vozlov in ugotovil, da je elemente nizal v seznam v napačnem vrstnem redu. Zdaj je treba seznam obrniti, tako da obstoječih vozlov ne brišemo in ne dodajamo novih. Sestavite funkcijo obrni_na_mestu(v), ki dobi verigo vozlov in jo obrne na mestu. Funkcija mora vrniti referenco na prvi vozel. Zgled:

>>> v = iz_seznama([7, 5, 2, 1])
>>> v = obrni_na_mestu(v)
>>> v.vrni_seznam()
[1, 2, 5, 7]

3. podnaloga

Napišite funkcijo uredi_z_izbiranjem(v), ki verigo vozlov uredi z izbiranjem. Funkcija naj deluje tako, da najprej ustvari novo prazno verigo. V seznamu v naj poišče največji element ter ga prestavi na začetek nove verige. To naj ponavlja, doker v seznamu v ne zmanjka elementov. Funkcija naj vrne referenco na prvi vozel v urejeni verigi. Zgled:

>>> v = iz_seznama([4, 7, 3, 6, 5, 2, 1])
>>> v = uredi_z_izbiranjem(v)
>>> vrni_seznam(v)
[1, 2, 3, 4, 5, 6, 7]

Branje verig vozlov

Za spodnje naloge morate uvoziti vse definicije iz naloge Veriga vozlov. To storite z:

from veriga_vozlov import Vozel, dodaj_na_konec, dodaj_na_zacetek, vrni_seznam, iz_seznama

1. podnaloga

Sestavite funkcijo dolzina(prvi), ki vrne število vozlov v verigi vozlov, ki se začne z vozlom prvi. Zgled:

>>> v = Vozel('sobota')
>>> v = dodaj_na_konec(v, 'nedelja')
>>> v = dodaj_na_zacetek(v, 'petek')
>>> dolzina(v)
3

2. podnaloga

Sestavite funkcijo zadnji_vozel(prvi), ki vrne referenco na zadnji vozel v verigi vozlov, ki se začne z vozlom prvi. Zgled:

>>> v = iz_seznama(['sreda', 'četrtek', 'petek', 'sobota'])
>>> zadnji_vozel(v).podatek
'sobota'

3. podnaloga

Sestavite funkcijo seznam_sodih(prvi), ki vrne seznam vseh sodih elementov v verigi vozlov, ki se začne z vozlom prvi. Predpostavite lahko, da so vsi podatki cela števila. Zgled:

>>> v = iz_seznama([3, 4, 5, 6, 7, 8, 9, 10, 11])
>>> seznam_sodih(v)
[4, 6, 8, 10]

4. podnaloga

Sestavite funkcijo pogojni_seznam(prvi, pogoj), ki kot argument dobil verigo vozlov, ki se začne z vozlom prvi, ter funkcijo pogoj, ki sprejme en element in vrne logično vrednost. Funkcija pogojni_seznam naj sestavi in vrne seznam vseh podatkov, pri katerih funkcija pogoj vrne True. Zgled:

>>> v = iz_seznama(['sreda', 'četrtek', 'petek', 'sobota'])
>>> pogojni_seznam(v, lambda s: s.endswith('ek'))
['četrtek', 'petek']

5. podnaloga

Sestavite funkcijo je_urejen(prvi), ki vrne True, če so podatki v verigi vozlov urejeni naraščajoče in False, če niso. Zgled:

>>> v = iz_seznama([1, 2, 4, 7, 8])
>>> je_urejen(v)
True
>>> v = iz_seznama([1, 2, 4, 3, 7])
>>> je_urejen(v)
False

Izštevanka

1. podnaloga

Otroci se bodo igrali skrivalnice. Izbrati morajo nekoga, ki bo mižal, zato so se vsi postavili v krog. Uporabljajo zelo popularno izštevanko, ki ima n zlogov. Sestavite funkcijo kdo_mizi(imena, n), ki kot argument dobi seznam imen in naravno število n. Funkcija naj najprej sestavi krožni seznam (tako kot verižni seznam, samo da zadnji element kaže na prvega). Nato vozle izločamo iz kroga, tako da zbrišemo $n$-tega in začnemo ponovno izštevanje pri naslednjemu. Funkcija na vrne ime otroka, ki bo mižal. Zgled:

>>> kdo_mizi(['Mojca', 'Janez', 'Micka', 'Peter', 'Matjaž', 'Jožefa'], 5)
'Mojca'

Ne pozabi na from veriga_vozlov import *

2. podnaloga

Sestavite še funkcijo zgodovina_izstevanja(imena, n), ki naj deluje podobno kot funkcija iz prve podnaloge, le da vrne seznam, ki vsebuje imena v takem vrstnem redu, kot smo jih izločali pri izštevanki. Zgled:

>>> zgodovina_izstevanja(['Mojca', 'Janez', 'Micka', 'Peter', 'Matjaž', 'Jožefa'], 5)
['Matjaž', 'Peter', 'Jožefa', 'Janez', 'Micka', 'Mojca']

3. podnaloga

Zdaj pa sestavite še funkcijo odhajanje_iz_kroga(imena, n), ki deluje podobno kot prejšnja funkcija, le da vrne verižni seznam namesto običajnega seznama. Vozli naj bodo urejeni tako, da je v zadnjem vozlu shranjeno ime otroka, ki je najprej zapustil krog. Zgled:

>>> v = odhajanje_iz_kroga(['Mojca', 'Janez', 'Micka', 'Peter', 'Matjaž', 'Jožefa'], 5)
>>> v.vrni_seznam()
['Mojca', 'Micka', 'Janez', 'Jožefa', 'Peter', 'Matjaž']

Časovna zahtevnost (osnovno)

Ocenjevanje časovne zahtevnosti

Dostikrat lahko časovno zahtevnost algoritma ocenimo že iz njegove izvorne kode.

1. podnaloga

Dane naj bodo sledeče funkcije:

def vsota1(n):
    vsota = 0
    for i in range(n):
        for j in range(n):
            vsota += i + j
    return vsota

def vsota2(n):
    vsota = 0
    for i in range(n):
        for j in range(100):
            vsota += i + j
    return vsota

def vsota3(n):
    vsota = 0
    for i in range(n):
        for j in range(n):
            vsota += sum(range(i))
    return vsota

V spremenljivko potence1 shranite nabor potenc njihovih časovnih zahtevnosti v odvisnosti od vhoda $n$. Na primer, če bi imele funkcije časovne zahtevnosti $O(n^3)$, $O(n)$ in $O(n^4)$, bi v spremenljivko potence1 shranili nabor (3, 1, 4).

2. podnaloga

Dane naj bodo sledeče funkcije na seznamih:

def poisci_max1(sez):
    return sez.index(max(sez))

def poisci_max2(sez):
    najvecji = None
    for i in range(len(sez)):
        if najvecji is None or sez[i] > najvecji:
            najvecji_i = i
            najvecji = sez[i]
    return najvecji_i

def poisci_max3(sez):
    for i in range(len(sez)):
        if sez[i] == max(sez):
            return i

V spremenljivko potence2 shranite nabor potenc njihovih časovnih zahtevnosti v odvisnosti od dolžine vhodnega seznama.

3. podnaloga

Dane naj bodo sledeče funkcije, ki izračunajo sled kvadratne matrike velikosti $n \times n$:

def sled1(mat):
    sled = 0
    for i in range(len(mat)):
         for j in range(len(mat)):
             if i == j:
                 sled += mat[i][j]
    return sled

def sled2(mat):
    sled = 0
    for i in range(len(mat)):
         sled += mat[i][i]
    return sled

def sled3(mat):
    sled = 0
    for i, vrstica in enumerate(mat):
         sled += vrstica[i]
    return sled

V spremenljivko potence3 shranite nabor potenc njihovih časovnih zahtevnosti v odvisnosti od števila $n$.

4. podnaloga

Dane naj bodo sledeče funkcije, ki iščejo dani element v urejenem seznamu:

def poisci1(sez, x):
    return x in sez

def poisci2(sez, x):
    for y in sez:
        if x == y:
            return True
    return False

def poisci3(sez, x):
    od, do = 0, len(sez)
    while od < do:
        sredina = (od + do) // 2
        sredinski = sez[sredina]
        if x == sredinski:
            return True
        elif x < sredinski:
            do = sredina
        elif x > sredinski:
            od = sredina + 1
    return False

def poisci4(sez, x, od=0, do=None):
    if do is None:
        do = len(sez)
    if od == do:
        return False
    else:
        sredina = (od + do) // 2
        sredinski = sez[sredina]
        if x == sredinski:
            return True
        elif x < sredinski:
            return poisci4(sez, x, od, sredina)
        elif x > sredinski:
            return poisci4(sez, x, sredina + 1, do)

def poisci5(sez, x):
    if not sez:
        return False
    else:
        sredina = len(sez) // 2
        sredinski = sez[sredina]
        if x == sredinski:
            return True
        elif x < sredinski:
            return poisci5(sez[:sredina], x)
        elif x > sredinski:
            return poisci5(sez[sredina + 1:], x)

V spremenljivko zahtevnosti4 shranite nabor njihovih časovnih zahtevnosti, v odvisnosti od dolžine seznama. Časovne zahtevnosti opišite z enim od nizov 'O(1)', 'O(n)', 'O(n^2)', 'O(log n)', 'O(n log n)', 'O(n^3)'.

Največja podvsota

1. podnaloga

Sestavite funkcijo najvecja_podvsota(sez), ki izračuna največjo podvsoto strnjenega podzaporedja števil v seznamu sez. Naloga je opravljena, če dosežete vsaj kvadratično časovno zahtevnost, možna pa je linearna. Primer:

>>> najvecja_podvsota([2, 3, -3, -4, 2])
5
>>> najvecja_podvsota([2, 3, -3, 4, 2])
8

Največji podprodukt

1. podnaloga

Sestavite funkcijo najvecji_podprodukt(sez), ki izračuna največji produkt strnjenega podzaporedja števil v seznamu sez. Naloga je opravljena, če dosežete vsaj kvadratično časovno zahtevnost, možna pa je linearna. Primer:

>>> najvecji_podprodukt([0.5, 2, 0.7, 3])
4.2
>>> najvecji_podprodukt([2, 3, 0, 4, 2])
8

Če naloge ne znaš rešiti za poljubna števila, predpostavi, da so v seznamu samo pozitivna števila.

Časovna zahtevnost

Ocenjevanje časovne zahtevnosti

Dostikrat lahko časovno zahtevnost algoritma ocenimo že iz njegove izvorne kode.

1. podnaloga

Dane naj bodo sledeče funkcije:

def vsota1(n):
    vsota = 0
    for i in range(n):
        for j in range(n):
            vsota += i + j
    return vsota

def vsota2(n):
    vsota = 0
    for i in range(n):
        for j in range(100):
            vsota += i + j
    return vsota

def vsota3(n):
    vsota = 0
    for i in range(n):
        for j in range(n):
            vsota += sum(range(i))
    return vsota

V spremenljivko potence1 shranite nabor potenc njihovih časovnih zahtevnosti v odvisnosti od vhoda $n$. Na primer, če bi imele funkcije časovne zahtevnosti $O(n^3)$, $O(n)$ in $O(n^4)$, bi v spremenljivko potence1 shranili nabor (3, 1, 4).

2. podnaloga

Dane naj bodo sledeče funkcije na seznamih:

def poisci_max1(sez):
    return sez.index(max(sez))

def poisci_max2(sez):
    najvecji = None
    for i in range(len(sez)):
        if najvecji is None or sez[i] > najvecji:
            najvecji_i = i
            najvecji = sez[i]
    return najvecji_i

def poisci_max3(sez):
    for i in range(len(sez)):
        if sez[i] == max(sez):
            return i

V spremenljivko potence2 shranite nabor potenc njihovih časovnih zahtevnosti v odvisnosti od dolžine vhodnega seznama.

3. podnaloga

Dane naj bodo sledeče funkcije, ki izračunajo sled kvadratne matrike velikosti $n \times n$:

def sled1(mat):
    sled = 0
    for i in range(len(mat)):
         for j in range(len(mat)):
             if i == j:
                 sled += mat[i][j]
    return sled

def sled2(mat):
    sled = 0
    for i in range(len(mat)):
         sled += mat[i][i]
    return sled

def sled3(mat):
    sled = 0
    for i, vrstica in enumerate(mat):
         sled += vrstica[i]
    return sled

V spremenljivko potence3 shranite nabor potenc njihovih časovnih zahtevnosti v odvisnosti od števila $n$.

4. podnaloga

Dane naj bodo sledeče funkcije, ki iščejo dani element v urejenem seznamu:

def poisci1(sez, x):
    return x in sez

def poisci2(sez, x):
    for y in sez:
        if x == y:
            return True
    return False

def poisci3(sez, x):
    od, do = 0, len(sez)
    while od < do:
        sredina = (od + do) // 2
        sredinski = sez[sredina]
        if x == sredinski:
            return True
        elif x < sredinski:
            do = sredina
        elif x > sredinski:
            od = sredina + 1
    return False

def poisci4(sez, x, od=0, do=None):
    if do is None:
        do = len(sez)
    if od == do:
        return False
    else:
        sredina = (od + do) // 2
        sredinski = sez[sredina]
        if x == sredinski:
            return True
        elif x < sredinski:
            return poisci4(sez, x, od, sredina)
        elif x > sredinski:
            return poisci4(sez, x, sredina + 1, do)

def poisci5(sez, x):
    if not sez:
        return False
    else:
        sredina = len(sez) // 2
        sredinski = sez[sredina]
        if x == sredinski:
            return True
        elif x < sredinski:
            return poisci5(sez[:sredina], x)
        elif x > sredinski:
            return poisci5(sez[sredina + 1:], x)

V spremenljivko zahtevnosti4 shranite nabor njihovih časovnih zahtevnosti, v odvisnosti od dolžine seznama. Časovne zahtevnosti opišite z enim od nizov 'O(1)', 'O(n)', 'O(n^2)', 'O(log n)', 'O(n log n)', 'O(n^3)'.

Merjenje časovne zahtevnosti

Če za algoritem nimamo na voljo izvorne kode, časovne zahtevnosti ne moremo oceniti drugače, kot da jo poskušamo izmeriti. Če odkomentirate vrstico

# import zlib, base64; exec(zlib.decompress(base64.b64decode('eJwll7eu...

v priloženi kodi, naložite definicijo 14 funkcij, katerih časovno zahtevnost boste merili pri tej nalogi. Funkcije kot vhod sprejmejo celo število n, glede na katerega časovno zahtevnost ocenjujemo.

1. podnaloga

Funkcije f1a, f1b, f1c, f1d in f1e imajo časovne zahtevnosti oblike $O(n^k)$ za nek neznani $k$. V spremenljivko potence1 shranite nabor potenc časovnih zahtevnosti posameznih funkcij. Na primer, če bi imele funkcije časovne zahtevnosti $O(n^3)$, $O(n)$, $O(n^4)$, $O(n)$ in $O(n^2)$, bi v spremenljivko potence1 shranili nabor (3, 1, 4, 1, 2).

2. podnaloga

V spremenljivko potence2 shranite nabor potenc časovnih zahtevnosti funkcij f2a, f2b, f2c, f2d in f2e.

3. podnaloga

V spremenljivko potence3 shranite nabor potenc časovnih zahtevnosti funkcij f3a, f3b, f3c in f3d.

Največji podprodukt

1. podnaloga

Sestavite funkcijo najvecji_podprodukt(sez), ki izračuna največji produkt strnjenega podzaporedja pozitivnih števil v seznamu sez. Naloga je opravljena, če dosežete vsaj kvadratično časovno zahtevnost, možna pa je linerarna. Primer:

>>> najvecji_podprodukt([0.5, 2, 0.7, 3])
4.2
>>> najvecji_podprodukt([2, 3, 0, 4, 2])
8

Pobijajoči se pari

1. podnaloga

Sestavite funkcijo nicelni_pari_v_urejenem(seznam), ki vrne True, če v urejenem seznamu celih števil obstaja par elementov, ki se sešteje v 0, in False sicer.

2. podnaloga

Sestavite funkcijo nicelni_pari_v_neurejenem(seznam), ki vrne True, če v neurejenem seznamu celih števil obstaja par elementov, ki se sešteje v 0, in False sicer.

Največja podvsota matrike

1. podnaloga

Sestavite funkcijo matrika_delnih_vsot(matrika), ki vrne matriko delnih vsot, v kateri je na vsakem mestu vsota vseh elementov v bloku levo zgoraj od danega mesta. Na primer, če je matrika enaka

 1  2 -1
-5  4  6
 2  0  1

mora funkcija vrniti matriko

 1  3  2
-4  2  7
-2  4  10

Če želite uspešno rešiti zadnji del naloge, mora funkcija delovati v linearnem času (v odvisnosti od velikosti matrike).

2. podnaloga

Sestavite funkcijo vsota_podmatrike(delne_vsote, i1, j1, i2, j2), ki iz matrike delnih vsot, kot jo izračuna prejšnja funkcija, v konstantnem času izračuna vsoto vseh elementov med vrsticami i1 (vključno) in i2 (brez) ter stolpci j1 (vključno) in j2 (brez).

Natančneje, če velja delne_vsote = matrika_delnih_vsot(matrika), potem velja

vsota_podmatrike(delne_vsote, i1, j1, i2, j2)
= sum(vrstica[j1:j2] for vrstica in matrika[i1:i2])

Časovna zahtevnost (dodatne vaje)

Največje podvsote

V gradivih že spoznali tri algoritme za izračun največje vsote strnjenega podzaporedja v danem seznamu. Pri tej nalogi boste namesto vsote izračunali krajišča vseh možnih podzaporedij, pri katerih je ta vsota dosežena. Na primer, pri seznamu [12, 3, 5, -10, -8, 7, 11, -30, 6, 8, -40] dobimo največjo vsoto za podzaporedji [12, 3, 5] ter [12, 3, ..., 7, 11]. V slogu Pythona bomo prvo podzaporedje predstavili s parom (0, 3), saj je [12, 3, 5] ravno [12, 3, 5, -10, ..., -40][0:3], drugo podzaporedje pa s parom (0, 7).

1. podnaloga

Priloženo kodo, ki v kubičnem času izračuna največjo vsoto strnjenega podzaporedja v zaporedju sez, spremenite, da bo vrnila množico parov vseh krajišč podzaporedij, kjer je ta vsota dosežena.

2. podnaloga

Priloženo kodo, ki v kvadratnem času izračuna največjo vsoto strnjenega podzaporedja v zaporedju sez, spremenite, da bo vrnila množico parov vseh krajišč podzaporedij, kjer je ta vsota dosežena.

3. podnaloga

Priloženo kodo, ki v linearnem času izračuna največjo vsoto strnjenega podzaporedja v zaporedju sez, spremenite, da bo vrnila množico parov vseh krajišč podzaporedij, kjer je ta vsota dosežena. Ker je število vseh takih parov lahko tudi kvadratno v odvisnosti od zaporedja, pri vsakem možnem začetku izberite le najkrajše podzaporedje, kjer je vsota dosežena.

Dvojiško drevo I

Primer implementacije dvojiškega drevesa lahko dobite tukaj.

Predvidene operacije so:

drevo.prazno

drevo.levo

drevo.desno

drevo.podatek

Drevo() ustvari prazno dvojiško drevo

Drevo(podatek, levo, desno) ustvari dvojiško drevo z danim podatkom v korenu ter levim in desnim sinom. Če kakšen od sinov manjka, se privzame, da je prazen.

Ogrevanje

Poglejte implementacijo drevesa, ki jo uporabljate, in rešite naslednje naloge.

1. podnaloga

Napišite funkcijo vrni_koren(drevo), ki vrne podatek v korenu drevesa, če pa je drevo prazno pa vrne None.

2. podnaloga

Napišite funkcijo je_list(drevo), ki preveri ali je podano drevo list.

3. podnaloga

Napišite funkcijo nikoli_levo(drevo), ki preveri, da ima vsako vozlišče drevesa kvečjemu desno poddrevo.

4. podnaloga

Napišite funkcijo visina(drevo), ki izračuna višino dvojiškega drevesa.

Preiskovanje dreves

V vseh spodnjih primerih naj bo d dvojiško drevo na spodnji sliki:

     5
   /   \
  3     2
 /     / \
1     6   9

1. podnaloga

Sestavite funkcijo vsota(drevo), ki vrne vsoto vseh števil v drevesu drevo. Zgled:

>>> vsota(d)
26

2. podnaloga

Dodajte funkcijo stevilo_listov(drevo), ki vrne število listov v drevesu drevo. Zgled:

>>> stevilo_listov(d)
3

3. podnaloga

Dodajte funkcijo minimum(drevo), ki vrne najmanjše število v drevesu. Če je drevo prazno, naj funkcija vrne None. Zgled:

>>> minimum(d)
1
>>> minimum(Drevo())
None

4. podnaloga

Dodajte funkcijo premer(drevo), ki vrne premer drevesa, torej dolžino najdaljše poti med katerima koli dvema vozliščema v drevesu. Zgled:

>>> premer(Drevo('x', levo=Drevo('y'), desno=Drevo('z')))
2  # najdaljša pot je y-x-z
>>> premer(Drevo('x', levo=Drevo('y', levo=Drevo('z'), desno=Drevo('w'))))
2  # najdaljša pot je y-z-w
>>> premer(Drevo('x', levo=Drevo('y'), desno=Drevo('z', levo=Drevo('w'))))
3  # najdaljša pot je y-x-z-w
>>> premer(Drevo())
-inf  # v drevesu ni vozlišč
>>> premer(Drevo('x'))
0  # v drevesu je le eno vozlišče

Pregledi dreves

V vseh spodnjih primerih delovanja funkcij je d dvojiško drevo na spodnji sliki:

     5
   /   \
  3     2
 /     / \
1     6   9

1. podnaloga

Sestavite funkcijo premi_pregled(drevo), ki sestavi tabelo elementov drevesa drevo v premem vrstnem redu (pre-order). To pomeni, da najprej obiščemo koren drevesa, nato levo poddrevo in na koncu še desno poddrevo. Vozlišča poddreves obiskujemo po enakem pravilu. Zgled:

>>> premi_pregled(d)
[5, 3, 1, 2, 6, 9]

2. podnaloga

Sestavite funkcijo vmesni_pregled(drevo), ki sestavi tabelo elementov drevesa drevo v vmesnem vrstnem redu (in-order). To pomeni, da najprej obiščemo levo poddrevo, nato koren drevesa in na koncu še desno poddrevo. Vozlišča poddreves obiskujemo po enakem pravilu. Zgled:

>>> vmesni_pregled(d)
[1, 3, 5, 6, 2, 9]

3. podnaloga

Sestavite generator obratni_pregled(drevo), sestavi tabelo elementov drevesa drevo v obratnem vrstnem redu (post-order). To pomeni, da najprej obiščemo levo poddrevo, nato desno poddrevo in na koncu še koren drevesa. Vozlišča poddreves obiskujemo po enakem pravilu. Zgled:

>>> obratni_pregled(d)
[1, 3, 6, 9, 2, 5]

4. podnaloga

Sestavite funkcijo pregled_po_nivojih(drevo), sestavi tabelo elementov drevesa drevo v zaporedju po nivojih (level-order). To pomeni, da najprej obiščemo koren, nato vsa vozlišča, ki so na globini 1, nato vsa vozlišča, ki so na globini 2 itn. Vsa vozlišča na isti globini naštejemo od leve proti desni. Zgled:

>>> pregled_po_nivojih(d)
[5, 3, 2, 1, 6, 9]

Izrisi dreves

V vseh spodnjih primerih delovanja funkcij je d dvojiško drevo na spodnji sliki:

     5
   /   \
  3     2
 /     / \
1     6   9

1. podnaloga

Sestavite funkcijo premi_izris(drevo), ki zgornje drevo izriše v obliki

    -> 1
  -> 3
-> 5
    -> 6
  -> 2
    -> 9

Pri rekurzivni funkciji si je koristno pomagati z neobveznim parametrom nivo

2. podnaloga

Sestavite funkcijo vmesni_izris(drevo), ki zgornje drevo izriše v obliki

-> 5
  -> 3
    -> 1
  -> 2
    -> 6
    -> 9

Pri rekurzivni funkciji si je koristno pomagati z nebveznim parametrom nivo

3. podnaloga

Sestavite funkcijo obratni_izris(drevo), ki zgornje drevo izriše v obliki

    -> 1
  -> 3
    -> 6
    -> 9
  -> 2
-> 5

Pri rekurzivni funkciji si je koristno pomagati z nebveznim parametrom nivo

4. podnaloga

Sestavite funkcijo izris_po_nivojih(drevo), ki zgornje drevo izriše v obliki

    5
  3     2
1     6   9

Levo poddrevo mora biti poravnano desno in umaknjeno en presledek v levo. Desno poddrevo mora biti poravnanlo levo in umaknjeno en presledek desno. Bodite pozorni na dolžino izpisa podatka v korenu.

Generiranje dreves

1. podnaloga

Definirajte funkcijo drevo_v_levo(sez), ki seznam pretvori v drevo, ki ima le leva poddrevesa. Vrstni red elementov naj ustreza vmesnemu pregledu (in-order). Na primer drevo_v_levo([1, 2, 3, 4]) vrne

       4
      /
     3
    /
   2
  /
 1

2. podnaloga

Napišite funkcijo polno_drevo_nicel(n), ki vrne polno drevo globine n, katerega podatki so ničle.

3. podnaloga

Napišite funkcijo polno_drevo_globin(n), ki vrne polno drevo globine n, katerega podatki so globine vozlišč. Na primer polno_drevo_globin(3) je enako

     1
   /   \
  2     2
 / \   / \
3   3 3   3

4. podnaloga

Definirajte funkcijo drevo_vsot(sez), ki za rezultat vrne drevo delnih vsot elementov seznama, kjer postopoma seštevamo sosednja elementa. Na primer drevo_vsot([1, 2, 3, 4, 5]) vrne

        15
      /    \
     10     5
   /    \    \
  3      7    5
 / \    / \    \
1   2  3   4    5

Če je podvsot liho, se najbolj desna prenese na višji nivo.

Pregledi dreves z generatorji

V vseh spodnjih primerih delovanja funkcij je d dvojiško drevo na spodnji sliki:

     5
   /   \
  3     2
 /     / \
1     6   9

Namig: spomnite se ukazov yield in yield from.

1. podnaloga

Sestavite generator premi_pregled(drevo), ki vrača podatke v vozliščih drevesa v premem vrstnem redu (pre-order). To pomeni, da najprej obiščemo koren drevesa, nato levo poddrevo in na koncu še desno poddrevo. Vozlišča poddreves obiskujemo po enakem pravilu. Zgled:

>>> [x for x in premi_pregled(d)]
[5, 3, 1, 2, 6, 9]

2. podnaloga

Sestavite generator vmesni_pregled(drevo), ki vrača podatke v vozliščih drevesa v vmesnem vrstnem redu (in-order). To pomeni, da najprej obiščemo levo poddrevo, nato koren drevesa in na koncu še desno poddrevo. Vozlišča poddreves obiskujemo po enakem pravilu. Zgled:

>>> [x for x in vmesni_pregled(d)]
[1, 3, 5, 6, 2, 9]

3. podnaloga

Sestavite generator obratni_pregled(drevo), ki vrača podatke v vozliščih drevesa v obratnem vrstnem redu (post-order). To pomeni, da najprej obiščemo levo poddrevo, nato desno poddrevo in na koncu še koren drevesa. Vozlišča poddreves obiskujemo po enakem pravilu. Zgled:

>>> [x for x in obratni_pregled(d)]
[1, 3, 6, 9, 2, 5]

4. podnaloga

Sestavite generator pregled_po_nivojih(drevo), ki vrača podatke v vozliščih drevesa po nivojih (level-order). To pomeni, da najprej obiščemo koren, nato vsa vozlišča, ki so na globini 1, nato vsa vozlišča, ki so na globini 2 itn. Vsa vozlišča na isti globini naštejemo od leve proti desni. Zgled:

>>> [x for x in pregled_po_nivojih(d)]
[5, 3, 2, 1, 6, 9]

Dvojiško drevo II

Spreminjanje dreves

Dan je razred Drevo, ki predstavlja dvojiško drevo.

1. podnaloga

Dodajte metodo odrezi(self, n), ki odstrani vsa vozlišča, ki ležijo na globini (oz. nivojih) večji od n. Zgled:

>>> d = Drevo(5,
              levo=Drevo(3, levo=Drevo(1)),
              desno=Drevo(2, levo=Drevo(6), desno=Drevo(9)))
>>> d.odrezi(2)
>>> d
Drevo(5,
      levo = Drevo(3),
      desno = Drevo(2))

2. podnaloga

Sestavite metodo potroji(self), ki pod vsakim vozliščem doda še dve njegovi kopiji. Levo poddrevo prestavi levo od leve kopije, desno poddrevo pa desno od desne kopije. Zgled:

>>> d = Drevo(5, levo=Drevo(3), desno=Drevo(2))
>>> d.potroji()
>>> d
Drevo(5,
      levo = Drevo(5,
                   levo = Drevo(3,
                                levo = Drevo(3),
                                desno = Drevo(3)),
                   desno = Drevo()),
      desno = Drevo(5,
                    levo = Drevo(),
                    desno = Drevo(2,
                                  levo = Drevo(2),
                                  desno = Drevo(2))))

3. podnaloga

Sestavite metodo prezrcali(self), ki drevo prezrcali. Zgled:

>>> d = Drevo(5, levo=Drevo(3), desno=Drevo(2, levo=Drevo(1)))
>>> d.prezrcali()
>>> d
Drevo(5,
      levo = Drevo(2,
                   desno = Drevo(1)),
      desno = Drevo(3)

Rekonstrukcije dreves iz pregledov

V prvih treh nalogah je odgovor v primeru drevo na spodnji sliki.

      1
     / \
    3   4
   / \   \
  9   6   8
 /   /   /
5   7   2

1. podnaloga

Sestavite funkcijo drevo_vmesni_premi(vmesni, premi), ki iz seznama elementov v vmesnem in premem pregledu rekonstruira dvojiško drevo. Predpostavite lahko, da so vsi elementi drevesa med seboj paroma različni.

>>> drevo_vmesni_premi([5, 9, 3, 7, 6, 1, 4, 2, 8], [1, 3, 9, 5, 6, 7, 4, 8, 2])
Drevo(1, levo=Drevo(3, levo=Drevo(9, levo=Drevo(5)), desno=Drevo(6, ...)), ...)

2. podnaloga

Sestavite funkcijo drevo_vmesni_obratni(vmesni, obratni), ki iz seznama elementov v vmesnem in obratnem pregledu rekonstruira dvojiško drevo. Predpostavite lahko, da so vsi elementi drevesa med seboj paroma različni.

>>> drevo_vmesni_obratni([5, 9, 3, 7, 6, 1, 4, 2, 8], [5, 9, 7, 6, 3, 2, 8, 4, 1])
Drevo(1, levo=Drevo(3, levo=Drevo(9, levo=Drevo(5)), desno=Drevo(6, ...)), ...)

3. podnaloga

Sestavite funkcijo drevo_vmesni_nivojski(vmesni, nivojski), ki iz seznama elementov v vmesnem in nivojskem pregledu rekonstruira dvojiško drevo. Predpostavite lahko, da so vsi elementi drevesa med seboj paroma različni.

>>> drevo_vmesni_nivojski([5, 9, 3, 7, 6, 1, 4, 2, 8], [1, 3, 4, 9, 6, 8, 5, 7, 2])
Drevo(1, levo=Drevo(3, levo=Drevo(9, levo=Drevo(5)), desno=Drevo(6, ...)), ...)

4. podnaloga

Sestavite funkcijo drevesa_premi_obratni(premi, obratni), ki iz seznama elementov v premem in obratnem pregledu rekonstruira množico vseh možnih dvojiških dreves. Predpostavite lahko, da so vsi elementi drevesa med seboj paroma različni. Na primer:

drevesa_premi_obratni([1, 2, 4, 7, 8, 3], [4, 7, 2, 3, 8, 1])

naj vrne množico spodnjih dveh dreves:

     1               1    
   /   \           /   \    
  2     8         2     8    
 / \     \       / \   /
4   7     3     4   7 3

5. podnaloga

Sestavite funkcijo drevesa_vmesni_premi(vmesni, premi), ki iz seznama elementov v vmesnem in premem pregledu rekonstruira množico vseh možnih dvojiških dreves, pri čemer se lahko elementi v drevesu tudi ponovijo.

Plače

V nekem uspešnem slovenskem podjetju so zaposleni urejeni hierarhično. Vsakdo razen direktorja ima natanko enega nadrejenega. Vsak uslužbenec ima lahko pod seboj največ dva podrejena (levega in desnega). Primer takšne hierarhije (številke so njihove plače):

lucka = Drevo('Lučka', 800, levo=Drevo('Peter', 900), desno=Drevo('Tadeja', 700))
matjaz = Drevo('Matjaž', 1100, levo=Drevo('Simona', 700), desno=Drevo('Boris', 1000, levo=lucka))
branko = Drevo('Branko', 900, desno=Drevo('Benjamin', 1100))
ales = Drevo('Aleš', 1500, levo=matjaz, desno=branko)

V tem podjetju imajo zelo močen sindikat. Sindikalisti so ugotovili, da višine plač niso pravične. Nedopustno je, da imajo nekateri podrejeni višje plače od svojih nadrejenih! Zato sindikat zahteva, da mora imeti vsak zaposleni vsaj za 100 € višjo plačo od kateregakoli svojega podrejenega.

Direktor bi rad analiziral podatke, preden se spusti v pogajanja s sindikalisti. Podatke o zaposlenih je shranil v podatkovno strukturo Drevo, ki je že implementirana. V vozliščih so shranjeni podatki o plačah zaposlenih (atribut placa) in njihova imena (atribut ime).

1. podnaloga

Direktorja zanima, koliko dodatnega denarja bi potreboval vsak mesec, če bi ugodil zahtevam sindikata. Želi, da sestavite metodo odprava_krivic(self), ki vrne skupno vsoto denarja, ki bi ga potreboval za odpravo krivic. Primer (če d ustreza zgornji sliki):

>>> d.odprava_krivic()
700

Komentar: Lučka bi po novem prejemala 1000 €, ker dobiva Peter 900 €. Zaradi Lučke bi moral Boris prejemati 1100 €. Zaradi Borisa pa bi moral Matjaž prejemati 1200 €. Branko bi zaradi Benjamina moral prejemati 1200 €. Vsota vseh povišic znaša 700 €.

Komentar 2: ne pozabite, da se plače nikomur ne znižajo. Torej če imata podrejena plačo 800 in 900, šef pa 1500 in se recimo zgodi, da bosta podrejena po novem imela plači 850 in 1100, bo šef obdržal plačo 1500 (in ne dobil recimo plačo 1200)

2. podnaloga

Direktor bi sindikaliste rad prepričal, da se razburjajo po nepotrebnem. Rad bi imel seznam imen vseh tistih uslužbencev, ki bi prejeli povišice. (Od vseh takih bo namreč pridobil pisne izjave, da so zadovoljni s svojo plačo.) Napišite funkcijo pisne_izjave(self), ki vrne množico imen vseh zaposlenih, ki bi prejeli povišico. Primer:

>>> d.pisne_izjave()
{'Lučka', 'Boris', 'Branko', 'Matjaž'}

3. podnaloga

Po večtedenskih pogajanjih s sindikatom je imel direktor poln k███ vsega, zato je udaril po mizi! Odločil se je, da bo najprej vsem plače zmanjšal na "minimalce", potem pa bo povišal plače na način, ki ga predlaga sindikat. Tako bo volk sit in koza cela. Napišite metodo uravnilovka(self), ki vrne skupno vsoto denarja, ki bi ga na ta način prihranil vsak mesec (glede na trenutne plače). "Minimalec" znaša 500 €. Primer:

>>> d.uravnilovka()
3100

Aritmetični izraz

Aritmetične izraze, kot je na primer $(9 * (2 - 7)) + (5 * 3)$, lahko zapišemo v obliki dvojiškega drevesa (glejte spodaj). V vsakem vozlišču je zapisano bodisi neko celo število bodisi nek aritmetični operator. (Da ne bi imeli problemov z deljenjem s številom $0$, se bomo omejili na operatorje $+$, $-$ in $*$.) Če vozlišče predstavlja operator, potem ima nujno levega in desnega sina, ki predstavljata ustrezna podizraza. Če vozlišče predstavlja število, je nujno list drevesa. (Ste opazili, da je v korenu drevesa na spodnji sliki operator $+$, ki ga v tem izrazu izračunamo kot zadnjega?)

zgled = Izraz('+',
              levo=Izraz('*',
                         levo=Izraz(9),
                         desno=Izraz('-',
                                     levo=Izraz(2),
                                     desno=Izraz(7))),
              desno=Izraz('*',
                          levo=Izraz(5),
                          desno=Izraz(3)))

Implementacija podatkovne strukture Izraz je že v kodi, ki jo prenesete s Toma. Vsako vozlišče ima atribut operator, ki je lahko '+', '-', '*' ali None. Če je njegova vrednost None, predstavlja število in vozlišče ima še atribut stevilo (celo število). Če vrednost atributa operator ni None, ima vozlišče še atributa levo in desno, ki predstavljata levi in desni podizraz.

class Izraz:

    def __init__(self, operator, **kwargs):
        if operator in ['+', '-', '*']:
            self.operator = operator
            self.levo = kwargs.get('levo')
            self.desno = kwargs.get('desno')
        else:
            self.operator = None
            self.stevilo = operator

    def __repr__(self):
        if self.operator is None:
            return 'Izraz({0})'.format(self.stevilo)
        else:
            opis = repr(self.operator) + ', levo={0}, desno={1}'.format(self.levo, self.desno)
            return 'Izraz({0})'.format(opis)

1. podnaloga

Sestavite metodo vrednost(self), ki izračuna in vrne vrednost tega aritmetičnega izraza. Primer (če d ustreza zgornji sliki):

>>> d.vrednost()
-30

2. podnaloga

Napišite metodo obicajni_zapis(self), ki vrne niz z običajnim zapisom tega izraza (glejte primer spodaj). Pred in za vsakim operatorjem naj bo po en presledek. Podizrazi naj bodo v oklepajih, razen kadar so le-ti števila. Sicer oklepajev ne smete opuščati (pa čeprav nam asociativnostni zakon to omogoča). Primer (če d ustreza zgornji sliki):

>>> d.obicajni_zapis()
'(9 * (2 - 7)) + (5 * 3)'

3. podnaloga

Sestavite metodo poenostavi(self), ki izraz poenostavi, tako da odpravi "najbolj notranje" operatorje, tj. tiste operatorje, kjer sta oba podizraza števili. Primer (če d ustreza zgornjemu izrazu):

>>> d.poenostavi()
>>> d
Izraz('+', levo=Izraz('*', levo=Izraz(9), desno=Izraz(-5)), desno=Izraz(15))

Dvojiško drevo s pregledi

Tako kot v prejšnji nalogi napišite implementacijo razreda Drevo, le da imate tokrat le en razred Drevo, vsak objekt pa ima atributa _vmesni_pregled in _premi_pregled, ki sta seznama vrednosti v vmesnem in premem pregledu drevesa. Predpostavite lahko, da bomo v drevo shranjevali le različne vrednosti, zato je drevo s tema dvema pregledoma natanko določeno.

1. podnaloga

Sestavite razred Drevo, kot je opisano v navodilih.

2. podnaloga

Če ste strukturo pravilno implementirali, lahko sedaj v vseh nalogah že podano implementacijo nadomestite s svojo tako, da namesto

from dvojisko_drevo import Drevo

pišete

from dvojisko_drevo_s_pregledi import Drevo

Poskusite in kot rešitev naloge napišite, če ste imeli kje kakšne težave.

Iskalno drevo

Iskalno drevo

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).

IskalnoDrevo(6,
    levo = IskalnoDrevo(4,
                levo = IskalnoDrevo(1,
                                levo = IskalnoDrevo(),
                                desno = IskalnoDrevo(3)),
                desno = IskalnoDrevo(5)),
    desno = IskalnoDrevo(9,
                    levo = IskalnoDrevo(7),
                    desno = IskalnoDrevo()))

class IskalnoDrevo:

    def __init__(self, vsebina=[]):
        self.prazno = True
        for n in vsebina:
            self.dodaj(n)

    def __repr__(self, zamik = ''):
        if self.prazno:
          return 'IskalnoDrevo()'.format(zamik)
        elif self.levo.prazno and self.desno.prazno:
          return 'IskalnoDrevo({1})'.format(zamik, self.vsebina)
        else:
          return 'IskalnoDrevo({1},\n{0}      levo = {2},\n{0}      desno = {3})'.\
            format(
              zamik,
              self.vsebina,
              self.levo.__repr__(zamik + '             '),
              self.desno.__repr__(zamik + '              ')
            )

    def pravilno(self, minimum=None, maksimum=None):
        if self.prazno:
            return True
        elif minimum and self.vsebina < minimum:
            return False
        elif maksimum and self.vsebina > maksimum:
            return False
        else:
            return (self.levo.pravilno(minimum, self.vsebina) and
                    self.desno.pravilno(self.vsebina, maksimum))

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

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]

Množice z iskalnimi drevesi

Podatkovno strukturo množica lahko učinkovito predstavimo z iskalnim drevesom. V tej nalogi bomo najprej definirali nekaj pomožnih funkcij na drevesih, nato pa definirali razred Mnozica, ki podpira osnovne operacije na množicah. V rešitvi uporabi razred Drevo, ki smo ga že uporabili v eni od predhodnih vaj.

1. podnaloga

Sestavite funkcijo vstavi_v_iskalno_drevo(drevo, x), ki v iskalno drevo na pravo mesto vstavi element x ter vrne novo drevo. Če je x enak podatku v korenu drevesa, naj funkcija vrne prvotno drevo.

2. podnaloga

Sestavite funkcijo ali_vsebuje(drevo, x), ki vrne True, če dano iskalno drevo vsebuje podatek x, in False, če ga ne.

3. podnaloga

Z razredom Mnozica bomo predstavili nespremenljive množice, torej take, ki ne podpirajo metod za dodajanje in odstranjevanje elementov, le metode, ki izračunajo nove množice iz obstoječih. Vsako množico bomo predstavili z objektom, ki ima dva atributa: iskalnim drevesom elementov _elementi ter velikostjo _velikost.

Sestavite razred Mnozica z metodo __init__, ki mu za neobvezen prvi argument lahko podamo iterator začetnih elementov množice.

4. podnaloga

Dodajte metodo __iter__, ki vrne iterator, ki našteva elemente množice od najmanjšega do največjega.

5. podnaloga

Za lepši prikaz dodajte še metodo __str__, ki vrne niz oblike {el1, el2, ...}, kjer so elementi množice našteti od najmanjšega do največjega.

6. podnaloga

Za dostop do velikosti množice mn in iskanja elementov v njej bi sicer lahko napisali metodi mn.velikost() in mn.vsebuje(x), vendar je bolj Pythonovsko, da definiramo metodi __len__ in __contains__, da lahko pišemo kar len(mn) in x in mn oz. x not in mn. Definirajte ju.

Dvojiško drevo (dodatne vaje)

Skladišče

Neko podjetje ima skladišče svojih izdelkov organizirano v obliki drevesne strukture. Skladišče je sestavljeno iz več prostorov (vozlišč), vhod v skladišče je samo en (pri korenu), iz vsakega prostora pa vodita hodnika do največ dveh drugih prostorov (levo in desno poddrevo).

Oznaka prostora je kar opis poti, kako pridemo od vhoda do ustreznega prostora, pri čemer črka L pomeni levi hodnik, črka D pa desni hodnik. Oznaka DLD tako pomeni, da pri vhodu zavijemo desno, v naslednjem prostoru levo in nato še enkrat desno. V vhodu izdelkov ne hranimo.

Skladiščnik Stanko je pri zlaganju škatel z izdelki izjemno sistematičen, saj da novo škatlo vedno desno od zadnje škatle. Pri pobiranju pa Stanko malo bolj improvizira. Če v zadnjo sobo zavije na levo, bo tudi pobral najbolj levo škatlo, torej prvo, ki jo je odložil (tako kot pri vrsti). Če pa v zadnjo sobo zavije na desno, pa bo pobral najbolj desno, torej tisto, ki jo je odložil nazadnje (tako kot pri skladu).

Če bo v škatli več izdelkov, kot jih je treba, bo preostanek odložil nazaj na desno, če pa jih bo premalo, bo odprl še naslednjo škatlo. Če v sobi izdelkov ne bo dovolj, bo stvari pustil pri miru, vendar bo težavo zapisal v končno poročilo.

1. podnaloga

Napišite funkcijo stanko(narocila, porocilo), ki iz datoteke z imenom narocila prebere podatke o oznaki, cilju ter količini izdelkov (pozitivno za dobavo in negativno za naročilo), nato pa v datoteko z imenom porocilo najprej izpiše vsa naročila, ki jih ni mogel izvesti, na dnu pa še končno stanje v skladišču, urejeno po prostorih, kot si sledijo pri premem pregledu. V izpis naj vključi tudi vse prazne prostore, preko katerih dostopamo do nepraznih prostorov. Če so bila vsa naročila uspešno izvedena, naj program izpiše le končno stanje.

Na primer, za datoteko narocila.txt z vsebino

D1 LL 2
D2 LD 3
D3 D 2
D4 D 4
N1 LL -3
N2 D -1
D5 D 1
D6 LL 4
N3 LL -1

naj stanko('narocila.txt', 'porocilo.txt') v datoteko porocilo.txt zapiše:

OPOZORILA:
Naročilo N1: V prostoru LL je premalo izdelkov

KONČNO STANJE:
L: /
LL: 1, 4
LD: 3
D: 2, 3, 1

Namig: kljub temu, da je treba napisati le eno funkcijo, bo dobro, če jo razbijete na pomožne funkcije.

Iskalno drevo

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. Osnutek implementacije dobite tukaj.

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).

IskalnoDrevo(6,
    levo = IskalnoDrevo(4,
                levo = IskalnoDrevo(1,
                                levo = IskalnoDrevo(),
                                desno = IskalnoDrevo(3)),
                desno = IskalnoDrevo(5)),
    desno = IskalnoDrevo(9,
                    levo = IskalnoDrevo(7),
                    desno = IskalnoDrevo()))

class IskalnoDrevo:

    def __init__(self, vsebina=[]):
        self.prazno = True
        for n in vsebina:
            self.dodaj(n)

    def __repr__(self, zamik = ''):
        if self.prazno:
          return 'IskalnoDrevo()'.format(zamik)
        elif self.levo.prazno and self.desno.prazno:
          return 'IskalnoDrevo({1})'.format(zamik, self.vsebina)
        else:
          return 'IskalnoDrevo({1},\n{0}      levo = {2},\n{0}      desno = {3})'.\
            format(
              zamik,
              self.vsebina,
              self.levo.__repr__(zamik + '             '),
              self.desno.__repr__(zamik + '              ')
            )

    def pravilno(self, minimum=None, maksimum=None):
        if self.prazno:
            return True
        elif minimum and self.vsebina < minimum:
            return False
        elif maksimum and self.vsebina > maksimum:
            return False
        else:
            return (self.levo.pravilno(minimum, self.vsebina) and
                    self.desno.pravilno(self.vsebina, maksimum))

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

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]

Množice z iskalnimi drevesi

Podatkovno strukturo množica lahko učinkovito predstavimo z iskalnim drevesom. V tej nalogi bomo najprej definirali nekaj pomožnih funkcij na drevesih, nato pa definirali razred Mnozica, ki podpira osnovne operacije na množicah.

1. podnaloga

Sestavite funkcijo vstavi_v_iskalno_drevo(drevo, x), ki v iskalno drevo na pravo mesto vstavi element x ter vrne novo drevo. Če je x enak podatku v korenu drevesa, naj funkcija vrne prvotno drevo.

2. podnaloga

Sestavite funkcijo ali_vsebuje(drevo, x), ki vrne True, če dano iskalno drevo vsebuje podatek x, in False, če ga ne.

3. podnaloga

Z razredom Mnozica bomo predstavili nespremenljive množice, torej take, ki ne podpirajo metod za dodajanje in odstranjevanje elementov, le metode, ki izračunajo nove množice iz obstoječih. Vsako množico bomo predstavili z objektom, ki ima dva atributa: iskalnim drevesom elementov _elementi ter velikostjo _velikost.

Sestavite razred Mnozica z metodo __init__, ki mu za neobvezen prvi argument lahko podamo iterator začetnih elementov množice.

4. podnaloga

Dodajte metodo __iter__, ki vrne iterator, ki našteva elemente množice od najmanjšega do največjega.

5. podnaloga

Za lepši prikaz dodajte še metodo __str__, ki vrne niz oblike {el1, el2, ...}, kjer so elementi množice našteti od najmanjšega do največjega.

6. podnaloga

Za dostop do velikosti množice mn in iskanja elementov v njej bi sicer lahko napisali metodi mn.velikost() in mn.vsebuje(x), vendar je bolj Pythonovsko, da definiramo metodi __len__ in __contains__, da lahko pišemo kar len(mn) in x in mn oz. x not in mn. Definirajte ju.

7. podnaloga

Definirajte še metodi __or__ in __and__, ki sprejmeta dve množici ter vrneta njuno unijo in presek. Stvari naredite učinkovite tako, da upoštevate velikost množic.

8. podnaloga

Kaj bi se zgodilo, če bi sestavili množico z Mnozica(range(1000000))? Ali bi bila taka podatkovna struktura učinkovita? Na vajah se bomo pogovorili o tem, kako lahko izboljšamo učinkovitost s tem, da uporabimo uravnotežena dvojiška drevesa.

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. Ta naslednji element, tudi, če je 1, 2, 3 ali 4, preskočimo.
• če naletimo na število 2, iz kopice odstranimo naslednji element v seznamu, če tega števila ni, v rezultat dodamo -1. Tudi tu element, ki pove, katerega hočemo odstraniti, preskočimo. Če jih je več, odstranimo le enega.
• če naletimo na število 3, v rezultat vstavimo največji element v kopici (kopica se ne spremeni),
• če naletimo na število 4, v rezultat vstavimo najmanjši element v kopici, ki se ne spremeni.

Števil, ki so uporabljena kot podatki za vstavljanje in brisanje, torej ne tolmačimo kot ukaze (tudi, če so 1, 2, 3 ali 4)

Zgled:

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

V kopico vstavimo števila 2, 9 in 6, nato v rezultat dodamo število 9, ki je trenutno največje število v kopici. Nato nam 1 pove, da hočemo iz kopice brisati število 1. Ker tega števila v kopici ni, v rezultat dodamo -1. Nato v kopico dodamo še 11 (in ne 1!), v rezultatpa na koncu, zaradi zahteve po minimalnem elementu 4, dodamo še 5, ki je trenutno najmanjši element v kopici.

Namig: morda se splača imeti dve kopici!

Nogometna tekma

1. podnaloga

Mihec zelo rad spremlja nogometne tekme. Njegov najljubši klub je Manchester United. Mihec se je odločil, da bo si bo naslednjo tekmo tega kluba 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, priljubljenost_prejsnji_dan, število_objav, število_všečkov, število_komentarjev, število_delitev) in vrne seznam parov (ID, nova_priljubljenost) za top 5 tem, torej za tiste, za katere je pšriljubljenost najbolj narasla. 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)]

Prve 4 teme so torej imele prirastek priljubljenosti 100, peta pa 50.

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)]

Kovanci v vrsti na vse možne načine

Opozorilo. Naloge ne vsebujejo testov. Pravilnost delovanja moraš s testnimi primeri preveriti sam.

Kovanci v vrsti rekurzija

1. podnaloga

V tej podnalogi sestavi rešitev za kovance v vrsti s pomočjo rekurzije. naredi jo, tako, da bo opravljena od začetka do konca tabele kovancev (torej naprej). Funkcijo poimenuj naj_vsota_rec_naprej(K). kjer je K tabela kovancev, ki jih imaš na voljo.

2. podnaloga

Sedaj enako (s pomočjo rekurzije) najdi rešitev, le da tokrat rešitev najdeš od konca proti začetku tabele kovancev. Funkcijo poimenuj naj_vsota_rec_nazaj(K). kjer je K tabela kovancev, ki jih imaš na voljo.

Kovanci v vrsti memoizacija

1. podnaloga

Problem kovancev v vrsti reši s pomočjo memoizacije. Reši jo, tako, da se pomikaš od začetka tabele do konca. Funkciji daj ime naj_vsota_memo_naprej(K, slovar), ki sprejme K tabelo kovancev in slovar v katerega shranjujemo izračunane vrednosti, vrni pa dvojico (rezultat, slovar), ki predstavlja rešitev.

2. podnaloga

Problem kovancev v vrsti reši s pomočjo memoizacije. Reši jo, tako, da se pomikaš od konca tabele do začetka. Funkciji daj ime naj_vsota_memo_naprej(K, slovar), ki sprejme K tabelo kovancev in slovar v katerega shranjujemo izračunane vrednosti, vrni pa dvojico (rezultat, slovar), ki predstalvja rešitev.

Kovanci v vrsti tabela

1. podnaloga

Problem kovancev v vrsti reši s pomočjo tabele. Problem reši tako, da tabelo polniš od začetka do konca. Funkciji daj ime naj_vsota_tab_naprej(K), ki sprejme K tabelo kovancev in vrne maksimalno vsoto, ki jo lahko dobimo.

2. podnaloga

Problem kovancev v vrsti reši s pomočjo tabele. Problem reši tako, da tabelo polniš od začetka do konca. Funkciji daj ime naj_vsota_tab_nazaj(K), ki sprejme K tabelo kovancev in vrne maksimalno vsoto, ki jo lahko dobimo.

Kovanci v vrsti dva elementa

1. podnaloga

Problem kovancev reši s pomočjo uporabe dveh elementov. Reši s pomočjo pregleda tabele kovancev od začetka do konca. funkciji daj ime naj_vsota_dva_el_naprej(K), ki sprejme K tabelo kovancev in vrne največjo vsoto elementov.

2. podnaloga

Problem kovancev reši s pomočjo uporabe dveh elementov. Reši s pomočjo pregleda tabele kovancev od konca do začetka. funkciji daj ime naj_vsota_dva_el_nazaj(K), ki sprejme K tabelo kovancev in vrne največjo vsoto elementov.

0/1 nahrbtnik

0/1 nahrbtnik

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.

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)

6. podnaloga

Sestavi funkcijo resitev01(predmeti, velikost), ki reši problem 0/1 nahrbtnika kot pri prejšnji podnalogi, le 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]

7. 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]]

8. 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]

Dinamično programiranje

Pozor, naloge pogosto vsebujejo velik testni primer, ki preverja učinkovitost vaše rešitve.

Požrešna miška

1. podnaloga

Požrešna miška se nahaja v zgornjem levem kotu šahovnice. Premikati se sme samo za eno polje navzdol ali za eno polje na desno in na koncu mora prispeti v desni spodnji kot. Na vsakem polju šahovnice je en sirček. Ti sirčki imajo različne (ne-negativne) mase. Miška bi se rada kar se da nažrla, zato jo zanima, katero pot naj ubere.

Napišite funkcijo pozresna_miska(sircki), ki dobi matriko sircki z masami sirčkov in vrne skupno maso, ki jo bo miška požrla, če gre po optimalni poti.

>>> pozresna_miska([[1,2,0], [2,4,5], [7,0,1]])
13

Ž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 n, je cilj žabice priskakljati vsaj na n-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. Začetna energija je 0.

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.

Pobeg s Finske

1. podnaloga

Vaš sošolec Mortimer se je med potovanjem po Finski spravil v krepko godljo. Po divjem poskušanju lokalne vodke se je namreč stepel s kravo, zaradi česar ga sedaj lovi finska govedorejska mafija. Na srečo so za njegovo hrabro bitko slišale vse rokovske in metalske skupine, ki so mu pripravljene ponuditi prevoz.

Ker je Mortimer pridno poslušal predavanja iz finančne matematike, med potjo uspe prislužiti nekaj denarja, s katerim bo lahko plačal prevoz. Finci, navdušeni nad Mortimerjevim pogumom, mu dovolijo, da se med potjo zadolži, dokler na koncu pobega vse stroške povrne.

Mesta na poti predstavimo kot seznam, katerega elementi so seznami vseh možnih nadaljnjih poti. Pot je par (indeks_cilja, denar). Kot primer

[[(1, 10), (3, -10)],    # 0 
[(2, 10), (5, -20)],     # 1
[(3, -10)],              # 2 
[(4, 15)],               # 3 
[(5, 0)]]                # 4

pomeni, da lahko v mestu 1 Mortimer izbere med prevozom v mesto 2, kjer dodatno zasluži 10 evrov, ali pa prevoz v mesto 5, ki ga stane 20 evrov. Ker beži pred mafijo, lahko predpostavite, da bodo možne zgolj poti na mesta z višji indeksom (torej ni ciklov).

Pobeg je uspešen, čim lahko odpotuje v mesto, ki ni več na seznamu (torej skok na indeks, ki preseže seznam) in ima po koncu zadnjega skoka 0 ali več evrov. Napišite program, ki nam vrne pot z najmanjšim številom skokov, predstavljeno kot seznam indeksov mest na poti. Ker pobeg morda ni možen, naj v tem primeru funkcija vrne None.

Na primeru je optimalna pot [0, 3, 4, 5], kjer se Mortimer sicer zadolži, vendar v skoku iz 3 v 4 zasluži dovolj, da konča z 5 evri. Hitrejša pot bi bila [0, 1, 5], vendar v tem primeru Mortimer na koncu dolguje še 10 evrov.

Mortimer pot vedno začne v mestu z indeksom 0 in ima 0 evrov (saj je vse zapil). Funkcija pobeg sprejme seznam, ki predstavlja finska mesta in vrne seznam indeksov mest, v katerih se Mortimer ustavi.

Pričetek robotske vstaje

1. podnaloga

Nepreviden študent je pustil robotka z umetno inteligenco nenadzorovanega. Robotek želi pobegniti iz laboratorija, ki ga ima v pomnilniku predstavljenega kot matriko števil:

• ničla predstavlja prosto pot
• enica predstavlja izhod iz laboratorija
• katerikoli drugi znak označuje oviro, na katero robotek ne more zaplejati

Robotek se lahko premika le gor, dol, levo in desno ter ima omejeno količino goriva. V zbirki programov že ima funkcijo moznost_pobega(soba, vrsta, stolpec, koraki), ki pove ali je pobeg možen.

Napišite funkcijo pot_pobega(soba, vrsta, stolpec, koraki), ki sprejme matriko sobe, začetno pozicijo in število korakov ter izračuna pot po kateri robotek pobegne (če to ni možno vrne None). Pot zakodiramo s seznamom ukazov 'gor', 'dol', 'levo' in 'desno'.

Na primer za laboratorij:

[[0, 1, 0, 0, 2],
 [0, 2, 2, 0, 0],
 [0, 0, 2, 2, 0],
 [2, 0, 0, 2, 0],
 [0, 2, 2, 0, 0],
 [0, 0, 0, 2, 2]]

robotek iz vrste 3 in stolpca 1 pri vsaj petih korakih pobegne z ukazi

 ['gor', 'levo', 'gor', 'gor', 'desno']

medtem ko iz vrste 5 in stolpca 0 ne more pobegniti.

Nageljni

1. podnaloga

Mama Franca želijo na balkon širine n postaviti m korit z nageljni širine l (korit, ne nageljnov). Zaradi lažjega zalivanja mora biti med dvema koritoma vsaj za 1 enoto prostora. Mama Franca želijo postaviti vsa korita, jih pa zaradi slabega vida med seboj ne razlikujejo.

Vnuk je že spisal program, ki poišče število možnih postavitev, ne zna pa vrniti rešitev. Napišite funkcijo nageljni(n, m, l), ki vrne seznam vseh možnih postavitev, da se bodo mama Franca lažje odločili.

Primer vseh štirih možnih postavitev pri balkonu širine 9 s tremi koriti širine 2 (kjer z 1 označimo nagelj in z 0 prazen prostor):

[1, 1, 0, 1, 1, 0, 1, 1, 0]
[1, 1, 0, 1, 1, 0, 0, 1, 1]
[1, 1, 0, 0, 1, 1, 0, 1, 1]
[0, 1, 1, 0, 1, 1, 0, 1, 1]

Barvni stolpi

1. podnaloga

Sestavljamo stolpe, kjer zahtevamo, da sta zaporedna gradnika stolpa različne barve. Pri tem imamo štiri različne tipe gradnikov, dva modra in dva rdeča. Modri gradniki so višin 2 in 3, rdeči pa višin 1 in 2.

Sestavite funkcijo, ki za podano višino vrne število različnih stolpov dane višine, ki jih lahko zgradimo z našimi gradniki, kjer se barva gradnikov v stolpu izmenjuje (rdeč na modrem, moder na rdečem itd.). Začnemo z gradnikom poljubne barve.

>>> alternirajoci_stolpi(10)
35

Najdaljše naraščajoče podzaporedje

1. podnaloga

Napišite funkcijo najdaljse_narascajoce_podazporedje, ki sprejme seznam in poišče najdaljše (ne strogo) naraščajoce podzaporedje števil v seznamu.

Primer: v seznamu [2, 3, 6, 8, 4, 4, 6, 7, 12, 8, 9] kot rezultat vrne podzaporedje [2, 3, 4, 4, 6, 7, 8, 9].

2. podnaloga

Rešitev popravite tako, da funkcija vsa_najdaljsa vrne seznam vseh najdaljših naraščajočih podzaporedij.

Dinamično programiranje (dodatne vaje)

Množenje matrik

Izračunati želimo produkt $n$ matrik $A_1 \times A_2 \times \ldots \times A_n$. Dimenzije posameznih matrik so ustrezne, tako da je produkt možno izračunati. Zaradi asociativnosti množenja lahko matrike množimo na več različnih načinov, (tj. v izraz na različne načine postavimo oklepaje). Zanima nas, v kakšnem vrstnem redu moramo množiti, da bomo opravili kar se da malo množenj realnih števil.

1. podnaloga

Sestavi funkcijo stevilo_mnozenj(dim), ki izračuna najmanjše število množenj realnih števil, ki jih potrebujemo, da zmnožimo matrike danih velikosti. Velikosti matrik so podane s seznamom dim, katerega elementi so pari, ki določajo, koliko vrstic in koliko stolpcev ima posamezna matrika.

>>> stevilo_mnozenj([(30, 35), (35, 15), (15, 10), (10, 5), (5, 10)])
10125

2. podnaloga

Sestavi funkcijo vrstni_red(dim), ki izračuna vrstni red množenj matrik, pri katerem bomo potrebovali najmanj množenj realnih števil.

>>> vrstni_red([(30, 35), (35, 15), (15, 10), (10, 5), (5, 10)])
'((A1(A2(A3A4)))A5)'

Kovanci v vrsti

1. podnaloga

Čestitam! V nagradni igri si bil izžreban za dobitnika nagrade. Kolikšna bo nagrada, pa je odvisno od tvoje iznajdljivosti. Za nagrado si lahko izbereš poljubne kovance iz podane vrste kovancev (ki so lahko vsi različni ali pa tudi ne). Edini pogoj pri izbiranju je, da nikoli ne izbereš dveh sosednjih kovancev. Da se boš prepričal, da si boš izbral največjo možno nagrado, sestavi funkcijo nagrada(kovanci), ki bo za dane kovance vrnila največjo možno vsoto, ki jo lahko izbereš.

>>> nagrada([5, 6, 4, 8, 1, 2, 1, 1])
17
>>> nagrada([2, 2, 2])
4
>>> nagrada([1, 3, 1])
3
>>> nagrada([1, 3, 1, 4, 6])
9
>>> nagrada([3, 2, 1, 4, 6])
10
>>> nagrada([10, 2, 8, 16, 14, 2, 10, 4, 5, 7])
49
>>> nagrada([10, 2, 8, 16, 14, 10, 4, 5, 7])
43

2. podnaloga

Za izplačilo nagrade ni dovolj povedati, kakšno vsoto lahko dobiš, ampak s katerimi kovanci prideš do te vsote. Sestavi funkcijo kateri(kovanci), ki vrne tabelo z izbranimi kovanci, urejeno v naraščajočem vrstnem redu.

>>> kateri([5, 6, 4, 8, 1, 2, 1, 1])
[1, 2, 6, 8]

3. podnaloga

Predsednik komisije za nagradno igro pa s funkcijo kateri ni najbolj zadovoljen, saj mora sedaj, če želi ugotoviti znesek, poklicati funkcijo nagrada ali pa sešteti rezultat funkcije kateri. Zato želi funkcijo, ki vrne par - prva je maksimalna vrednost, druga vrednost pa tabela kovancev.

A pozor! Nalogo reši "od začetka", torej pri rešitvi nikakor ne uporabi funkciji nagrada in kateri.

  >>> naj_vsota([10, 2, 8, 16, 14, 10, 4, 5, 7])
  (43, [10, 8, 14, 4, 7])
  >>> naj_vsota([10, 2, 8, 16, 14, 2, 10, 4, 5, 7])
  (49, [10, 8, 14, 10, 7])
  >>> naj_vsota([3, 2, 1, 4, 6])
  (10, [3, 1, 6])
  >>> naj_vsota([1, 3, 1])
  (3, [3])
  >>> naj_vsota([2, 2, 2])
  (4, [2, 2])

4. podnaloga

Blagajnik komisije za nagradno igro pa pravi, da je predsednik malo čuden in si z njegovo funkcijo nima kaj pomagati. Želi bolj "vizualen" rezultat. Kakšne, je razvidno iz primerov!

  >>> naj_vsota_kako([10, 2, 8, 16, 14, 10, 4, 5, 7])
  (43, [10, '_', 8, '_', 14, '_', 4, '_', 7])
  >>> naj_vsota_kako([10, 2, 8, 16, 14, 2, 10, 4, 5, 7])
  (49, [10, '_', 8, '_', 14, '_', 10, '_', '_', 7])
  >>> naj_vsota_kako([3, 2, 1, 4, 6])
  (10, [3, '_', 1, '_', 6])
  >>> naj_vsota_kako([1, 3, 1])
  (3, ['_', 3, '_'])
  >>> naj_vsota_kako([2, 2, 2])
  (4, [2, '_', 2])

0/1 tabela

1. podnaloga

Sergej je iz ničel in enk sestavil vse možne tabele dolžine 3. Združil jih je v tabelo tabel in dobil rezultat[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]. Dobil je torej tabelo osmih različnih tabel. Zatem je želel zapisati vse možne tabele dolžine 7, a je hitro ugotovil, da je število teh zelo naraslo. Pomagaj mu in sestavi funkcijo tabele01(n), ki bo vrnila tabelo vseh možnih tabel dolžine n, sestavljenih iz samih ničel in enk. Tabela mora biti leksikografsko urejena!

>>>tabele01(3)
[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

Namig: morda ti prav pride

>>>bin(10)
'0b1010'

Študentski servis

1. podnaloga

Po koncu poletnega izpitnega obdobja si ugotovil, da imaš premalo denarja za potovanje, na katerega odhajaš čez slab mesec. Zato greš hitro pogledat na študentski servis, kako bi v tem času lahko zaslužil čimveč denarja. Denimo, da lahko delaš 22 dni. Našel si štiri ponudbe za delo in sicer * montaža, 6 dni, zaslužek: 300€ * razvoz, 10 dni, zaslužek: 440€ * anketiranje, 8 dni, zaslužek: 310€ * pomoč v kuhinji, 15 dni, zaslužek: 900€ Seveda želiš izbrati tista opravila, s katerimi boš v treh tednih zaslužil čimveč. Sestavi funkcijo zasluzek(opravila, cas), ki bo, s pregledom vseh možnih kombinacij izbire opravil, vrnila največji možni zaslužek v danem času. Opravila so podana v tabeli opravila, ki jo sestavljajo pari (trajanje, zasluzek).

>>>zasluzek([(6, 300), (10, 440), (8, 310), (15, 900)], 22)
1200

Namig: verjetno si lahko pomagaš tudi z rešitvijo naloge 0/1 tabela.

2. podnaloga

Poznavanje največjega možnega zaslužka nam ne koristi, če ne vemo pri kakšni izbiri opravil ga dosežemo. Sestavi funkcijo katera(opravila, cas), ki vrne tabelo enake dolžine kot tabela opravila in vsebuje enice na indeksih, ki sovpadajo z izbranimi opravili, na ostalih indeksih pa ničle. Nalogo reši s pregledom vseh možnih kombinacij izbire opravil.

>>>katera([(6, 300), (10, 440), (8, 310), (15, 900)], 22)
[1, 0, 0, 1]

3. podnaloga

Pregled vseh možnih kombinacij izbire opravil je zamuden postopek. Na predavanjih smo zato sestavili družino rekurzivnih funkcij, s katerimi lahko izračunamo največji možni zaslužek za poljubno število dni. I-ta funkcija upošteva prvih i opravil na voljo.

Funkcije (rečemo jim tudi Bellmanove enačbe) so oblike

$$G_i(Č) = max( G_{i-1}(Č), zaslužek_i + G_{i-1}(Č - trajanje_i))$$

Sestavi funkcijo zasluzek_bellman(opravila, cas), ki zgornjo nalogo reši z rekurzivno bellmanovo enačbo.

>>>zasluzek_bellman([(6, 300), (10, 440), (8, 310), (15, 900)], 22)
1200

4. podnaloga

Tudi za zgornji postopek bi bilo smiselno, da bi vedeli, katera opravila smo izbrali.

>>>katera_bellman([(6, 300), (10, 440), (8, 310), (15, 900)], 22)
[1, 0, 0, 1]

Preprost nahrbtnik

1. podnaloga

Dan je osnutek funkcije, ki naj bi poiskala rešitev preprostega nahrbtnika. Dopolni funkcijo ter odpravi morebitne napake. Pri tem je predmeti seznam parov, ki opisujejo predmete (vsak par je oblike (velikost, vrednost)), parameter velikost pa določa velikost nahrbtnika (število).

def nahrbtnik(predmeti, velikost):
    p = list(enumerate(predmeti))
    p.sort(key=lambda t: t[1] / t[0])
    v = 0
    x = [0] * len(predmeti)
    for i in range(len(p)):
        k =
        vel =
        if v + vel <= velikost:
            x[k] = 1
            v += vel
        else:
            if v != velikost:
                x[k] =
            break
    return x

Primer:

>>> nahrbtnik([(30,57),(27,60),(35,105),(40,113),(50,100),(51,108)], 60)
[0, 0, 1, 0.625, 0, 0]

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.

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.

Najdaljše naraščajoč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 max_podzaporedje_vsota(zaporedje), ki za dano zaporedje vrne največjo možno vsoto členov naraščajočega podzaporedja.

Funkcije ne piši iz nule, ampak si pomagaj z rešitvami prejšnjih podnalog.

5. podnaloga

Sestavi funkcijo max_podzaporedje_lihi(zaporedje), ki za dano zaporedje vrne najdaljše naraščajoče podzaporedje, sestavljeno iz samih lihih števil.

Funkcije ne piši iz nule, ampak si pomagaj z rešitvami prejšnjih podnalog.

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.