Novakovi starši

Testi

Testi: testi-novakovi-starsi.py

Ogrevalna naloga

Napiši funkcijo starost_starsa(oseba), ki vrne starost podane osebe, ko je imela prvega otroka. Ta funkcija najbrž ne bo rekurzivna (lahko pa je, če želiš). Če oseba nima otrok, naj funkcija vrne 999.

Nato napiši funkcijo najmlajsi_stars(oseba), ki vrne najnižjo starost, pri kateri je imel kdo iz rodbine podane osebe otroka. Klic najmlajsi_stars("Daniel") mora vrniti 17, saj je imela Elizabeta prvega otroka že pri sedemnajstih (in nihče ni imel otroka še mlajši). Prav tako in iz istega vzroka mora tudi najmlajsi_stars("Elizabeta") vrniti 17. Klic najmlajsi_stars("Jurij") vrne 19 (zaradi Jurija). Klic najmlajsi_stars("Barbara") vrne 999, ker nihče v Barbarini rodbini ni imel otrok (z drugimi besedami, Barbara nima otrok).

Ta, druga funkcija mora biti rekurzivna.

V rodbini se je pojavil tudi Kajn, kot Adamov oče. Opravičujem se za to historično netočnost, ki pa je potrebne za zaznavanje določene možne napake (ki sem jo naredil tudi sam in je kmalu ne bi opazil, ker ... za opažanje te napake potrebujemo še Adamovega prednika).

(Opomba: beseda starš se mi zdi grozna. Vendar je roditelj, ki se je uporabljala pred njo, še neumnejša, saj ne gibanja proti spolni diskriminaciji ne najsodobnejša medicina še niso proizvedla nobenega "roditelja".)

Rešitev

Če nekdo nima otrok, funkcija vrne 999. Sicer mora vrniti starost osebe, od katere odšteje starost najstarejšega otroka.

def starost_starsa(oseba):
    if not otroci(oseba):
        return 999
    else:
        return starost[oseba] - max(starost[otrok] for otrok in otroci(oseba))

Druga funkcija je tipična rekurzivna funkcija, kakršne smo delali na predavanjih. Najprej predpostavimo, da je najnižja starost kar ta, ki jo dobimo pri tej osebi. Potem (rekurzivno) povprašamo pri otrokih in shranimo morebitne nižje starosti.

def najmlajsi_stars(oseba):
    m = starost_starsa(oseba)
    for otrok in otroci(oseba):
        ss = najmlajsi_stars(otrok)
        if ss < m:
            m = ss
    return m

Obvezna naloga

Napiši rekurzivno funkcijo starsi_pred(oseba, n), ki vrne množico imen vseh oseb iz rodbine oseba, ki so imele otroka, še preden so bile stare n.

Če ti bo lažje, lahko najprej napišeš funkcijo starsi_pred_20(oseba), ki vrne množico imen vseh oseb, ki so imele otroka, preden so bile stare 20. (Za to funkcijo ni testov. To je samo za prvi korak.)

Rešitev

Tole je zelo podobno kot preštevanje rodbine. Tisto je izgledalo tako:

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

Tule bomo imeli namesto števila članov rodbine njihova imena. Če bi hoteli nabrati vso rodbino, bi rekli

def starsi_pred(oseba, n):  # Tole še ni prava rešitev!
    s = {oseba}
    for otrok in otroci(oseba):
        s |= starsi_pred(otrok, n)
    return s

Oseba najprej da v množico sebe, potem "priunija" vse, kar vrnejo otroci.

Vendar tako dobimo celotno rodbino, ne le tistih, ki so imeli otroka, ko so bili mlajši od n. Vse, kar moramo spremeniti, je, da oseba da v množico sebe le, če je imela otroka dovolj mlada. Recimo tako:

def starsi_pred(oseba, n):  # Tole še ni prava rešitev!
    if starost_starsa(oseba) < n:
        s = {oseba}
    else:
        s = set()
    for otrok in otroci(oseba):
        s |= starsi_pred(otrok, n)
    return s

Ali, malo drugače obrnjeno:

def starsi_pred(oseba, n):  # Tole še ni prava rešitev!
    s = set()
    if starost_starsa(oseba) < n:
        s.add(oseba)
    for otrok in otroci(oseba):
        s |= starsi_pred(otrok, n)
    return s

Pogosto napačno razmišljanje

Tole je precej pogosta napačna rešitev (ali vsaj napačen korak, ki ne vodi k rešitvi).

def starsi_pred(oseba,n):
    s = set()
    if starost_starsa(oseba) < n:
         s.add(oseba)
    for otrok in rodbina[oseba]:
         starsi_pred(otrok,n)
    return mnozica

Čeprav je tole skoraj enako pravilni rešitvi, je čisto drugače v tem smislu, da ta, ki razmišlja tako, najbrž razmišlja precej narobe. Napaka je v tem, da si predstavljamo, da bodo vsi klici funkcije starsi_pred dodajali v isto množico. Ne, ob vsakem klicu funkcije imamo nove lokalne spremenljivke. Vsaka funkcija ima svojo množico s.

Da je nekaj narobe, vidimo tudi po tem, da znotraj funkcije kličemo starsi_pred, vendar rezultata nikamor ne shranjujemo - kar zavržemo ga.

Kot vidimo, je sprememba, ki jo moramo narediti preprosta - tisto, kar vrača funkcija, moramo dodajati v množico.

Dodatna naloga

Funkcija najmlajsi_starsa ima nekoliko zavajajoče ime, saj vrne starost, ne pa imena oseba.

Napiši funkcijo ime_najml_starsa(oseba), ki vrne ime osebe, ki je imela najmlajša otroke. Klic ime_najml_starsa("Danijel") mora vrniti "Elizabeta". Če je takih oseb več, naj vrne ime prve po abecedi. Če ni nobene, naj vrne None.

Namig: ta funkcija morda ne bo rekurzivna. Pač pa napiši rekurzivno funkcijo, ki vrne par (starost, ime). Funkcija ime_najm_starsa(oseba) naj potem pokliče to funkcijo.

Rešitev

Težava je v tem, da mora funkcija vračati ime, primerjati pa mora števila. To najlažje rešimo tako, da napišemo funkcijo, ki vrača oboje.

def ime_najml_starsa0(oseba):
    jaz = (starost_starsa(oseba), oseba)
    potomec = min((ime_najml_starsa0(otrok) for otrok in otroci(oseba)),
                   default=(99, None))
    return min(jaz, potomec)

jaz so podatki o osebi, potomec pa o tistem članu rodbine, ki je imel najmlajši otroka. Vzamemo manjšo od teh.

Tisti default=(99, None) priskrbi vrednost, ki jo min vrne, kadar je seznam otrok prazen.

Vem, znotraj min uporabljam generatorje in tudi default je nov trik. Vendar gre tudi brez tega; sploh pa je to že dodatna naloga. :)

Nato le pokličemo to funkcijo in vrnemo prvi element.

def ime_najml_starsa(oseba):
    return ime_najml_starsa0(oseba)[1]

Zelo dodatna naloga

Na predavanjih smo napisali tole funkcijo, za katero ne vemo, kaj dela.

def kaj_dela(oseba):
    velikost = 0
    for otrok in otroci(oseba):
        velikost += kaj_dela(otrok)
    return abs(velikost - 1)

Ugotovi, kaj dela; rezultat svojega razmišljanja lahko napišeš kot komentar pod ostale funkcije.

Rešitev

Pojma nimam. Morda nič takšnega, kar bi se dalo pametno opisati. :)