Novakovi

Ogrevalna naloga

Napiši funkcijo najmlajsi_clan(oseba), ki kot argument prejme ime osebe in kot rezultat vrne starost in ime najmlajše osebe v rodbini. Tako naj, recimo, klic najmlajsi_clan("Jurij") vrne terko (5, "Aleksander").

Nasvet: če ima oseba nima otrok, naj vrne svojo starost in ime. Če ima otroke, naj sprašuje njih, rezultate pa naj - čeprav gre za terke - preprosto primerja. Če primerjamo dve terki, bo manjša tista, ki je manjša glede na prvi element.

Rešitev

Kako bi to izvedli v predavalnici? Natančno tako, kot bo program: vsaka oseba bi vprašala vse svoje otroke, "koliko star je najmlajši član tvoje rodbine in kako mu je ime?" Med odgovori bi si zapomnil najmanjšega. Kot je namigovala že naloga, nam tule pomaga, da Python primerja terke tako, da najprej primerja prvi element, torej, v tem primeru, starost. V dodatno pomoč je bilo, upam, da smo prav ta vzorček gledali (v nerekurzivni obliki) pri reševanju prejšnje domače naloge.

Kot običajno bo oseba najprej zase rekla, da je najmlajša, nato pa spraševala svoje otroke, ali je morda kdo že mlajši. Reč ni čisto povsem smiselna (razen, če je morda kdo posvojil otroka, starejšega od sebe), a če nič drugega, služi kot smiselna prva vrednost - namesto "velike številke", ki smo jo kot prvo vrednost uporabili včasih.

def najmlajsi_clan(oseba): naj = (starost[oseba], oseba) for otrok in otroci[oseba]: naj_pod = najmlajsi_clan(otrok) if naj_pod < naj: naj = naj_pod return naj

Oklepaji v prvem prirejanju niso potrebni - vendar jih pišemo, da poudarimo, da gre za terko.

Ne spreglejte, da nismo nikjer rekli "če oseba nima otrok, naj kot najmlajšega člana vrne sebe. To ni potrebno, saj se zanka v tem primeru pač ne bo izvedla in naj bo ostal, kar je - torej starost in ime te osebe.

Za iskanje minimumov imamo sicer funkcijo min, ki se je z generatorji pokazala v še uporabnejši luči. Poskusimo takole: vsaka oseba išče minimum tega, kar vrne najmlajsi_clan(otrok) za vsakega od svojih otrok.

def najmlajsi_clan(oseba): return min(najmlajsi_clan(otrok) for otrok in otroci[oseba]) Error Traceback (most recent call last): File "/Users/janezdemsar/Dropbox/Pedagosko/P1/2014/10 rekurzija/domaca/resitev.py", line 72, in test_najmlajsi_clan self.assertEqual(najmlajsi_clan("Adam"), (3, "Margareta")) File "/Users/janezdemsar/Dropbox/Pedagosko/P1/2014/10 rekurzija/domaca/resitev.py", line 15, in najmlajsi_clan return min(najmlajsi_clan(otrok) for otrok in otroci[oseba]) File "/Users/janezdemsar/Dropbox/Pedagosko/P1/2014/10 rekurzija/domaca/resitev.py", line 15, in <genexpr> return min(najmlajsi_clan(otrok) for otrok in otroci[oseba]) File "/Users/janezdemsar/Dropbox/Pedagosko/P1/2014/10 rekurzija/domaca/resitev.py", line 15, in najmlajsi_clan return min(najmlajsi_clan(otrok) for otrok in otroci[oseba]) File "/Users/janezdemsar/Dropbox/Pedagosko/P1/2014/10 rekurzija/domaca/resitev.py", line 15, in <genexpr> return min(najmlajsi_clan(otrok) for otrok in otroci[oseba]) File "/Users/janezdemsar/Dropbox/Pedagosko/P1/2014/10 rekurzija/domaca/resitev.py", line 15, in najmlajsi_clan return min(najmlajsi_clan(otrok) for otrok in otroci[oseba]) File "/Users/janezdemsar/Dropbox/Pedagosko/P1/2014/10 rekurzija/domaca/resitev.py", line 15, in <genexpr> return min(najmlajsi_clan(otrok) for otrok in otroci[oseba]) File "/Users/janezdemsar/Dropbox/Pedagosko/P1/2014/10 rekurzija/domaca/resitev.py", line 15, in najmlajsi_clan return min(najmlajsi_clan(otrok) for otrok in otroci[oseba]) ValueError: min() arg is an empty sequence

