Naloga

Ogrevalna naloga: Kolikokrat ime

Napiši funkcijo kolikokrat_ime(oseba, ime), ki pove, kolikokrat se v rodbini osebe oseba pojavi ime ime. Pri tem ime nima dodatnih oznak (številk ipd.). V rodbini Friderika I. so, recimo, trije Frideriki, dve Ani, ena Barbara in nič Francljev.

Če bi se to igrali na predavanjih, bi vsaka oseba vprašala svoje otroke, kolikokrat se to ime pojavi v njihovih rodbinah, zraven pa prištela 1, če je takšno tudi njeno ime.

Obvezna naloga: Koliko žensk

Napiši funkcijo zensk_v_rodbini(oseba), ki vrne število žensk v rodbini osebe oseba. Prepodstavi, da je oseba ženska, če se njeno ime (to je, prvi del, pred raznimi številkami in krajevnimi nadimki) konča s črko "a".

Dodatna, neobvezna naloga: Vse potomstvo določene osebe

Napiši funkcijo vse_potomstvo(oseba), ki vrne množico (set) potomcev podane osebe.

Potomci so unija množice otrok in množic potomcev otrok.

Kako se to reši, smo videli na predavanjih (le programirali nismo). Naloga v resnici res ni težka in jo priporočam tudi tistim, ki se dodatnih nalog bojite: tako boste vsaj enkrat lahko rekli, da ste jo zmogli!

Rešitev

Kolikokrat se pojavi ime

Ogrevalna in obvezna naloga sta bili praktično enaki in poleg tega sumljivo podobni eni od nalog, ki smo si jo zastavili na predavanjih, namreč tisti, ki prešteva velikost rodbine. Spomnimo se one rešitve:

def prestej_rodbino(oseba): rodbina = 1 otroci = rodovnik[oseba] for otrok in otroci: rodbina += prestej_rodbino(otrok) return rodbina

Kdor je hotel rešiti domačo nalogo, je moral le dobro razumeti, kako deluje ta funkcija. V začetku reče "v rodbini je en človek - namreč jaz". K temu prištejem še rodbine svojih otrok, tako da vsakega od njih rekurzivno vprašam, koliko otrok ima.

Če hočem prešteti, kolikokrat se v rodbini pojavi določeno ime, naredim popolnoma isto, le da vsaka oseba šteje sebe le, če ima pravo ime. Ime osebe izvemo tako, da jo z oseba.split() razdelimo na besede in potem primerjamo le prvo ime. Torej:

def kolikokrat_ime(oseba, ime): otroci = rodovnik[oseba] if oseba.split()[0] == ime: kolikokrat = 1 else: kolikokrat = 0 for otrok in otroci: kolikokrat += kolikokrat_ime(otrok, ime) return kolikokrat

Namesto rodbina imam kolikokrat in namesto prestej_rodbino imam kolikokrat_ime, pa še dodaten argument je dobila funkcija, namreč ime. Poleg tega kolikokrat včasih postavim na 0, včasih na 1. Za slednje obstaja še nekaj različic, kot sta

kolikokrat = 0 if oseba.split()[0] == ime: kolikokrat += 1

ali pa jedrnati

kolikokrat = int(oseba.split()[0] == ime)

za katerega se moramo spomniti, da sta False in True toliko kot 0 in 1, če ju pretvorimo v int.

Žensk v rodbini

Preštevanje žensk v rodbini je nesramno enaka reč: kdor je znal prešteti člane rodbine, ki imajo določeno ime, je znal prešteti tudi ženske, le tega se je moral spomniti, kako priti do zadnje črke imena.

Ponovimo, enkrat za zmeraj: do zadnje črke niza s pridemo s s[-1]. Podobno je z zadnjim elementom seznama. Nobenega len(s) ali, bognedaj, s.find ne potrebujemo.

Ostalo je natanko takšno kot prej.

def zensk_v_rodbini(oseba): otroci = rodovnik[oseba] if oseba.split()[0][-1] == "a": zensk = 1 else: zensk = 0 for otrok in otroci: zensk += zensk_v_rodbini(otrok) return zensk

