Rešitve s komentarji
Bomboniera
(Za inspiracijo za nalogo hvala kolegom s FMF. :)
Benjamin je našel bomboniero, v kateri je sirina stolpcev in visina vrstic bombonov. Že pred njim jo je našla in nekoliko izropala njegova sestra Ana. Benjamin se ne bo dotaknil vrstic in stolpcev, iz katerih je Ana že vzela kak bombon. Pojedel pa bo vse ostale.
Napiši funkcijo bomboniera(sirina, visina, pojedeno), ki pove, koliko
bombonov bo pojedel. Seznam pojedeno vsebuje pare z vodoravnimi in navpičnimi
koordinatami. Če pokličemo bomboniera(8, 5, [(2, 1), (2, 4)]) bo Benjamin
pojedel vse bombone razen tistih v drugem stolpcu ter tistih v prvi in četrti
vrstici, saj je tam stikala že Ana.
Rešitev
Naloga je zelo preprosta, če razmislimo, kaj pravzaprav hoče: število bombonov, ki jih bo snedel Benjamin, je enaka produktu števila nedotaknjenih vrstic in nedotaknjenih stolpcev.
Množice sem na predavanjih propagiral kot lep način za štetje različnih reči -
z len(set("barbara")) izvemo, koliko različnih črk je v besedi barbara.
Tule v dve množici zložimo vse številke stolpcev in vse številke vrstic. To
lahko naredimo z
stolpci = set()
vrstice = set()
for s, v in pojedeno:
stolpci.add(s)
vrstice.add(s)
ali - varianta "ne me zezat" - z
stolpci = {s for s, v in pojedeno}
vrstice = {v for s, v in pojedeno}
Četudi je iz istega stolpca (ali vrstice) morda vzel več bombonov, se v
množici pojavi le enkrat - ker je to pač množica. Število dotaknjenih stolpcev
in vrstic je potem len(stolpci) in len(vrstice), število nedotaknjenih pa
sirina - len(stolpci) in visina - len(vrstice).
Pa smo rešili nalogo.
def bomboniera(sirina, visina, pojedeni):
return (sirina - len({x for x, _ in pojedeni})) * (visina - len({y for _, y in pojedeni}))
Vreme
Napiši funkcijo izpis_vrstice(kraj, vreme, temperatura, veter, tlak), ki
prejme vremenske podatke: prva dva argumenta sta niza. Ostali argumenti so
številke ali pa prazen niz, če podatek ni znan. Funkcija vrne niz z opisom
vremena (glej teste). Kraj je izpisan na 35 mest, vreme na 20, temperatura in
veter na 5 ter tlak na 8.
Napiši funkcijo izpisi_vreme(datoteka), ki prejme ime datoteke z vremenskimi
podatki in vrne niz s celotnim “vremenskim poročilom” (glej teste). Kako je
videti datoteka, si oglej v vreme.txt, ki se uporablja tudi v testih.
Rešitev
Za prvi del naloge je potrebno znati oblikovati nize v Pythonu. Širine je podala naloga, v testih pa moramo opaziti še, da je vreme poravnano na desno.
def izpis_vrstice(kraj, vreme, temperatura, veter, tlak):
return "{:35}{:>20}{:5}{:5}{:8}".format(kraj, vreme, temperatura, veter, tlak)
Branje je nekoliko nadležnejše, ker nekateri podatki manjkajo. Ko bomo niz razbili glede na tabulator, recimo takole
podatki = vrstica.strip().split("\t")
bomo dobili seznam, ki ima lahko tudi manj kot pet elementov. Zato ne
kraj, vreme, temperatura, veter, tlak = line.strip().split("\t)"
ne (grši, a nič bolj delujoč)
kraj = podatki[0]
vreme = podatki[1]
temperatura = podatki[2]
veter = podatki[3]
tlak = podatki[4]
ne bosta delovala.
Drugo, gršo različico, rešimo s kupom if-ov v slogu
if len(podatki) >= 3:
veter = int(podatki[3])
else:
veter = ""
in tako tudi za vse ostale.
Če ne maramo dolgih programov, uporabimo trik: k podatkom prištejemo seznam s petimi presledki, da dodamo morebitne manjkajoče podatke.
podatki = podatki + [""] * 5
Vendar imamo zdaj obratni problem: zdaj imajo podatki lahko več kot pet elementov. No, to pa je lahko rešljivo: vse od petega naprej odbijemo, saj smo jih dodajali brez potrebe. Torej
podatki = (podatki + [""] * 5)[:5]
Ta trik si zapomnite. Je uporaben.
Tako dobimo naslednjo rešitev.
def izpisi_vreme(fname):
s = []
for line in open(fname):
data = (line.strip().split("\t") + [""] * 5)[:5]
kraj, vreme = data[:2]
temperatura, veter, tlak = [int(x) if x else "" for x in data[2:]]
s.append(izpis_vrstice(kraj, vreme, temperatura, veter, tlak))
return "\n".join(s)
Vse vrstice, ki jih je potrebno sestaviti, najprej zlagamo v seznam s in jih
na koncu zlepimo skupaj z "\n".
Prafaktorji
Napišite funkcijo prafaktorji(n), ki razcepi podano število n na prafaktorje
in vrne razcep v obliki slovarja. Če pokličemo prafaktorji(1400), vrne
slovar {2: 3, 5: 2, 7: 1}, saj je 1400 = 235271.
Nato napišite funkcijo gcd(a, b), ki prejme dva slovarja, kakršna vrača
prejšnja naloga, in vrne največji skupni delitelj števil, ki ju predstavljata
tadva slovarja. Če pokličemo gcd({2: 3, 5: 2, 7: 1}, {2: 2, 7: 2, 11:1}),
vrne 28. Prvi slovar namreč predstavlja število 1400 in drugi število 2156,
njun največji skupni delitelj pa je 28. Da bi dobil vse točke, nalogo reši,
ne da bi izračunal števili (npr. 1400 in 2156). Delaj s slovarjema, ki si ju
dobil.
Namig: 1400 = 235271 in 2156 = 2272111 , zato je njun največji skupni delitelj enak 2271.
Rešitev
Prvi, težji del naloge se je moral zdeti znan vsem, ki ste kaj gledali stare domače naloge in pri tem naleteli na nalogo Razcep na prafaktorje. Tam je sicer zahtevala malo več, vseeno pa ste si - tisti, ki ste vedeli zanjo, lahko z njo pošteno pomagali.
Tu si ne bomo. Sprogramirali jo bomo od začetka, brez dodatne šare, ki jo je zahtevala ona domača naloga.
def prafaktorji(n):
fact = {}
for i in range(2, n + 1):
for d in range(n):
if n % i == 0:
n //= i
else:
break
if d != 0:
fact[i] = d
return fact
Z zunanjo zanko pošljemo i prek vseh števil od 2 do n. Nato z notranjo zanko
preštejemo, kolikokrat i deli n: z d-jem štejemo od 0 do n. Če i deli
n, ga (celoštevilsko, //) delimo. Sicer prekinemo zanko. Notranja zanka se
izvede nobenkrat, enkrat, dvakrat ... tolikokrat, kolikorkrat je pač mogoče
deliti n z i. Po zanki preverimo, ali smo n kdaj delili z i in če smo
ga, to zapišemo.
Funkcija je počasna: za i ni potrebno, da gre čisto do n. Pospešimo jo
lahko na različne načine. Vstavimo lahko, recimo,
if i > n:
break
ali, kar se izkaže za isto
if n == 1:
break
med prvi in drugi for.
Kako lahko vemo, da bodo delitelji praštevila? Kaj, če bi bil i, recimo 6?
V tem primeru ne bo delil n-ja. Preden bo i enak 6, je bil enak 2 in 3;
ko n ni več deljiv ne z 2 ne s 3, pa tudi s 6 ne bo več.
Zanimiva druga rešitev je tale:
def prafaktorji(n):
fact = defaultdict(int)
i = 2
while n > 1:
if n % i == 0:
fact[i] += 1
n //= i
else:
i += 1
return fact
Če n deli i, povečamo potenco fact[i] za 1 in delimo n. Sicer gremo
na naslednji i.
Funkcija gcd dobi dva slovarja. Zanimajo nas ključi, ki se pojavijo v obeh;
iz slovarjev vzamemo tisto vrednost pri tem ključu, ki je manjša. Vse skupaj
množimo v končno število n: če je v enem slovarju 7:3 in v drugem 7:2,
bomo n pomnožili s 7:2.
def gcd(f1, f2):
n = 1
for p in f1:
if p in f2:
n *= p ** min(f1[p], f2[p])
return n
To se da skrajšati na različne načine, recimo tako, da uporabimo get: če
drugi slovar nima tega ključa, se delajmo, da obstaja, vendar ima potenco 0.
p ** 0 bo 1, torej n *= p ** 0 ne bo spremenil n-ja.
def gcd(f1, f2):
n = 1
for p, m1 in f1.items():
m2 = f2.get(p, 0)
n *= p ** min(m1, m2)
return n
Še elegantneje gre z množicami: izračunamo presek ključev. Gremo prek tega preseka ... ostanek pa je podoben kot prej
def gcd(f1, f2):
n = 1
for p in set(f1) & set(f2):
n *= p ** min(f1[p], f2[p])
return n
Prafaktorji - rekurzivno
Če želiš (ni pa nujno), si pripravi funkcijo najm_prafaktor(n), ki vrne
najmanjše praštevilo, ki deli n.
Napiši funkcijo prafaktorji_rec(n), ki vrača isto kot prafaktorji(n).
Funkcija mora biti rekurzivna: ne sme vsebovati zanke in klicati nobene druge
funkcije, razen, če želiš, najm_prafaktor (in, če hočeš, defaultdict).
Namig: če je p praštevilo, ki deli n, je razcep enak razcepu števila n
deljeno s p, ki mu dodaš še faktor p.
Rešitev
Sledimo ponujeni ideji in pripravimo funkcijo najm_prafaktor(n).
def najm_praf(n):
for i in range(2, n + 1):
if n % i == 0:
return i
Če je n praštevilo, bo funkcija vrnila n.
Funkcija je zdaj takšna: poiščemo najmanjši prafaktor. Če je različen od
n-ja, gre za praštevilo iz namiga: izračunamo n // p in rekurzivno
pokličemo prafaktorji_rec, da izvemo ostale prafaktorje. Sicer rečemo,
da so ostali prafaktorji defaultdict(int) - prazen slovar.
Ker vemo, da np deli n, na koncu k ostali[np] prištejemo 1 in to vrnemo.
def prafaktorji_rec(n):
np = najm_praf(n)
if np != n:
ostali = prafaktorji_rec(n // np)
else:
ostali = defaultdict(int)
ostali[np] += 1
return ostali
- Pisni izdelek
Napiši razred PisniIzdelek, ki bi bil uporaben za ocenjevanje študentk ali
študentov na izpitu.
- Konstruktor prejme in shrani ime študentke oz. študenta.
daj_tocke(naloga, tocke)zabeleži, da je študent pri podani nalogi (naloge so oštevilčene od 1 do 5!) dobil podano število točk. Če funkcijo pokličemo večkrat za isto nalogo, si zapomni zadnje število.rezultat()vrne rezultat v obliki("Janez Novak", (20, 10, None, 0, 20)); prvi element rezultata je ime študenta, drugi pa terka, katere elementi so število točk pri tej nalogi, oz. None, če za to nalogo nismo poklicalidaj_tocke.vsota()vrne skupno število točk.naredil()vrneTrue, če je skupno število točk večje ali enako 50;False, če ni.ocena()vrne 5, če je število točk manjše od 50; 6, če je število točk med 50 in 59; 7, če je med 60 in 69, ..., 10, če med 90 in 100. (Opomba: to ni nujno lestvica za ocenjevanje pri tem ali drugih predmetih!)
Rešitev
Konstruktor shrani ime in priimek in pripravi seznam s petimi None, ki jih
bo v metodi daj_tocke zamenjeval s točkami.
Vse metode so potem preproste. Metodo ocena bi se dalo razpisati z if-i,
lahko pa jo rešimo z nekaj čaranja z max in min - le razmislite, kako in
zakaj to deluje!
class PisniIzdelek:
def __init__(self, ime_in_priimek):
self.ime_in_priimek = ime_in_priimek
self.tocke = [None] * 5
def daj_tocke(self, naloga, tock):
self.tocke[naloga - 1] = tock
def rezultat(self):
return self.ime_in_priimek, tuple(self.tocke)
def vsota(self):
return sum(x or 0 for x in self.tocke)
def ocena(self):
return max(5, min(1 + self.vsota() // 10, 10))
def naredil(self):
return self.vsota() >= 50