Naloga

V nalogi se ukvarjamo z isto rodbino kot na predavanjih. V pomoč naj vam bo rodbinsko drevo.

Ogrevalna naloga

Napiši funkcijo preveri_otroke(oseba), ki preveri, ali so vsi otroci podane osebe mlajši od te osebe. Če bi bil, recimo, Adam star 89, mora klic preveri_otroke("Adam") vrniti False, saj bi bil v tem primeru Adam mlajši od Matjaža.

Funkcije ni potrebno programirati rekurzivno. ("Ni potrebno" = "Ni tudi nobene potrebe po tem, da bi jo")

Obvezna naloga

Napiši funkcijo preveri_rodbino, ki preveri, ali so vse osebe v rodbini podane osebe mlajši od svojih staršev. Če bi bil, recimo, Jurij star 25, mora preveri_rodbino("Daniel") vrniti False, ker je eden od njegovih potomcev (Jurij) mlajši od enega od svojih otrok (pravzaprav od obeh). Kljub temu pa mora, recimo, preveri_rodbino("Matjaž") vrniti False, saj je v Matjaževi rodbini vse v redu.

Dodatna naloga

Napiši funkcijo skupni_prednik(oseba, potomec1, potomec2), ki vrne najmlajšega skupnega prednika oseb potomec1 in potomec2. (Argument oseba potrebujemo, da imamo kje začeti; boste videli, ko boste programirali...)

Tako mora skupni_prednik("Adam", "Franc", "Margareta") vrniti "Elizabeta", saj je Elizabeta najmlajši skupni prednik Franca in Margarete. skupni_prednik("Adam", "Tadeja", "Hans") mora vrniti "Adam". skupni_prednik("Daniel", "Herman", "Margareta") mora vrniti "Herman".

Da ne zapletemo bolj, kot je potrebno, predpostavimo, da bo skupni prednik vedno obstajal. Lahko pa programirate tako, da boste popazili tudi na ta primer.

Dodatno nalogo je mogoče rešiti na več načinov. Bodite ustvarjalni. :)

Rešitev

Preverjanje otrok

Standardni vzorec: gremo prek vseh otrok in ko zalotimo koga, ki je prestar, vrnemo False. Če ga ne, je vse v redu in vrnemo True.

def preveri_otroke(oseba): for otrok in otroci[oseba]: if starost[otrok] > starost[oseba]: return False return True

Nekoč se bomo učili o generatorjih in izvedeli, da gre za vzorec, ki mu pravimo all. Takrat bomo znali nalogo rešiti preprosteje.

def preveri_otroke(oseba): return all(starost[otrok] < starost[oseba] for otrok in otroci[oseba])

Nekateri ste to pravzprav že uporabljali. Pohvalno. (Če je kdo dobil takšno rešitev od kolega ali kolegice, pa je to seveda manj pohvalno in bo postalo problem.)

Preverjanje rodbine

Najprej preverimo direktne otroke - s funkcijo, ki smo jo napisali prejle. Nato vsakemu otroku naročimo, naj preveri svojo rodbino. Če gre pri enem ali drugem kaj narobe, vrnemo False. Če je šlo obakrat vse prav in nikoli ne vrnemo False, vrnemo True.

def preveri_rodbino(oseba): if not preveri_otroke(oseba): return False for otrok in otroci[oseba]: if not preveri_rodbino(otrok): return False return True

Vzorec je torej podoben kot prej, spet imamo "all", le da pogoj pač slučajno vključuje rekurzivni klic.

Tako kot prej, gre tudi zdaj hitreje: vse je v redu, če uspe preverjanje otrok in vseh rodbin otrok. Tega sicer še ne znamo, a vseeno kar povejmo.

def preveri_rodbino(oseba): return preveri_otroke(oseba) and all(preveri_rodbino(otrok) for otrok in otroci[oseba])

Šlo bi tudi brez klica preveri_otroke.

def preveri_rodbino(oseba): for otrok in otroci[oseba]: if starost[otrok] > starost[oseba] or not preveri_rodbino(otrok): return False return True

Nekateri pridno pišete stvari kot if preveri_otroke(oseba) == False. Ne; v te namene uporabimo not. Prav tako ni potrebe, da bi dajali rezultat v ločeno spremenljivko.

a = preveri_otroke(oseba) if a == False:

To le brez potrebe zaplete in podaljša program.

Skupni prednik

Najprej definirajmo funkcijo poisci(oseba, ime), ki pove, ali je v rodbini osebe kdo z imenom ime.

def poisci(oseba, ime): if oseba == ime: return True for otrok in otroci[oseba]: if poisci(otrok, ime): return True return False

(Tule spet vidimo podoben vzorec, le da ni "all" temveč "any" - čim najdemo, vrnemo True. Če se na koncu izkaže, da nismo našli nič, vrnemo False.)

Zdaj niti ne potrebujemo več rekurzije. Načrt napada je takšen: med otroki podane osebe, bomo poiskali tistega, za katerega velja, da sta oba potomca v njegovi rodbini. Če ga najdemo, bomo rekli oseba = otrok in ponovili vajo - zdaj iščemo med otroki tega otroka.

Ko se zgodi, da takšnega otroka ni več, vrnemo osebo, do katere smo prišli. Očitno je namreč, da potomec1 in potomec2 v tem primeru pripadata rodbinam različnih otrok, torej je trenutna oseba najbližji skupni prednik.

def skupni_prednik(oseba, potomec1, potomec2): while True: for otrok in otroci[oseba]: if poisci(otrok, potomec1) and poisci(otrok, potomec2): oseba = otrok break else: break return oseba

Bodite pozorni na igro break-ov: notranji break prekine zanko for, kadar najdemo ustreznega otroka. Zunanji break je v for-ovem else, torej se izvede, če nismo našli primernega otroka. Ta break je v zanki while, torej prekinja while.

Ta program ni prav učinkovit, saj zahteva precej iskanja po drevesu. Boljše je takole: za vsakega od dveh potomcev najdemo pot od osebe do njega - poiščemo torej seznam, ki vsebuje vsa imena prednikov od osebe do potomca.

Druga funkcija, zadnji_enak dobi dva seznama. Predpostavimo, da je prvih nekaj elementov v seznamu enakih, potem se lahko začneta razlikovati. Lahko sta celo različno dolga. Funkcija naj vrne zadnji še enaki element. Funkcijo je mogoče narediti na različne načine. Tule se bomo znašli tako, da bomo oba seznama zazipali skupaj (če sta različno dolga, bo zip odrezal rep), ga obrnili naokrog - tako da se bomo po njem v bistvu sprehajali z desne proti levi in ne z leve proti desni, ter vrnili prvi enaki element.

Funkcija skupni_prednik zdaj sestavi obe poti in poišče zadnji skupni element.

def pot_do(oseba, potomec): if oseba == potomec: return [oseba] for otrok in otroci[oseba]: pot = pot_do(otrok, potomec) if pot: return [oseba] + pot def zadnji_enak(s, t): for e, f in reversed(list(zip(s, t))): if e == f: return e def skupni_prednik(oseba, potomec1, potomec2): return zadnji_enak(pot_do(oseba, potomec1), pot_do(oseba, potomec2))
Zadnja sprememba: sreda, 15 april 2015, 10:43