V zvezi s to nalogo sem vas posvaril pred pastjo (ki je seveda nisem razkril) in v resnici ste kar prijetno padali vanjo. Past je bila v tem, da ste znotraj zanke preverjali, ali je otrok ženska in rekurzivno klicali funkcijo le v tem primeru. To je narobe: ženske se lahko nahajajo tudi v delih rodbine, za katere so odgovorni sinovi. (Še več, ker je ta rodovnik skladen s patriarhalnimi navadami srednjega veka, so ženske v njem celo brez potomcev, saj se upoštevajo le moške linije!)

Množica potomcev

Tokratna domača naloga je bila celo tako dolgočasna, da ste pravzaprav trikrat programirali eno in isto. Tretja je bila vsaj toliko drugačna, da se ne ukvarja z rodbino, temveč s potomstvom. Spomnimo se naloge s predavanj, preštevanja potomstva:

def prestej_potomce(oseba): otroci = rodovnik[oseba] potomcev = len(otroci) for otrok in otroci: potomcev += prestej_potomce(otrok) return potomcev

Spet, če razumem, kako deluje preštevanje potomstva, mi ni težko narediti naštevanja - le še z množicami moram znati delati. Preštevanje deluje tako, da najprej reče "potomcev je toliko, kolikor imam otrok", nato pa k temu prišteje potomce, o katerih poročajo (s pomočjo rekurzije) otroci. Funkcija prestej_potomce torej vrne število potomcev.

Funkcija vse_potomstvo bo vrnila množico potomcev. Torej si v začetku ne bo zapomnila števila otrok temveč množico otrok in k njej ne bo prištevala števila potomcev, ki jih imajo otroci, temveč dodajala množice potomcev, ki jih imajo otroci.

Vse ostalo je enako. (Na prvi pogled potemtakem domača naloga ni prav poučna, saj morate zanjo le znati spremeniti program, ki smo ga napisali na predavanjih? Da, res je. Vendar ga morate za to, da ga znate spremeniti, tudi razumeti. "Razumeti" še ni isto kot "znati napisati", a nič narobe, če ste dobili nekoliko lažjo nalogo. Sicer pa imam tako ali tako občutek, da je večina pisala znova, od začetka. ;).

Rešitev je torej

def vse_potomstvo(oseba): otroci = rodovnik[oseba] potomstvo = set(otroci) for otrok in otroci: potomstvo |= vse_potomstvo(otrok) return potomstvo

Mimogrede spomnimo na dvoje. Morda je kdo sprva napisal potomstvo = {otroci} in ugibal, zakaj to ne deluje. Problem je v tem, da bi tako dobili množico, katere element bi bil seznam otrok. Torej nekaj takšnega: {["Janko", "Metka"]} in ne: {"Janko", "Metka"}. Pa še to ne gre, ker seznam ne more biti element množice (spomnimo se: množica lahko vsebuje le reči, ki so nespremenljive, seznam pa je spremenljiv).

Če pokličemo funkcijo set, ji damo kot argument seznam nekih reči (ali slovar nekih reči ali niz nekih črk ali kaj podobnega) in to spremeni v množico teh reči.

Drugo, na kar vas velja opozoriti je eleganca iz predzadnje vrstice: tako kot lahko namesto x = x + a pišemo x += a (prvo bi prebral "x-u priredi vsoto x-a in a-ja", drugo pa "k x-u prištej a", zato mi je drugo jasnejše), moremo tudi namesto potomstvo = potomstvo | vse_potomstvo(otrok) ("potomstvu priredi unijo potomstva in vsega potomstva otroka") pisati potomstvo |= vse_potomstvo(otrok) ("k potomstvu 'priunijaj' potomstvo otroka").

Nekaj zanimivih napak

Spodaj je nekaj primerov iz študentskih izdelkov. Čeprav bodo "izpostavljeni", se zavedajte, da gre v glavnem za dobre izdelke, saj je v slabih težje poiskati poučne napake. Poleg tega je programiranje takšen posel, da se tudi izkušen program (če sodim po sebi in kolegih) ob kakem svojem programu prime za glavo in smeji.

Tole je že takšen nekoliko zabaven primer, ki pa se lahko - čeprav včasih v malo bolj sofisticirani obliki - zgodi vsakemu:

