From 236001ec7563804f87a40c924681461bc8b2d764 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Martin=20Mo=C5=BEina?= Date: Mon, 5 Dec 2016 11:51:58 +0100 Subject: Added a new set of exercises (regular expressions). --- python/problems/recursion/recursion_sl.html | 407 ++++++++++++++++++++++++++++ 1 file changed, 407 insertions(+) create mode 100644 python/problems/recursion/recursion_sl.html (limited to 'python/problems/recursion') diff --git a/python/problems/recursion/recursion_sl.html b/python/problems/recursion/recursion_sl.html new file mode 100644 index 0000000..340055e --- /dev/null +++ b/python/problems/recursion/recursion_sl.html @@ -0,0 +1,407 @@ + + + + + + + + + + +

Rekurzija na primeru družinskega drevesa

+ +

Najstarejši član rodbine Novakovih, Adam, 111 let, ima štiri otroke: Matjaža, +Cilko, Danieka in Erika. Matjaž ima enega, namreč Viljema. Danijel ima +Elizabeto in Hansa (kasneje se je namreč preselil v predmestje Graza, kjer ima +manjše podjetje), Cilka in Erik pa nimata otrok. In tako naprej. Vse skupaj je +nabrano v spodnjem slovarju.

+
+otroci = {
+	"Adam":	["Matjaž", "Cilka", "Daniel", "Erik"],
+	"Aleksander": [],
+	"Alenka": [],
+	"Barbara": [],
+	"Cilka": [],
+	"Daniel": ["Elizabeta", "Hans"],
+	"Erik": [],
+	"Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"],
+	"Franc": [],
+	"Herman": ["Margareta"],
+	"Hans": [],
+	"Jožef": ["Alenka", "Aleksander", "Petra"],
+	"Jurij": ["Franc", "Jožef"],
+	"Ludvik": [],
+	"Margareta": [],
+	"Matjaž": ["Viljem"],
+	"Mihael": [],
+	"Petra": [],
+	"Tadeja": [],
+	"Viljem": ["Tadeja"],
+}
+
+ +

Znane so tudi starosti vseh teh ljudi.

+
+starost = {
+	"Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83,
+	"Viljem": 58, "Tadeja": 20, "Elizabeta": 68, "Hans": 64, "Ludvik": 50,
+	"Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30,
+	"Jožef": 29, "Margareta": 3, "Alenka": 9, "Aleksander": 5, "Petra": 7}
+
+ +

Napišimo, takole, za preprosto vajo, funkcijo, ki ji podamo osebo in pove, +koliko otrok ima.

+
+def stevilo_otrok(oseba):
+	return len(otroci[oseba])
+
+ +

Če pokličemo, recimo, `stevilo_otrok("Adam")`, dobimo 4.

+ +

Kako pa bi izvemo število vnukov posamezne osebe? Tako da gremo prek vseh + otrok in seštevamo število njihovih otrok, recimo z

+
+def stevilo_vnukov(oseba):
+	v = 0
+	for otrok in otroci[oseba]:
+		v += len(otroci[otrok])
+	return v
+
+ +

ali, brez velike razlike,

+
+def stevilo_vnukov(oseba):
+	v = 0
+	for otrok in otroci[oseba]:
+		v += stevilo_otrok(otrok)
+	return v
+
+ +

Uh, kaj kompliciramo, saj že znamo

+
+def stevilo_vnukov(oseba):
+	return sum(stevilo_otrok(otrok) for otrok in otroci[oseba])
+
+ +

Velikost rodbine

+ +

Do sem - nič posebnega. Zdaj pa pridejo zanimive reči: za nekoga nas zanima, +velika je njegova rodbina, skupaj z njim, njegovimi otroki, vnuki, pravnuki +in tako naprej. Recimo, da ima rojstni dan in bo povabil vso svojo rodbino +na večerjo. Koliko krožnikov za juho potrebuje.

+ +

