Tile zapiski vsebujejo le programerski del predavanj. Na predavanjih smo funkcije "odigrali", tako da so različni študenti predstavljali različne osebe.

Novakovi

Najstarejši član rodbine Novakovih, Adam, 111 let, ima štiri otroke: Matjaža, Cilko, Danieka in Erika. Matjaž ima enega, namreč Viljema. Danijel ima Elizabeto in Hansa (kasneje se je namreč preselil v predmestje Graza, kjer ima manjše podjetje), Cilka in Erik pa nimata otrok. In tako naprej. Vse skupaj je nabrano v spodnjem slovarju.

rodbina = {
    "Adam": ["Matjaž", "Cilka", "Daniel"],
    "Aleksander": [],
    "Alenka": [],
    "Barbara": [],
    "Cilka": [],
    "Daniel": ["Elizabeta", "Hans"],
    "Erik": [],
    "Elizabeta": ["Ludvik", "Jurij", "Barbara"],
    "Franc": [],
    "Herman": ["Margareta"],
    "Hans": ["Herman", "Erik"],
    "Jožef": ["Alenka", "Aleksander", "Petra"],
    "Jurij": ["Franc", "Jožef"],
    "Ludvik": [],
    "Margareta": [],
    "Matjaž": ["Viljem"],
    "Petra": [],
    "Tadeja": [],
    "Viljem": ["Tadeja"],
}

Znane so tudi starosti vseh teh ljudi.

starost = {
    "Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83,
    "Viljem": 58, "Tadeja": 20, "Elizabeta": 68, "Hans": 64, "Ludvik": 50,
    "Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30,
    "Jožef": 29, "Margareta": 3, "Alenka": 9, "Aleksander": 5, "Petra": 7}

Napišimo, takole, za preprosto vajo, funkcijo, ki ji podamo osebo in pove, koliko otrok ima.

def stevilo_otrok(oseba):
    return len(otroci[oseba])

Če pokličemo, recimo, stevilo_otrok("Adam"), dobimo 4.

Kako pa bi izvemo število vnukov posamezne osebe? Tako da gremo prek vseh otrok in seštevamo število njihovih otrok, recimo z

def stevilo_vnukov(oseba):
    v = 0
    for otrok in otroci[oseba]:
        v += len(otroci[otrok])
    return v

ali, brez velike razlike,

def stevilo_vnukov(oseba):
    v = 0
    for otrok in otroci[oseba]:
        v += stevilo_otrok(otrok)
    return v

Uh, kaj kompliciramo, saj že od predprejšnjega tedna znamo

def stevilo_vnukov(oseba):
    return sum(stevilo_otrok(otrok) for otrok in otroci[oseba])

V živo je bilo to videti tako, da smo nekoga vprašali, koliko vnukov ima. Ker tega podatka ni imel na svojem listu, je moral povprašati svoje otroke, natančno tako, kot to počne funkcija (ki smo jo napisali takoj po tem).

Velikost rodbine

Do sem - nič posebnega. Zdaj pa pridejo zanimive reči: za nekoga nas zanima, velika je njegova rodbina, skupaj z njim, njegovimi otroki, vnuki, pravnuki in tako naprej. Recimo, da ima rojstni dan in bo povabil vso svojo rodbino na večerjo. Koliko krožnikov za juho potrebuje.

Kaj mu je storiti? Vse svoje otroke, bo vprašal, kako velike so njihove rodbine. To bo seštel in prištel še sebe. Kako bodo ti otroci izvedeli velikosti svojih rodbin? Tako, da bodo vprašali vse svoje otroke po velikosti njihovih rodbin, to sešteli in prišteli še sebe. Pa njihovi otroci? Enako.

Spremenimo to v funkcijo. Velikost rodbine dobimo tako, da gremo prek otrok in seštevamo velikosti njihovih rodbin.

def velikost_rodbine(oseba):
    v = 0
    for otrok in otroci[oseba]:
        v += velikost_rodbine(otrok)
    return v + 1

Za tiste, ki znajo snov izpred dveh tednov:

def velikost_rodbine(oseba):
    return sum(velikost_rodbine(otrok) for otrok in otroci[oseba]) + 1

Poišči osebo

Potem nas je zanimalo, kako odkriti, ali je v rodbini določene osebe oseba s takšnim in takšnim imenom. Storiti nam je tole: če je tako ime ravno vprašani osebi, bo odgovorila True. Sicer bo enega za drugim spraševala otroke, dokler prvi ne odgovori True; tedaj vrnemo True. Če noben otrok nima takšnega potomca - in torej noben otrok ne odgovori True, odgovorimo False. Z drugimi besedami,

def obstaja_ime(oseba, ime):
    if oseba == ime:
        return True
    for otrok in otroci[oseba]:
        if obstaja_ime(otrok, ime):
            return True
    return False

S snovjo izpred dveh tednov:

def obstaja_ime(oseba, ime):
    return oseba == ime or any(obstaja_ime(otrok, ime) for otrok in otroci[oseba])