def kolikokrat_ime(oseba, ime): otroci = rodovnik[oseba] counter = 0 if ime in oseba.split(" ")[0]: counter += 1 if ime in otroci: #Če je ime med otroci counter += 1 for otrok in otroci: counter += kolikokrat_ime(otrok, ime) if ime == otrok: #Da se ne ponavlja otrok.. Mi je vzelo preveč časa, da sem to ugotovil :S counter -= 1 return counter

Tule se je nekdo, kot je videti iz komentarja, precej mučil, ker je otroke štel dvakrat. Problem je v tem, da najprej šteje osebo samo, potem šteje otroke, nato pa otroke sprašuje, kolikokrat se pojavi ime. Tudi otroci se štejejo kot osebe, zato so potem šteti dvakrat. Da, takšne napake je težko odkriti.

Ni pa jih tako težko popraviti. Tule sta popravek predzadnji dve vrstici. Vendar popravljata le simptom, ne pa napake (no, napako odpravljata, namesto da bi jo popravila). Ko pogledamo program od daleč (in ne z očmi nekoga, ki se je namučil, da je prišel do njega), pa hitro vidimo, da je pravzaprav zabaven: v drugem if-u prišteje, kar potem v zanki odšteje.

Veliko lažje bi bilo le pobrisati, kar je odveč:

def kolikokrat_ime(oseba, ime): otroci = rodovnik[oseba] counter = 0 if ime in oseba.split(" ")[0]: counter += 1 for otrok in otroci: counter += kolikokrat_ime(otrok, ime) return counter

Mimogrede, tisti ime in oseba.split(" ")[0] je nekoliko nevaren. Pravilno bi bilo ime == oseba.split(" ")[0], sicer bi program tudi Anamarijo štel kot Ano.

Ne počnite takšnih reči:

def zensk_v_rodbini(oseba): counter = 0 if oseba == "Katarina": #Rahlo grd način, ampak če je oseba ravno Katarina, funkcija ne deluje prav -.- return 1 otroci = rodovnik[oseba] for zenske in otroci: zenska = zenske.split()[0][-1] if zenska == "a": counter += 1 for otrok in otroci: counter += zensk_v_rodbini(otrok) if counter == 8: #Še več grdobe, nekako je treba pokompenzirat z Katarina fiaskotom, ker z tistim grdim hackom^^ 2x prešteje Katarinco counter =7 return counter

Ta program deluje samo za tale rodovnik in te teste. Raje ga popravite tako, da bo res deloval.

V naslednjem programu sta zanimivi dve stvari.

def vse_potomstvo(oseba): mnozica = set() mnozica1 =set() rodovnik = preberi("rodovnik.txt") otroci = rodovnik[oseba] for i in otroci: mnozica.add(i) mnozica1 = vse_potomstvo(i) mnozica = mnozica | mnozica1 return mnozica

mnozica1 = set() ni potrebno pisati. Tej množici ničesar ne dodajamo, temveč bomo kasneje imenu mnozica1 priredili rezultat klica funkcije vse_potomstvo. Tisto, kar ji priredimo v začetku, se nikjer ne uporabi, temveč samo povozi.

PyCharm je zelo pametna žival in to celo opazi ter vam mnozica1 v drugi vrstici funkcije pobarva s sivo, češ, te spremenljivke pa ne potrebuješ, saj z njo ne počneš ničesar.

Razlog, da vas opozarjam na to, je, da opažam, da nekateri zelo pogosto na začetku funkcije "naštejete" vse spremenljivke, ki jih boste uporabljali. Tako bi, recimo, funkcijo, ki izračuna ploščino trikotnika sprogramirali z

def p(a, b, c): s = 0 p = 0 # Izračunamo pol obseg s = (a + b + c) / 2 # Zdaj pa še ploščino p = math.sqrt(s * (s - a) * (s - b) * (s - c))

V modernem krščanstvu je veliko običajev, ki izvirajo iz poganstva, iz predkrščanskih časov. V tem programu pa je nekaj, kar izvira iz predpythonovskih časov: predpostavljam, da tole pišejo tisti, ki jih mika, da bi napisali

float s, p;

če gre za pogana C-jevskega porekla ali

var s, p: real;

