diff options
Diffstat (limited to 'python/problems/recursion')
| -rw-r--r-- | python/problems/recursion/recursion_sl.html | 407 |
1 files changed, 407 insertions, 0 deletions
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 @@ +<!DOCTYPE html>
+<html lang="sl">
+<head>
+<meta charset="utf-8" />
+<title></title>
+<link rel="stylesheet" type="text/css" href="/css/codeq.css" />
+<link rel="stylesheet" type="text/css" href="../../style.css" />
+</head>
+<body>
+
+<h1>Rekurzija na primeru družinskega drevesa </h1>
+
+<p>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.</p>
+<pre>
+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"],
+}
+</pre>
+
+<p>Znane so tudi starosti vseh teh ljudi.</p>
+<pre>
+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}
+</pre>
+
+<p>Napišimo, takole, za preprosto vajo, funkcijo, ki ji podamo osebo in pove,
+koliko otrok ima.</p>
+<pre>
+def stevilo_otrok(oseba):
+ return len(otroci[oseba])
+</pre>
+
+<p>Če pokličemo, recimo, `stevilo_otrok("Adam")`, dobimo 4.</p>
+
+<p>Kako pa bi izvemo število vnukov posamezne osebe? Tako da gremo prek vseh
+ otrok in seštevamo število njihovih otrok, recimo z</p>
+<pre>
+def stevilo_vnukov(oseba):
+ v = 0
+ for otrok in otroci[oseba]:
+ v += len(otroci[otrok])
+ return v
+</pre>
+
+<p>ali, brez velike razlike,</p>
+<pre>
+def stevilo_vnukov(oseba):
+ v = 0
+ for otrok in otroci[oseba]:
+ v += stevilo_otrok(otrok)
+ return v
+</pre>
+
+<p>Uh, kaj kompliciramo, saj že znamo</p>
+<pre>
+def stevilo_vnukov(oseba):
+ return sum(stevilo_otrok(otrok) for otrok in otroci[oseba])
+</pre>
+
+<h2> Velikost rodbine </h2>
+
+<p>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. </p>
+
+<p> 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. </p>
+
+<p>Spremenimo to v funkcijo. Velikost rodbine dobimo tako, da gremo prek otrok
+in seštevamo velikosti njihovih rodbin.</p>
+<pre>
+def velikost_rodbine(oseba):
+ v = 0
+ for otrok in otroci[oseba]:
+ v += velikost_rodbine(otrok)
+ return v + 1
+</pre>
+
+<p>Za tiste, ki so se dobro naučili prejšnjo snov:</p>
+<pre>
+def velikost_rodbine(oseba):
+ return sum(velikost_rodbine(otrok) for otrok in otroci[oseba]) + 1
+</pre>
+
+<h2> Poišči osebo </h2>
+
+<p>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 <code>True</code>. Sicer bo enega za drugim spraševala
+otroke, dokler prvi ne odgovori <code>True</code>; tedaj vrnemo
+<code>True</code>. Če noben otrok nima takšnega potomca - in torej noben otrok
+ne odgovori <code>True</code>, odgovorimo <code>False</code>. Z drugimi
+ besedami,</p>
+<pre>
+def obstaja_ime(oseba, ime):
+ if oseba == ime:
+ return True
+ for otrok in otroci[oseba]:
+ if obstaja_ime(otrok, ime):
+ return True
+ return False
+</pre>
+
+<p>S snovjo izpred dveh tednov:</p>
+<pre>
+def obstaja_ime(oseba, ime):
+ return oseba == ime or any(obstaja_ime(otrok, ime) for otrok in otroci[oseba])
+</pre>
+
+<h2> Največja družina </h2>
+
+<p>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.</p>
+<pre>
+def najvec_otrok(oseba):
+ najvec = len(otroci[oseba])
+ for otrok in otroci[oseba]:
+ koliko = najvec_otrok(otrok)
+ if koliko > najvec:
+ najvec = koliko
+ return najvec
+</pre>
+
+<p>Kdor zna, zna takole:</p>
+<pre>
+def najvec_otrok(oseba):
+ return max([len(otroci[oseba])] + [najvec_otrok(otrok) for otrok in otroci[oseba]])
+</pre>
+
+
+<p>Študenti pogosto zagrešijo tole precej napačno rešitev:</p>
+<pre>
+def najvec_otrok(oseba):
+ najvec = len(otroci[oseba])
+ for otrok in otroci[oseba]:
+ if najvec_otrok(otrok) > najvec:
+ najvec = najvec_otrok(otrok)
+ return najvec
+</pre>
+
+<p>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.</p>
+
+
+<h2> Najdaljše ime v rodbini </h2>
+
+<p>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.</p>
+<pre>
+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
+</pre>
+
+<h2> Globina rodbine </h2>
+
+<p>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.</p>
+
+<p>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.</p>
+<pre>
+def globina(oseba):
+ najvecja = 0
+ for otrok in otroci[oseba]:
+ g = globina(otrok)
+ if g > najvecja:
+ najvecja = g
+ return najvecja + 1
+</pre>
+
+<p>Ali, krajše</p>
+<pre>
+def globina(oseba):
+ return max(globina(otrok) for otrok in otroci[oseba]) + 1
+</pre>
+
+<h2> Velikost potomstva </h2>
+
+<p>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).</p>
+
+<p>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.</p>
+<pre>
+def velikost_rodbine(oseba):
+ v = 0
+ for otrok in otroci[oseba]:
+ v += velikost_rodbine(otrok)
+ return v
+</pre>
+
+<p>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š. </p>
+
+
+<p>Ena rešitev je, da vsak vrne število svojih otrok, ki čemur morajo otroci
+prišteti število svojih otrok, in vnuki število svojih...</p>
+<pre>
+def stevilo_potomcev(oseba):
+ potomcev = len(otroci[otroci])
+ for otrok in otroci[oseba]:
+ potomcev += stevilo_potomcev(otrok)
+ return potomcev
+</pre>
+
+<p>Ali isto, le na drug način:</p>
+<pre>
+def stevilo_potomcev(oseba):
+ potomcev = 0
+ for otrok in otroci[oseba]:
+ potomcev += 1 + stevilo_potomcev(otrok)
+ return potomcev
+</pre>
+
+<p>Lahko pa si pomagamo tudi z rodbino:</p>
+<pre>
+def stevilo_potomcev(oseba):
+ return velikost_rodbine(oseba) - 1
+</pre>
+
+<h1> Rekurzivne funkcije na seznamih </h1>
+
+<h2>Palindrom</h2>
+
+<p>Niz je palindrom, če se naprej in nazaj bere enako.</p>
+
+<p>Pisati funkcijo, ki pove, ali je podani niz palindrom, je sicer železni
+repertoar pouka programiranja - v Pythonu pa je nekoliko trivialen. Če imamo
+niz <code>s</code>, bomo z <code>s[1:-1]</code> dobili obrnjen niz, niz
+"prebran" nazaj. Če sta tadva enaka, je funkcija palindrom.</p>
+
+<p>Ker vem, da ste pametni ljudje, ne boste pisali</p>
+
+<pre>def palindrom(s):
+ if s == s[::-1]:
+ return True
+ else:
+ return False</pre>
+
+<p>temveč, kratko in jedrnato</p>
+
+<pre>def palindrom(s):
+ return s == s[::-1]</pre>
+
+<p>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 <code>s</code> 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 <code>Falsch!</code>; če pridemo do konca
+brez težav, vrnemo <code>True</code>.</p>
+
+<pre>def palindrom(s):
+ for i in range(len(s)):
+ if s[i] != s[-i - 1]:
+ return False
+ return True</pre>
+
+<p>(Pravzaprav ni potrebno, da gremo "tako naprej do konca", saj bi zadoščalo
+"tako naprej do sredine". A to tule ni pomembno.)</p>
+
+<p>Palindrome lahko definiramo na drug način, ki ne zahteva štetja: rečemo
+lahko, da je <code>s</code> 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.</p>
+
+<p>Z enim stavkom: <code>s</code> 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.</p>
+
+<pre>def palindrom(s):
+ return len(s) < 2 or s[0] == s[-1] and palindrom(s[1:-1])</pre>
+
+<p>Študente tole pogosto zbega. Funkcija <code>palindrom</code> je definirana
+s funkcijo <code>palindrom</code>. Sama s sabo. Je to sploh dovoljeno? Deluje?
+</p>
+
+<p>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.</p>
+
+<h2>Vsota elementov seznama</h2>
+
+<p>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.</p>
+
+<p>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.</p>
+
+<pre>def vsota(s):
+ if not s:
+ return 0
+ return s[0] + vsota(s[1:])</pre>
+
+<h2>Ima seznam sama soda števila</h2>
+
+<p>Seznam ima sama soda števila, če je prazen ali pa je prvi element sod in
+ima preostanek sama soda števila.</p>
+
+<pre>def soda(s):
+ return not s or s[0] % 2 == 0 and soda(s[1:])</pre>
+
+<h2>Vsota sodih števil v seznamu</h2>
+
+<p>Napisati želimo funkcijo, ki vrne vsoto vseh sodih elementov v podanem
+seznamu.</p>
+
+<p>Č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.</p>
+
+<pre>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:])</pre>
+
+<h2>Prvi sodi element seznama</h2>
+
+<p>Napisali bomo funkcijo, ki vrne prvi sodi element.</p>
+
+<p>Če je ničti element sod, vrnemo tega. Sicer vrnemo prvega sodega med
+ostalimi.</p>
+
+<pre>def prvi_sodi(s):
+ if s[0] % 2 == 0:
+ return s[0]
+ else:
+ return prvi_sodi(s[1:])</pre>
+
+<p>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,
+<code>s[0]</code> in Python bo javil napako, <code>Index out of range</code>.
+</p>
+
+<p>Recimo, da bo funkcija v takšnem primeru vrnila <code>None</code>.</p>
+
+<pre>def prvi_sodi(s):
+ if not s:
+ return None
+ if s[0] % 2 == 0:
+ return s[0]
+ else:
+ return prvi_sodi(s[1:])</pre>
+
+
+</body>
+</html>
|