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
  1. 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 poklicali daj_tocke.
  • vsota() vrne skupno število točk.
  • naredil() vrne True, č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
Last modified: Tuesday, 16 February 2016, 7:26 PM