Teme

Naloge so pokrivale enake teme kot navadno:

• Ravnotežje: malo telovadbe z zankami in slovarji, klasičen vzorec (iskanje elementa, pri katerem je vrednost določene lastnosti maksimalna...)
• k_ti: delo s slovarji in seznami, predvsem pa še malo telovadbe
• Koliko brez otrok: rekurzija, očitno
• Osnovnošolski ples: razumevanje slovarjev in množic, brez pretiranega programiranja
• Mobilni operater: objektno programiranje (razumevanje atributov, definicija metod...), brez pretiranega programiranja

Ravnotežje

Razliko med težo seznama do i-tega elementa in od i-tega naprej izračunamo takole: sum(s[:i]) - sum(s[i:]). Ker hočemo, da je razlika čim manjša, bomo opazovali absolutno vrednost te razlike, torej abs(sum(s[:i]) - sum(s[i:])).

Zdaj se zapeljemo z i od začetka do konca in si zapomnimo, pri katerem i je bila razlika najmanjša.

def ravnotezje(s): naj_i = 0 naj_r = sum(s) for i in range(len(s)): r = abs(sum(s[:i]) - sum(s[i:])) if r < naj_r: naj_i, naj_r = i, r return naj_i

Kot začetno vrednost najboljšega i in najmanjše razlike vzamemo kar naj_i = 0, pripadajoča razlika pa je seveda naj_r = sum(s) (vsi elementi so na isti strani). Namesto tega bi lahko naredili tudi kako drugače - na kakega od načinov, ki smo jih za podobne naloge (tole smo reševali velikokrat...) uporabljali doslej.

Pri reševanju naloge ste se mnogi izgubili pri računanju vsot.

K-ti

Nalogo najprej rešimo na okornejši, daljši način. Najprej bomo prešteli pogostosti posameznih črk. Za to bomo uporabili slovarje s privzetimi vrednostmi. Ta slovar bi si potem želeli urediti po pogostosti črk, vendar se slovarjev ne da urejati. Zato prepišemo slovar v seznam parov, pri čemer je prvi element para pogostost, drugi črka. Ta slovar uredimo padajoče in vrnemo k-ti element. (Če ne bi znali urejati nepadajoče, bi vrnili k-tega z zadnjega konca, torej element z indeksom -1 - k.) Celoten program po tej, bolj zapleteni različici, je takšen.

def k_ti(s, k): from collections import defaultdict stevci = defaultdict(int) for crka in s: stevci[crka] += 1 pari = [] for crka, pogostost in stevci.items(): pari.append((pogostost, crka)) pari.sort(reverse=True) return pari[k][1]

Krajši program je na koncu te strani.

Mnogi ste se pri tej nalogi zaplezali in izgubljali čas z običajnimi slovarji. S tem ne bi bilo nič narobe - če ne postane program zaradi tega tako zapleten, da se izgubite v njem.

Brez otrok

Naloga je podobna drugim rodbinskim nalogam. Tokrat gre tako: Če neka oseba nima otrok, je v njeni rodbini natančno ena oseba brez otrok, namreč ona. Sicer pa gre prek otrok in vsakega vpraša, koliko je v njegovi rodbini takšnih, ki nimajo otrok, ter sešteje odgovore.

def brez_otrok(oseba): if not otroci[oseba]: return 1 s = 0 for otrok in otroci[oseba]: s += brez_otrok(otrok) return s

Krajša verzija - na koncu besedila.

Kandidati

def kandidati(tipi): from collections import defaultdict punce = defaultdict(set) for tip, punca in tipi.items(): punce[punca].add(tip) return punce

Spet bomo uporabili slovar s privzetimi vrednostmi. Vrednosti bodo množice. Gremo čez slovar, v katerem so fantje izbirali punce in v novi slovar dodajemo ravno obratno - k puncam dodajamo fante. To je vse. ;)

Naročniki

Naloga je zahtevala, da razumete, da v self.klici shranjujemo neke informacije o klicih, ki jih potem uporabljamo v metodah.

Glede na to, da se vse metode, ki jih pišemo, sprašujejo le o dolžinah klicev, ne bo nič narobe, če v self.klici shranjujemo le dolžine. Rešitev je tedaj kar takšna:

class Narocnik: def __init__(self): self.klici = [] def dodaj_klic(self, od, do): self.klici.append(do - od) def st_klicev(self): return len(self.klici) def dolzina_klicev(self): return sum(self.klici) def najdaljsi_klic(self): return max(self.klici) def najkrajsi_klic(self): return min(self.klici)

Rešitev, ki shranjuje začetke in konce, pa je spodaj.

Krajše rešitve

def ravnotezje(s): return min((abs(sum(s[:i]) - sum(s[i:])), i) for i in range(len(s)))[1] def k_ti(s, k): from collections import Counter return sorted([(v, k) for k, v in Counter(s).items()], reverse=True)[k][1] def brez_otrok(oseba): return not otroci[oseba] or sum(brez_otrok(otrok) for otrok in otroci[oseba]) def kandidati(tipi): return {punca: {tip for tip, izbranka in tipi.items() if izbranka == punca} for punca in tipi.values()} class Narocnik: def __init__(self): self.klici = [] def dodaj_klic(self, od, do): self.klici.append((od, do)) def st_klicev(self): return len(self.klici) def dolzina_klicev(self): return sum(do - od for do, od in self.klici) def najdaljsi_klic(self): return max(do - od for do, od in self.klici) def najkrajsi_klic(self): return min(do - od for do, od in self.klici)

"Funkcijska" rešitev zadnje naloge

Tule je še ena malo drugače zasukana rešitev zadnje naloge. Zanimiva je, ker boste nekaj več tega videli pri Programiranju 2.

class Narocnik: def __init__(self): self.klici = [] def dodaj_klic(self, od, do): self.klici.append((od, do)) def st_klicev(self): return len(self.klici) def izr(self, f): return f(do - od for od, do in self.klici) def dolzina_klicev(self): return self.izr(sum) def najdaljsi_klic(self): return self.izr(max) def najkrajsi_klic(self): return self.izr(min)