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.
otroci = {
"Adam": ["Matjaž", "Cilka", "Daniel", "Erik"],
"Aleksander": [],
"Alenka": [],
"Barbara": [],
"Cilka": [],
"Daniel": ["Elizabeta", "Hans"],
"Erik": [],
"Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"],
"Franc": [],
"Herman": ["Margareta"],
"Hans": [],
"Jožef": ["Alenka", "Aleksander", "Petra"],
"Jurij": ["Franc", "Jožef"],
"Ludvik": [],
"Margareta": [],
"Matjaž": ["Viljem"],
"Mihael": [],
"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 znamo
def stevilo_vnukov(oseba): return sum(stevilo_otrok(otrok) for otrok in otroci[oseba])
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 so se dobro naučili prejšnjo snov:
def velikost_rodbine(oseba): return sum(velikost_rodbine(otrok) for otrok in otroci[oseba]) + 1
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])
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.
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
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
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
Niz je palindrom, če se naprej in nazaj bere enako.
Pisati funkcijo, ki pove, ali je podani niz palindrom, je sicer železni
repertoar pouka programiranja - v Pythonu pa je nekoliko trivialen. Če imamo
niz s, bomo z s[1:-1] dobili obrnjen niz, niz
"prebran" nazaj. Če sta tadva enaka, je funkcija palindrom.
Ker vem, da ste pametni ljudje, ne boste pisali
def palindrom(s):
if s == s[::-1]:
return True
else:
return False
temveč, kratko in jedrnato
def palindrom(s):
return s == s[::-1]
Zdaj pa recimo, da za tole obračanje nizov ne vemo (ali pa, da programiramo
v jeziku, ki česa takšnega nima. V tem primeru potrebujemo zanko: rekli bomo,
da je s palindrom, če je ničti znak enak zadnjemu, prvi
predzadnjemu in tako naprej do konca. Po vzorcu, ki nam je že čisto domač,
bomo ob prvem neujemanju zatulili Falsch!; če pridemo do konca
brez težav, vrnemo True.
def palindrom(s):
for i in range(len(s)):
if s[i] != s[-i - 1]:
return False
return True
(Pravzaprav ni potrebno, da gremo "tako naprej do konca", saj bi zadoščalo "tako naprej do sredine". A to tule ni pomembno.)
Palindrome lahko definiramo na drug način, ki ne zahteva štetja: rečemo
lahko, da je s palindrom, če je ničti znak enak zadnjemu in je
palindrom tudi vse med njima. Poskrbeti je le potrebno za nize, ki nimajo
dveh znakov: če je niz krajši od dveh znakov, bomo rekli, da je palindrom.
Z enim stavkom: s je palindrom, če je krajši od dveh znakov ALI
pa je ničti znak enak zadnjemu IN so vsi znaki od prvega do predzadnjega
palindrom.
def palindrom(s):
return len(s) < 2 or s[0] == s[-1] and palindrom(s[1:-1])
Študente tole pogosto zbega. Funkcija palindrom je definirana
s funkcijo palindrom. Sama s sabo. Je to sploh dovoljeno? Deluje?
Razlog, da deluje, je v tem, da je niz vedno krajši. Ko se vprašamo, ali je "abcdcba" palindrom, funkcija ugotovi, da to sicer ni manj kot dva znaka, vendar je palindrom, če je ničti znak enak zadnjemu (kar je) in če je "bcdcb" palindrom. Ko preverja, ali je "bcdcb" palindrom, ugotovi, da je daljši od dveh znakov, zato bo palindrom, če je ničti enak zadnjemu (kar je) in če je "cdc" palindrom. Ta je daljši od dveh znakov, zato bo palindrom, če je ničti znak enak zadnjemu in je "d" palindrom. Niz "d" je krajši od dveh znakov, torej je palindrom. Zato je torej tudi "cdc" palindrom. Zato je "bcdcb" palindrom. Zato je "abcdcba" palindrom.
Kako bi izračunali vsoto elementov seznama. Z zanko seveda znamo. Pa poskusimo še s trikom, kakršnega smo uporabili zgoraj. Za to potrebujemo rekurzivno definicijo vsote seznama - definicijo, ki se nanaša sama nase.
Takole lahko rečemo: vsoto elementov seznama dobimo tako, da k prvemu elementu prištejemo vsoto ostalih. Če je seznam prazen, pa je vsota 0.
def vsota(s):
if not s:
return 0
return s[0] + vsota(s[1:])
Seznam ima sama soda števila, če je prazen ali pa je prvi element sod in ima preostanek sama soda števila.
def soda(s):
return not s or s[0] % 2 == 0 and soda(s[1:])
Napisati želimo funkcijo, ki vrne vsoto vseh sodih elementov v podanem seznamu.
Če je seznam prazen, je vsota enaka 0. Sicer pa naredimo tole: če je ničti element sod, vrnemo vsoto ničtega elementa in vsote ostalih. Če ni sod, vrnemo le vsoto ostalih.
def vsota_sodih(s):
if not s:
return 0
if s[0] % 2 == 0:
return s[0] + vsota_sodih(s[1:])
else:
return vsota_sodih(s[1:])
Napisali bomo funkcijo, ki vrne prvi sodi element.
Če je ničti element sod, vrnemo tega. Sicer vrnemo prvega sodega med ostalimi.
def prvi_sodi(s):
if s[0] % 2 == 0:
return s[0]
else:
return prvi_sodi(s[1:])
Funkcija ima manjšo težavo, kadar v
seznamu ni nobenega sodega elementa. Ker prvi ni sod, išče sodega v preostanku.
Ker prvi iz preostanka ni sod, išče sodega v preostanku. Ker prvi v tem
preostanku ni sod ... in tako naprej, dokler ne pride do praznega seznama.
Takrat bomo v prvi vrstici funkcije spraševali po prvem (no, ničtem) elementu,
s[0] in Python bo javil napako, Index out of range.
Recimo, da bo funkcija v takšnem primeru vrnila None.
def prvi_sodi(s):
if not s:
return None
if s[0] % 2 == 0:
return s[0]
else:
return prvi_sodi(s[1:])