summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMartin Možina <martin.mozina@fri.uni-lj.si>2016-10-25 11:44:09 +0200
committerMartin Možina <martin.mozina@fri.uni-lj.si>2016-10-25 11:44:09 +0200
commit0bfa95be7046b101a00f83f082260b5d0e007159 (patch)
tree3d40f550b1b4ac620ca16914cef62f7066d2ef12
parentf12796f00b36d143d8e2735cbec988cad3a3e9e3 (diff)
Added new exercises with recursion.
Added description for functions.
-rw-r--r--python/problems/functions/functions_sl.html587
-rw-r--r--python/problems/functions/sl.py2
-rw-r--r--python/problems/recursion/distance/common.py84
-rw-r--r--python/problems/recursion/distance/en.py13
-rw-r--r--python/problems/recursion/distance/sl.py31
-rw-r--r--python/problems/recursion/find_sum/find_sum.py19
-rw-r--r--python/problems/recursion/map.pngbin0 -> 12202 bytes
-rw-r--r--python/problems/recursion/maxroom/common.py73
-rw-r--r--python/problems/recursion/maxroom/en.py13
-rw-r--r--python/problems/recursion/maxroom/sl.py29
-rw-r--r--python/problems/recursion/where_to/common.py77
-rw-r--r--python/problems/recursion/where_to/en.py13
-rw-r--r--python/problems/recursion/where_to/map.pngbin0 -> 12202 bytes
-rw-r--r--python/problems/recursion/where_to/sl.py55
14 files changed, 976 insertions, 20 deletions
diff --git a/python/problems/functions/functions_sl.html b/python/problems/functions/functions_sl.html
new file mode 100644
index 0000000..1bd0a25
--- /dev/null
+++ b/python/problems/functions/functions_sl.html
@@ -0,0 +1,587 @@
+<!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> Kako definiramo funkcije? </h1>
+
+<p>Funkcije smo si doslej predstavljali kot škatlice: nekaj gre noter
+(temu smo in bomo rekli <em>argument</em>), nekaj pride ven (temu se reče
+ rezultat funkcije), vmes pa se lahko še kaj opaznega dogaja, recimo
+ izpisuje. Primer funkcije, ki je počela vse to, je <code>input</code>: kot
+argument smo ji povedali, kaj naj vpraša uporabnika; kot rezultat je vrnila,
+kar je vtipkal uporabnik; vmes se je zgodilo to, da je funkcija nekaj vprašala
+uporabnika in počakala, da je le-ta odgovoril. Druga funkcija, ki smo jo
+srečali, je bila <code>sqrt</code>, ki dobi kot argument neko število in vrne
+njegov koren. Vmes se ne dogaja nič opaznega, funkcija le "neopazno" naredi,
+kar mora narediti.</p>
+
+<p>S tem, kako delujejo funkcije in kako kaj naredijo, se doslej nismo
+ukvarjali. Te stvari so za nas napisali drugi (hvala, hvala) in mi jih lahko
+uporabljamo, ne da bi nas vznemirjalo vprašanje, kako so napisane. S tem, kako
+so napisane funkcije, ki so jih naredili drugi, se tudi v prihodnje ne bomo
+ukvarjali. Pač pa se bomo danes naučili pisati svoje.</p>
+
+
+<h2>Popolna števila</h2>
+
+<p>Število je <em>popolno</em>, če je enako vsoti svojih deliteljev. 28 je
+deljivo z 1, 2, 4, 7 in 14 ter je popolno, saj je 1+2+4+7+14 ravno 28. Napišimo
+program, ki sestavi seznam vseh popolnih števil do 1000.</p>
+
+<h3>Delitelji števila</h3>
+
+<p>Znamo napisati program, ki sestavi seznam vseh deliteljev nekega števila
+ <em>n</em>?</p>
+
+<pre>
+n = int(input("Vnesi število: "))
+
+s = []
+for i in range(1, n):
+ if n % i == 0:
+ s.append(i)
+
+print(s)</pre>
+
+<p>Najprej naredimo prazen seznam, nato gremo prek vseh števil od 1 do n in
+če število deli <code>n</code>, ga dodamo v <code>s</code>.</p>
+
+<p>Kaj ne bi bilo lepo, če bi imel Python kar funkcijo <code>delitelji</code>,
+ki bi jo lahko uporabili? Potem bi lahko napisali kar</p>
+
+<pre>
+stevilka = int(input("Vnesi število: "))
+s = delitelji(stevilka)
+print(s)</pre>
+
+<p>Napišimo si takšno funkcijo, da jo bomo lahko klicali.</p>
+
+<pre>def delitelji(n):
+ s = []
+ for i in range(1, n):
+ if n % i == 0:
+ s.append(i)
+ return s</pre>
+
+<p>Definicijo funkcije začnemo z <code>def</code>; to je rezervirana beseda, ki
+pomeni, da to, kar sledi, ni "program, ki ga je treba takoj izvesti", temveč
+funkcija. Z drugimi besedami, <code>def delitelji</code> pomeni: "<em>kadar bo
+kdo poklical funkcijo <code>delitelji</code>, naredi naslednje:</em>".</p>
+
+<p>Imenu sledijo oklepaji, v katerih navedemo <em>imena argumentov
+funkcije</em>. V našem primeru bo funkcija zahtevala en argument. Torej, ta,
+ki bo poklical funkcijo, bo moral v oklepaje napisati eno reč (upamo, da bo
+napisal število, sicer pa naj si sam pripiše posledice).</p>
+
+<p>Tista reč, ki jo bomo ob klicu funkcije podali kot argument, se bo znotraj
+funkcije pojavila kot spremenljivka z imenom <code>n</code>. Takšno ime smo
+namreč uporabili v prvi vrstici, v "glavi" funkcije. Vrednosti ji ne bomo
+priredili: ko bo nekdo poklical funkcijo, bo Python tej "spremenljivki" kar sam
+od sebe priredil vrednost, ki jo bo "klicatelj" napisal kot argument funkcije.
+Če torej nekdo pokliče
+
+<pre>s = delitelji(35)</pre>
+
+bo imel <code>n</code> vrednost 35 in če pokliče
+
+<pre>s = delitelji(13)</pre>
+
+bo imel <code>n</code> vrednost 13. <code>n</code> ima vrednost argumenta.</p>
+
+<p>Za <code>def delitelji(n)</code> sledi dvopičje in zamik. Vse, kar sledi
+takole zamaknjeno, je koda funkcije. Kaj mora narediti le-ta? No, tisto, kar
+pač dela funkcija: sestaviti seznam deliteljev <code>n</code>. To pa ne le
+znamo narediti, temveč smo celo ravno prejle tudi zares naredili in lahko le
+skopiramo.</p>
+
+<p>Na koncu (ali tudi že kje vmes - bomo že videli primer) funkcija pove, kaj
+naj klicatelj dobi kot rezultat. To stori s stavkom <code>return s</code>.</p>
+
+<h3>Geometrija</h3>
+
+<p>Napišimo funkcijo, ki dobi kot argument dolžine stranic trikotnika in vrne
+ njegovo ploščino. Ta funkcija bo imela tri argumente; poimenujmo jih
+ <code>a</code>, <code>b</code> in <code>c</code>.
+
+
+<pre>from math import *
+def ploscina_trikotnika(a, b, c):
+ s = (a + b + c) / 2
+ return sqrt(s * (s - a) * (s - b) * (s - c))</pre>
+
+<p>Ko smo pri tem, napišimo še funkcijo funkcijo za obseg trikotnika ter za
+ obseg in ploščino kroga.</p>
+
+<pre>from math import *
+
+def obseg_trikotnika(a, b, c):
+ return a + b + c
+
+def ploscina_kroga(r):
+ return pi * r ** 2
+
+def obseg_kroga(r):
+ return 2 * pi * r</pre>
+
+<h3>Vsota števil v seznamu</h3>
+
+<p>Zdaj napišimo drugo funkcijo: funkcijo, ki dobi seznam števil in izračuna
+njihovo vsoto.</p>
+
+<pre>def vsota(s):
+ vsota = 0
+ for e in s:
+ vsota += e
+ return vsota</pre>
+
+<p>Funkcija ima spet en argument, tokrat smo ga poimenovali <code>s</code>.
+Ta argument bo seznam števil, ki jih je potrebno sešteti. Funkcija gre - z
+zanko <code>for</code> - prek tega seznama in sešteva, kot smo počeli že
+prejšnji teden, le brez funkcij. Na koncu rezultata ne izpiše
+(<code>print</code>), kot smo delali doslej, temveč ga vrne
+(<code>return</code>).</p>
+
+<p>(Mimogrede povejmo še, da nam funkcije <code>vsota</code> ne bi bilo
+potrebno napisati, saj obstaja: imenuje se <code>sum</code>.)</p>
+
+
+<h4>Za napredno misleče</h4>
+
+<p>Nekateri se sprašujejo, kako funkcija ve, kakšnega tipa bodo argumenti,
+ki jih bo dobila. Nekateri se zdaj, ko so izvedeli, da se nekateri sprašujejo
+o tem, sprašujejo, zakaj bi se kdo to spraševal.</p>
+
+<p>Vsebina tega razdelka je namenjena samo prvim. Kasneje bo vse, kar pišemo
+tu, postalo samoumevno, ne da bi bilo potrebno razlagati. Tule pa povejmo
+zaradi tistih, ki prihajajo iz drugih jezikov.</p>
+
+<p>V nekaterih jezikih je potrebno za vsako spremenljivko, preden jo uporabimo,
+povedati, kakšnega tipa bo. Python ni eden izmed teh "nekaterih jezikov".
+Podobno je z argumenti funkcij. V nekaterih jezikih bi morali povedati,
+kakšnega tipa bodo argumenti funkcije in kakšen bo rezultat. Tudi takšen
+Python ni. Funkcija sprejme, kar sprejme in vrača, kar vrača.</p>
+
+<p>Za primer vzemimo preprostejšo funkcijo <code>vsota</code>, ki ji podamo dva
+ argumenta, funkcija pa vrne njuno vsoto.</p>
+
+<pre>def vsota(a, b):
+ return a + b</pre>
+
+<p>Če jo pokličemo z <code>vsota(2, 5)</code>, vrne <code>2 + 5</code>, torej
+ <code>7</code>. Če jo pokličemo z <code>vsota("Ana", "Marija")</code> vrne
+ <code>"Ana" + "Marija"</code>, torej <code>"AnaMarija"</code>. Če jo
+ pokličemo z <code>vsota(2, "Ana")</code>, poskuša izračunati
+ <code>2 + "Ana"</code> in vrne napako, ker se ne da seštevati števil in
+ nizov.</p>
+
+<p>Jezikom, ki delajo tako, pravimo dinamično tipizirani jeziki. Stvar deluje
+(približno) tako, da Python, ko pride do <code>a + b</code>, reče objektoma
+<code>a</code> in <code>b</code>, naj se seštejeta. Če se znata, je to v redu,
+če ne, pa javita napako in Python jo izpiše. Python v resnici ne zna seštevati,
+seštevati (se) znajo objekti.</p>
+
+<p>Vrnimo se k prvi funkciji <code>vsota</code>, oni od prej. Kaj bi se
+ zgodilo, če bi dali funkciji namesto seznama kaj drugega, recimo
+ terko ali kaj podobnega? No, preskusimo jo nekoliko.</p>
+
+<pre> vsota([1, 5, 3])
+9
+>>> vsota((1, 5, 3))
+9
+>>> vsota(range(4))
+6</pre>
+
+<p>S seznamom dela. Prvi klic pomeni isto, kot če bi napisali:
+<pre>s = [1, 5, 3]
+v = 0
+for e in s:
+ v += e</pre>
+
+Drugi klic je podoben, le da je <code>s</code> zdaj terka <code>(1, 5, 3)</code>,
+torej dobimo
+
+<pre>v = 0
+for e in (1, 5, 3):
+ v += e</pre>
+
+Tretji klic pa je isto, kot če bi rekli
+
+<pre>v = 0
+for e in range(4):
+ v += e</pre>
+</p>
+
+<p>Kaj pa, če bi namesto seznama celih števil podali seznam necelih?</p>
+
+<pre>>>> vsota([1.3, 2.2, 3.1])
+6.6</pre>
+
+<p>Dela, jasno. Zakaj pa ne bi?</p>
+
+<p>Kaj pa, če bi dali seznam nizov? Poglejmo, poučno bo.</p>
+
+<pre>>>> vsota(["Ana", "Berta", "Cilka"])
+Traceback (most recent call last):
+ File "<stdin>", line 1, in <module>
+ File "<stdin>", line 4, in vsota
+TypeError: unsupported operand type(s) for +=: 'int' and 'str'</pre>
+
+<p>Zgodi se tole. Najprej je <code>v</code> enak 0. V prvem koraku zanke
+poskuša izračunati <code>0 + "Ana"</code>, kar se ne da.</p>
+
+<p>Funkcijo je mogoče popraviti, da bo delovala tudi za nize. </p>
+
+<pre>def vsota(s):
+ v = None
+ for e in s:
+ if v == None:
+ v = e
+ else:
+ v += e
+ return v</pre>
+
+<p>(<br/>Komur se mozga, naj razmisli, zakaj dela tudi naslednja (grda)
+ različica funkcije:</p>
+<pre>def vsota(s):
+ v = None
+ for e in s:
+ v = v and v + e or e
+ return v</pre>
+<p>.)</p>
+
+<p>Tule smo torej naleteli na <code>None</code>. Tole je kar tipična situacija,
+ v kateri ga uporabimo. <code>v</code>-ju moramo bo v začetku dati neko
+ vrednost, ki bo povedala, da še nima nobene vrednosti. <code>None</code> je
+ idealna konstanta, s katero povemo kaj takega. V zanki preverimo, ali je
+ <code>v</code> še vedno nič in mu v tem primeru priredimo <code>e</code>,
+ sicer mu prištejemo <code>e</code>.</p>
+
+<p>Razlika je v tem, da <code>v</code>-ju zdaj ne priredimo vrednosti že pred
+zanko, temveč jo dobi šele pri prvem elementu zanke. Tako bo gotovo pravega
+tipa. Zdaj zna seštevati vse živo.</p>
+
+<pre>>>> vsota([1, 2, 3])
+6
+>>> vsota(["Ana", "Benjamin", "Cilka"])
+'AnaBenjaminCilka'</pre>
+
+<p>Kaj pa tole?</p>
+
+<pre>>>> vsota("Benjamin")
+'Benjamin'</pre>
+
+<p>Zanka <code>for</code> gre prek niza in sešteje njegove črke. Rezultat je,
+seveda, spet isti niz.</p>
+
+<p>Pač pa funkcija ne deluje, če ji damo seznam, ki vsebuje reči, ki jih ni
+mogoče sešteti.</p>
+
+<pre>>>> vsota([1, "a"])
+Traceback (most recent call last):
+ File "<stdin>", line 1, in <module>
+ File "<stdin>", line 8, in vsota
+TypeError: unsupported operand type(s) for +=: 'int' and 'str'</pre>
+
+
+
+<h3>Popolno število</h3>
+
+<p>Vrnimo se k popolnim številom. Rekli smo, da je število popolno, če je enako
+ vsoti svojih deliteljev. Lahko bi torej rekli</p>
+
+<pre>stevilo = int(input("Vnesi število: "))
+d = delitelji(stevilo)
+v = vsota(d)
+if v == d:
+ print("Število", stevilo, "je popolno")
+else:
+ print("Število", stevilo, "ni popolno")</pre>
+
+<p>vendar ne bomo. Napisali bomo funkcijo, ki vrne <code>True</code>, če je
+število popolno in <code>False</code>, če ni.</p>
+
+<pre>def popolno(n):
+ d = delitelji(n)
+ v = vsota(d)
+ return v == n</pre>
+
+<p>Pazite, tule nismo pisali</p>
+
+<pre>def popolno(n):
+ d = delitelji(n)
+ v = vsota(d)
+ if v == n:
+ return True
+ else:
+ return False</pre>
+
+<p>Lahko bi, vendar bi bilo smešno. Pač pa lahko funkcijo še skrajšamo (in
+navadno bi jo tudi res), takole</p>
+
+<pre>def popolno(n):
+ return vsota(delitelji(n)) == n</pre>
+
+<p>Končno ostane še program, ki bo z uporabo gornje funkcije sestavil seznam
+vseh popolnih števil manjših od 1000.
+V njem z zanko <code>for</code> preštejemo do 1000, za vsako število posebej
+preverimo, ali je popolno in če je, ga dodamo na seznam.</p>
+
+<pre>s = []
+for i in range(1, 1001):
+ if popolno(i):
+ s.append(i)
+
+print(s)</pre>
+
+<p>Lepo prosim, ne pišite <code>if popolno(i) == True:</code>. Smo že povedali,
+zakaj, ne?</p>
+
+<h2>Klici funkcij</h2>
+
+<p>Najprej zberimo vse skupaj:</p>
+
+<pre>def delitelji(n):
+ s = []
+ for i in range(1, n):
+ if n % i == 0:
+ s.append(i)
+ return s
+
+def vsota(s):
+ v = 0
+ for e in s:
+ v += e
+ return v
+
+def popolno(n):
+ d = delitelji(n)
+ v = vsota(d)
+ return v == n
+
+
+s = []
+for i in range(1, 1001):
+ if popolno(i):
+ s.append(i)
+
+print(s)</pre>
+
+<p>Kako se izvaja tako napisan program? Malo drugače, kot smo vajeni. Začetek
+programa - vse do mesta <code>s = []</code>, so definicije funkcij. Python tega
+dela programa ne izvede, le zapomni si funkcije, da jih bo kasneje lahko
+poklical. Stvari se začnejo zares dogajati šele, pri <code>s = []</code>. Ko
+program pride do klica funkcije <code>popolno</code>, skoči v to funkcijo --
+vendar si zapomni, odkod je skočil, tako da se bo kasneje lahko vrnil na to
+mesto.</p>
+
+<p>Prav. Zdaj smo v funkciji <code>popolno</code> in <code>n</code> je neka
+številka (najprej 1, naslednjič bo 2 in tako naprej). Že takoj, v prvi
+vrstici skoči izvajanje v funkcijo <code>delitelji</code>. Ta sestavi seznam
+deliteljev in ga vrne - tistemu, ki jo je poklical, funkciji
+<code>popolno</code>. Nato se nadaljuje izvajanje funkcije <code>popolno</code>:
+ta v naslednji vrsti pokliče funkcijo <code>vsota</code>. Funkcija
+<code>vsota</code> izračuna in vrne vsoto. Spet smo v funkciji
+<code>popolno</code>, ki izračuna vrednost izraza <code>v == n</code>;
+vrednost izraza je <code>True</code> ali <code>False</code>. Funkcija
+<code>popolno</code> ga vrne tistemu, ki jo je klical, se pravi oni zanki
+na koncu skripte. Če je rezultat <code>True</code>, dodamo število v seznam,
+sicer ne.</p>
+
+<p>Ta program je lep zato, ker je pregleden. Razdelili smo ga na tri funkcije,
+vsaka opravlja svoje delo. Ko pišemo eno funkcijo, se ne ukvarjamo
+s celo sliko, temveč le s tem, kar počne ta funkcija. Če mislimo
+le na eno stvar naenkrat, nam bo lažje programirati in manj se bomo motili.</p>
+
+<h2>Rezultat sredi funkcije</h2>
+
+<p>Napišimo funkcijo, ki pove, ali je dano število praštevilo. Vrnila bo
+<code>True</code> (je) ali <code>False</code> (ni).</p>
+
+<p>Prejšnjič smo v te namene spoznali <code>break</code> - <code>break</code>
+ je bil ukaz, s katerim smo lahko prekinili zanko. No, prekinemo jo lahko
+ tudi z <code>return</code>.</p>
+
+<pre>def prastevilo(n):
+ for i in range(2, n):
+ if n % i == 0:
+ return False
+ return True
+</pre></p>
+
+<p>Prvi <code>return</code> je znotraj stavka <code>if</code>. Če odkrijemo,
+da kakšno število med 2 in n-1 deli n (se pravi, če je ostanek po deljenju
+<code>n</code> z <code>i</code> enak 0), dano število ni praštevilo in vrnemo
+<code>False</code>. S tem se izvajanje funkcije prekine, funkcija vrne
+rezultat in konec. Nobenega <code>break</code> ali česa podobnega ne
+potrebujemo. <code>return</code> vedno konča izvajanje funkcije. Do drugega
+<code>return</code>a tako pridemo le, če se ni izvedel prvi
+<code>return</code>. To pa seveda pomeni, da ni bilo nobenega števila, ki bi
+delilo dano število <code>n</code>.</p>
+
+
+<h2>Funkcije (navadno) vračajo rezultate, ne izpisujejo</h2>
+
+<p>Iz neznanega razloga so študentom - kot opažam na izpitih in v domačih
+nalogah - veliko bolj pri srcu funkcije, ki nekaj izpišejo, kot funkcije,
+ki vračajo rezultat. Tako bi jih mikalo, recimo, funkcijo za <code>vsoto</code>
+napisati tako, da bi na koncu namesto <code>return v</code> pisalo
+<code>print(v)</code>.</p>
+
+<p>Vendar to ni prav! S takšno funkcijo si nimamo kaj pomagati! Ne potrebujemo
+funkcije, ki <em>izpiše</em> vsoto; potrebujemo funkcijo, ki <em>vrne</em>
+vsoto, da bomo lahko s to vsoto še kaj počeli. Če jo bomo hoteli izpisati, bomo
+pač poklicali funkcijo in izpisali, kar vrne. Funkcija naj jo le izračuna. Si
+predstavljate, kako neuporabna bi bila funkcija <code>sin</code>, če bi le
+izpisala sinus, namesto da ga vrne? Bi si lahko pri programiranju topov z njo
+sploh kaj pomagali?</p>
+
+<p>To seveda ne pomeni, da funkcije ne smejo ničesar izpisovati. Smejo; nekatere
+so pač namenjene temu. Najbolj očiten primer takšne funkcije je očitno kar
+<code>print</code>.</p>
+
+<h2>Funkcije, ki ne vračajo ničesar</h2>
+
+<p>Vse funkcije v Pythonu vračajo rezultat. Če funkcija ne vrača ničesar, vrača
+ nič, torej <code>None</code>. To se bo zgodilo, kadar funkcija nima
+ <code>return</code> ali kadar se ta ne izvede.</p>
+
+<p>Napišimo, na primer, funkcijo, ki kot argument dobi seznam in vrne prvo sodo
+ število v njem.</p>
+
+<pre>def prvo_sodo(s):
+ for e in s:
+ if e % 2 == 0:
+ return e</pre>
+
+<p>In zdaj jo preskusimo:
+<pre>>>> prvo_sodo([1, 2, 3, 4, 5])
+2
+>>> prvo_sodo([1, 3, 5])
+>>> print(prvo_sodo([1, 3, 5]))
+None</pre>
+
+<p>Prvi klic je jasen: funkcija vrne 2. V drugem primeru pa nikoli ne pride do
+ <code>return</code>a, zato funkcija pač ne vrne ničesar. Ko smo jo
+ poklicali, se tudi ni nič izpisalo, saj Python, kadar ga poganjamo v
+ načinu za čvekanje, ne izpiše <code>None</code> ... razen, kadar ga k temu
+ prisilimo s <code>print</code>, kot smo storili v zadnji vrstici.</p>
+
+<p>Konstanta <code>None</code> se šteje za neresnično. To je praktično, saj jo
+lahko uporabljamo v pogojnih stavkih. Imejmo nek seznam <code>s</code> in
+izpišimo prvo sodo število ali pa povejmo, da v seznamu ni sodih števil.</p>
+
+<pre>sodo = prvo_sodo(s)
+if sodo:
+ print("Prvo sodo število je", sodo)
+else:
+ print("V seznamu ni sodih števil.")</pre>
+
+<p>Vendar moramo biti pri takšnem početju majčkeno previdni. Kaj, če je prvo sodo
+število v seznamu 0? Ker je tudi 0 neresnično, bo program v tem primeru napisal,
+da ni sodih števil. Pravilno bi bilo torej</p>
+
+<pre>sodo = prvo_sodo(s)
+if sodo != None:
+ print("Prvo sodo število je", sodo)
+else:
+ print("V seznamu ni sodih števil.")</pre>
+
+<p>Iz nekega razloga, ki ga bomo pojasnili čez dva tedna, pa običajno pišemo</p>
+
+<pre>sodo = prvo_sodo(s)
+if sodo is not None:
+ print("Prvo sodo število je", sodo)
+else:
+ print("V seznamu ni sodih števil.")</pre>
+
+
+<h2>Več rezultatov</h2>
+
+<p>Funkcija lahko vrača tudi "več rezultatov", tako kot tale funkcija, ki vrne,
+kvadrat in kub števila.</p>
+
+<pre>def kk(x):
+ return x ** 2, x ** 3</pre>
+
+<p>Pokličemo jo lahko takole.</p>
+
+<pre>kvad, kub = kk(5)</pre>
+
+<p>Pozoren študent je najbrž že spregledal mojo laž. V resnici funkcija
+vrača en sam rezultat, namreč terko in ob klicu funkcije to terko razpakiramo.
+Vendar nam o tem, tehničnem vidiku zadeve, ni potrebno razmišljati. Mirno se
+lahko vedemo, kot da smo dobili dve vrednosti.</p>
+
+<p>V tem primeru navadno ne pišemo oklepajev okrog terk. Funkcija bo delovala
+tudi, če pišemo <code>return (x ** 2, x ** 3)</code>, vendar to ni običajen
+zapis za vračanje dveh vrednosti.</p>
+
+<h2>Več returnov</h2>
+
+<p>Funkcija ima seveda lahko več <code>return</code>ov. Izvede se tisti, na
+ katerega naleti. En primer smo že videli (določanje praštevilskosti).
+ Naredimo še enega: funkcijo, ki vrne absolutno vrednost danega števila.</p>
+
+<pre>def abs(x):
+ if x < 0:
+ return -x
+ else:
+ return x
+</pre>
+
+<p>Funkcija ima torej dva <code>return</code>. Eden se izvede, če je število
+ negativno in drugi, če pozitivno.</p>
+
+
+<h2>Funkcije brez argumentov</h2>
+
+<p>Funkcija je lahko tudi brez argumentov. Tule je funkcija, ki nima argumentov,
+ vrne pa 42. Vedno.</p>
+
+<pre>def odgovor():
+ return 42
+</pre>
+
+<p>Tako funkcijo je potrebno tudi poklicati s praznim seznamov argumentov -
+oklepajev pa vseeno ne smemo pozabiti.</p>
+
+<pre>koliko = odgovor()</pre>
+
+<p>Malo pametnejši primer funkcije brez argumentov bi bila funkcija, ki
+ uporabniku zastavi račun in pove (s <code>True</code> ali
+ <code>False</code>), ali ga je pravilno rešil.</p>
+
+<pre>def uganka():
+ a = randint(2, 10)
+ b = randint(2, 10)
+ c = int(input("Koliko je {}x{}? ".format(a, b)))
+ return a * b == c</pre>
+
+<p>Z njo postane rešitev lanske domače naloge precej preglednejša.</p>
+
+<pre>from random import *
+from time import *
+
+konec = time() + 20
+tock = 0
+while time() < konec:
+ if uganka():
+ print("Pravilno.")
+ tock += 1
+ else:
+ print("Napačno.")
+print("Dosegli ste", tock, "tock")</pre>
+
+<p>Zdaj, ko znamo definirati funkcije, bo postalo naše življenje veliko lažje
+in preglednejše. Naši programi so, z vsem kar znamo, začeli postajati
+dolgi in razvlečeni. Zdaj jih bomo lahko razsekali v posamezne funkcije in se
+v njih tako lažje znašli.</p>
+
+</body>
+</html>
diff --git a/python/problems/functions/sl.py b/python/problems/functions/sl.py
index 7de0a40..7e00895 100644
--- a/python/problems/functions/sl.py
+++ b/python/problems/functions/sl.py
@@ -1,3 +1,3 @@
name = 'Funkcije'
-description = 'Pisanje in uporaba funkcij.'
+description = '<a target="_blank" href="[%@resource functions_sl.html%]">Pisanje in uporaba funkcij</a>'
diff --git a/python/problems/recursion/distance/common.py b/python/problems/recursion/distance/common.py
new file mode 100644
index 0000000..f9a8c13
--- /dev/null
+++ b/python/problems/recursion/distance/common.py
@@ -0,0 +1,84 @@
+import re
+from python.util import has_token_sequence, string_almost_equal, \
+ string_contains_number, get_tokens, get_numbers, get_exception_desc, \
+ all_tokens, has_comprehension, has_loop, almost_equal, get_ast
+from server.hints import Hint
+
+id = 20811
+number = 11
+visible = True
+
+solution = '''\
+def distance(map, room1, room2):
+ if room1 not in map or room2 not in map:
+ return -1
+ if room1 == room2:
+ return 0
+ d1 = distance(map, map[room1][0], room2)
+ if d1 > -1:
+ return d1 + 1
+ d2 = distance(map, map[room1][1], room2)
+ if d2 > -1:
+ return d2 + 1
+ return -1
+'''
+
+hint_type = {
+ 'final_hint': Hint('final_hint')
+}
+
+map = {0: [6, 3], 6: [5, 81], 3: [8, 24], 5: [2, 18],
+81: [None, None], 8: [42, None], 24: [63, 13], 2: [7, 27],
+18: [None, 35], 42: [None, 66], 63: [61, None], 13: [4, 12],
+7: [None, None], 27: [None, None], 35: [None, None], 66: [None, None],
+61: [None, None], 4: [None, None], 12: [None, None]}
+
+def test(python, code, aux_code=''):
+ func_name = 'distance'
+ tokens = get_tokens(code)
+ if not has_token_sequence(tokens, ['def', func_name]):
+ return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}]
+
+ in_out = [
+ ((0, 42), 3),
+ ((0, 4), 4),
+ ((0, 5), 2),
+ ((0, 3), 1),
+ ((0, 0), 0),
+ ((42, 42), 0),
+ ((8, 66), 2),
+ ]
+ test_in = [('{}({}, {}, {})'.format(func_name, str(map), l[0][0], l[0][1]), None)
+ for l in in_out]
+ test_out = [l[1] for l in in_out]
+
+ answers = python(code=aux_code+code, inputs=test_in, timeout=1.0)
+ n_correct = 0
+ tin, tout = None, None
+ for i, (ans, to) in enumerate(zip(answers, test_out)):
+ res = ans[0]
+ corr = res == to
+ n_correct += corr
+ if not corr:
+ tin = test_in[i][0]
+ tout = to
+
+ passed = n_correct == len(test_in)
+ hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}]
+ if tin:
+ hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}})
+ if passed:
+ hints.append({'id': 'final_hint'})
+
+ return passed, hints
+
+
+def hint(python, code, aux_code=''):
+ tokens = get_tokens(code)
+
+ # run one test first to see if there are any exceptions
+ answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0)
+ exc = get_exception_desc(answer[0][3])
+ if exc: return exc
+
+ return None
diff --git a/python/problems/recursion/distance/en.py b/python/problems/recursion/distance/en.py
new file mode 100644
index 0000000..316859b
--- /dev/null
+++ b/python/problems/recursion/distance/en.py
@@ -0,0 +1,13 @@
+id = 20811
+name = 'Distance'
+
+description = '''\
+<p>(translation missing)</p>'''
+
+hint = {
+ 'plan': '''\
+<p>(translation missing)</p>''',
+
+ 'no_input_call': '''\
+<p>(translation missing)</p>''',
+}
diff --git a/python/problems/recursion/distance/sl.py b/python/problems/recursion/distance/sl.py
new file mode 100644
index 0000000..9cf9418
--- /dev/null
+++ b/python/problems/recursion/distance/sl.py
@@ -0,0 +1,31 @@
+import server
+mod = server.problems.load_language('python', 'sl')
+
+id = 20811
+name = 'Razdalja'
+
+description = '''\
+<p> <img src="[%@resource map.png%]"> </p>
+<p>
+Nadaljujmo z meglenim gorovjem. Napiši funkcijo
+<code>distance(map, start_room, ring_room)</code>,
+ki prejme zemljevid, številko začetne sobe in številko sobe s prstanom,
+kot rezultat pa vrne dolžino poti do nje. Če katerakoli od sob ne obstaja,
+vrni <code>-1</code>.
+Na gornjem zemljevidu je globina sobe 42 enaka 3. Zato:</p>
+<pre>
+>>> distance(map, 0, 42)
+3
+>>> distance(map, 0, 43)
+-1
+</pre>
+'''
+
+plan = []
+
+hint = {
+ 'final_hint': ['''\
+<p>Program je pravilen! <br>
+</p>
+''']
+}
diff --git a/python/problems/recursion/find_sum/find_sum.py b/python/problems/recursion/find_sum/find_sum.py
deleted file mode 100644
index 85f472b..0000000
--- a/python/problems/recursion/find_sum/find_sum.py
+++ /dev/null
@@ -1,19 +0,0 @@
-def find_sum(xs, gs):
- if gs < 0:
- return False
- if gs == 0:
- return True
- if not xs:
- return False
- return find_sum(xs[1:], gs-xs[0]) or find_sum(xs[1:], gs)
-
-print (find_sum([2,7,3,1,4], 10))
-print (find_sum([2,3,2,4], 10))
-print (find_sum([], 10))
-print (find_sum([1,2,3], 2))
-print (find_sum([1,2,3], 7))
-print (find_sum([2,7,3,1,4], 9))
-print (find_sum([2,7,3,2,4], 17))
-
-
-
diff --git a/python/problems/recursion/map.png b/python/problems/recursion/map.png
new file mode 100644
index 0000000..014d78e
--- /dev/null
+++ b/python/problems/recursion/map.png
Binary files differ
diff --git a/python/problems/recursion/maxroom/common.py b/python/problems/recursion/maxroom/common.py
new file mode 100644
index 0000000..2709d76
--- /dev/null
+++ b/python/problems/recursion/maxroom/common.py
@@ -0,0 +1,73 @@
+import re
+from python.util import has_token_sequence, string_almost_equal, \
+ string_contains_number, get_tokens, get_numbers, get_exception_desc, \
+ all_tokens, has_comprehension, has_loop, almost_equal, get_ast
+from server.hints import Hint
+
+id = 20812
+number = 12
+visible = True
+
+solution = '''\
+def maxroom(map, room):
+ if room == None:
+ return -1
+ return max(room, maxroom(map, map[room][0]), maxroom(map, map[room][1]))
+'''
+
+hint_type = {
+ 'final_hint': Hint('final_hint')
+}
+
+map = {0: [6, 3], 6: [5, 81], 3: [8, 24], 5: [2, 18],
+81: [None, None], 8: [42, None], 24: [63, 13], 2: [7, 27],
+18: [None, 35], 42: [None, 66], 63: [61, None], 13: [4, 12],
+7: [None, None], 27: [None, None], 35: [None, None], 66: [None, None],
+61: [None, None], 4: [None, None], 12: [None, None]}
+
+def test(python, code, aux_code=''):
+ func_name = 'maxroom'
+ tokens = get_tokens(code)
+ if not has_token_sequence(tokens, ['def', func_name]):
+ return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}]
+
+ in_out = [
+ (0, 81),
+ (3, 66),
+ (63, 63),
+ (5, 35),
+ ]
+ test_in = [('{}({}, {})'.format(func_name, str(map), l[0]), None)
+ for l in in_out]
+ test_out = [l[1] for l in in_out]
+
+ answers = python(code=aux_code+code, inputs=test_in, timeout=1.0)
+ n_correct = 0
+ tin, tout = None, None
+ for i, (ans, to) in enumerate(zip(answers, test_out)):
+ res = ans[0]
+ corr = res == to
+ n_correct += corr
+ if not corr:
+ tin = test_in[i][0]
+ tout = to
+
+ passed = n_correct == len(test_in)
+ hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}]
+ if tin:
+ hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}})
+ if passed:
+ hints.append({'id': 'final_hint'})
+
+ return passed, hints
+
+
+def hint(python, code, aux_code=''):
+ tokens = get_tokens(code)
+
+ # run one test first to see if there are any exceptions
+ answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0)
+ exc = get_exception_desc(answer[0][3])
+ if exc: return exc
+
+ return None
diff --git a/python/problems/recursion/maxroom/en.py b/python/problems/recursion/maxroom/en.py
new file mode 100644
index 0000000..a876812
--- /dev/null
+++ b/python/problems/recursion/maxroom/en.py
@@ -0,0 +1,13 @@
+id = 20812
+name = 'Max room'
+
+description = '''\
+<p>(translation missing)</p>'''
+
+hint = {
+ 'plan': '''\
+<p>(translation missing)</p>''',
+
+ 'no_input_call': '''\
+<p>(translation missing)</p>''',
+}
diff --git a/python/problems/recursion/maxroom/sl.py b/python/problems/recursion/maxroom/sl.py
new file mode 100644
index 0000000..bfc5313
--- /dev/null
+++ b/python/problems/recursion/maxroom/sl.py
@@ -0,0 +1,29 @@
+import server
+mod = server.problems.load_language('python', 'sl')
+
+id = 20812
+name = 'Največja številka'
+
+description = '''\
+<p> <img src="[%@resource map.png%]"> </p>
+<p>
+Napiši funkcijo <code>maxroom(map, room)</code>, ki vrne največjo številko,
+v katero lahko pridemo, če se spustimo iz te sobe. </p>
+<pre>
+>>> maxroom(map, 0)
+81
+>>> maxroom(map, 3)
+66
+>>> maxroom(map, 12)
+12
+</pre>
+'''
+
+plan = []
+
+hint = {
+ 'final_hint': ['''\
+<p>Program je pravilen! <br>
+</p>
+''']
+}
diff --git a/python/problems/recursion/where_to/common.py b/python/problems/recursion/where_to/common.py
new file mode 100644
index 0000000..55a9aed
--- /dev/null
+++ b/python/problems/recursion/where_to/common.py
@@ -0,0 +1,77 @@
+import re
+from python.util import has_token_sequence, string_almost_equal, \
+ string_contains_number, get_tokens, get_numbers, get_exception_desc, \
+ all_tokens, has_comprehension, has_loop, almost_equal, get_ast
+from server.hints import Hint
+
+id = 20810
+number = 10
+visible = True
+
+solution = '''\
+def where_to(map, room, path):
+ if path:
+ return where_to(map, map[room][path[0] == "R"], path[1:])
+ else:
+ return room
+'''
+
+hint_type = {
+ 'final_hint': Hint('final_hint')
+}
+
+map = {0: [6, 3], 6: [5, 81], 3: [8, 24], 5: [2, 18],
+81: [None, None], 8: [42, None], 24: [63, 13], 2: [7, 27],
+18: [None, 35], 42: [None, 66], 63: [61, None], 13: [4, 12],
+7: [None, None], 27: [None, None], 35: [None, None], 66: [None, None],
+61: [None, None], 4: [None, None], 12: [None, None]}
+
+def test(python, code, aux_code=''):
+ func_name = 'where_to'
+ tokens = get_tokens(code)
+ if not has_token_sequence(tokens, ['def', func_name]):
+ return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}]
+
+ in_out = [
+ ((0, "LLR"), 18),
+ ((0, "RRRR"), 12),
+ ((0, "L"), 6),
+ ((0, ""), 0),
+ ((0, "RLL"), 42),
+ ((0, "RRLL"), 61),
+ ((0, "LLLL"), 7),
+ ]
+ test_in = [('{}({}, {}, "{}")'.format(func_name, str(map), l[0][0], l[0][1]), None)
+ for l in in_out]
+ test_out = [l[1] for l in in_out]
+
+ answers = python(code=aux_code+code, inputs=test_in, timeout=1.0)
+ n_correct = 0
+ tin, tout = None, None
+ for i, (ans, to) in enumerate(zip(answers, test_out)):
+ res = ans[0]
+ corr = res == to
+ n_correct += corr
+ if not corr:
+ tin = test_in[i][0]
+ tout = to
+
+ passed = n_correct == len(test_in)
+ hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}]
+ if tin:
+ hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}})
+ if passed:
+ hints.append({'id': 'final_hint'})
+
+ return passed, hints
+
+
+def hint(python, code, aux_code=''):
+ tokens = get_tokens(code)
+
+ # run one test first to see if there are any exceptions
+ answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0)
+ exc = get_exception_desc(answer[0][3])
+ if exc: return exc
+
+ return None
diff --git a/python/problems/recursion/where_to/en.py b/python/problems/recursion/where_to/en.py
new file mode 100644
index 0000000..df43164
--- /dev/null
+++ b/python/problems/recursion/where_to/en.py
@@ -0,0 +1,13 @@
+id = 20810
+name = 'Where to'
+
+description = '''\
+<p>(translation missing)</p>'''
+
+hint = {
+ 'plan': '''\
+<p>(translation missing)</p>''',
+
+ 'no_input_call': '''\
+<p>(translation missing)</p>''',
+}
diff --git a/python/problems/recursion/where_to/map.png b/python/problems/recursion/where_to/map.png
new file mode 100644
index 0000000..014d78e
--- /dev/null
+++ b/python/problems/recursion/where_to/map.png
Binary files differ
diff --git a/python/problems/recursion/where_to/sl.py b/python/problems/recursion/where_to/sl.py
new file mode 100644
index 0000000..365d7cd
--- /dev/null
+++ b/python/problems/recursion/where_to/sl.py
@@ -0,0 +1,55 @@
+import server
+mod = server.problems.load_language('python', 'sl')
+
+id = 20810
+name = 'Kam?'
+
+description = '''\
+<p>
+od Meglenim gorovjem je, kot nekateri vedo že dolgo,
+nekateri pa so morali čakati na film, cel labirint votlin.
+Bilbu bi bilo veliko lažje, če bi imel zemljevid. Mi ga imamo.
+
+Zemljevid lahko shranimo tudi v obliki slovarja,
+v katerem so ključi številke sob, vrednosti pa sobe,
+v katere pridemo po levi in po desni poti.
+Kadar kakšne poti ni, je ustrezni element enak None.</p>
+
+<img src="[%@resource map.png%]">
+
+<pre>
+map = {0: [6, 3], 6: [5, 81], 3: [8, 24], 5: [2, 18],
+81: [None, None], 8: [42, None], 24: [63, 13], 2: [7, 27],
+18: [None, 35], 42: [None, 66], 63: [61, None], 13: [4, 12],
+7: [None, None], 27: [None, None], 35: [None, None], 66: [None, None],
+61: [None, None], 4: [None, None], 12: [None, None]}</pre>
+
+<p>Napiši funkcijo <code>where_to(map, room, path)</code>,
+ki kot argument prejme zemljevid (npr. zgornji slovar),
+začetno sobo (ta bo vedno 0, a to naj te ne moti) in pot (<code>path</code>),
+podano kot zaporedje znakov <code>L</code> in <code>R</code> (levo in desno).
+Kot rezultat mora vrniti sobo, v katero pelje podana pot.</p>
+
+<pre>
+>>> where_to(map, 0, "LLR")
+18
+>>> where_to(map, 0, "RRRR")
+12
+>>> where_to(map, 0, "L")
+6
+>>> where_to(map, 0, "")
+0
+</pre>
+
+<p> Predpostaviti smeš, da je pot pravilna in se nikoli ne odpravi v hodnik,
+ki ga ni.</p>
+'''
+
+plan = []
+
+hint = {
+ 'final_hint': ['''\
+<p>Program je pravilen! <br>
+</p>
+''']
+}