Rekurzivne okužbe
Pri reševanju te naloge ti bo v izrazito pomoč ena od nalog z vaj. Če jih ali jo boš izpustil, si si sam(a) kriv(a). :)
V tej nalogi se bomo učili pisati preproste rekurzivne funkcije. Vse te stvari bi seveda znali brez težav sprogramirati nerekurzivno in v praksi bi tako tudi počeli. Tu pa vadimo rekurzijo.
V teh funkcijah torej ne boste pisali nobenih zank (for, while), pa tudi Pythonovih funkcij ne boste klicali.
Obvezna naloga
Napiši rekurzivno funkcijo koliko_cesa(x, s), ki prejme nek seznam aktivnosti s in neko aktivnost x. Funkcija vrne število pojavitev te aktivnosti v seznamu. Tako klic koliko_cesa("kava", ["kava", "kava", "telovadba", "zdravnik", "kava", "zdravnik"]) vrne 3.
To uspevši napiši še zelo podobno rekurzivno funkcijo koliko_aktivnosti(kje, obiski), ki prejme aktivnost kje (npr. "kava") in seznam, kakršnega smo že vajeni, na primer [("Ana", "kava"), ("Berta", "kava"), ("Ana", "telovadba"), ("Cilka", "zdravnik"), ("Cilka", "kava"), ("Dani", "zdravnik")], rezultat pa pove, kolikokrat se dotična aktivnost pojavi v seznamu. V gornjem primeru 3, ker imamo tri pitja kave. Če ista oseba pije kavo večkrat, to tudi štejemo večkrat.
Rešitev
Stvar se konča, ko je seznam prazen: takrat vrnemo 0.
if s == []:
return 0
Sicer pa je prva aktivnost tista, ki jo preštevamo (s[0] == x), ali pa ni tista, ki jo preštevamo. Če je, je vseh pojavitev te aktivnosti 1 + toliko, kolikor se je pojavi v ostanku seznama. Če ni, pa je je toliko, kolikor se je pojavi v preostanku seznama.
def koliko_cesa(x, s):
if s == []:
return 0
if s[0] == x:
return 1 + koliko_cesa(x, s[1:])
else:
return koliko_cesa(x, s[1:])
Druga funkcija je enaka, le da v seznamu ni le aktivnosti, temveč imamo pare; aktivnost je drugi element para. Namesto s[0] imamo torej s[0][1].
def koliko_aktivnosti(kaj, s):
if s == []:
return 0
if s[0][1] == kaj:
return 1 + koliko_aktivnosti(kaj, s[1:])
else:
return koliko_aktivnosti(kaj, s[1:])
Dodatna naloga
Napiši podobno rekurzivno funkcijo okuzena(oseba, skupine, okuzene), ki prejme ime osebe, skupine, ki so se družile in množico okuženih oseb. Funkcija vrne True, če se oseba pojavi v skupini, v kateri je tudi katera od oseb, ki je okužena. Poleg tega vrne True tudi, če je oseba tako ali tako okužena (pa četudi se morda sploh ne pojavlja v nobeni skupini). Tu gledamo le neposredne okužbe, ne pa okužb prek tretje osebe.
Klic
okuzena(
"Ana",
[{"Berta", "Ema", "Ana"}, {"Ema", "Fanči"}, {"Ana", "Greta", "Iva"}],
{"Helga", "Greta"})
vrne True, ker se je Ana družila z Greto, ki je (skupaj s Helgo) okužena.
Rešitev
Če je oseba okužena, je stvar preprosta: vrnemo True.
Če je seznam skupin prazen, je stvar preprosta: vrnemo False.
Sicer pa, če je oseba v prvi skupini in je v tej skupini tudi kdo, ki je okužen, je stvar preprosta: vrnemo True. (Prvi pogoj je potemtakem videti odveč: če je oseba v skupini in je ta oseba okužena, bomo itak vrnili True. Vendar ne: prvi pogoj je potreben za primer, ko je nekdo okužen, ne da bi se družil s kako osebo. Morda se je družil z netopirji.)
Sicer pa je stvar še preprostejša: preverimo, ali je dotična oseba okužena zaradi katere od preostalih skupin.
def okuzena(oseba, skupine, okuzeni):
if oseba in okuzeni:
return True
if not skupine:
return False
if oseba in skupine[0] and skupine[0] & okuzeni:
return True
else:
return okuzena(oseba, skupine[1:], okuzeni)
Še malo stilskega izziva
Vse rekurzivne funkcije preobrni tako, da bodo zahtevale le eno vrstico, se pravi, le return. Seveda morajo ostati rekurzivne. To v resnici ni posebej težko.
Prva funkcija bo dolga cca 60 znakov, druga dobrih 80, tretja pa se je vsaj meni zavlekla na 130. Pri tem so imena argumentov takšna kot v zgornjih navodilih.
Rešitev
def koliko_cesa(x, s):
return s != [] and (s[0] == x) + koliko_cesa(x, s[1:])
def koliko_aktivnosti(kje, obiski):
return obiski != [] and (obiski[0][1] == kje) + koliko_aktivnosti(kje, obiski[1:])
def okuzena(oseba, skupine, okuzeni):
return oseba in okuzeni or skupine and (oseba in skupine[0] and skupine[0] & okuzeni or okuzena(oseba, skupine[1:], okuzeni))