Ups!?

Preberimo: po tem, ko je funkcija nekajkrat poklicala samo sebe, smo poskusili izračunati minimum praznega zaporedja. Ah, ja, to so tisti brez otrok. Tule jih bo očitno potrebno obravnavati ločeno.

def najmlajsi_clan(oseba): if not otroci[oseba]: return starost[oseba], oseba return min(najmlajsi_clan(otrok) for otrok in otroci[oseba])

Obvezna naloga

Napiši funkcijo mlajsi_od(oseba, n), ki vrne množico tistih članov rodbine podane osebe, ki imajo manj kot n let. Tako mora mlajsi_od("Jurij", 10) vrniti {"Alenka", "Petra", "Aleksander"}.

Namig: če ne znaš, preberi zapiske predavanj.

Rešitev

Tokrat začnimo s pogostimi napačnimi iskanji.

def mlajsi_od(oseba, n): seznam = set() for otrok in otroci[oseba]: mlajsi_od(otrok, n) if starost[otrok] < n: seznam.add(otrok) return seznam

Nekoč, ko bom star in pameten, bom morda razumel, zakaj študenti ne razumejo rekurzije. Morda me je tale funkcija - praktično enako funkcijo sem ta teden precejkrat dobil po mailu, torej ste mnogi razmišljali na podoben način - pripeljala malo bližje k temu razumevanju.

Preden pogledamo, kaj je narobe zgoraj, naj ugibam: osnovna ideja je bila pravzaprav tale:

def mlajsi_od(oseba, n): if starost[oseba] < n: seznam.add(oseba) for otrok in otroci[oseba]: mlajsi_od(otrok, n) return seznam

Imamo "seznam", v katerega doda oseba najprej sebe, če je dovolj mlada, nato pa pozove še svoje otroke, naj naredijo isto. Problem je tule: kdo bo naredil ta seznam? Glede na to, da ga potrebuje funkcija, ga bo najbrž naredila funkcija, ne?

def mlajsi_od(oseba, n): seznam = set() if starost[oseba] < n: seznam.add(oseba) for otrok in otroci[oseba]: mlajsi_od(otrok, n) return seznam

To ne deluje zato, ker ima vsaka funkcija svoj seznam. Nepokorni otroci ne zlagajo sebe in svojih potomcev v isti seznam, temveč naredijo nov seznam in zlagajo vanj. Ta seznam sicer vrnejo (return seznam), vendar ta, ki je poklical funkcijo, z vrnjeno množico ne naredi ničesar - pokliče mlajsi_od(otrok, n), rezultat klica pa zavrže.

Navidezna rešitev tega je, da pač poskrbimo, da bodo vsi pisali v isto množico, takole:

seznam = set() def mlajsi_od(oseba, n): if starost[oseba] < n: seznam.add(oseba) for otrok in otroci[oseba]: mlajsi_od(otrok, n) return seznam

Lani sem videl precej takšnih (napačnih) rešitev, letos ne. Morda niso prišle do mene, morda sem vas dovolj prestrašil in prepričal, da se tako ne da rešiti naloge. Tole bi sicer delalo - vendar le prvič. Ko bi funkcijo poklicali naslednjič, množica v začetku ne bi bila več prazna.

Rešitev v tej smeri sicer obstaja, vendar jo je najbrž težje razumeti kot pravo. Pa še precej grša je, ker uporablja globalne spremenljivke na način, s kakšrnim se izpostavlja nevarnostim, o katerih pri Programiranju 1 še ne znamo razmišljati.

def mlajsi_od(oseba, n): global seznam seznam = set() mlajsi_od1(oseba, n) return seznam def mlajsi_od1(oseba, n): if starost[oseba] < n: seznam.add(oseba) for otrok in otroci[oseba]: mlajsi_od1(otrok, n)

Zdaj naša funkcija mlajsi_od ni več rekurzivna. Njena naloga je, da le zbriše množico seznam in pokliče pravo rekurzivno funkcijo mlajsi_od1. Ta kliče samo sebe, tako kot prej, in napolni seznam. Ker nihče ne gleda njene vrednosti, pa ga niti ne vrača. Pač pa ga na koncu vrne mlajsi_od.

To že dela, kar mora in tudi teste preživi, je pa grdo.

