Zanke#
Rekurzivni klici nam omogočajo, da se pri izvajanju poljubno mnogokrat vrnemo na poljubne konce programa. V veliki večini primerov pa nam je dovolj že to, da ponovimo določen del programa. Temu so namenjene zanke.
Zanka while#
Z zanko while določene ukaze izvajamo toliko časa, dokler velja dani pogoj. Pišemo jo kot
while pogoj:
# stavki, ki jih ponavljamo
# od prvega do zadnjega,
# dokler velja pogoj
Na primer, program
n = 12
while n < 1000:
n = n * 2
print(n)
24
48
96
192
384
768
1536
bo n nastavil na 12, nato pa ga toliko časa podvojeval in izpisoval, dokler njegova vrednost ne bo presegla 1000.
V programih bomo pogostokrat novo vrednost spremenljivke izračunali tako, da bomo spremenili staro (zato tudi govorimo o spremenljivkah). Na primer, ko bomo šteli vsa praštevila med 1 in 1000000, bomo imeli spremenljivko, ki bo imela na začetku vrednost 0, nato pa jo bomo ob vsakem praštevilu povečali za 1. V ta namen lahko namesto n = n * 2 pišemo kar operator n *= 2, saj je *= operacija, ki spremenljivko na levi pomnoži z vrednostjo na desni. Tudi za ostale operacije obstajajo podobne bližnjice, na primer -=, *=, //= in tako naprej.
x = 3
x += 2
x *= 4
x
20
Zgornji program bi tako na krajše lahko napisali kot:
n = 12
while n < 1000:
n *= 2
print(n)
24
48
96
192
384
768
1536
Za primer izračunajmo stopnjo največje potence števila 2, ki še deli število 1580160. To storimo tako, da število zaporedoma celoštevilsko delimo z 2 in ob vsakem deljenju števec stopnje povečamo za 1. Ukaze ponavljamo toliko časa, dokler je ostanek pri deljenju z 2 enak 0:
n = 1580160
stopnja = 0
while n % 2 == 0:
n //= 2
stopnja += 1
print(stopnja)
stopnja
1
2
3
4
5
6
7
7
Program bi lahko pretvorili tudi v splošnejšo funkcijo:
def celostevilski_logaritem(n, k):
"""Vrne stopnjo največje potence števila k, ki še deli n."""
stopnja = 0
while n % k == 0:
n //= k
stopnja += 1
return stopnja
celostevilski_logaritem(81, 3)
4
celostevilski_logaritem(1580160, 2)
7
Isto funkcijo bi lahko napisali tudi z rekurzijo:
def celostevilski_logaritem_rek(n, k):
"""Vrne stopnjo največje potence števila k, ki še deli n."""
if n % k == 0:
return 1 + celostevilski_logaritem_rek(n // k, k)
else:
return 0
celostevilski_logaritem_rek(81, 3)
4
celostevilski_logaritem_rek(1580160, 2)
7
Vseeno v praksi za tiste programe, pri katerih neko stvar ponavljamo toliko časa, dokler velja določen pogoj, raje uporabimo zanko while, saj je učinkovitejša (vsaj v Pythonu, v drugih jezikih je rekurzija ravno tako učinkovita). Poleg tega se Python pritoži, če gremo pri rekurziji pregloboko. Običajno se to zgodi takrat, kadar smo rekurzijo napisali tako, da se ne ustavi. Vendar računalnik tega ne more vedeti, zato se Python ustavi po določenem številu klicev ustavi:
celostevilski_logaritem_rek(2 ** 2950, 2)
2950
celostevilski_logaritem_rek(2 ** 2960, 2)
2960
Pri zankah teh težav ni:
celostevilski_logaritem(2 ** 2950, 2)
2950
celostevilski_logaritem(2 ** 2960, 2)
2960
celostevilski_logaritem(2 ** 10000, 2)
10000
Se pa lahko pri zanki while zgodi, da se njeno izvajanje nikoli ne zaključi. Na primer, če bi poklicali celostevilski_logaritem(12345, 1),
bi bil ostanek pri deljenju z 1 v pogoju vedno enak 0 in zanka bi tekla v neskončnost. Ko se naveličamo čakanja, lahko pritisnemo Ctrl-C in izvajanje prekinemo.
Zanka for#
Zanko while torej uporabimo takrat, kadar želimo ukaze ponavljati, dokler velja nek pogoj. Včasih pa že vnaprej vemo, kolikokrat bomo te ukaze ponovili. Na primer, funkcijo za izračun fakultete bi lahko pisali kot:
def fakulteta(n):
"""Vrne fakulteto naravnega števila n."""
produkt = 1
i = 1
while i <= n:
produkt *= i
i += 1
return produkt
vendar vemo, da se bo zanka izvedla natanko enkrat za vsako število od 1 do n. Poleg tega se nam hitro zgodi, da vrstico i += 1 po nesreči pozabimo ali napišemo kot i + 1 ali kot i = 1, zaradi česar se zanka izvaja v neskončnost. Za primere, ko vemo, kolikokrat izvedemo določeno kodo, raje uporabimo zanko for, ki jo pišemo kot:
for spremenljivka in vrednosti:
# stavki, ki jih izvedemo
# po enkrat za vsako izmed
# podanih vrednost spremenljivke
izvede pa se enako, kot če bi napisali
# v spremenljivko shrani prvo vrednost
# izvedi vse stavke v telesu zanke
# v spremenljivko shrani drugo vrednost
# izvedi vse stavke v telesu zanke
# ...
# v spremenljivko shrani zadnjo vrednost
# izvedi vse stavke v telesu zanke
Na primer, čez vse črke danega niza se sprehodimo kot:
for znak in 'to je en niz':
print(znak)
t
o
j
e
e
n
n
i
z
samoglasnike pa lahko preštejemo kot:
def stevilo_samoglasnikov(niz):
stevilo = 0
for znak in niz:
if znak.lower() in 'aeiou':
stevilo += 1
return stevilo
stevilo_samoglasnikov('Uvod v programiranje')
7
Če se želimo sprehoditi po številih, uporabimo funkcijo range. Ta zaporedoma vrača vsa števila v danem razponu:
for x in range(5, 10):
print(x ** 2)
25
36
49
64
81
Vidimo, da tako kot rezine tudi range ne doseže zgornje meje. Če funkciji range podamo en argument, bo začela šteti z 0, če pa ji podamo še tretji argument, ga bo uporabila za velikost koraka (kot pri rezinah).
for x in range(5):
print(x)
0
1
2
3
4
for x in range(5, 10, 2):
print(x)
5
7
9
S pomočjo funkcije range bi fakulteto torej napisali kot:
def fakulteta(n):
"""Vrne fakulteto naravnega števila n."""
produkt = 1
for i in range(1, n + 1):
produkt *= i
return produkt
fakulteta(20)
2432902008176640000
Stavki break, continue in pass#
V zankah lahko uporabimo tudi posebne ukaze, ki spreminjajo običajen potek programa. Stavek break prekine trenutno zanko. Na primer:
for n in range(1, 5):
print(n)
if n == 2 or n == 3:
break
print('x')
1
x
2
izmenično izpisuje števila od 1 do 4 ter znak x. V trenutku, ko pride do števila 2, ki zadošča pogoju n == 2 or n == 3, izvajanje zanke v celoti prekine in preneha z izpisovanjem.
Primer je napisan za zanko for, vendar enako deluje tudi za zanko while.
Stavek continue zanke ne ustavi, temveč le preskoči preostanek trenutnega obhoda zanke in gre nazaj na začetek z naslednjo vrednostjo. Na primer:
for n in range(1, 5):
print(n)
if n == 2 or n == 3:
continue
print('x')
1
x
2
3
4
x
pri številih 2 in 3, ki zadoščata pogoju, preskoči izpis znaka x, ki bi moral slediti.
Tudi stavek continue deluje tako za zanko for kot za zanko while.
Stavek pass pa ne stori ničesar. Na primer:
for n in range(1, 5):
print(n)
if n == 2 or n == 3:
pass
print('x')
1
x
2
x
3
x
4
x
pri številih 2 in 3, ki zadoščata pogoju, vstopi v pogojni stavek, vendar tam ne stori ničesar, zato je izpis enak, kakor bi bil za program brez pogojnega stavka.
Stavek pass lahko uporabljamo kjerkoli v Pythonu, ne le v zankah. Najpogosteje ga uporabimo takrat, kadar Python zahteva, da napišemo vsaj en ukaz, vendar ne želimo storiti ničesar. Recimo, da imamo program:
for x in range(100):
if x % 2 == 0:
print(x, 'je sod')
else:
print(x, 'je lih')
in za trenutek želimo izklopiti izpisovanje sodih števil. Če bi napisali le
for x in range(100):
if x % 2 == 0:
# print(x, 'je sod')
else:
print(x, 'je lih')
bi se Python pritožil, da je prva veja pogojnega stavka prazna, saj komentarje ignorira. Seveda bi lahko celoten program preuredili v
for x in range(100):
if x % 2 != 0:
print(x, 'je lih')
vendar tega ne želimo (sploh pri večjih programih). S pomočjo stavka pass pa lahko napišemo
for x in range(100):
if x % 2 == 0:
# print(x, 'je sod')
pass
else:
print(x, 'je lih')
Tudi če se odločimo, da bi zopet vklopili izpisovanje, lahko stavek pass pustimo v kodi, ker ne stori ničesar.
Metoda Monte-Carlo#
Metoda Monte-Carlo je postopek, ki ga uporabljamo za približno izračunavanje numeričnih rezultatov s pomočjo naključnega vzorčenja. Njeni začetki segajo v 1940. leta, ko je bila uporabljena za simulacijo fizikalnih procesov v jedrskem orožju, kjer so bili natančni analitični izračuni prezapleteni. Za primer si oglejmo, kako ocenimo število \(\pi\).
Želimo izračunati približno vrednost števila \(\pi\) z metodo Monte-Carlo. Vemo, da enotska krožnica v celoti leži v kvadratu \([-1, 1] \times [-1, 1]\). Verjetnost, da naključno izbrana točka iz tega kvadrata leži v krogu, je enaka razmerju površin:
Če bi torej naključno izbrali veliko število točk iz kvadrata, bi jih približno \(\frac{\pi}{4}\) ležalo v krogu. Obratno lahko \(\pi\) izračunamo tako, da delež točk, ki ležijo v krogu, pomnožimo s 4. Tudi če ne vemo, koliko je \(\pi\), lahko enostavno izračunamo, ali točka leži v krogu ali ne. Napišimo funkcijo, ki naključno izbere n točk iz kvadrata, v spremenljivko v_krogu zabeleži število tistih, ki ležijo v krogu, ter vrne približek števila \(\pi\). Pri tem bomo uporabili funkcijo uniform(a, b) iz knjižnice random, ki naključno izbere število s plavajočo vejico med a in b.
import random
def oceni_pi(n):
v_krogu = 0
for i in range(1, n + 1):
x = random.uniform(-1, 1)
y = random.uniform(-1, 1)
if x ** 2 + y ** 2 <= 1:
v_krogu += 1
print(4 * v_krogu / i)
delez_v_krogu = v_krogu / n
return 4 * delez_v_krogu