če imamo opravka s pascalskim poganom. A če tako govorite s Pythonom, vas bo samo debelo gledal, res.

Tole je delček programa, v katerem bi se dalo del kode potegniti iz if-a, ker je enak ne glede na to, ali je pogoj resničen ali ne:

def kolikokrat_ime(oseba, ime): otroci=rodovnik[oseba] oseba=oseba.split()[0] st=0 if (oseba==ime): st+=1 for otrok in otroci: st+=kolikokrat_ime(otrok,ime) else: for otrok in otroci: st+=kolikokrat_ime(otrok,ime) return(st)

Veliko preprosteje bi bilo

def kolikokrat_ime(oseba, ime): otroci = rodovnik[oseba] oseba = oseba.split()[0] st = 0 if oseba == ime: st += 1 for otrok in otroci: st += kolikokrat_ime(otrok,ime) return st

Prvi program bi me kot bralca zbegal, ker bi šel preverjat, ali se zanki for v čem razlikujeta (predpostavil bi namreč, da najbrž se, sicer ne bi imel ločene zanke v if in v else).

Mimogrede: tudi oklepaji v pogojih in stavku return so poganskega porekla.

Tole je zelo lep primer tega, s čimer smo se ukvarjali na predavanjih po onih iz rekurzije:

## Ne znam inicializirat 'seznam' po končanem prvem ## testu, da bi začel program šteti na novo in ne prištevati prvemu; ## če pa dam seznam = [] v funkcijo, pa mi dolžino seznama po vsakem klicu ## inicializira (postavi na 0) def zensk_v_rodbini(oseba): ime = oseba.strip().split()[-1] otroci = rodovnik[oseba] if ime[-1] == "a": seznam.append(osebica) for otrok in otroci: zensk_v_rodbini(otrok) return len(seznam)

Avtor te rešitve je dobil točke za nedelujoč program zato, ker je dobro razmišljal o tem, kje tičijo njegove težave.

Če hočem, da funkcija, ki rekurzivno kliče samo sebe, dodaja v en in isti seznam, lahko to dosežem na dva načina: funkcije ta seznam vračajo kot rezultat ali pa si ga podajajo kot argument. Potreboval bi torej funkcijo

def zensk_v_rodbini_0(oseba, dodajaj_v_ta_seznam): ime = oseba.strip().split()[0] otroci = rodovnik[oseba] if ime[-1] == "a": dodajaj_v_ta_seznam.append(oseba) for otrok in otroci: zensk_v_rodbini_0(otrok, dodajaj_v_ta_seznam)

Izpustil sem return, ker ga v resnici ne potrebujemo. Hm, kakšna funkcija pa je potem to, če računa, a ničesar ne vrača? Vrača res ne ničesar, vendar počne nekaj drugega, dodaja v seznam.

Vendar imam zdaj funkcijo z dvema argumentoma, namreč osebo in seznamom, v katerega je potrebno dodajati. Testi pa jo pokličejo le z enim argumentom. No, zato sem ji dal ime zensk_v_rodbini_0. Zdaj moram priskrbeti še "pravo" funkcijo. Da bo pregledneje, napišimo kar obe skupaj.

def zensk_v_rodbini_0(oseba, dodajaj_v_ta_seznam): ime = oseba.strip().split()[0] otroci = rodovnik[oseba] if ime[-1] == "a": dodajaj_v_ta_seznam.append(oseba) for otrok in otroci: zensk_v_rodbini_0(otrok, dodajaj_v_ta_seznam) def zensk_v_rodbini(oseba): vse_zenske = [] zensk_v_rodbini_0(oseba, vse_zenske) return len(vse_zenske)

Spodnja funkcija sestavi seznam. Rekurzivni klici funkcije zensk_v_rodbini si bodo podajali ta (prav ta, taisti) seznam in vanj dodajali ženske. Ko opravijo svoje, so v seznamu vse ženske in funkcija zensk_v_rodbini jih le prešteje.

Tole je precej pogost način uporabe rekurzije, vendar ga na predavanjih nisem posebej kazal, saj je za začetnika morda nekoliko prezapleten. Če tole berete pred izpitom, ko je rekurzija že malo uležana, pa bi ga morali že razumeti.