Kaj mu je storiti? Vse svoje otroke, bo vprašal, kako velike so njihove +rodbine. To bo seštel in prištel še sebe. Kako bodo ti otroci izvedeli velikosti +svojih rodbin? Tako, da bodo vprašali vse svoje otroke po velikosti njihovih +rodbin, to sešteli in prišteli še sebe. Pa njihovi otroci? Enako.

+ +

Spremenimo to v funkcijo. Velikost rodbine dobimo tako, da gremo prek otrok +in seštevamo velikosti njihovih rodbin.

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

Za tiste, ki so se dobro naučili prejšnjo snov:

+
+def velikost_rodbine(oseba):
+	return sum(velikost_rodbine(otrok) for otrok in otroci[oseba]) + 1
+
+ +

Poišči osebo

+ +

Potem nas je zanimalo, kako odkriti, ali je v rodbini določene osebe oseba +s takšnim in takšnim imenom. Storiti nam je tole: če je tako ime ravno vprašani +osebi, bo odgovorila True. Sicer bo enega za drugim spraševala +otroke, dokler prvi ne odgovori True; tedaj vrnemo +True. Če noben otrok nima takšnega potomca - in torej noben otrok +ne odgovori True, odgovorimo False. Z drugimi + besedami,

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

S snovjo izpred dveh tednov:

+
+def obstaja_ime(oseba, ime):
+	return oseba == ime or any(obstaja_ime(otrok, ime) for otrok in otroci[oseba])
+
+ +

Največja družina

+ +

Kako velika je največja družina v rodbini neke osebe - s temi mislimo le +otroke, brez staršev? Tu osebe razmišljajo tako: najprej predpostavijo, da je to +njihova družina - največ otrok je torej toliko otrok, kolikor jih imajo oni. +Potem vprašajo vsakega od otrok, kako velika je največja družina v njegovi +rodbini. Če naleti na koga z večjo družino, si to zapomni. Na koncu vrne največ, +kar je videl.

+
+def najvec_otrok(oseba):
+	najvec = len(otroci[oseba])
+	for otrok in otroci[oseba]:
+		koliko = najvec_otrok(otrok)
+		if  koliko > najvec:
+			najvec = koliko
+	return najvec
+
+ +

Kdor zna, zna takole:

+
+def najvec_otrok(oseba):
+	return max([len(otroci[oseba])] + [najvec_otrok(otrok) for otrok in otroci[oseba]])
+
+ + +

Študenti pogosto zagrešijo tole precej napačno rešitev:

+
+def najvec_otrok(oseba):
+	najvec = len(otroci[oseba])
+	for otrok in otroci[oseba]:
+		if najvec_otrok(otrok) > najvec:
+			najvec = najvec_otrok(otrok)
+	return najvec
+
+ +

Tu vsaka oseba večkrat vpraša svoje otroke, kako velike so največje družine. +Vsaj tistega z največjo družino vpraša dvakrat. Doslej smo takšno programiranje +tolerirali (in le občasno postokali, da to ni najlepše). Tu ga ne moremo več. +Vsak od teh, ki so bili po nepotrebnem vprašani dvakrat, spet dvakrat vpraša +svoje otroke vpraša po dvakrat, torej se v bistvu vprašajo po štirikrat. Oni +spodaj so vprašani že po osemkrat. Pri tako majhnih drevesih to ni tako hudo. +Pri velikih pa si tega ne bi mogli privoščiti.

+ + +

Najdaljše ime v rodbini

+ +

Katero je najdaljše ime v rodbini neke osebe? Tole je precej podobno +največjemu številu otrok: najdaljše je moje, razen če je daljše katero od imen +v rodbini katerega od otrok.

+
+def najdaljse_ime(oseba):
+	najdaljse = oseba
+	for otrok in otroci[oseba]:
+		naj_pod = najdaljse_ime(otrok)
+		if len(naj_pod) > len(najdaljse):
+			najdaljse = naj_pod
+	return najdaljse
+
+ +

Globina rodbine

+ +