Največja družina

Kako velika je največja družina v rodbini neke osebe - s temi mislimo le otroke, brez staršev? Tu osebe razmišljajo tako: najprej predpostavijo, da je to njihova družina - največ otrok je torej toliko otrok, kolikor jih imajo oni. Potem vprašajo vsakega od otrok, kako velika je največja družina v njegovi rodbini. Če naleti na koga z večjo družino, si to zapomni. Na koncu vrne največ, kar je videl.

def najvec_otrok(oseba):
    najvec = len(otroci[oseba])
    for otrok in otroci[oseba]:
        koliko = najvec_otrok(otrok)
        if  koliko > najvec:
            najvec = koliko
    return najvec

Kdor zna, zna takole:

def najvec_otrok(oseba):
    return max([len(otroci[oseba])] + [najvec_otrok(otrok) for otrok in otroci[oseba]])

Študenti pogosto zagrešijo tole precej napačno rešitev:

def najvec_otrok(oseba):
    najvec = len(otroci[oseba])
    for otrok in otroci[oseba]:
        if najvec_otrok(otrok) > najvec:
            najvec = najvec_otrok(otrok)
    return najvec

Tu vsaka oseba večkrat vpraša svoje otroke, kako velike so največje družine. Vsaj tistega z največjo družino vpraša dvakrat. Doslej smo takšno programiranje tolerirali (in le občasno postokali, da to ni najlepše). Tu ga ne moremo več. Vsak od teh, ki so bili po nepotrebnem vprašani dvakrat, spet dvakrat vpraša svoje otroke vpraša po dvakrat, torej se v bistvu vprašajo po štirikrat. Oni spodaj so vprašani že po osemkrat. Pri tako majhnih drevesih to ni tako hudo. Pri velikih pa si tega ne bi mogli privoščiti.

Najdaljše ime v rodbini

Katero je najdaljše ime v rodbini neke osebe? Tole je precej podobno največjemu številu otrok: najdaljše je moje, razen če je daljše katero od imen v rodbini katerega od otrok.

def najdaljse_ime(oseba):
    najdaljse = oseba
    for otrok in otroci[oseba]:
        naj_pod = najdaljse_ime(otrok)
        if len(naj_pod) > len(najdaljse):
            najdaljse = naj_pod
    return najdaljse

(Z izpeljanimi seznami bi šlo enako kot prej. A pustimo.)

Globina rodbine

Kako globoka je rodbina določene osebe? Torej, nekdo, ki nima otrok, ima rodbino globinee 1. Če ima otroke, nima pa vnukov, ima rodbino globine 2. Če ima tudi kakega vnuka, vendar nobenega pravnuka, ima rodbino globine 3.

Globino rodbine izračunamo tako, da vprašamo vse otroke po globinah njihovih rodbin in k največji globini, ki jo dobimo, prištejemo 1.

def globina(oseba):
    najvecja = 0
    for otrok in otroci[oseba]:
        g = globina(otrok)
        if g > najvecja:
            najvecja = g
    return najvecja + 1

Ali, krajše

def globina(oseba):
    return max(globina(otrok) for otrok in otroci[oseba]) + 1

Velikost potomstva

Pripadnike Novakove rodbine smo nato spraševali, koliko potomstva imajo. S potomci mislimo nekaj takšnega kot rodbino, a brez te osebe same. Jurij (ki ima dva otroka in tri vnuke) ima pet potomcev).

Tale zahteva malo razmisleka. Navidez bi jo lahko ugnali tako, kot smo velikost rodbine, le 1 ne smemo prišteti na koncu, saj oseba ne sme šteti sebe.

def velikost_rodbine(oseba):
    v = 0
    for otrok in otroci[oseba]:
        v += velikost_rodbine(otrok)
    return v

Zoprna reč je, da je ta funkcija nekoliko napačna. No, precej napačna. Vedno vrne 0 - ker nihče nikoli ničesar ne prišteje, vse seštevajo samo ničle. In iz ničel nikoli ne boš dobil ničesar, pa jih seštevaj, kolikor dolgo hočeš.

Ena rešitev je, da vsak vrne število svojih otrok, ki čemur morajo otroci prišteti število svojih otrok, in vnuki število svojih...

def stevilo_potomcev(oseba):
    potomcev = len(otroci[otroci])
    for otrok in otroci[oseba]:
        potomcev += stevilo_potomcev(otrok)
    return potomcev

Ali isto, le na drug način:

def stevilo_potomcev(oseba):
    potomcev = 0
    for otrok in otroci[oseba]:
        potomcev += 1 + stevilo_potomcev(otrok)
    return potomcev

Lahko pa si pomagamo tudi z rodbino:

def stevilo_potomcev(oseba):
    return velikost_rodbine(oseba) - 1

Še nekaj nalog

Še nekaj zanimivih nalog in rešitev si lahko ogledate v domači nalogi Novakovi.

Zadnja sprememba: torek, 9. januar 2024, 11.53