Potomci
Ogrevanje: množice članov rodbin
Napiši funkcijo rodbina(oseba), ki vrne množico članov rodbine osebe. Skoraj tako kot na predavanjih, le, da hočem množico in ne seznama.
Rešitev
Na predavanjih smo napisali
def rodbina(oseba):
s = [oseba]
for otrok in otroci[oseba]:
s += rodbina(otrok)
return s
Namesto seznama s = [oseba] naredimo množico s = {oseba}. Namesto da bi rodbino otroka prišteli, s += rodbina(otrok), jo priunijamo r |= rodbina(otrok). Tako dobimo
def rodbina(oseba):
r = {oseba}
for otrok in otroci[oseba]:
r |= rodbina(otrok)
return r
Obvezna naloga: množice opotomčenih
Napiši funkcijo imajo_potomce(oseba), ki vrne vse tiste člane rodbine podane
osebe, ki imajo potomce.
Rešitev
Če oseba nima potomcev, vrne prazno množico. Otrok ne bo spraševala, ker ... jih nima, ne?
if not otroci[oseba]:
return set()
Sicer pa je v množici ljudi iz njegove rodbine, ki imajo potomce, gotovo prav ta oseba.
imajo = {oseba}
K temu je potrebno prišteti potomce otrok.
for otrok in otroci[oseba]:
imajo |= imajo_potomce(otrok)
Dobimo, glej no, skoraj isto reč kot v ogrevalni nalogi, le z dodatnim pogojem.
def imajo_potomce(oseba):
if not otroci[oseba]:
return set()
imajo = {oseba}
for otrok in otroci[oseba]:
imajo |= imajo_potomce(otrok)
return imajo
Dodatna naloga: velikosti rodbin
Napiši funkcijo velikosti_rodbin(oseba), ki vrne slovar, katerega ključi
so člani rodbine podane osebe, vrednosti pa velikosti teh rodbin.
Pri programiranju si očitno lahko pomagaš s funkcijama, ki vrneta člane
rodbine in velikost rodbine - samo tidve funkciji daš skupaj in to je to.
Ampak to ni tako zabavno. Obstaja nenavadno elegantna rešitev, v kateri nastopa
le funkcija velikosti_rodbin, brez drugih rodbinskih funkcij.
Morda ti pride prav tole
>>> a = {"Ana": 5, "Berta": 12}
>>> b = {"Cilka": 7, "Dani": 3, "Ema": 1}
>>> a.update(b)
>>> a
{'Dani': 3, 'Ana': 5, 'Berta': 12, 'Cilka': 7, 'Ema': 1}
Rešitev
Ta naloga je ena luštnejših. Kar malo ponosen sem nanjo, saj ima zelo lepo rešitev. (Seveda obstajajo tudi manj lepe.)
Očitna rešitev je
def velikosti_rodbin(oseba):
velikosti = velikost_rodbine(oseba)
for otrok in otroci[oseba]:
velikosti.update(velikosti_rodbin(otrok))
velikosti[oseba] = len(velikosti) + 1
return velikosti
Pri tem je velikost_rodbine funkcija, ki smo jo pisali na predavanjih. Gornja rešitev torej sestavi slovar, v katerem je velikost rodbine podane osebe, nato pa vanj doda slovarje, ki jih prispevajo otroci. Zgoraj sestavljamo množice z operatorjem za unijo (|=), za slovarje pa uporabimo update, kot je svetoval namig ob nalogi.
Vse lepo in prav, vendar nas malo boli, da funkcija velikost_rodbine pokliče velikosti rodbin vseh otrok in jih sestavi v velikost rodbine te osebe. Ko kasneje pokličemo velikosti_rodbin za vsakega otroka, ta zase kliče velikost_rodbine. Zgodba se ponavlja v globino. Vnuke kličemo po trikrat - enkrat zaradi osebe, enkrat zaradi otroka, enkrat zaradi vnuka samega. Šele v tretjem letniku boste (upam!) znali izračunati, kako grozno je to, kar počnemo.
Obrnimo v drugo smer: najprej sestavimo prazen slovar in mu dodajmo slovarje, ki jih vrnejo otroci
def velikosti_rodbin(oseba):
velikosti = {}
for otrok in otroci[oseba]:
velikosti.update(velikosti_rodbin(otrok))
velikosti[oseba] = ???
return velikosti
Kaj pa bomo dali namesto vprašajev? Kako izvedeti, kako velika je rodbina osebe? Preprosto! V slovarju velikosti imamo za vsakega iz rodbine osebe oseba zapisano velikost njegove rodbine, drži? Potem je velikost rodbine osebe enaka dolžini tega slovarja - pa še ena zraven, za to osebo samo!
def velikosti_rodbin(oseba):
velikosti = {}
for otrok in otroci[oseba]:
velikosti.update(velikosti_rodbin(otrok))
velikosti[oseba] = len(velikosti) + 1
return velikosti