Rešitve z razlago

Rešitev (v enem kosu)

Tule so rešitve vseh izpitnih nalog v obliki, kakršno bi pričakovali. Podrobnejša razlaga je spodaj.

def ostanki(vrt, pot): vrt = vrt[:] x = 0 for korak in pot: if vrt[x] == 0: break vrt[x] = 0 x += korak vrt[x] = 0 return sum(vrt) def pretakanje(s): posode = {"A": 0, "B": 1, "P": 2} velikost = 5, 8, 1000 vsebina = [0, 0, 500] for poteza in s: iz = posode[poteza[0]] v = posode[poteza[-1]] if vsebina[v] + vsebina[iz] > velikost[v]: vsebina[iz] -= velikost[v] - vsebina[v] vsebina[v] = velikost[v] else: vsebina[v] += vsebina[iz] vsebina[iz] = 0 return tuple(vsebina[:2]) def izplacilo(bankovci, znesek): for bankovec, kolicina in sorted(bankovci.items(), reverse=True): if znesek >= bankovec: koliko = znesek // bankovec if koliko >= bankovci[bankovec]: koliko = bankovci[bankovec] del bankovci[bankovec] else: bankovci[bankovec] -= koliko znesek -= bankovec * koliko def crv(drevo): naj = 0 for veja, naprej in drevo.items(): if veja == "zelena": naj = max(naj, 1 + crv(naprej)) return naj class Racunalnik_Sodo(Racunalnik): def preveri_geslo(self, geslo): return geslo % 2 == 0 class Racunalnik_Sudo(Racunalnik): def preveri_geslo(self, geslo): return geslo == "sudo"

Razlaga

Ostanki

Na predavanjih in vajah smo rešili že precej nalog s skoraj enako zgodbo - čebela hodi sem in tja - tako da naloga ne bi smela povzročati težav. Razmisliti je potrebno le, kako obrniti zanko, da bo čebela obrala tako prvi kot zadnji cvet. V spodnji rešitvi smo to storili tako, da postavimo vrt[x] na 0, preden povečamo x, po zanki pa postavimo na 0 še vrt[x] za zadnji x. Tudi preverjanje, ali je cvet že obran, na ta način lepo sodi v začetek zanke, saj preveri tudi cvet, s katerim čebela začne svojo pot.

def ostanki(vrt, pot): vrt = vrt[:] x = 0 for korak in pot: if vrt[x] == 0: break vrt[x] = 0 x += korak vrt[x] = 0 return sum(vrt)

Pri tej nalogi ste mnogi delali zanimivo napako: pisali ste

if korak > 0: x+=korak else: x-=korak

Tole čebelo vedno premika v desno, saj takrat, ko je x negativen, odšteva ta, negativni x - kar spet pomeni prištevanje.

Pretakanje

Tole je edina sitna naloga. Lahko bi se je lotili tako, da bi imeli spremenljivke a, b in p, ki bi shranjevale količino vode v posameznih piskrih. Vendar bi to vodilo v neskončne špagete if-ov. Zato raje uporabimo seznam s tremi elementi, ki pomenijo količino vode v posameznih posodah, vsebina = [0, 0, 500]. Da bomo vedeli, kje je kateri, si pripravimo slovar posode = {"A": 0, "B": 1, "P": 2}. Poleg tega potrebujemo še terko (lahko bi bil tudi seznam, a jasno povejmo, da je reč fiksna, nespremenljiva) velikost = (5, 8, 1000).

Zdaj v vsaki potezi (for poteza in s) najprej ugotovimo indeks posode, iz katere in v katero točimo - iz = posode[poteza[0]] in v = posode[poteza[-1]]. Če, recimo, točimo iz A v P, bo iz enak 0 in v bo enak 2.

Z naslednjim if-om razlikujemo med tem, ali bomo točili, dokler ne bo ciljna posoda polna ali dokler ne bo začetna. V prvem primeru zmanjšamo količino mleka v začetni za toliko, kolikor je prostora v ciljni, za ciljno pa zabeležimo, da je polna. V drugem primeru pa k ciljni posodi prištejemo količino mleka v začetni, za začetno pa zabeležimo, da je prazna.

