Petlje (1)
The class of problems capable of solution by the machine can be defined fairly specifically. They are those problems which can be solved by human clerical labour, working to fixed rules, and without understanding. A. Turing, 1946. |
Do sada ste upoznali tri vrste jednostavnih naredaba:
Naredbe–izrazi upotrebljavaju se—u interaktivnom radu, u zadnjem (ili jedinom) retku u ćeliji—za izračunavanje i ispisivanje vrijednosti. Može se reći da je izraz opis (ili zapis) operacije, a naredba zahtjev za njezinim izračunavanjem (slikovito, izraz upisan u ćeliju postaje naredbom pritiskom na dugme evaluate ).
Naredbom print ispisuje se vrijednost izraza ili niz vrijednosti nanizanih izraza (odvojenih zarezima), neovisno o tome je li to posljednja naredba u ćeliji ili ne. (Ispisuje se vrijednost izraza, što znači da se izraz prije ispisivanja izračunava.)
U naredbama pridruživanja s desne su strane znaka pridruživanja izrazi vrijednosti kojih se (nakon izračunavanja) pridružuju varijablama s lijeve strane.
Upravljačke strukture određuju redoslijed izvođenja naredaba:
Mnogi su od primjera u prethodnim predavanjima (u pojedinim ćelijama, a katkad i u nizu uzastopnih ćelija) primjeri najjednostavnije upravljačke strukture—nizanja naredaba.
Petlja je upravljačka struktura koja omogućava ponavljanje jedne naredbe ili više njih unaprijed utvrđeni broj puta ili tako dugo dok je ispunjen određeni uvjet.
Naredba koja se ponavlja ili niz naredaba koji se ponavlja nazivaju se tijelom petlje. Jedno izvođenje tijela petlje nazivat ćemo korakom petlje (i, kraće, samo korakom) ili prolaskom kroz petlju.
Petlja for
Petlja for se u pravilu upotrebljava onda kada je broj prolazaka kroz petlju poznat prije ulaska u nju.
Opći je oblik petlje for:
for jedinka in lista :
tijelo petlje
u „prijevodu”:
za svaku jedinku u listi
uradi to i to ...
Najjednostavniji je oblik:
for cjelobrojni_brojač in cjelobrojni_niz :
tijelo petlje
0 1 2 3 4 5 0 1 2 3 4 5 |
The only way to learn a new programming language is by writing programs in it.
B. Kernighan & D. Ritchie
Izračunavanje vrijednosti polinoma
Napisat ćemo programsku funkciju za izračunavanje vrijednosti polinoma n-toga stupnja
Pn(x)=a0+a1x+a2x2+⋯+an−1xn−1+anxn
za odabranu vrijednost varijable x. Parametri funkcije su niz a koji sadrži koeficijente polinoma,
a=[a0,a1,a2,…,an−1,an],
i varijabla x.
„Naivni” algoritam
Najjednostavniji, ali ne i pretjerano učinkovit algoritam gotovo je „doslovni prijevod” funkcijskoga izraza kojim je polinom definiran, odnosno izraza u kojem smo ugniježđenim zagradama istaknuli redoslijed zbrajanja:
Pn(x)=(((⋯(((a0)+a1x1)+a2x2)+⋯)+an−1xn−1)+anxn).
Treba, dakle, izračunati svaki član polinoma, redom od drugoga (s indeksom koeficijenta i potencijom 1: a1x1) do posljednjeg (n-tog), i pribrojiti ga zbroju prethodnih članova. Zbrojeve članova pohranjivat ćemo u varijablu y. Varijabli y prvo ćemo pridružiti prvi/nulti član a0, a potom ćemo joj u svakom koraku petlje pridružiti zbroj vrijednosti koja je u njoj prethodno pohranjena i vrijednosti sljedećega člana polinoma:
y←a0y←y+a1x1y←(a0)+a1x1y←y+a2x2y←((a0)+a1x1)+a2x2⋮⋮y←y+an−1xn−1y←(⋯((a0)+a1x1)+a2x2+⋯)+an−1xn−1y←y+anxny←((⋯((a0)+a1x1)+a2x2+⋯)+an−1xn−1)+anxn
Lijevi stupac, od drugoga retka nadalje, možemo sažeti u
y←y+akxk za k od 1 do n
ili, s pogledom prema petlji for,
za k od 1 do n :
y←y+akxk
pa je sažeti zapis cijeloga lijevog stupca
y←a0
za k od 1 do n :
y←y+akxk
Za tvorbu rastućega niza vrijednosti, od 1 do n, možemo upotrijebiti funkciju srange(). Dva su „jednostavnija” oblika poziva te funkcije
Budući da end nije uključen u niz koji stvara funkcija srange(), niz koji će sadržavati vrijednosti od 1 do n dobit ćemo pozivom srange (1, n+1). Kako niz koji sadrži koeficijente polinoma n-tog stupnja ima n+1 komponentu, drugi argument u pozivu funkcije srange() može biti njegova duljina, koju dobivamo pozivom funkcije len().
|
Pozivom funkcije eval_poly() izračunat ćemo, primjerice, vrijednost polinoma P5(x)=2−3x−4x2+x3+3x5 u x=2 i u x=−2:
|
84 -112 84 -112 |
Još dva primjera (napišite funkcijske izraze za oba polinoma!):
1 0 1 0 |
Zornosti prikaza radi ispisat ćemo pojedine korake u izračunavanju vrijednosti polinoma u prethodnim primjerima (definiciju funkcije eval_poly_wp() u sljedećoj ćeliji možete preskočiti):
|
y = a[0] = 2 y = y + a[1]*x^1 = 2 + (-3)*2^1 = -4 y = y + a[2]*x^2 = -4 + (-4)*2^2 = -20 y = y + a[3]*x^3 = -20 + 1*2^3 = -12 y = y + a[4]*x^4 = -12 + 0*2^4 = -12 y = y + a[5]*x^5 = -12 + 3*2^5 = 84 y = a[0] = 2 y = y + a[1]*x^1 = 2 + (-3)*2^1 = -4 y = y + a[2]*x^2 = -4 + (-4)*2^2 = -20 y = y + a[3]*x^3 = -20 + 1*2^3 = -12 y = y + a[4]*x^4 = -12 + 0*2^4 = -12 y = y + a[5]*x^5 = -12 + 3*2^5 = 84 |
y = a[0] = 2 y = y + a[1]*x^1 = 2 + (-3)*(-2)^1 = 8 y = y + a[2]*x^2 = 8 + (-4)*(-2)^2 = -8 y = y + a[3]*x^3 = -8 + 1*(-2)^3 = -16 y = y + a[4]*x^4 = -16 + 0*(-2)^4 = -16 y = y + a[5]*x^5 = -16 + 3*(-2)^5 = -112 y = a[0] = 2 y = y + a[1]*x^1 = 2 + (-3)*(-2)^1 = 8 y = y + a[2]*x^2 = 8 + (-4)*(-2)^2 = -8 y = y + a[3]*x^3 = -8 + 1*(-2)^3 = -16 y = y + a[4]*x^4 = -16 + 0*(-2)^4 = -16 y = y + a[5]*x^5 = -16 + 3*(-2)^5 = -112 |
y = a[0] = 1 y = y + a[1]*x^1 = 1 + 1*(-1)^1 = 0 y = y + a[2]*x^2 = 0 + 1*(-1)^2 = 1 y = y + a[3]*x^3 = 1 + 1*(-1)^3 = 0 y = y + a[4]*x^4 = 0 + 1*(-1)^4 = 1 y = y + a[5]*x^5 = 1 + 1*(-1)^5 = 0 y = y + a[6]*x^6 = 0 + 1*(-1)^6 = 1 y = a[0] = 1 y = y + a[1]*x^1 = 1 + 1*(-1)^1 = 0 y = y + a[2]*x^2 = 0 + 1*(-1)^2 = 1 y = y + a[3]*x^3 = 1 + 1*(-1)^3 = 0 y = y + a[4]*x^4 = 0 + 1*(-1)^4 = 1 y = y + a[5]*x^5 = 1 + 1*(-1)^5 = 0 y = y + a[6]*x^6 = 0 + 1*(-1)^6 = 1 |
y = a[0] = 1 y = y + a[1]*x^1 = 1 + (-1)*1^1 = 0 y = y + a[2]*x^2 = 0 + 1*1^2 = 1 y = y + a[3]*x^3 = 1 + (-1)*1^3 = 0 y = y + a[4]*x^4 = 0 + 1*1^4 = 1 y = y + a[5]*x^5 = 1 + (-1)*1^5 = 0 y = y + a[6]*x^6 = 0 + 1*1^6 = 1 y = y + a[7]*x^7 = 1 + (-1)*1^7 = 0 y = a[0] = 1 y = y + a[1]*x^1 = 1 + (-1)*1^1 = 0 y = y + a[2]*x^2 = 0 + 1*1^2 = 1 y = y + a[3]*x^3 = 1 + (-1)*1^3 = 0 y = y + a[4]*x^4 = 0 + 1*1^4 = 1 y = y + a[5]*x^5 = 1 + (-1)*1^5 = 0 y = y + a[6]*x^6 = 0 + 1*1^6 = 1 y = y + a[7]*x^7 = 1 + (-1)*1^7 = 0 |
Složenost algoritma (uz „naivno” potenciranje anxn=an×x×x×⋯×x⏟nputa) jest
0+1+2+⋯+(n−2)+(n−1)+n množenja i n zbrajanja.
Broj je množenja, kraće,
12n2+12n
|
... ili
12(n+1)n
|
Na primjer, za izračunavanje vrijednosti polinoma petoga stupnja potrebno je
15 15 |
množenja i 5 zbrajanja.
O početnim vrijednostima (ili: varijacija na temu)
U „naivnom” smo algoritmu prije ulaska u petlju varijabli y pridružili vrijednost a0 konstantnoga člana polinoma (komponentu niza a s indeksom 0), a potom smo u petlji čitali kompente niza od one s indeksom 1 nadalje i izračunavali članove polinoma od člana a1x1 nadalje.
Budući da je x0=1, konstantni član polinoma možemo napisati u obliku a0x0, pa je
Pn(x)=(((⋯(((a0x0)+a1x1)+a2x2)+⋯)+an−1xn−1)+anxn)
[matematičari se, doduše, još uvijek nisu dogovorili koliko je 00 (primjerice: ♠ ili ♣ ili ♦), ali u SageMath-u i Python-u je i 00=1].
Sada su svi članovi polinoma istog oblika, akxk za k od 0 do n, pa ih sve možemo izračunati unutar petlje:
za k od 0 do n :
y←y+akxk
No, u svakom prolazu kroz petlju, pa i u prvom, izračunani član niza pribrajamo vrijednosti prethodno pohranjenoj u varijablu y. Pitanje je, stoga, koja vrijednost mora biti u varijabli y prije ulaska u petlju...
Budući da u petlji vrijednosti u varijablu y akumuliramo zbrajanjem, početna vrijednost mora biti neutralni element operacije zbrajanja: broj 0. [Neutralni element e neke (komutativne) binarne operacije ♥ element je za koji je y♥e=e♥y=y za svaki y za koji je operacija definirana. Za zbrajanje je y+0=0+y=y.]
Varijanta „naivnog” algoritma za izračunavanje vrijednosti polinoma je, prema tome:
y←0
za k od 0 do n :
y←y+akxk
|
1 0 1 0 |
Ako se vrijednosti u nekoj varijabli akumuliraju množenjem, a sva se „stvarna” izračunavanja vrše unutar petlje, varijabli prije ulaska u petlju mora biti pridružen broj 1, neutralni element operacije množenja (y⋅1=1⋅y=y).
Ako pak varijabla ima ulogu brojača, njezina je početna vrijednost 0 (još nismo počeli prebrojavati); prebrojavanje je samo poseban slučaj akumuliranja zbrajanjem.
Hornerov algoritam
Na 14. predavanju (MPZI_predavanje_14) pokazat ćemo da postoji učinkovitiji postupak izračunavanja n-te potencije broja x, xn, sa znatno manje od n−1 množenja, tako da za izračunavanje vrijednosti polinoma n-tog stupnja treba manje od 12(n+1)n množenja. No, lako je vidjeti da se učinkoviti algoritam za izračunavanje vrijednosti polinoma—učinkovitiji i od „naivnoga” algoritma s poboljšanim potenciranjem—može oblikovati na drugi način: pri izračunavanju k-toga člana polinoma, akxk, ne treba xk izračunavati „ispočetka”. Ako smo za izračunavanje člana ak−1xk−1 izračunali xk−1, onda je xk, potreban za izračunavanje člana akxk, jednostavno xk=xk−1×x.
Vrijednost polinoma možemo stoga izračunati prema izrazu
Pn(x)=((⋯(((anx+an−1)x+an−2)x+an−3)⋯)x+a1)x+a0.
„Prijevod” je toga izraza u algoritam koji nosi ime Williama Georgea Hornera (iako je šest stotina godina ranije bio poznat kineskom matematičaru Qinu Jiushaou):
y←any←yx+an−1y←(an)x+an−1=anx+an−1y←yx+an−2y←((an)x+an−1)x+an−2=anx2+an−1x+an−2y←yx+an−3y←(((an)x+an−1)x+an−2)x+an−3y←=anx3+an−1x2+an−2x+an−3⋮⋮y←yx+a1y←(⋯((((an)x+an−1)x+an−2)x+an−3)⋯)x+a1y←=anxn−1+an−1xn−2+an−2xn−3+⋯+a2x+a1y←yx+a0y←((⋯((((an)x+an−1)x+an−2)x+an−3)⋯)x+a1)x+a0y←=anxn+an−1xn−1+an−2xn−2+⋯+a2x2+a1x+a0
Varijabli y sada prije ulaska u petlju pridružujemo posljednju komponentu niza a, an, a potom u petlji niz čitamo unazad, od predzadnje, an−1, do prve/nulte komponente, a0. U svakom koraku petlje pročitanu vrijednost ak pribrajamo vrijednosti dobivenoj množenjem vrijednosti pohranjene u varijabli y i broja x, pa dobivenu vrijednost pridružujemo varijabli y:
y←an
za k u padajućem nizu od n−1 do 0 :
y←yx+ak
odnosno
y←an
za k od n−1 do 0 s korakom −1 :
y←yx+ak
I za tvorbu padajućega niza možemo upotrijebiti funkciju srange():
Kako end nije uključen u nastali niz, padajući niz od n−1 do 0 s korakom −1, koji će sadržavati i 0, dobit ćemo pozivom srange (n-1, -1, -1).
|
84 -112 84 -112 |
1 0 1 0 |
Ispisat ćemo i pojedine korake u izračunavanju vrijednosti polinoma primjenom Hornerova algoritma (kao i prije, definiciju funkcije horner_wp() možete preskočiti):
|
y = a[n] = 3 y = y*x + a[4] = 3 * 2 + 0 = 6 y = y*x + a[3] = 6 * 2 + 1 = 13 y = y*x + a[2] = 13 * 2 + (-4) = 22 y = y*x + a[1] = 22 * 2 + (-3) = 41 y = y*x + a[0] = 41 * 2 + 2 = 84 y = a[n] = 3 y = y*x + a[4] = 3 * 2 + 0 = 6 y = y*x + a[3] = 6 * 2 + 1 = 13 y = y*x + a[2] = 13 * 2 + (-4) = 22 y = y*x + a[1] = 22 * 2 + (-3) = 41 y = y*x + a[0] = 41 * 2 + 2 = 84 |
y = a[n] = 3 y = y*x + a[4] = (3) * (-2) + 0 = -6 y = y*x + a[3] = (-6) * (-2) + 1 = 13 y = y*x + a[2] = (13) * (-2) + (-4) = -30 y = y*x + a[1] = (-30) * (-2) + (-3) = 57 y = y*x + a[0] = (57) * (-2) + 2 = -112 y = a[n] = 3 y = y*x + a[4] = (3) * (-2) + 0 = -6 y = y*x + a[3] = (-6) * (-2) + 1 = 13 y = y*x + a[2] = (13) * (-2) + (-4) = -30 y = y*x + a[1] = (-30) * (-2) + (-3) = 57 y = y*x + a[0] = (57) * (-2) + 2 = -112 |
y = a[n] = 1 y = y*x + a[5] = (1) * (-1) + 1 = 0 y = y*x + a[4] = (0) * (-1) + 1 = 1 y = y*x + a[3] = (1) * (-1) + 1 = 0 y = y*x + a[2] = (0) * (-1) + 1 = 1 y = y*x + a[1] = (1) * (-1) + 1 = 0 y = y*x + a[0] = (0) * (-1) + 1 = 1 y = a[n] = 1 y = y*x + a[5] = (1) * (-1) + 1 = 0 y = y*x + a[4] = (0) * (-1) + 1 = 1 y = y*x + a[3] = (1) * (-1) + 1 = 0 y = y*x + a[2] = (0) * (-1) + 1 = 1 y = y*x + a[1] = (1) * (-1) + 1 = 0 y = y*x + a[0] = (0) * (-1) + 1 = 1 |
y = a[n] = -1 y = y*x + a[6] = -1 * 1 + 1 = 0 y = y*x + a[5] = 0 * 1 + (-1) = -1 y = y*x + a[4] = -1 * 1 + 1 = 0 y = y*x + a[3] = 0 * 1 + (-1) = -1 y = y*x + a[2] = -1 * 1 + 1 = 0 y = y*x + a[1] = 0 * 1 + (-1) = -1 y = y*x + a[0] = -1 * 1 + 1 = 0 y = a[n] = -1 y = y*x + a[6] = -1 * 1 + 1 = 0 y = y*x + a[5] = 0 * 1 + (-1) = -1 y = y*x + a[4] = -1 * 1 + 1 = 0 y = y*x + a[3] = 0 * 1 + (-1) = -1 y = y*x + a[2] = -1 * 1 + 1 = 0 y = y*x + a[1] = 0 * 1 + (-1) = -1 y = y*x + a[0] = -1 * 1 + 1 = 0 |
Složenost algoritma odmah je vidljiva: n množenja i n zbrajanja. Primjerice, vrijednost polinoma petoga stupnja izračunava se u 5 množenja i 5 zbrajanja.
U Python-u i SageMath-u niz se može indeksirati unatrag i pomoću negativnih indeksa: indeks je posljednje komponente −1, dok je indeks prve komponente niza s n komponenata −n:
|
84 -112 84 -112 |
... zašto je end u pozivu funkcije srange() jednak -len(a)-1?
|
84 -112 84 -112 |
Animacija
Na predavanju Elementi matematičke analize (1) (MPZI_predavanje_07) za zorni prikaz značenja derivacije funkcije f uveli smo, bez objašnjenja, programsku funkciju animate_tangents() koja crta tangente u nizu točaka uzduž njezina grafa i, istodobno, graf derivacije f′. Pokušat ćemo sada rad te funkcije objasniti.
Parametri funkcije su:
def animate_tangents (f, xmin, xmax, ymin, ymax, delay = 4)
Animirani prikaz putovanja tangente po grafu funkcije nastaje tako da se crteži tangenata u nizu točaka grafa izmjenjuju jedan za drugim u određenim, razmjerno kratkim vremenskim razmacima. Programsku zadaću, prema tome, možemo podijeliti u dva dijela: crtanje niza slika i njihovo prikazivanje. Slike ćemo, kad ih nacrtamo, pohranjivati u listu plots. Oblikovanje liste izdvojit ćemo u programsku funkciju tangents_plot_list().
Na početku je lista crteža prazna:
plots = []
Svaku ćemo novu sliku dodati na kraj liste. Dodavanju komponenata na kraj lista namijenjena je Python-ova funkcija .append():
plots.append (nova_slika)
Na svakoj ćemo slici prikazati graf funkcije na intervalu [xmin,xmax], tangentu u točki (xi,f(xi)) i graf derivacije na intervalu [xmin,xi]; uz to, posebno ćemo istaknuti točku (xi,f(xi)) u kojoj je nacrtana tangenta i točku (xi,f′(xi)) do koje je nacrtan graf derivacije.
Graf funkcije f se ne mijenja, pa je nacrtan samo jednom, prije ulaska u petlju:
pf = plot (f, xmin, xmax, ymin = ymin, ymax = ymax)
Tangente ćemo crtati u nizu točaka čije su apscise x0=xmin+12Δx, x1=x0+Δx, x2=x1+Δx, … Korak Δx određen je podjelom intervala [xmin,xmax] na odabrani broj odsječaka:
dx = (xmax-xmin) / 66
a niz apscisa dobivamo pozivom funkcije srange():
srange (xmin + 0.5*dx, xmax, dx)
Nagib tangente jednak je vrijednosti derivacije funkcije u apscisi točke u kojoj crtamo tangentu; za deriviranje funkcije f upotrijebit ćemo SageMath-ovu funkciju diff():
df = diff (f)
Na 7. predavanju izveli smo i izraz kojim je određena tangenta na graf funkcije f u točki (xi,f(xi)):
ℓ(x)=f′(xi)(x−xi)+f(xi)
Izraz se može neposredno prevesti u programski kôd:
l(x) = df(xi) * (x — xi) + f(xi)
Njime je definirana funkcija, pa je crtež tangente
pl = plot (l, xmin, xmax, ymin = ymin, ymax = ymax, color = 'orange')
Diralište tangente označavamo povećanom točkom:
pt = point ((xi, f(xi)), pointsize = 20, color = 'orange')
Graf derivacije funkcije crtamo samo do točke (xi,f′(xi)) čija je apscisa jednaka apscisi točke u kojoj crtamo tangentu:
pdf = plot (df, xmin, xi, ymin = ymin, ymax = ymax, color = 'red')
pt2 = point ((xi, df(xi)), pointsize = 15, color = 'red')
Prikaz više crteža na jednoj slici ostvaruje se, kao što znate, njihovim „zbrajanjem”:
pf + pl + pdf + pt + pt2
|
Nakon što oblikujemo listu slika, animirat ćemo je SageMath-ovom funkcijom animate().
![]() |
Brzinu izmjene slika možemo mijenjati primjenom SageMath-ove funkcije .show():
![]() |
Pozive funkcija tangents_plot_list(), animate() i .show() ćemo jednostavnije primjene radi uklopiti u funkciju animate_tangents():
|
Primjeri su primjene funkcije animate_tangents():
![]() |
![]() |
Oblikovanje liste crteža izdvojili smo u funkciju tangents_plot_list() jer će nam možda jednom ta lista ili pojedini crteži zatrebati za nešto drugo, a ne za animaciju. Primjerice, svaki crtež možemo zasebno prikazati.
![]() |
![]() |
![]() |
Jedno od „pravila” dobroga stila programiranja kaže da svaku „elementarnu” zadaću treba odvojiti u posebnu funkciju (u našemu primjeru tangents_plot_list()) pa zatim, po potrebi, takve funkcije pozivati u funkcijama namijenjenima rješavanju složenijih zadaća (animate_tangents()).
|