Adamovo potomstvo

Naloga se nanaša na rodbino Novakovih, s katero smo se ukvarjali zadnjo uro predavanj.

Slovar z rodovnikom in funkcija otroci(oseba) (ki sicer niti ni nujno potrebna) so priloženi testom.

Ogrevalna naloga

Če oseba nima otrok, rečemo, da je globina njene rodbine 1. Če ima otroke, nima pa vnukov, je globina njene rodbine 2. Če ima vnuke, nima pa pravnukov, 3. In tako naprej.

Napiši funkcijo globina(oseba), ki vrne globino rodbine podane osebe.

Rešitev

Kot pri ostalih rodbinskih nalogah tudi tu pomislimo, kako preložiti delo na otroke. Torej: vsakega otroka vprašamo o globini njegove rodbine. Zapomnimo si najglobjo in prištejemo 1.

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

ali pa kar

def globina(oseba):
    naj_g = 0
    for otrok in otroci(oseba):
        naj_g = max(globina(otrok), naj_g)
    return naj_g + 1

Tole deluje tudi, če oseba nima potomcev. V tem primeru bo g ostal 0 in g+1 bo enak 1.

Če znamo malo več, lahko napišemo kar

def globina(oseba):
    return 1 + max((globina(otrok) for otrok in otroci(oseba)), default=0)

Zdaj pa zelo napačna rešitev:

def globina(oseba):
    naj_g = 0
    for otrok in otroci(oseba):
        if naj_g > globina(otrok):
            naj_g = globina(otrok)
    return naj_g + 1

Tole ni samo dvakrat počasnejše, ker pač dvakrat pokliče funkcijo globina_otrok. Vsak od otrok potem dvakrat pokliče globina_otrok za svoje otroke, torej imamo že štirikrat več klicev. Vsak vnuk to pokliče dvakrat; ker smo vnuke (brez potrebe) klicali štirikrat, imamo tako že osemkrat več klicev.

Pri drevesu globine 10 dobimo tisočkrat počasnejši program.

Obvezna naloga

Napiši funkcijo globina_imena(oseba, potomec), ki pove, kako oddaljen potomec osebe oseba je potomec. Če gre za isto osebo (globina_imena("Hans", "Hans"))) vrne 0. Če je potomec otrok osebe, (globina_imena("Elizabeta", "Barbara")) vrne 1. Če je potomec vnuk osebe, vrne 2. Če pravnuk, vrne 3...

Če v rodbini podane osebe ni tega imena, ne vrne ničesar (torej None).

Rešitev

S to nalogo ste imeli precej problemov. Najprej zato, ker ste jo poskusili reševati tako, da ste predelovali funkcijo globina. Doslej je bila ogrevalna naloga res pogosto "uvod" v pravo, tokrat pa ne. (Vsaj malo lahko prevzamem odgovornost, ker sem vas zavedel.)

Če je oseba ravno ta, ki jo iščemo, vrnemo 0.

Vsakega otroka vprašamo, kako globoko v njegovi rodbini je ta potomec. Če vrne None (kar pomeni, da te osebe sploh ni v njegovi rodbini), pač nadaljujemo z naslednjim otrokom. Če vrne kako število, vrnemo za 1 več, saj je ta potomec glede na to osebo za 1 globlje kot za otroka. Se pravi: takoj ko od kakega otroka dobimo kaj, kar ni None, že vrnemo rezultat, ne da bi spraševali naprej. Če od nobenega otroka ne dobimo nič, pa tudi funkcija ne vrne nič.

def globina_imena(oseba, ime):
    if ime == oseba:
        return 0
    for otrok in otroci(oseba):
        g = globina_imena(otrok, ime)
        if g is not None:
            return g + 1

Dodatna naloga

Na predavanjih smo napisali funkcijo, ki vrne seznam vseh oseb iz rodbine podane osebe. Za domačo nalogo boste napisali funkcijo, ki vrne množico vseh oseb od določene globine naprej. Če pokličemo globje_od_n(oseba, 0) vrne celotno rodbino. Če pokličemo globje_od_n(oseba, 1) vrne otroke, vnuke, pravnuke, prapravnuke in tako do konca. Če pokličemo globja_od_n(oseba, 2) vrne vnuke, pravnuke, prapravnuke... Če pokličemo globje_od_n(oseba, 3), začne pri pravnukih. In tako naprej.

Rešitev

Funkcija je pravzaprav popolnoma enaka funkciji, ki je vrnila vse člane rodbine. Razlika je samo v dodatnem argumentu. Če iščemo osebe na globini n, vsakemu otroku naročimo, naj vrne osebe na globini n-1. Oseba pa doda samo sebe le, če je n enak ali manjši 0.

def globje_od_n(oseba, n):
    vse = set()
    for otrok in otroci(oseba):
        vse |= globje_od_n(otrok, n - 1)
    if n <= 0:
        vse.add(oseba)
    return vse