Skoki

Naloga preskuša, ali znamo napisati zanko in jo po potrebi prekiniti. Očitno zahteva samo, da si zapomnimo trenutno pozicijo (p) in jo v zanki spreminjamo. Šteti moramo poteze in če trenutno pozicija kdaj spet postane 1, vrnemo število potez. Če je trenutna pozicija izven seznama, vrnemo -1. Kako pa zaznamo cikel? O tem govori namig: naredili bomo samo toliko potez, kolikor je dolg seznam. Če v tem času ne pridemo na začetno polje, ne bomo nikoli.

def skoki(s): p = 0 n = len(s) for i in range(n): if s[p] >= n: return -1 p = s[p] if p == 0: return i + 1 return -2

Transakcije

Naloga preskuša, ali znamo narediti in uporabiti slovar. Kot pravi namig, najprej pretvorimo vse skupaj v slovar; to lahko naredimo z zanko for ali, če smo bili na predavanjih dovolj pozorni, s klicem funkcije dict. Nato gremo z zanko prek transakcij, odštejemo denar prvemu in ga preštejemo drugemu. Končno v tem slovarju poiščemo tistega z največ denarja. Z malo sprednosti bi lahko uporabili kar funkcijo max, v spodnji rešitvi pa smo uporabili običajno zanko.

def transakcije(zacetek, trans): stanje = dict(zacetek) for kdo, komu, koliko in trans: stanje[kdo] -= koliko stanje[komu] += koliko najvec = None # lahko bi napisali -1, a morda so vsi v dolgovih... for kdo, koliko in stanje.items(): if najvec is None or koliko > najvec: najvec, kdo_naj = koliko, kdo return kdo_naj

Deli niz

Če je niz "deljiv" s k, bo njegova dolžina večkratnik k in če vzamemo prvih len(s)/k znakov ter jih pomnožimo s k, spet dobimo isti niz. Če vse to drži, torej vrnemo teh prvih len(s)/k znakov. Sicer ne naredimo ničesar in funkcije, ki ne vračajo ničesar, vemo, vračajo None, kot zahteva naloga.

def deli_niz(s, k): d = s[:len(s)//k] if d * k == s: return d

Pravokotniki

Bistvo naloge je, da znate napisati tri funkcije in jih poklicati med sabo. Vse, kar se dogaja znotraj njih, je trivialno: prvi dve smo videli v domačih nalogah (recimo Album), tretjo pa v lanskem izpitu (in še kje). A tudi, če jih ne bi, so preproste.

def v_prav(prav, tocka): x0, y0, x1, y1 = prav x, y = tocka return x0 <= x <= x1 and y0 <= y <= y1 def se_sekata(prav1, prav2): x0, y0, x1, y1 = prav1 a0, b0, a1, b1 = prav2 return (v_prav(prav1, (a0, b0)) or v_prav(prav1, (a0, b1)) or v_prav(prav1, (a1, b0)) or v_prav(prav1, (a1, b1)) or v_prav(prav2, (x0, y0)) or v_prav(prav2, (x0, y1)) or v_prav(prav2, (x1, y0)) or v_prav(prav2, (x1, y1))) def sekajoci_par(pravokotniki): for i, prav1 in enumerate(pravokotniki): for prav2 in pravokotniki[:i]: if se_sekata(prav1, prav2): return prav1, prav2

Globina drevesa

Naloga zahteva, da znamo izpeljati razred in dodati metodo (to ne bi smel biti problem) in da znamo napisati rekurzivno funkcijo, ki je zelo podobna tistim, ob katerih so preživeli večji del enega od predavanj.

class VozliscePlus(Vozlisce): def globina(self): g = 0 if self.levi(): g = 1 + self.levi().globina() if self.desni(): g = max(g, 1 + self.desni().globina()) return g
Zadnja sprememba: torek, 5. februar 2013, 22.52