Funkcija vrne prva dva elementa seznama vsebina, to je, količina mleka v prvih dveh posodah, ki ju, kot se za rezultate funkcij spodobi, spremenimo v terko.

def pretakanje(s): posode = {"A": 0, "B": 1, "P": 2} velikost = (5, 8, 1000) vsebina = [0, 0, 500] for poteza in s: iz = posode[poteza[0]] v = posode[poteza[-1]] if vsebina[v] + vsebina[iz] > velikost[v]: vsebina[iz] -= velikost[v] - vsebina[v] vsebina[v] = velikost[v] else: vsebina[v] += vsebina[iz] vsebina[iz] = 0 return tuple(vsebina[:2])

Tule pa je elegantna - čeprav ne preveč hitra - rešitev enega od študentov.

def pretakanje(s): sodi = {"A":0, "B":0, "P":500} max = {"A":5, "B":8, "P":1000} for pretok in s: while sodi[pretok[0]] > 0 and sodi[pretok[3]] < max[pretok[3]]: sodi[pretok[0]] -= 1 sodi[pretok[3]] += 1 return sodi["A"], sodi["B"]

Všeč mi je, kako lepo si je pomagal s slovarji.

Izplačilo

Kot je jasno namignila naloga, gremo s for bankovec, kolicina in sorted(bankovci.items(), reverse=True) lepo po bankovcih od večjih k manjšim.

Bankovec nas zanima le, če je znesek, ki ga želimo izplačati z njim, večji od bankovca. (Ta pogoj ni čisto potreben, a ga obdržimo zaradi preglednosti. Delovalo pa bi tudi brez njega.

Nato izračunamo, koliko kosov tega bankovca bi bilo potrebno izplačati. Uporabimo celoštevilsko deljenje. Če bi izplačali toliko, kolikor jih imamo ali pa celo več, si zapomnimo, da jih bomo izplačali, kolikor jih imamo in pobrišemo bankovec iz slovarja; sicer pa število bankovcev v slovarju zmanjšamo za toliko, kolikor jih bomo izplačali. Na koncu zmanjšamo še znesek za toliko, kolikor je vreden bankovec * število kosov, ki smo jih izplačali.

def izplacilo(bankovci, znesek): for bankovec, kolicina in sorted(bankovci.items(), reverse=True): if znesek >= bankovec: koliko = znesek // bankovec if koliko >= bankovci[bankovec]: koliko = bankovci[bankovec] del bankovci[bankovec] else: bankovci[bankovec] -= koliko znesek -= bankovec * koliko

Črv

Takšnole rekurzijo smo delali že tolikokrat, da o njej ni kaj povedati. "Novost" v tej rešitvi je le priročen trik z max, s katerim se izognemo potrebi po dodatni spremenljivki, ki smo jo sicer uporabljali v primerih s predavanj in vaj.

def crv(drevo): naj = 0 for veja, naprej in drevo.items(): if veja == "zelena": naj = max(naj, 1 + crv(naprej)) return naj

Pri sestavljanju te naloge sem naredil zanimivo traparijo. Slovar ne more imeti večkrat istega ključa: če iz neke rogovile raste več zelenih ali suhih vej, bo v slovarju shranjena le ena. Na srečo to na reševanje naloge ni vplivalo. (Če bi, pa bi opazil, ko sem nalogo reševal sam.) Opravičim se lahko s tem, da je slovar za tole tako ali tako neprimerna struktura (boljša bi bila terka), vendar sem izbral slovar, ker ste po njem navajeni "rekurzirati" (vsaj morali bi biti, a žal niste...)

Računalnik

Naloga je trivialna za vsakega, ki ve, kako se izpeljujejo razredi in kako delujejo metode. Potrebujemo dva nova razreda, ki sta izpeljana iz starih in edina metoda, ki jo je potrebno povoziti, je preverjanje gesel. Sama metoda pa je trivialna.

class Racunalnik_Sodo(Racunalnik): def preveri_geslo(self, geslo): return geslo % 2 == 0 class Racunalnik_Sudo(Racunalnik): def preveri_geslo(self, geslo): return geslo == "sudo"