Druga rešitev, ki uporablja enak vzorec, je tale:

def mlajsi_od(oseba, n): seznam = set() mlajsi_od1(oseba, n, seznam) return seznam def mlajsi_od1(oseba, n, seznam): if starost[oseba] < n: seznam.add(oseba) for otrok in otroci[oseba]: mlajsi_od1(otrok, n, seznam)

Razlika je v tem, da seznam ni več globalna spremenljivka, temveč ga funkcija mlajsi_od naredi in si ga potem mlajsi_od1 podaja kot argument. Funkcija mlajsi_od1 tako dobi tri argumente: ime osebe, mejno starost in množico, v katero mora dopisovati člane rodbine. Pri igri v predavalnici bi bilo to ekvivalentno temu, da bi si ti, ki se izprašujejo, pošiljali po predavalnici list (isti list!), na katerega bi dopisovali rodbinske člane.

Na ta način bi nalogo rešili v jezikih, ki v delu z množicami niso tako spretni kot Python. Včasih kaj podobnega počnemo tudi v Pythonu, pri tej nalogi pa ni potrebno.

Rešitev je podobna funkciji, ki je zbrala vse rodbinske člane: naredili smo jo tako na predavanjih kot na vajah.

def rodbina(oseba): rod = {oseba} for otrok in otroci[oseba]: rod |= rodbina(otrok) return rod

Kdor je res razumel, kako deluje ta funkcija, mu je ni bilo težko dopolniti tako, da je osebo dodala le, če je dovolj mlada.

def mlajsi_od(oseba, n): seznam = set() if starost[oseba] < n: seznam.add(oseba) for otrok in otroci[oseba]: seznam |= mlajsi_od(otrok, n) return seznam

Rešitev, ob kateri bi malo pogodrnjal, vendar ne bi smel preveč protestirati, saj je nisem prepovedal, je, da naredite množico, v kateri je vse rodbina, a nato obdržite le tiste, ki so dovolj mladi. Uporabimo torej funkcijo s predavanj in ji dodamo le še tole:

def mlajsi_od(oseba, n): return {ime for ime in rodbina(oseba) if starost[ime] < n}

Še en komentar: v gornji funkciji smo imeli spremenljivko z imenom seznam. Dajati spremenljivkam imena, kot so stevilo, niz, slovar, mnozica ali seznam ni preveč posrečena ideja. Še posebej pa je to ponesrečeno, če ta seznam v resnici ni seznam, temveč množica.

Dodatna naloga

Daniel ima liho število let (85). Njegova hči Elizabeta ima sodo število (68). Njen sin Jurij ima liho (49). Njegov sin Franc ima spet sodo (30). Veriga Daniel -> Elizabeta -> Jutri -> Franc se izmenjuje glede na lihost in sodost števila let in je dolga štiri člene.

Napiši funkcijo naj_izmenicna_starost(oseba), ki vrne dolžino najdaljše takšne izmenjujoče se verige, ki se prične pri podani osebi.

Rešitev

Spomnimo se, kako smo na predavanjih računali globino rodbine: vsaka oseba je vprašala vsakega otroka po globini njegove rodbine. Zapomnila si je največji odgovor in k njemu prištela 1, zase.

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

Ali, krajše

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

Dodati moramo še pogoj, pod katerim nas otrok zanima: če ima oseba sodo število let, mora imeti otrok liho in obratno. To se da lepo zaplesti

if starost[oseba] % 2 == 0 and starost[oseba] % 2 == 1 or \ starost[oseba] % 2 == 1 and starost[oseba] % 2 == 0:

Če se spomnimo česa iz osnovne šole, pa vemo, da je vsota dveh sodih števil soda, dveh lihih prav tako; pač pa je vsota lihega in sodega liha. Torej preverimo le vsoto starosti; če je liha, ima nekdo sodo število let in drugi liho. Kdo je kdo, ni pomembno. Tako dobimo

def naj_izmenicna_starost(oseba): naj = 0 for otrok in otroci[oseba]: if (starost[otrok] + starost[oseba]) % 2 == 1: ta = naj_izmenicna_starost(otrok) if ta > naj: naj = ta return naj + 1

Ali, krajše,

def globina(oseba): return max([globina(otrok) for otrok in otroci[oseba] if (starost[oseba] + starost[otrok]) % 2 == 1] + [0]) + 1