Kako globoka je rodbina določene osebe? Torej, nekdo, ki nima otrok, ima +rodbino globinee 1. Če ima otroke, nima pa vnukov, ima rodbino globine +2. Če ima tudi kakega vnuka, vendar nobenega pravnuka, ima rodbino globine 3.

+ +

Globino rodbine izračunamo tako, da vprašamo vse otroke po globinah njihovih +rodbin in k največji globini, ki jo dobimo, prištejemo 1.

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

Ali, krajše

+
+def globina(oseba):
+	return max(globina(otrok) for otrok in otroci[oseba]) + 1
+
+ +

Velikost potomstva

+ +

Pripadnike Novakove rodbine smo nato spraševali, koliko potomstva imajo. S +potomci mislimo nekaj takšnega kot rodbino, a brez te osebe same. Jurij +(ki ima dva otroka in tri vnuke) ima pet potomcev).

+ +

Tale zahteva malo razmisleka. Navidez bi jo lahko ugnali tako, kot smo +velikost rodbine, le 1 ne smemo prišteti na koncu, saj oseba ne sme šteti +sebe.

+
+def velikost_rodbine(oseba):
+	v = 0
+	for otrok in otroci[oseba]:
+		v += velikost_rodbine(otrok)
+	return v
+
+ +

Zoprna reč je, da je ta funkcija nekoliko napačna. No, precej napačna. +Vedno vrne 0 - ker nihče nikoli ničesar ne prišteje, vse seštevajo samo ničle. +In iz ničel nikoli ne boš dobil ničesar, pa jih seštevaj, kolikor dolgo hočeš.

+ + +

Ena rešitev je, da vsak vrne število svojih otrok, ki čemur morajo otroci +prišteti število svojih otrok, in vnuki število svojih...

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

Ali isto, le na drug način:

+
+def stevilo_potomcev(oseba):
+	potomcev = 0
+	for otrok in otroci[oseba]:
+		potomcev += 1 + stevilo_potomcev(otrok)
+	return potomcev
+
+ +

Lahko pa si pomagamo tudi z rodbino:

+
+def stevilo_potomcev(oseba):
+	return velikost_rodbine(oseba) - 1
+
+ +

Rekurzivne funkcije na seznamih

+ +

Palindrom

+ +

Niz je palindrom, če se naprej in nazaj bere enako.

+ +

Pisati funkcijo, ki pove, ali je podani niz palindrom, je sicer železni +repertoar pouka programiranja - v Pythonu pa je nekoliko trivialen. Če imamo +niz s, bomo z s[1:-1] dobili obrnjen niz, niz +"prebran" nazaj. Če sta tadva enaka, je funkcija palindrom.

+ +

Ker vem, da ste pametni ljudje, ne boste pisali

+ +
def palindrom(s):
+    if s == s[::-1]:
+        return True
+    else:
+        return False
+ +

temveč, kratko in jedrnato

+ +
def palindrom(s):
+    return s == s[::-1]
+ +

Zdaj pa recimo, da za tole obračanje nizov ne vemo (ali pa, da programiramo +v jeziku, ki česa takšnega nima. V tem primeru potrebujemo zanko: rekli bomo, +da je s palindrom, če je ničti znak enak zadnjemu, prvi +predzadnjemu in tako naprej do konca. Po vzorcu, ki nam je že čisto domač, +bomo ob prvem neujemanju zatulili Falsch!; če pridemo do konca +brez težav, vrnemo True.

+ +
def palindrom(s):
+    for i in range(len(s)):
+        if s[i] != s[-i - 1]:
+            return False
+    return True
+ +

(Pravzaprav ni potrebno, da gremo "tako naprej do konca", saj bi zadoščalo +"tako naprej do sredine". A to tule ni pomembno.)

+ +

Palindrome lahko definiramo na drug način, ki ne zahteva štetja: rečemo +lahko, da je s palindrom, če je ničti znak enak zadnjemu in je +palindrom tudi vse med njima. Poskrbeti je le potrebno za nize, ki nimajo +dveh znakov: če je niz krajši od dveh znakov, bomo rekli, da je palindrom.

+ +

Z enim stavkom: s je palindrom, če je krajši od dveh znakov ALI +pa je ničti znak enak zadnjemu IN so vsi znaki od prvega do predzadnjega +palindrom.

+ +
def palindrom(s):
+    return len(s) < 2 or s[0] == s[-1] and palindrom(s[1:-1])
+ +

Študente tole pogosto zbega. Funkcija palindrom je definirana +s funkcijo palindrom. Sama s sabo. Je to sploh dovoljeno? Deluje? +

+ +

Razlog, da deluje, je v tem, da je niz vedno krajši. Ko se vprašamo, ali je +"abcdcba" palindrom, funkcija ugotovi, da to sicer ni manj kot dva znaka, +vendar je palindrom, če je ničti znak enak zadnjemu (kar je) in če je "bcdcb" +palindrom. Ko preverja, ali je "bcdcb" palindrom, ugotovi, da je daljši od dveh +znakov, zato bo palindrom, če je ničti enak zadnjemu (kar je) in če je "cdc" +palindrom. Ta je daljši od dveh znakov, zato bo palindrom, če je ničti znak +enak zadnjemu in je "d" palindrom. Niz "d" je krajši od dveh znakov, torej je +palindrom. Zato je torej tudi "cdc" palindrom. Zato je "bcdcb" palindrom. +Zato je "abcdcba" palindrom.

+ +

Vsota elementov seznama

+ +

Kako bi izračunali vsoto elementov seznama. Z zanko seveda znamo. Pa +poskusimo še s trikom, kakršnega smo uporabili zgoraj. Za to potrebujemo +rekurzivno definicijo vsote seznama - definicijo, ki se nanaša sama nase.

+ +

Takole lahko rečemo: vsoto elementov seznama dobimo tako, da k prvemu +elementu prištejemo vsoto ostalih. Če je seznam prazen, pa je vsota 0.

+ +
def vsota(s):
+    if not s:
+        return 0
+    return s[0] + vsota(s[1:])
+ +

Ima seznam sama soda števila

+ +

Seznam ima sama soda števila, če je prazen ali pa je prvi element sod in +ima preostanek sama soda števila.

+ +
def soda(s):
+    return not s or s[0] % 2 == 0 and soda(s[1:])
+ +

Vsota sodih števil v seznamu

+ +

Napisati želimo funkcijo, ki vrne vsoto vseh sodih elementov v podanem +seznamu.

+ +

Če je seznam prazen, je vsota enaka 0. Sicer pa naredimo tole: če je ničti +element sod, vrnemo vsoto ničtega elementa in vsote ostalih. Če ni sod, vrnemo +le vsoto ostalih.

+ +
def vsota_sodih(s):
+    if not s:
+        return 0
+    if s[0] % 2 == 0:
+        return s[0] + vsota_sodih(s[1:])
+    else:
+        return vsota_sodih(s[1:])
+ +

Prvi sodi element seznama

+ +

Napisali bomo funkcijo, ki vrne prvi sodi element.

+ +

Če je ničti element sod, vrnemo tega. Sicer vrnemo prvega sodega med +ostalimi.

+ +
def prvi_sodi(s):
+    if s[0] % 2 == 0:
+        return s[0]
+    else:
+        return prvi_sodi(s[1:])
+ +

Funkcija ima manjšo težavo, kadar v +seznamu ni nobenega sodega elementa. Ker prvi ni sod, išče sodega v preostanku. +Ker prvi iz preostanka ni sod, išče sodega v preostanku. Ker prvi v tem +preostanku ni sod ... in tako naprej, dokler ne pride do praznega seznama. +Takrat bomo v prvi vrstici funkcije spraševali po prvem (no, ničtem) elementu, +s[0] in Python bo javil napako, Index out of range. +

+ +

Recimo, da bo funkcija v takšnem primeru vrnila None.

+ +
def prvi_sodi(s):
+    if not s:
+        return None
+    if s[0] % 2 == 0:
+        return s[0]
+    else:
+        return prvi_sodi(s[1:])
+ + + + -- cgit v1.2.1