Osnove Algoritama

Sveuciliste u Zagrebu
Prirodoslovno-matematicki fakultet
Matematicki odsjek
OSNOVE ALGORITAMA
Predavanja
Vedran Krcadinac
Akademska godina 2010./2011.
Sadrzaj
1 Pojam algoritma 1
2 Brojevni sustavi 7
3 Nacini zapisivanja algoritama 19
4 Pseudojezik 27
5 Neki algoritmi za prirodne brojeve 39
6 Nizovi i sortiranje 53
7 Jos neki matematicki algoritmi 67
8 Prikaz brojeva u racunalu 81
9 Rjesenja nekih zadataka 87
Bibliograja 101
Poglavlje 1
Pojam algoritma
Pojam algoritma pokusat cemo objasniti kroz jednostavan primjer. Treba zbrojiti dva
velika prirodna broja bez kalkulatora, recimo 6247345 i 98492. Sjetimo se postupka za
zbrajanje naucenog u osnovnoj skoli:
1 1
6 2 4 7 3 4 5
+ 9 8 4 9 2
6 3 4 5 8 3 7
Ovdje nas ne zanima rezultat, nego postupak kojim do njega dolazimo to je prvi primjer
algoritma kojeg cemo obraditi!
Pokusajmo precizno zapisati algoritam za zbrajanje. Kao prvo, na ovaj nacin mozemo
zbrojiti bilo koja dva prirodna broja. Na pocetku ih moramo zadati. Ulazni podaci algo-
ritma za zbrajanje su dva prirodna broja zadana s pomocu svojih znamenaka:
(a
m
, a
m1
, . . . , a
2
, a
1
) i (b
n
, b
n1
, . . . , b
2
, b
1
), gdje su a
i
, b
j
0, 1, . . . , 9. Brojevi ne
moraju imati jednako mnogo znamenaka, tj. moze biti m ,= n. Medutim, mozemo
nadopisati vodece nule onom broju koji ima manje znamenaka. Tako ce zapis algoritma
za zbrajanje biti jednostavniji.
Ako oba broja na ulazu imaju n znamenaka, rezultat moze imati najvise n + 1 zna-
menaka. Izlazne podatke cini niz znamenaka zbroja (c
n+1
, c
n
, c
n1
, . . . , c
2
, c
1
). U slucaju
kada zbroj ima samo n znamenaka, stavljamo c
n+1
= 0. Racun opcenito izgleda ovako:
a
n
a
n1
a
2
a
1
+ b
n
b
n1
b
2
b
1
c
n+1
c
n
c
n1
c
2
c
1
Zbrajanje pocinjemo zdesna, od znamenaka jedinica. U prvom koraku racunamo a
1
+b
1
i
rezultat zapisemo na mjesto c
1
. U uvodnom primjeru imamo a
1
= 5 i b
1
= 2, pa je c
1
= 7.
Kad bismo algoritam za zbrajanje zeljeli analizirati do najjednostavnijih koraka, mogi
bismo se upitati otkud znamo da je 5+2 = 7? Takve male zbrojeve mozemo izracunati na
prste, no tijekom skolovanja zapamtili smo sve moguce zbrojeve znamenaka. Mozemo,
1
2 POGLAVLJE 1. POJAM ALGORITMA
dakle, reci da znamenke zbrajamo prema ovoj tablici:
+ 0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9 10
2 2 3 4 5 6 7 8 9 10 11
3 3 4 5 6 7 8 9 10 11 12
4 4 5 6 7 8 9 10 11 12 13
5 5 6 7 8 9 10 11 12 13 14
6 6 7 8 9 10 11 12 13 14 15
7 7 8 9 10 11 12 13 14 15 16
8 8 9 10 11 12 13 14 15 16 17
9 9 10 11 12 13 14 15 16 17 18
U drugom koraku racunamo 4 + 9 = 13, no na mjesto c
2
pisemo samo znamenku 3.
Znamenku desetice prenosimo u treci korak (pisem 3, pamtim 1). Radi jednostavnijeg
zapisa razdvojit cemo tablicu zbrajanja znamenaka na tablicu zbrojeva (koje potpisujemo
ispod trenutacnih znamenaka pribrojnika) i na tablicu prijenosa (koje pamtimo za sljedeci
korak, odnosno zabiljezimo iznad odgovarajucih znamenaka pribrojnika). Dakle, imamo
ove dvije tablice:
Zbroj 0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9 0
2 2 3 4 5 6 7 8 9 0 1
3 3 4 5 6 7 8 9 0 1 2
4 4 5 6 7 8 9 0 1 2 3
5 5 6 7 8 9 0 1 2 3 4
6 6 7 8 9 0 1 2 3 4 5
7 7 8 9 0 1 2 3 4 5 6
8 8 9 0 1 2 3 4 5 6 7
9 9 0 1 2 3 4 5 6 7 8
Prijenos 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 1
2 0 0 0 0 0 0 0 0 1 1
3 0 0 0 0 0 0 0 1 1 1
4 0 0 0 0 0 0 1 1 1 1
5 0 0 0 0 0 1 1 1 1 1
6 0 0 0 0 1 1 1 1 1 1
7 0 0 0 1 1 1 1 1 1 1
8 0 0 1 1 1 1 1 1 1 1
9 0 1 1 1 1 1 1 1 1 1
Na unose u tablicama pozivat cemo se s pomocu uglatih zagrada. Tako je npr. Zbroj[4, 9] =
3 i Prijenos[4, 9] = 1 jer je 4 + 9 = 13.
U trecem koraku zbrajamo znamenke a
3
= 3, b
3
= 4 i dodajemo im prijenos iz
prethodnog koraka. Taj prijenos moze biti samo 0 ili 1, zato nam je jednostavnije modi-
cirati tablice zbrajanja nego ih pozivati vise puta. Ako je prijenos iz prethodnog koraka 0,
3
koristimo gore navedene tablice, a ako je prijenos 1 ove modicirane tablice:
Zbroj2 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0 1
2 3 4 5 6 7 8 9 0 1 2
3 4 5 6 7 8 9 0 1 2 3
4 5 6 7 8 9 0 1 2 3 4
5 6 7 8 9 0 1 2 3 4 5
6 7 8 9 0 1 2 3 4 5 6
7 8 9 0 1 2 3 4 5 6 7
8 9 0 1 2 3 4 5 6 7 8
9 0 1 2 3 4 5 6 7 8 9
Prijenos2 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1 1
2 0 0 0 0 0 0 0 1 1 1
3 0 0 0 0 0 0 1 1 1 1
4 0 0 0 0 0 1 1 1 1 1
5 0 0 0 0 1 1 1 1 1 1
6 0 0 0 1 1 1 1 1 1 1
7 0 0 1 1 1 1 1 1 1 1
8 0 1 1 1 1 1 1 1 1 1
9 1 1 1 1 1 1 1 1 1 1
Dakle, u trecem koraku pisemo znamenku c
3
= Zbroj2[3, 4] = 8 i pamtimo Prijenos2[3, 4] =
0. Analogno nastavljamo dalje.
Zapisimo sada sto radimo u i-tom koraku algoritma. Neka p oznacava prijenos iz
prethodnog koraka. Ako je p = 0, znamenku c
i
i prijenos za sljedeci korak uzimamo iz
tablica Zbroj i Prijenos, a u slucaju p = 1 koristimo tablice Zbroj2 i Prijenos2. To
mozemo zapisati ovako:
ako je p = 0 onda
_
c
i
= Zbroj[a
i
, b
i
]
p = Prijenos[a
i
, b
i
]
inace
_
c
i
= Zbroj2[a
i
, b
i
]
p = Prijenos2[a
i
, b
i
]
Ovo ponavljamo za i = 1, 2, . . . , n. U prvom koraku nema prijenosa pa stavljamo p = 0,
a na kraju deniramo c
n+1
kao prijenos iz iz n-tog koraka. Zapis cijelog algoritma izgleda
ovako:
p = 0
za i = 1, . . . , n radi
_
_
ako je p = 0 onda
_
c
i
= Zbroj[a
i
, b
i
]
p = Prijenos[a
i
, b
i
]
inace
_
c
i
= Zbroj2[a
i
, b
i
]
p = Prijenos2[a
i
, b
i
]
c
n+1
= p
Sada kad smo upoznali jedan primjer algoritma, mozemo istaknuti neke opce znacajke
tog pojma. Opcenito, algoritam je postupak za rjesavanje neke klase problema. Pojedine
probleme iz te klase nazivamo instancama. Na pocetku poglavlja prisjetili smo se algo-
ritma za zbrajanje prirodnih brojeva kroz instancu 6247345 + 98492 problema zbrajanja.
Svaki algoritam uzima neke ulazne podatke; oni odreduju instancu problema na koji
ga primjenjujemo. Na kraju rada vraca izlazne podatke, koji predstavljaju rjesenje tog
problema. Kod algoritma za zbrajanje ulazni podaci su pribrojnici, a izlazni podaci njihov
zbroj.
Algoritam staje nakon konacno mnogo koraka, za svaku instancu problema kojeg
rjesava. Nije tesko napisati niz naredbi koji bi se izvodio beskonacno, ali takve programe
ne smatramo opisima algoritama. Nas algoritam za zbrajanje staje nakon n koraka ako
su na ulazu n-znamenkasti brojevi (ne racunajuci prvo i zadnje pridruzivanje).
Svaki korak od kojeg se sastoji algoritam je precizno i jednoznacno odreden. U praksi
mozemo imati jednostavnije ili kompliciranije korake, no bitno je da ih covjek ili stroj koji
izvodi algoritam moze izvrsavati tocno i bez dvosmislenosti.
Slika 1.1: Al-Khwarizmi (oko 790 840 g.)
1
.
Rijec algoritam potjece od perzijskog matematicara, astronoma i geografa iz 9.
stoljeca al-Khwarizmija (puno ime u engleskoj transkripciji glasi Muhammad ibn Musa
al-Khwarizmi ). Napisao je knjigu u kojoj je opisao postupke za racunanje u indijskom
brojevnom sustavu. Original na arapskom nije sacuvan, a latinski prijevod prosirio eu-
ropom pod naslovom Algoritmi de numero Indorum (Al-Khwarizmi o indijskim broje-
vima). Prema tom naslovu postupke za sustavno rjesavanje problema danas nazivamo
algoritmima. Stariji naziv algorizam ponekad se koristi u uzem, aritmetickom smislu
2
.
Al-Khwarizmi napisao je jos jednu iznimno vaznu knjigu, Hisab al-jabr wal-muqabala,
u kojoj se bavi rjesavanjem linearnih i kvadratnih jednadzbi. Matematicka disciplina alge-
bra dobila je ime po drugoj rijeci iz tog naslova. S danasnjeg stanovista problemi kojima se
al-Khwarizmi bavi mogu se ciniti trivijalnim. Medutim, tehniku njihovog rjesavanja dugu-
jemo upravo Al-Khwarizmiju: postavimo problem u obliku algebarskih jednadzbi i prim-
jenjujemo unaprijed zadana pravila da bismo dosli do rjesenja. Trivijalizacija problema
koji se svode na linearne ili kvadratne jednadzbe posljedica je duboke algoritmizacije
matematike. Formula za rjesenja kvadratne jednadzbe
x
1,2
=
b
b
2
4ac
2a
zapravo je sazet opis algoritma kojim od koecijenata jednadzbe ax
2
+bx+c = 0 dolazimo
do njezinih rjesenja.
1
Slika je preuzeta s web stranice [19].
2
U Klaicevom rjecniku stranih rijeci [14] algoritam se denira kao pravilan postupak pri racunanju.
5
Vratimo se algoritmima za osnovne aritmeticke operacije. U skoli smo osim algoritma
za zbrajanje naucili algoritme za oduzimanje, mnozenje, dijeljenje, mozda cak i algoritam
za racunanje priblizne vrijednosti drugog korijena. Mnoga djeca ne vole matematiku
upravo zbog inzistiranja na mehanickom savladavanju takvih racunskih rutina
3
.
Cilj ove skripte nije ucenje izabranih algoritama napamet, nego razvijanje sposobnosti
razumijevanja i kreiranja novih algoritama. Za to nam je nuzna vjestina preciznog zapi-
sivanja algoritama i citanja s razumijevanjem algoritama koji je netko drugi napisao.
Po misljenju autora, da bi se to savladalo potrebno je upoznati neke vazne algoritme
i samostalno rijesiti odreden broj zadataka u kojima se trazi razvijanje algoritma za
neki problem.

Citatelje takoder poticemo da algoritme koje cemo upoznati pokusaju
implementirati u nekom programskom jeziku. Pritom treba savladati odredene tehnicke
prepreke, ali na taj nacin alogitmi ozive i dobiva se mogucnost testiranja, isprobavanja
s raznim ulaznim podacima i jednostavnog modiciranja algoritama. Izbor programskog
jezika manje je vazan. Koristit cemo uglavnom naredbe i koncepte koji postoje u svima,
ili barem u vecini programskih jezika
4
.
Zadaci
Zadatak 1.1. Dokazite da zbrajanjem dvaju n-znamenkastih prirodnih brojeva dobivamo
broj s najvise n + 1 znamenaka.
Zadatak 1.2. Zapisite algoritam za mnozenje prirodnih brojeva naucen u osnovnoj skoli!
Koraci algoritma mogu biti slozenijih od onih koje smo koristili u zapisu algoritma za
zbrajanje, npr. mozete koristiti zbrajanje viseznamenkastih brojeva kao poznatu operaciju.
Zadatak 1.3. Na slican nacin zapisite algoritam za dijeljenje prirodnih brojeva naucen
u osnovnoj skoli.
Zadatak 1.4. Sjetite se i zapisite algoritam za rucno vadenje drugog korijena, u kojem
se znamenke grupiraju po dvije.
Zadatak 1.5. Pokusajte izmisliti i zapisati alternativne algoritme za osnovne racunske
operacije, razlicite od onih koje ste naucili u skoli.
3
U americkom skolskom kurikulumu Everiday mathematics djecu se potice da razviju vlastite pos-
tupke za racunanje i upoznaje ih se s alternativnim algoritmima za osnovne aritmeticke operacije; vidi [25].
4
Prethodnih akademskih godina na vjezbama iz kolegija Osnove algoritama zadaci su se radili u
programskim jezicima C, Pascal i Python.
Poglavlje 2
Brojevni sustavi
Razvoj sustava za zapisivanje brojeva mozemo smatrati pocetkom matematike. Jedan od
najranijih poznatih sustava razvili su Babilonci oko 2000 godine prije Krista. Danasnji
nacin zapisivanja brojeva potjece iz Indije i vjerojatno je nastao krajem 6. stoljeca.
Ponekad se takvi brojevi nazivaju arapskim, jer su ih u srednjem vijeku Arapi donijeli
u Europu. Taj je sustav zapisivanja brojeva omogucio razvoj algoritama za racunanje
o kojima smo govorili u prethodnom poglavlju. U drugom poznatom sustavu, rim-
skom aditivno-suptraktivnom sustavu, racunanje je vrlo nespretno. Pokusajte direktno
pomnoziti brojeve CXVII i XXIV!
Slika 2.1: Znamenke u babilonskom brojevnom sustavu
1
.
U indijsko-arapskom sustavu koristi se deset znamenaka 0, 1, 2, 3, 4, 5, 6, 7, 8 i
9. Znacenje znamenaka ovisi o polozaju u zapisu broja, zato se takvi sustavi nazivaju
pozicionim. Naprimjer, zapis 2562 znaci 2 10
3
+5 10
2
+6 10+2 (prva i zadnja znamenka
2 ne doprinose isto!). Istaknuta uloga broja 10 posljedica je cinjenice da ljudi imaju 10
prstiju. Na isti nacin mozemo zapisivati brojeve koristeci se bilo kojim skupom od b
razlicitih simbola, gdje je b 2 prirodan broj koji nazivamo bazom.
1
Slika je preuzeta s web stranice [20].
7
8 POGLAVLJE 2. BROJEVNI SUSTAVI
Tijekom povijesti koristili su se i sustavi s bazom 20, a spomenuti babilonski sustav
bio je pozicioni s bazom 60. Babilonci ipak nisu imali 60 razlicitih simbola, nego su
znamenke zapisivali aditivno s pomocu dvaju simbola (vidi sliku 2.1). U racunarstvu su
posebno pogodni sustavi kojima je baza potencija od 2. Sustav s bazom b = 2 naziva se
binarnim sustavom, sustav s bazom b = 3 ternarnim sustavom i tako dalje. Uobicajeni
sustav s bazom b = 10 zovemo dekadskim sustavom, a koriste se i oktalni sustav (b = 8) te
heksadecimalni sustav (b = 16). Naprimjer, binarni broj (101101)
2
znaci 1 2
5
+0 2
4
+1
2
3
+1 2
2
+0 2+1, a oktalni broj (2763)
8
predstavlja 2 8
3
+7 8
2
+6 8+3. U sustavima s
bazom manjom od 10 kao znamenke koristimo podskup uobicajenih dekadskih znamenaka.
U heksadecimalnom sustavu trebamo 16 simbola, pa se uz dekadske znamenke koristimo
slovima A, B, C, D, E i F koja redom predstavljaju brojeve od 10 do 15. Heksadecimalni
broj (7A9FE)
16
znaci 7 16
4
+ 10 16
3
+ 9 16
2
+ 15 16 + 14.
Opcenito, u sustavu s bazom b skup simbola identiciramo s brojevima koje pred-
stavljaju: 0, 1, 2, . . . , b 1. Zapis (x
k
x
k1
x
1
x
0
)
b
sa znamenkama x
i
iz tog skupa
predstavlja broj x
k
b
k
+ x
k1
b
k1
+ . . . + x
1
b + x
0
. S pomocu ove denicije brojeve
zapisane u bazi b lako mozemo prevesti u uobicajeni dekadski zapis.
Primjer 2.1. Zapisimo brojeve (1011011)
2
, (123)
4
i (BABA)
16
u dekadskom sustavu.
Rjesenje. Po deniciji, vrijedi (1011011)
2
= 2
6
+ 2
4
+ 2
3
+ 2 + 1 = 91. Kada u zapisu
ne istaknemo bazu, podrazumijevat cemo da je dekadski (b = 10). Analogno dobivamo
(123)
4
= 1 4
2
+2 4 +3 = 27 i (BABA)
16
= 11 16
3
+10 16
2
+11 16 +10 = 47802.
Valjanost pozicionih sustava pociva na cinjenici da se svaki prirodan broj moze na
jedinstven nacin zapisati u sustavu s bilo kojom bazom.
Teorem 2.2. Neka je b 2 zadani prirodan broj. Za svaki prirodan broj n postoji
jedinstveni niz znamenaka (x
k
, . . . , x
1
, x
0
), x
i
0, 1, . . . , b 1, x
k
,= 0, takav da je
n = x
k
b
k
+ . . . + x
1
b + x
0
.
Za dokaz ovog teorema trebat ce nam teorem o dijeljenju s ostatkom.
Teorem 2.3 (o dijeljenju s ostatkom). Neka su m, n N prirodni brojevi. Tada postoje
jedinstveni brojevi k, o N
0
, o < n takvi da je m = k n + o.
Broj k zovemo kvocijentom ili kolicnikom, a broj o ostatkom dijeljenja. Zbog njihove
jedinstvenosti mozemo uvesti oznake k = m div n i o = m mod n. Naprimjer, 17 div 5 =
3 i 17 mod 5 = 2 jer je 17 = 3 5 + 2. Dokazimo sada teorem 2.2.
Dokaz. Trebamo dokazati egzistenciju i jedinstvenost prikaza broja n u bazi b. Egzis-
tenciju cemo dokazati konstruktivno, opisujuci algoritam za nalazenje trazenog prikaza.
Oznacimo n
0
= n i podijelimo taj broj s b. Kvocijent oznacimo n
1
, a ostatak x
0
:
n
0
= n
1
b + x
0
.
Zatim podijelimo n
1
s b uz kvocijent n
2
i ostatak x
1
:
n
1
= n
2
b + x
1
.
9
Postupak analogno nastavimo dalje:
n
2
= n
3
b + x
2
,
n
3
= n
4
b + x
3
,
.
.
.
n
k
= 0 b + x
k
.
Zaustavljamo se kada kvocijent postane 0. Svi daljnji kvocijenti n
i
i ostaci x
i
bili bi 0.
Opisani postupak ovako mozemo zapisati u obliku algoritma:
n
0
= n
i = 0
dok je n
i
,= 0 radi
_
_
x
i
= n
i
mod b
n
i+1
= n
i
div b
i i + 1
Naredba i i + 1 u zadnjem retku povecava vrijednost varijable i za jedan.
Da bi ovo zaista bio dokaz egzistencije prikaza u bazi b, trebamo se uvjeriti da postupak
staje nakon konacno mnogo koraka i da denira trazeni prikaz. Svaki sljedeci n
i
dobivamo
od prethodnog cjelobrojnim dijeljenjem s b 2. Jasno je da ce nakon konacno mnogo
koraka rezultat biti 0 i tada algoritam staje. Jos treba provjeriti da su ostaci x
0
, . . . , x
k

0, . . . , b1 zaista znamenke od n u bazi b. Pretpostavimo da smo nakon k koraka dobili
kvocijent n
k+1
= 0. U prethodnom koraku denirali smo n
k
= n
k+1
b+x
k
= 0b+x
k
= x
k
.
Supstitucijom u prethodne korake dobivamo redom
n
k1
= n
k
b + x
k1
= x
k
b + x
k1
,
n
k2
= n
k1
b + x
k2
= (x
k
b + x
k1
) b + x
k1
= x
k
b
2
+ x
k1
b + x
k2
,
.
.
.
n
0
= n
1
b + x
0
= (x
k
b
k1
+ . . . + x
1
) b + x
0
= x
k
b
k
+ . . . + x
1
b + x
0
.
Vidimo da n = n
0
ima prikaz (x
k
x
1
x
0
)
b
. Sada jos treba provjeriti jedinstvenost tog
prikaza. Pretpostavimo da n ima jos jedan prikaz (y
l
y
1
y
0
)
b
. Tada je n = (x
k
b
k1
+
. . . + x
1
) b + x
0
= (y
l
b
l1
+ . . . + y
1
) b + y
0
. Podijelimo li taj izraz cjelobrojno s b,
zbog jedinstvenosti u teoremu o dijeljenju s ostatkom dobivamo da je x
0
= y
0
= n mod b
i x
k
b
k1
+. . . +x
2
b +x
1
= y
l
b
l1
+. . . +y
2
b +y
1
= n div b. Posljednji izraz ponovo
dijelimo s b i dobivamo x
1
= y
1
i tako dalje. Buduci da su sve znamenke jednake (x
i
= y
i
,
i = 0, 1, 2, . . . ), vodeca nenul znamenka se takoder podudara pa su zapisi jednake duljine
(k = l). Ta se duljina moze izraziti kao funkcija od n i od b, sto ostavljamo citateljima
kao zadatak.
Kroz ovaj dokaz ujedno smo dobili postupak kojim broj n zapisan u dekadskom sustavu
mozemo prevesti su sustav s bilo kojom bazom b. Algoritam iz dokaza izvodimo na papiru
tako da desno od broja n povucemo vertikalnu crtu i uzastopno ga dijelimo s bazom.
Ostatke dijeljenja pisemo desno od crte, a kvocijente lijevo, jedan ispod drugog.
Primjer 2.4. Zapisimo broj n = 3761 u sustavu s bazom b = 7.
Rjesenje. Dijeljenjem sa 7 dobivamo kvocijent 537 i ostatak 2.
3761 2
537
Zatim podijelimo 537 sa 7, kvocijent 76 napisemo ispod, a ostatak 5 desno od crte:
3761 2
537 5
76
Nastavimo dijeliti sa 7, rezultate pisati ispod, a ostatke desno.
3761 2
537 5
76 6
10 3
1 1
0
Kada dobijemo nulu, procitamo ostatke odozdo prema gore i imamo zapis n = (13652)
7
.
Broj zapisan u bazi b
1
mozemo prevesti u bazu b
2
tako da ga najprije zapisemo u
dekadskom sustavu, a zatim prebacimo u bazu b
2
algoritmom koji smo upoznali. Ako su
b
1
i b
2
potencije istog broja, to mozemo uciniti ekasnije grupiranjem ili prosirivanjem
znamenaka.
Primjer 2.5. Zapisimo binarni broj (10110111101)
2
u oktalnom sustavu.
Rjesenje. Najprije znamenke grupiramo po 3 zdesna na lijevo:
10[110[111[101

2 6 7 5
Istaknute nizove triju binarnih znamenaka prevodimo u po jednu oktalnu: 000 0,
001 1, 010 2, . . . , 111 7. Vodecu grupu znamenaka 10 tretiramo kao 010. Tako
dobivamo zapis (2675)
8
.
Primjer 2.6. Zapisimo heksadecimalni broj (2A9)
16
u binarnom sustavu.
Rjesenje. Svaku heksadecimalnu znamenku prevodimo u niz od 4 binarne znamenke: 0
0000, 1 0001, 2 0010, . . . , 9 1001, A 1010, . . . , F 1111. Vodece nule prvog
po redu niza zanemarujemo. Tako dolazimo do zapisa (1010101001)
2
.
11
Primjer 2.7. Zapisimo oktalni broj (6251)
8
u heksadecimalnom sustavu.
Rjesenje. Prvo oktalni broj pretvorimo u binarni:
6 2 5 1

110[010[101[001
Zatim grupiramo binarne znamenke po cetiri i prevedemo ih u hekdadecimalne:
1100[1010[1001

C A 9
Dobili smo broj (CA9)
16
.
Algoritmi za osnovne racunske operacije koje smo naucili u skoli funkcioniraju u sus-
tavu s bilo kojom bazom. Postupci su potpuno analogni onima u dekadskom sustavu,
samo treba prilagoditi tablice zbrajanja i mnozenja znamenaka. Naprimjer, u binarnom
sustavu je (1)
2
+ (1)
2
= (10)
2
(pisem 0, pamtim 1).
Primjer 2.8. Izracunajmo zbroj (12201)
3
+ (2121)
3
u ternarnom sustavu.
Rjesenje. Treba nam tablica zbrajanja ternarnih znamenaka:
+ 0 1 2
0 0 1 2
1 1 2 10
2 2 10 11
Postupak izgleda ovako:
1 1
1 2 2 0 1
+ 2 1 2 1
2 2 0 2 2
Rezultat je broj (22022)
3
.
Primjer 2.9. Izracunajmo razliku (421314)
5
(34123)
5
u sustavu s bazom 5.
Rjesenje. I za oduzimanje koristit cemo se tablicom zbrajanja znamenaka u bazi 5.
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 10
2 2 3 4 10 11
3 3 4 10 11 12
4 4 10 11 12 13
Postupak pocinje isto kao u dekadskom sustavu:
4 2 1 3 1 4
3 4 1 2 3
1
Oduzimamo najdesnije znamenke (4)
5
(3)
5
= (1)
5
i rezultat pisemo ispod crte. U
iducem koraku trebali bismo oduzeti vecu znamenku od manje. Posudujemo jedinicu
sa sljedece pozicije i umjesto (1)
5
(2)
5
racunamo (11)
5
(2)
5
. U tablici zbrajanja
pronalazimo (2)
5
+ (4)
5
= (11)
5
, pa je rezultat znamenka 4.
2
4 2 1 ,3 1 4
3 4 1 2 3
4 1
Sada zbog posudene jedinice ne racunamo (3)
5
(1)
5
, nego (2)
5
(1)
5
= (1)
5
.
2
4 2 1 ,3 1 4
3 4 1 2 3
1 4 1
U iduca dva koraka takoder posudujemo jedinice sa sljedecih pozicija.
3 1 2
,4 ,2 1 ,3 1 4
3 4 1 2 3
3 3 2 1 4 1
Rezultat je (332141)
5
.
Primjer 2.10. Izracunajmo umnozak (1011011)
2
(1101)
2
u binarnom sustavu.
Rjesenje. Mnozenje je u binarnom sustavu posebno jednostavno jer su jedine znamenke 0
i 1, pa nam tablice ne trebaju. Za svaku znamenku jedinice iz desnog faktora potpisujemo
lijevi faktor pomaknut odgovarajuci broj mjesta udesno.
1 0 1 1 0 1 1 1 1 0 1
1 0 1 1 0 1 1
1 0 1 1 0 1 1
0
+ 1 0 1 1 0 1 1
1 0 0 1 0 0 1 1 1 1 1
Zbrajanjem potpisanih brojeva dobivamo umnozak (10010011111)
2
.
13
Primjer 2.11. Izracunajmo umnozak (3122)
4
(232)
4
Rjesenje. Za ovaj racun trebaju nam tablice zbrajanja i mnozenja u bazi 4.
+ 0 1 2 3
0 0 1 2 3
1 1 2 3 10
2 2 3 10 11
3 3 10 11 12
1 2 3
1 1 2 3
2 2 10 12
3 3 12 21
Mnozimo (3122)
4
s prvom znamenkom drugog faktora 2, zdesna na lijevo. U tablici
nalazimo produkt znamenaka (2)
4
(2)
4
= (10)
4
, pisemo znamenku 0 i prenosimo 1 u
sljedeci korak. U drugom koraku racunamo (2)
4
(2)
4
+ (1)
4
= (11)
4
, pisemo 1 ponovo
prenosimo 1. U trecem koraku pisemo (2)
4
(1)
4
+ (1)
4
= (3)
4
, a u cetvrtom (2)
4
(3)
4
=
(12)
4
:
1 1
3 1 2 2 2 3 2
1 2 3 1 0
Na slican nacin mnozimo (3122)
4
sa znamenkom 3 i rezultat zapisujemo jedno mjesto
udesno.
1 1 1
3 1 2 2 2 3 2
1 2 3 1 0
2 2 0 3 2
Na kraju ponovno mnozimo s 2 i zbrajamo tri produkta.
3 1 2 2 2 3 2
1 2 3 1 0
2 2 0 3 2
+ 1 2 3 1 0
2 1 3 0 2 3 0
Rezultat je (2130230)
4
.
Primjer 2.12. U binarnom sustavu podijelimo brojeve (100011)
2
: (111)
2
.
Rjesenje. Dijeljenje je jednostavnije u binarnom nego u dekadskom sustavu. Da bismo
odredili prvu znamenku kvocijenta, moramo procijeniti koliko puta djelitelj stane u
pocetni niz znamenaka djeljenika. U binarnom sustavu odgovor moze biti samo 0 ili 1!
1 0 0 0 1 1 : 1 1 1 =1
1 1 1
1 1
Broj (111)
2
oduzimamo od prve cetiri znamenke broja (100011)
2
i zatim spustamo
sljedecu znamenku. Dobili smo broj (11)
2
koji je manji od djelitelja, pa na rezultat
dijeljenja dodajemo 0 i spustamo jos jednu znamenku djeljenika.
1 0 0 0 1 1 : 1 1 1 =1 0
1 1 1
1 1 1
Sada djelitelj stane tocno jednom u (111)
2
i vidimo da je kvocijent (101)
2
:
1 0 0 0 1 1 : 1 1 1 =1 0 1
1 1 1
1 1 1
1 1 1
0
Osim prirodnih brojeva u sustavima s razlicitim bazama mozemo zapisivati cijele,
racionalne i realne brojeve. Broj nula u svim sustavima zapisujemo kao 0. Zanimljivo
je da u Babilonskom heksadecimalnom sustavu nije bilo posebnog simbola za nulu. Vri-
jednost broja morala se pogadati iz konteksta i razmaka medu znamenkama. Negativne
cijele brojeve zapisujemo na uobicajen nacin, sa znakom ispred zapisa. Naprimjer,
(1100)
2
je binarni zapis broja 12.
Razlomci su omjeri cijelog i prirodnog broja i mozemo ih tako zapisivati. Druga
mogucnost je da prosirimo pozicioni sustav i dozvolimo negativne potencije baze, analogno
decimalnim brojevima
2
u dekadskom sustavu. Decimalni zapis 27.69 predstavlja broj
2 10
1
+ 7 10
0
+ 6 10
1
+ 9 10
2
. Opcenito, zapis (x
k
x
1
x
0
.x
1
x
m
)
b
znaci
x
k
b
k
+ . . . + x
1
b
1
+ x
0
b
0
+ x
1
b
1
+ . . . + x
m
b
m
. Pritom su k, m N, a
x
k
, . . . , x
0
, . . . , x
m
0, . . . , b 1 su znamenke.
Primjer 2.13. Zapisimo razlomak 91/16 u binarnom sustavu.
Rjesenje. Rjesenje mozemo dobiti tako da brojnik 91 = (1011011)
2
i nazivnik 16 =
(10000)
2
zapisemo u binarnom sustavu i primijenimo algoritam za dijeljenje:
1 0 1 1 0 1 1 : 1 0 0 0 0 =1 0 1
1 0 0 0 0
1 1 0 1 1
1 0 0 0 0
1 0 1 1
Dobili smo kvocijent (101)
2
i ostatak (1011)
2
, koji nastavljamo dijeliti spustanjem nula.
2
Prema pravopisu decimalne brojeve trebali bismo pisati sa zarezom umjesto s tockom, tj. kao 27, 69.
U ovoj knjizi ipak cemo se koristiti decimalnom tockom zbog citljivijeg zapisa nizova decimalnih brojeva.
Pisat cemo 1.1, 1.2, 1.3. . . umjesto 1, 1, 1, 2, 1, 3. . . .
15
Znamenke koje dobivamo biljezimo iza znaka tocke.
1 0 1 1 0 1 1 : 1 0 0 0 0 =1 0 1 . 1 0 1 1
1 0 0 0 0
1 1 0 1 1
1 0 0 0 0
1 0 1 1 0
1 0 0 0 0
1 1 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
0
Rezultat je (101.1011)
2
. Alternativno, razlomak 91/16 = 5
11
16
mozemo zapisati u binarnom
sustavu prevodeci posebno cjelobrojni dio 5, a zatim decimalni dio
11
16
. Za cjelobrojni
dio koristimo algoritam uzastopnog dijeljenja s bazom, koji smo ranije upoznali:
5 1
2 0
1 1
0
Znamenke iza tocke dobivamo dualnim algoritmom. Pomnozimo brojnik 11 s bazom 2
i cjelobrojno ga podijelimo s nazivnikom. Kvocijent 22 div 16 = 1 je prva znamenka i za-
pisujemo ga desno od crte, a ostatak 22 mod 16 = 6 zapisujemo ispod i s njim nastavljamo
postupak.
11 1
6
Produkt 2 6 = 12 daje rezultat 0 i ostatak 12 pri dijeljenju s nazivnikom 16.
11 1
6 0
12
Nadalje, 2 12 = 24 daje rezultat 1 i ostatak 8 pri dijeljenju s 16.
11 1
6 0
12 1
8 1
0
U zadnjem koraku 2 8 = 16 djeljiv je bez ostatka s nazivnikom pa algoritam staje.
Znamenke cjelobrojnog dijela pisemo od decimalne tocke ulijevo (redom kojim smo ih
dobivali), a znamenke decimalnog dijela udesno: (101.1011)
2
.
U prethodnom primjeru razlomak ima konacni zapis. Kada razlomak do kraja skra-
timo i u nazivniku ostane prosti faktor koji ne dijeli bazu, dobivamo beskonacni periodicni
zapis.
Primjer 2.14. Zapisimo razlomak 7/15 u ternarnom sustavu.
Rjesenje. Koristimo se algoritmom uzastopnog mnozenja s bazom b = 3 i dijeljenja s
nazivnikom 15, kojeg smo upoznali u prethodnom primjeru.
7 1
6 1
3 0
9 1
12 2
6
U petom koraku dobili smo ostatak 3 12 mod 15 = 6, koji smo vec imali u prvom koraku.
To znaci da ce se u nastavku ponavljati niz ternarnih znamenaka 1012. Razlomak ima
zapis (0.11012101210121012 . . .)
3
, sto krace zapisujemo kao (0.11012)
3
ili (0.1
101
2)
3
.
Pokazuje se da svi razlomci imaju beskonacne periodicne zapise. Konacni zapis
shvacamo kao periodicni u kojem se ponavlja znamenka 0. Iracionalni brojevi kao
2,
i e i imaju beskonacne neperiodicne zapise u pozicionom sustavu s bilo kojom bazom. Uz
odredeni tehnicki dogovor, svaki realan broj ima jedinstven zapis u sustavu s bazom b.
Problem nastaje upravo zbog brojeva s konacnim zapisom. Naime, umjesto ponav-
ljanja znamenke 0, broj mozemo zapisati ponavljanjem najvece znamenke b1. Naprimjer,
broj 1 u dekadskom sustavu mozemo zapisati kao 1.000 . . . ili 0.999 . . .. Da bismo osigurali
jedinstvenost zapisa drugu mogucnost zabranjujemo.
Teorem 2.15. Neka je b 2 prirodan broj. Za svaki realan broj x > 0 postoji jedinstveni
cijeli broj k i niz znamenaka x
i
0, . . . , b 1, i k takav da je x
k
,= 0, x =
ik
x
i
b
i
i
da ne postoji m takav da je x
i
= b 1 za sve i m.
Nulu zapisujemo kao 0, a negativne realne brojeve s pomocu znaka . Dokaz ovog
teorema za b = 10 nalazi se u knjizi [21] na str. 35 (teorem 2).
Za racunanje s realnim brojevima zapisanim na ovaj nacin koristimo iste algoritme
kao za prirodne brojeve. Pritom zapis ogranicavamo na konacan broj znamenaka kako bi
algoritmi stali u konacno mnogo koraka. Kod zbrajanja pazimo da pribrojnike potpisemo
s tockom na odgovarajucim mjestima, kod mnozenja je broj znamenaka iza tocke u pro-
duktu jednak zbroju broja znamenaka iza tocke u faktorima itd. Neke probleme koji nas-
taju zbog ogranicenja na konacan broj znamenaka upoznat cemo u poglavlju o prikazu
brojeva u racunalu.
Zadaci
Zadatak 2.1. Opisite algoritam za zbrajanje brojeva u rimskom brojevnom sustavu.
17
Zadatak 2.2. Dokazite teorem o dijeljenju s ostatkom.
Zadatak 2.3. Napisite formulu za broj znamenaka prirodnog broja n u zapisu s bazom b.
Zadatak 2.4. Zapisite brojeve (100110111)
2
, (1201221)
3
, (42310)
5
, (2147)
8
i (DEDA)
16
u dekadskom sustavu.
Zadatak 2.5. Zapisite dekadski broj 5790 u sustavima s bazom 2, 3, 8 i 16.
Zadatak 2.6. Grupiranjem znamenaka pretvorite heksadecimalni broj (8D6E)
16
u oktalni
sustav.
Zadatak 2.7. Zbrojite direktno, bez pretvaranja u dekadski sustav (1111011)
2
+(10110)
2
,
(122)
3
+ (211)
3
+ (101)
3
+ (120)
3
+ (222)
3
i (BABA)
16
+ (DEDA)
16
.
Zadatak 2.8. Oduzmite direktno, bez pretvaranja u dekadski sustav (110011011)
2
(110110)
2
i (1302)
4
(123)
4
.
Zadatak 2.9. Pomnozite direktno, bez pretvaranja u dekadski sustav (1101)
2
(101)
2
i
(21201)
3
(1022)
3
.
Zadatak 2.10. Podijelite direktno, bez pretvaranja u dekadski sustav (110323)
5
: (401)
5
i (1101)
2
: (110)
2
.
Zadatak 2.11. Precizno zapisite algoritme za zbrajanje, oduzimanje, mnozenje i dijel-
jenje u binarnom sustavu.
Zadatak 2.12. Zapisite brojeve (102.21)
3
, (0.4)
7
i (3.032)
5
kao razlomke i kao decimalne
brojeve u sustavu s bazom 10.
Zadatak 2.13. Zapisite dekadski broj 17.3125 u binarnom i u ternarnom sustavu.
Zadatak 2.14. Precizno zapisite algoritam za pretvaranje razlomka manjeg od 1 u sustav
s bazom b uzastopnim mnozenjem s bazom i dijeljenjem s nazivnikom, opisan u primje-
rima 2.13 i 2.14.
Zadatak 2.15. Prosirivanjem i grupiranjem znamenaka pretvorite broj (123.4567)
8
u
sustav s bazom 2 te brojeve (10111011.101)
2
i (443.5274)
8
u sustav s bazom 16.
Zadatak 2.16. Odredite bazu b takvu da broj (235)
b+1
bude dvostruko veci od broja (141)
b
.
Zadatak 2.17. Odredite sesteroznamenkasti broj u sustavu s bazom 5 kojemu je zadnja
znamenka 2 i koji se poveca dva puta kad zadnju znamenku premjestimo na prvo mjesto.
Rezultat zapisite u sustavu s bazom 5.
Zadatak 2.18. Odredite bazu b u kojoj je moguc racun (11x)
b
+(x3y)
b
= (3y0)
b
, za neke
znamenke x i y.
Zadatak 2.19. Neka je b 2 prirodan broj. Zapisite brojeve (bbb)
b
2 i (b.b)
b
2 u sustavu s
bazom b.
Zadatak 2.20. Dokazite da se svaki prirodan broj n moze na jedinstven nacin prikazati
u obliku n = x
k
k! + x
k1
(k 1)! + . . . + x
2
2! + x
1
1!, pri cemu su znamenke
x
i
0, 1, . . . , i, i = 1, . . . , k te vrijedi x
k
,= 0. Pisemo n = (x
k
x
k1
x
2
x
1
)
!
. To je
takozvani faktorijelski brojevni sustav.
Zadatak 2.21. Fibonaccijevi brojevi denirani su s F
0
= 0, F
1
= 1 i s rekurzijom F
k+1
=
F
k
+ F
k1
za k N. Dokazite da se svaki prirodan broj n moze prikazati kao zbroj
medusobno razlicitih Fibonaccijevih brojeva n = F
k
1
+F
k
2
+. . . +F
kr
. Ako zahtjevamo da
pritom vrijedi k
i+1
k
i
2, i = 1, . . . , r 1 i k
r
2, takav prikaz je jedinstven. Ovaj
nacin prikazivanja brojeva naziva se Fibonaccijevim brojevnim sustavom.
Poglavlje 3
Nacini zapisivanja algoritama
U prethodnom poglavlju upoznali smo algoritme za osnovne aritmeticke operacije i za
prevodenje brojeva iz baze u bazu. Neke od tih algoritama nastojali smo precizno zapisati,
dok smo druge opisali neformalno ili smo ih objasnili kroz primjere i zadatke. Taj je
pristup prikladniji kod poducavanja. Ne bi bilo mudro skolsku djecu uciti zbrajanje tako
da im se na plocu napise algoritam iz prvog poglavlja.
Potreba za preciznim zapisivanjem algoritama pojavila se s razvojem racunskih stro-
jeva. U prvoj polovici 19. stoljeca engleski matematicar, inzenjer i izumitelj Charles
Babbage projektirao je prvo univerzalno racunalo, sposobno izvoditi razlicite proracune
ovisno o programu koji se u njega unese. Babbage je stroj nazvao Analytical engine i
do kraja zivota nije ga uspio izgraditi. Ipak, u suradnji s Adom Lovelace
1
razvijao je prve
programe za svoj mehanicki kompjuter. Mnogo kasnije programski jezik Ada nazvan je
po prvoj programerki Adi Lovelace.
Sredinom 20. stoljeca izgradena su prva elektronicka racunala. Tehnologiju elektron-
skih cijevi ubrzo su zamijenili tranzistori, a u 70-tim godinama poluvodicki integrirani
krugovi. S minijaturizacijom racunala postaju sve brza i sve mocnija. Svjedoci smo da se
taj proces nastavlja i danas.
Prva elektronicka racunala programirala su se u strojnom jeziku, naredbama koje
izvodi procesor. Kao pomoc u programiranju razvijeni su tzv. asembleri, programi koji
prevode simbolicke naredbe u strojne i pomazu pri adresiranju memorije. Stoga se takvi
programski jezici nazivaju i asemblerskim jezicima.
Prvi visi programski jezik bio je FORTRAN (od engleskog FORmula TRANslator),
razvijen 1954. Jos neki od ranih programskih jezika iz tog doba su LISP, Cobol, Algol i
Basic. Da bi se programi pisani u tim jezicima mogli izvoditi na racunalu, potrebno ih je
najprije prevesti na strojni jezik. To se radi s pomocu posebnih programa prevoditelja ili
kompilatora (eng. compiler). Jedna naredba viseg programskog jezika tipicno se prevodi
u vise strojnih naredbi.
U 70-tim godinama 20. stoljeca razvijeni su mnogi specijalizirani programski jezici.
Programski jezik Pascal razvijen je za ucenje strukturiranog programiranja. Programski
jezik C originalno je razvijen za sistemsko programiranje, zajedno s operacijskim sustavom
Unix. Oba su postala vrlo popularna i C se do danas koristi za mnoge druge svrhe. Iz
1
Augusta Ada King, vojvotkinja od Lovelacea, bila je matematicarka i kci poznatog pjesnika lorda
Byrona.
19
20 POGLAVLJE 3. NA
CINI ZAPISIVANJA ALGORITAMA

tog razdoblja potjecu i prvi objektno orijentirani programski jezici Simula i Smalltalk.
Razvoj novih programskih jezika i novih inacica postojecih nastavljen je u 80-tim i
90-tim godinama. Godine 1983. deniran je vec spomenuti programski jezik Ada, s ciljem
standardizacije softvera pisanog za Ministarstvo obrane Sjedinjenih americkih drzava. Iste
godine razvijen je C++, objektno orijentirana inacica jezika C. Godine 1987. razvijen je
skriptni jezik Perl, a 1991. Python. Takvi jezici ne prevode se s pomocu kompilatora, nego
ih izvodi takozvani interpreter, program koji paralelno prevodi i izvodi naredbe. Takoder,
1991. godine razvijen je jezik Java koji je postao popularan za pisanje aplikacija za web.
U 90-tim godinama sve je vise programskih jezika namijenjenih za internet, naprimjer
PHP razvijen 1995. godine.
Za buduce nastavnike vazni su edukacijski programski jezici namijenjeni djeci. Jedan
od najpoznatijih je LOGO, razvijen 1967. i poznat po takozvanoj kornjacinoj graci.
Od 2007. godine slobodno je dostupan programski jezik Scratch [23] razvijen na MIT-
u. Postoje inacice za razne operacijske sustave i na hrvatskom jeziku. Scratch takoder
omogucuje kornjacinu graku, ali i puno vise od toga. Zanimljiv je zato sto se programira
bez pisanja, slaganjem pravokutnika i okvira s naredbama (vidi sliku 3.1).
Vrlo rano uocena je potreba zapisivanja algoritama u jednostavnom i preglednom
obliku, citljivijem od koda pisanog u nekom programskom jeziku. Jedan od nacina su
dijagrami toka, poput onog na slici 3.2. Dijagrami toka vizualno su atraktivni, ali zahti-
Slika 3.1: Programski jezik Scratch.
21
Pocetak
c
Ucitaj
a i b
c
c = b
b = a mod b
a = c
c
d
d
d
d
d
d
d
d
d
d
Da li je
b = 0?
Ne
Da
'
c
Ispisi a
Kraj
Slika 3.2: Primjer dijagrama toka.
jevaju puno prostora i zato ih necemo koristiti u ovoj skripti. Algoritme cemo zapisivati
u takozvanom pseudojeziku.
Vecina programskih jezika ima mnostvo zajednickih znacajki. Ilustrirat cemo ih na
primjerima jezika FORTRAN, Pasca, C i Python. U ta cetiri jezika, kao i u skoro svim
ostalim, ulazni podaci, medurezultati i rezultati proracuna pohranjuju se u varijablama.
Na pocetku programa potrebno je deklarirati varijable, tj. odrediti koji ce se tip podataka
u njima spremati (npr. cijeli brojevi integeri, realni brojevi, znakovi ili nizovi znakova
i dr.). Programski jezik Python po tome je nesto drugaciji. U njemu se varijable ne
deklariraju, ali ih je prije prve upotrebe potrebno inicijalizirati, tj. pridruziti im neku
vrijednost. Time se ujedno odreduje koji je tip podataka spremljen u pojedinoj varijabli.
Deklaracija i inicijalizacija varijabli radi se u nasa cetiri ogledna programska jezika na
sljedeci nacin.
22 POGLAVLJE 3. NA

Deklaracija / inicijalizacija varijabli i pridruzivanje
FORTRAN Pascal
INTEGER m,n var m,n:integer;
REAL x,y x,y:real;
x = 3.14 x := 3.14;
y = SIN(x) - x**3 y := sin(x) - x*x*x;
m = 49 / 21 m := 49 div 21;
n = MOD(49,21) n := 49 mod 21;
C Python
int m,n; m = n = 0
float x,y; x = y = 0.0
x = 3.14; x = 3.14
y = sin(x) - pow(x,3); y = math.sin(x) - x**3
m = 49 / 21; m = 49 / 21
n = 49 % 21; n = 49 % 21
Ovdje smo ujedno vidjeli kako se varijablama pridruzuju konstante ili rezultati nekih
racunskih operacija.
Kao sto smo objasnili, svaki algoritam na pocetku uzima ulazne podatke, a na kraju
vraca izlazne podatke koji predstavljaju rjesenje problema. Zato svi programski jezici
imaju naredbe za ulaz i za izlaz podataka.
Ulaz i izlaz podataka
FORTRAN Pascal
PRINT *,Unesi prirodan broj writeln(Unesi prirodan broj);
READ *,n read(n);
C Python
printf("Unesi prirodan broj\n"); print "Unesi prirodan broj"
scanf("%d",&n); n = input()
Programi su nizovi naredbi i izvode se redom kojim su napisani.

Cesto je potrebno
dio programa izvesti ili ne izvesti, ovisno o nekom uvjetu. To nam omogucuje naredba za
grananje.
23
Grananje
FORTRAN Pascal
if (n=0 and m<>0) then
IF ((n.EQ.0).AND.(m.NE.0)) THEN begin
.
.
.
.
.
.
ENDIF end;
C Python
if (n==0 && m!=0) if n==0 and m!=0:
{ naredba unutar if
.
.
.
.
.
.
} naredba nakon if
Takoder, cesto je potrebno dio programa izvesti vise puta. Zato u programskim jezicima
postoje naredbe za ponavljanje, tzv. petlje.
Ponavljanje
FORTRAN Pascal
for i:=1 to n do
DO 10 i=1,n begin
.
.
.
.
.
.
10 CONTINUE end;
10 IF (n.GT.0) THEN while (n>0) do
.
.
. begin
GOTO 10
.
.
.
ENDIF end;
C Python
for (i=0; i<n; ++i) for i in range(n):
{ naredba unutar for
.
.
.
.
.
.
} naredba nakon for
while (n>0) while n>0:
{ naredba unutar while
.
.
.
.
.
.
} naredba nakon while
24 POGLAVLJE 3. NA

Nasa cetiri programska jezika dozvoljavaju indeksirane varijable, takozvane nizove ili
polja (eng. arrays).
Nizovi
FORTRAN Pascal
INTEGER a(0:99) var a:array [0..99] of integer;
DO 10 i=0,99 for i:= 0 to 99 do
10 a(i) = 2*i+1 a[i] := 2*i+1;
C Python
int a[100]; a = [0] * 100
for (i=0; i<100; ++i) a = [2*i+1 for i in range(100)]
a[i] = 2*i+1;
Dijelovi programa mogu se izdvojiti u zasebne cjeline i kasnije pozivati preko imena.
To su takozvani potprogrami ili funkcije.
Potprogrami
FORTRAN Pascal
SUBROUTINE ispis(n) procedure ispis(n:integer);
INTEGER n begin
PRINT *,Rezultat je ,n writeln(Rezultat je ,n);
RETURN end;
END
C Aritmeticka sredina (* Aritmeticka sredina *)
REAL FUNCTION sredina(x,y) function sredina(x,y:real):real;
REAL x,y begin
sredina = (x+y)/2 sredina := (x+y)/2;
RETURN end;
END
C Python
void ispis(int n) def ispis(n):
{ printf("Rezultat je %d\n",n); print "Rezultat je", n
}
25
C Python
/* Aritmeticka sredina */ # Aritmeticka sredina
float sredina(float x, float y) def sredina(x,y):
{ return (x+y)/2; return (x+y)/2.0
}
Pseudojezik objedinjuje zajednicke znacajke ovih cetiriju i mnogih drugih program-
skih jezika. Omogucuje nam manje formalno zapisivanje algoritama, prilagodeno ljudima
umjesto racunalima. Nadedbe cemo pisati na hrvatskom, slicno kao u zapisu algoritma
za zbrajanje iz prvog poglavlja i algoritma iz dokaza teorema 2.2. U iducem poglavlju
preciznije cemo opisati pseudojezik i koristit cemo ga u nastavku za zapisivanje raznih
algoritama. Programe pisane u pseudojeziku lako je prevesti na neki pravi programski
jezik. Savjetujemo citateljima da to rade paralelno s citanjem ove skripte.
Zadaci
Zadatak 3.1. Istrazite sto radi algoritam prikazan dijagramom toka na slici 3.2.
Zadatak 3.2. Zapisite s pomocu dijagrama toka algoritam za zbrajanje iz prvog poglavlja
te algoritam iz dokaza teorema 2.2.
Zadatak 3.3. U programskom jeziku Pascal napisite program Hello world, koji ispisuje
poruku na ekranu:
PROGRAM hello(input, output);
BEGIN
writeln(Hello, world!);
END.
Prevedite ga s pomocu nekog kompilatora za Pascal i pokrenite. Besplatno dostupni kom-
pilatori za Pascal su npr. Free Pascal [7] i GNU Pascal [11].
Zadatak 3.4. Napisite program Hello world u programskom jeziku C :
#include <stdio.h>
main()
{ printf("Hello, world!\n");
}
Prevedite ga s pomocu nekog kompilatora za C i pokrenite. Besplatno dostupni kompilatori
za C su npr. GCC [8] i Dev-C++ [2].
Zadatak 3.5. Napisite program Hello world u programskom jeziku Python i pokrenite
ga s pomocu odgovarajuceg interpretera:
print "Hello, world!"
Interpreteri i dokumentacija za Python besplatno su dostupni na web stranici [22].
26 POGLAVLJE 3. NA

Zadatak 3.6. Instalirajte programski jezik Scratch [23] i poigrajte se s njime. Natjerajte
macu da govori Hello, world, mijauce, hoda po ekranu i crta s pomocu kornjacine
grake.
Poglavlje 4
Pseudojezik
Da bismo algoritam mogli izvoditi na racunalu, moramo ga kodirati u nekom program-
skom jeziku. K od mora biti potpuno u skladu sa sintaksom izabranog formalnog jezika
i algoritam mora biti do kraja precizno opisan, cak i detalji koji nam se cine jasnima iz
konteksta.
Ako je nas algoritam namijenjen za citanje ljudima, mozemo ga zapisati na manje
formalan nacin. Mozemo si dozvoliti slobodniju sintaksu i detaljno raspisati samo bitne
dijelove algoritma. Takav nacin zapisivanja algoritama naziva se pseudojezik ili pseudokod.
Pseudojezik se koristi u mnogim knjigama i clancima koji se bave algoritmima, ali
zapravo ne postoji standardna verzija pseudojezika. Ovisno o kontekstu koristi se sazetiji
ili detaljniji nacin zapisivanja algoritama. Dijelove algoritma mozemo zamijeniti pojedi-
nacnim naredbama, opisati ih prirodnim jezikom, ili ih raspisati do u detalje kao u pravom
programskom jeziku. U ovom poglavlju upoznat cemo se sa stilom pisanja pseudokoda
koji cemo koristiti u nastavku skripte. U pravilu cemo algoritme zapisivati dosta detaljno,
tako da ih se lako moze prevesti na neki pravi programski jezik.
Algoritam, odnosno racunalni program, sastoji se od niza naredbi koje se izvode redom
kojim su napisane. U pseudojeziku za naredbe koristimo hrvatske rijeci. Zapisujemo ih
uspravnim slovima, jednu ispod druge. Ponekad je potrebno grupirati nekoliko uzastopnih
naredbi u jednu cjelinu, sto cinimo uglatim zagradama:
_
_
prva naredba
druga naredba
treca naredba
Ulazni podaci, medurezultati i rezultati proracuna pohranjuju se u varijablama. Varijable
cemo oznacavati s jednim ili vise kosih slova. Slicno kao u programskom jeziku Python,
necemo deklarirati tip podataka koji spremamo u varijable.
Spomenuli smo da algoritam uzima ulazne podatke i vraca izlazne podatke, koji pred-
stavljaju rjesenje. Za ulaz i izlaz podataka u pseudojeziku koristimo naredbe ucitaj i
ispisi.
Primjer 4.1. Program Hello world u pseudojeziku izgleda ovako:
ispisi "Hello, world!"
27
28 POGLAVLJE 4. PSEUDOJEZIK
Ovaj program doslovno ispisuje tekst u navodnicima. Ako iza naredbe ispisi stavimo
ime varijable (bez navodnika), nece se ispisati ime nego sadrzaj pohranjen u varijabli.
Iza naredbe za ulaz podataka uvijek stoji ime jedne ili vise varijabli u koje ce se ucitani
podaci spremiti.
Primjer 4.2. Program koji ucitava dva prirodna broja i ispisuje njihov zbroj:
ucitaj m, n
ispisi m + n
Ovdje nismo raspisivali algoritam za zbrajanje prirodnih brojeva opisan u prvom
poglavlju, nego smo samo napisali izraz m + n. Programski jezici sadrze gotovo rjesenje
za zbrajanje prirodnih brojeva, a isto cemo pretpostavljati za pseudojezik.
Jedna od najvaznijih naredbi pseudojezika i pravih programskih jezika je naredba koja
nekoj varijabli pridruzuje odredenu vrijednost. U primjerima algoritama iz prethodnih
poglavlja vec smo se susreli s pridruzivanjem. Oznacavali smo ga uglavnom znakom
jednakosti =. Od sada cemo pridruzivanje uvijek oznacavati znakom , da bismo ga
razlikovali od usporedivanja.
Na lijevoj strani naredbe za pridruzivanje stoji ime varijable. Na desnoj strani
moze biti konstanta, ime varijable ili izraz sastavljen od konstanti i varijabli s pomocu
aritmetickih, logickih i znakovnih operacija. Izraz na desnoj strani se evaluira: imena
varijabli se zamjenjuju sa sadrzajem pohranjenim u tim varijablama i izracunavaju se sve
operacije. Konacna vrijednost se pohranjuje u varijablu napisanu s lijeva.
Primjer 4.3.
a 2
b a + 3
c a b
ispisi c
Prva naredba pohranjuje u varijablu a broj 2. Druga naredba pohranjuje u varijablu b
vijednost spremljenu u a uvecanu za 3, tj. broj 5. Treca naredba pohranjuje u c produkt
vrijednosti spremljenih u a i b. Program na kraju ispisuje vrijednost spremljenu u c, tj. 10.
Cesto je potrebno povecati vrijednost neke varijable. S time smo se vec susreli u
algoritmu iz dokaza teorema 2.2.
Primjer 4.4.
ucitaj x
x x + 1
ispisi x
Program ucitava broj u varijablu x, povecava vrijednost x za jedan i ispisuje novi x.
Naprimjer, ako korisnik upise broj 17, program ce ispisati 18.
Vidimo da izraz s desne strane naredbe za pridruzivanje moze sadrzati i varijablu koju
smo naveli na lijevoj strani. Naprimjer, naredba x 2x broj spremljen u x mnozi s 2 i
rezultat pohranjuje u x. S lijeve strane naredbe za pridruzivanje smije stajati iskljucivo
29
ime jedne varijable, nikada konstanta ili izraz. Pridruzivanja 2 x, x+1 x i x+y 2
nemaju smisla. Osim brojeva, varijablama mozemo pridruzivati znakove, nizove znakova
(stringove) i logicke vrijednosti.
Primjer 4.5. Ovaj program takoder ispisuje poruku Hello, world!.
poruka "Hello, world!"
ispisi poruka
Primjer 4.6. Program ispisuje ISTINA ako korisnik unese pozitivan broj, a u suprotnom
ispisuje LA
Z.
ucitaj br
poz br > 0
ispisi poz
Argumenti operatora usporedivanja >, <, , , = i ,= su brojevi ili izrazi kojima je
vrijednost broj, a rezultat tih operacija je logicka vrijednost ISTINA ili LA
Z. Logickim op-
eratorima i, ili, ne argumenti i rezultat su logicke vrijednosti. Jos jednom naglasavamo
razliku izmedu naredbe za pridruzivanje i operatora usporedivanja =.
Primjer 4.7. Opisite sto rade sljedece naredbe. Koje od njih nemaju smisla?
uvjet (x < 1) ili (x > 1)
i = i + 1
nula x
2
x 6 = 0
a (x + 2) i (y 7)
b (x 0) + (y 0)
Rjesenje. Prva naredba u varijablu uvjet sprema logicku vrijednost izraza (x < 1) ili
(x > 1). Vrijednost je ISTINA ako je u varijabli x pohranjen broj koji je manji od 1 ili
veci od 1, a u suprotnom je LA
Z.
U drugom retku naveden je logicki izraz, a ne naredba. Sam za sebe taj izraz nema
smisla. U sklopu neke naredbe izraz bi uvijek poprimio vrijednost LA
Z, bez obzira na
sadrzaj varijable i. Naime, i ne moze biti jednak i + 1. Ako zelimo povecati sadrzaj
varijable i za 1, trebamo napisati naredbu za pridruzivanje i i + 1.
Treca naredba pohranjuje u varijablu nula logicku vrijednost ISTINA ili LA
Z ovisno
o tome je li u x pohranjena nultocka polinoma x
2
x 6 ili nije.
Cetvrta i peta naredba nemaju smisla. Na desnoj strani cetvrte naredbe je logicka
operacija i primijenjena na aritmeticke izraze x+2 i y7, a u petoj naredbi je aritmeticka
operacija + primijenjena na logicke izraze x 0 i y 0. Napominjemo da se u nekim
programskim jezicima (npr. C i Python) umjesto logickih vrijednosti ISTINA i LA
Z koriste
brojevi 1 i 0, pa bi tamo peta naredba imala smisla.
Primjer 4.8. Napisite program koji ucitava neke vrijednosti u varijable x i y, zamjenjuje
sadrzaj tih varijabli i ispisuje ih.
Rjesenje. Ako korisnik unese redom vrijednosti 5, 7, trazeni program treba ispisati 7, 5.
Sljedeci program ponasa se identicno, ali ipak ne predstavlja rjesenje zadatka.
ucitaj x, y
ispisi y, x
Naime, u varijablama su i dalje pohranjene vrijednosti x = 5, y = 7. Niti ovaj program
ne radi ispravno:
ucitaj x, y
x y
y x
ispisi x, y
Nakon prvog pridruzivanja obje varijable sadrze broj 7, a broj 5 je izgubljen. Program
ce ispisati 7, 7. Rjesenje je da prije pridruzivanja x y broj koji je bio u x spremimo u
pomocnu varijablu. Na kraju cemo varijabli y pridruziti broj iz pomocne varijable.
ucitaj x, y
pom x
x y
y pom
ispisi x, y
Zamjena varijabli cesta je i vazna operacija. Koristit cemo je npr. u algoritmima za
sortiranje. Mozemo si je predociti preko problema zamjene dviju vrsti pica ulivenih u
pogresne case. Zamislimo da smo crno vino ulili u casu za bijelo vino, a bijelo u casu za
crno. Za zamijenu pica koristimo trecu, pomocnu casu (vidi sliku 4.1). Analogija ipak
nije potpuna kad u casu B prelijemo pice iz case A, casa A ostane prazna. S druge
strane, nakon pridruzivanja b a obje varijable a, b sadrze vrijednost koja je bila u a.
U dosadasnjim primjerima algoritama naredbe se izvode tocno onim redom kojim
su napisane.

Cesto je potrebno utjecati na tijek izvodenja algoritma. U programskim
jezicima i u pseudojeziku za to sluzi naredba za grananje, koja je oblika
ako je logicki izraz onda
_
prvi niz naredbi
inace
_
drugi niz naredbi
Naredba za grananje evaluira logicki izraz. Ako je njegova vrijednost ISTINA, izvodi
se prvi niz naredbi, a u suprotnom se izvodi drugi niz naredbi. Cijeli drugi dio (inace
i odgovarajuci niz naredbi) moze se izostaviti. Kljucne rijeci ako je . . . onda . . . inace
na engleskom glase if . . . then. . . else, zato se naredba za grananje ponekad naziva if
naredbom.
31
1. 2.
3. 4.
Slika 4.1: Zamjena pica ulivenih u pogresne case.
Primjer 4.9. Program za rjesavanje kvadratne jednadzbe ax
2
+ bx + c = 0.
ucitaj a, b, c
ako je a ,= 0 onda
_
_
d b
2
4ac
ako je d > 0 onda
_
_
x
1
(b +
d)/(2a)
x
2
(b
d)/(2a)
ispisi "Rje senja su ", x
1
, x
2
inace
_
_
ako je d = 0 onda
_
x
1
b/(2a)
ispisi "Dvostruko rjesenje je ", x
1
inace
_
ispisi "Nema realnih rje senja"
inace
_
_
ako je b ,= 0 onda
_
x c/b
ispisi "Rje senje je ", x
inace
_
_
ako je c = 0 onda
_
ispisi "Svi realni brojevi su rje senja"
inace
_
ispisi "Nema rjesenja"
Ovaj program predstavlja detaljni zapis u pseudojeziku nacina na koji izracunavamo
formulu
x
1,2
=
b
b
2
4ac
2a
.
Raspisali smo sve moguce slucajeve (diskriminanta pozitivna, nula ili negativna, vodeci
koecijent nula).
Jos jednu vaznu grupu naredbi koje utjecu na tijek izvodenja programa cine naredbe
za ponavljanje, takozvane petlje (eng. loops). Pretpostavimo da zelimo ispisati prvih 100
prirodnih brojeva. Bez naredbe za ponavljanje morali bismo napisati 100 naredbi za ispis:
ispisi 1
ispisi 2
ispisi 3
.
.
.
Elegantnije rjesenje sastoji se od petlje koja nekoj varijabli redom pridruzuje brojeve od
1 do 100 i ispisuje vrijednost te varijable:
za i = 1, . . . , 100 radi
_
ispisi i
Ovaj oblik naredbe za ponavljanje naziva se for petljom, prema engleskom zapisu
for i = 1, . . . , 100 do
_
.
.
.
Varijabla koja poprima vrijednosti od 1 do 100 naziva se kontrolnom varijablom. Naravno,
moguce je staviti neku drugu donju i gornju granicu za kontrolnu varijablu umjesto 1 i 100.
Niz naredbi koje se ponavljaju zvat cemo tijelom petlje. U tijelu for petlje nije potrebno
povecavati vrijednost kontrolne varijable pretpostavljamo da se to dogada automatski.
Postoji i drugi oblik naredbe za ponavljanje, takozvana while petlja:
dok je logicki izraz radi
_
.
.
.
ili, na engleskom:
while logicki izraz do
_
.
.
.
Tijelo while petlje se ponavlja sve dok je logicki izraz istinit. Kad bismo s pomocu while
petlje zeljeli ispisati brojeve od 1 do 100, morali bismo sami inicijalizirati i povecavati
kontrolnu varijablu:
i 1
dok je i 100 radi
_
ispisi i
i i + 1
Za neke probleme prakticnija je for petlja, a za druge while petlja.
33
Primjer 4.10. Napisite program koji ucitava prirodan broj n i ispisuje kvadrate prvih n
prirodnih brojeva.
Rjesenje. Ovaj zadatak lakse je rijesiti s for petljom, jer ne moramo brinuti o kontrolnoj
varijabli:
ucitaj n
za i = 1, . . . , n radi
_
ispisi i
2
Primjer 4.11. Napisite program koji ucitava prirodan broj n i ispisuje prirodne brojeve
iz skupa 1, . . . , n koji su kvadrati nekog prirodnog broja.
Rjesenje. Nespretno rjesenje bila bi for petlja s kontrolnom varijablom i = 1, . . . , n. U
tijelu petlje provjeravali bismo je li i kvadrat prirodnog broja i ispisivali ga ako jest.
Spretnije je umjesto i ispisivati i
2
, ali tada gornja granica za kontrolnu varijablu nije n.
Petlja treba ici do najveceg prirodnog broja i za koji je i
2
n. Taj uvjet mozemo napisati
u while petlji.
ucitaj n
i 1
dok je i
2
n radi
_
ispisi i
2
i i + 1
Primjer 4.12. Napisite program koji ucitava 100 brojeva i ispisuje njihov zbroj.
Rjesenje. Koristimo pomocnu varijablu s kojoj na pocetku pridruzimo 0. Svaki puta kad
ucitamo broj x, pribrojimo ga pomocnoj varijabli: s s+x (pridruzimo varijabli s staru
vrijednost od s uvecanu za x). Na kraju s sadrzi zbroj svih ucitanih brojeva.
s 0
za i = 1, . . . 100 radi
_
ucitaj x
s s + x
ispisi s
Primjer 4.13. Napisite program koji ucitava prirodne brojeve sve dok se ne ucita nula.
Program treba ispisati produkt ucitanih prirodnih brojeva.
Rjesenje. U ovom zadatku ne znamo unaprijed koliko ce se brojeva ucitati, pa se ko-
ristimo while petljom. Produkt izracunavamo slicno kao sumu: pomocnu varijablu p
inicijaliziramo na 1 i mnozimo je ucitanim brojevima.
p 1
ucitaj x
dok je x ,= 0 radi
_
p p x
ucitaj x
ispisi p
Pretpostavimo da korisnik upise redom brojeve 2, 5, 3, 0. Primijetimo da se prvi broj
ucitava prije ulaza u petlju. Kada bi prvi ucitani broj bio 0, tijelo petlje uopce se ne bi
izvodilo, a program bi ispisao prazan produkt 1. U nasem slucaju program ce ucitati
x = 2 i prvi puta izvesti tijelo petlje. Varijabli p se pridruzuje p x = 1 2 = 2 i ucitava
se sljedeci broj, x = 5. Sada se ponovo provjerava uvjet x ,= 0, koji je istinit, i drugi
puta izvodi tijelo petlje. Varijabli p se pridruzuje 2 5 = 10 i ucitava se x = 3. U trecem
prolazu kroz petlju p postaje 30 i ucitava se 0. Sada uvjet x ,= 0 vise nije istinit, pa se
izlazi iz petlje. Na kraju se ispisuje varijablu p, tj. produkt ucitanih brojeva 30.
Primjer 4.14. Napisite program koji ucitava prirodan broj n i nakon toga n brojeva.
Program treba ispisati koliko medu ucitanim brojevima ima negativnih.
Rjesenje. U ovom primjeru pomocnu varijablu koristimo kao brojac. Na pocetku je inici-
jaliziramo na 0 i povecavamo je za 1 svaki puta kad korisnik unese negativan broj.
ucitaj n
br 0
za i = 1, . . . , n radi
_
_
ucitaj x
ako je x < 0 onda
_
br br + 1
ispisi br
Pokusajte sami detaljno opisati rad programa ako korisnik upise n = 5 i niz brojeva 2,
1, 0, 7, 14.
Primjer 4.15. Napisite program koji ucitava brojeve sve dok se ne ucita nula. Program
treba ispisati aritmeticku sredinu ucitanih brojeva (osim nule).
Rjesenje. Aritmeticka sredina jednaka je sumi ucitanih brojeva podijeljenoj s brojem
ucitanih brojeva:
A =
x
1
+ x
2
+ . . . + x
n
n
.
Koristit cemo dvije pomocne varijable prva prebrojava ucitane brojeve, a druga izracunava
sumu.
n 0
s 0
ucitaj x
dok je x ,= 0 radi
_
_
n n + 1
s s + x
ucitaj x
ako je n > 0 onda
_
ispisi s/n
inace
_
ispisi "Nije ucitan niti jedan broj"
Prije ispisa aritmeticke sredine provjeravamo je li ucitan barem jedan broj, da bismo
izbjegli dijeljenje s nulom.
35
Primjer 4.16. Napisite program koji ucitava n brojeva i ispisuje najveci od ucitanih
brojeva.
Rjesenje. U ovom programu koristit cemo pomocnu varijablu max u kojoj pamtimo naj-
veci od do sada ucitanih brojeva. Ako je sljedeci ucitani broj veci od max, pridruzimo ga
varijabli max:
za i = 1 . . . , n radi
_
_
ucitaj x
ako je x > max onda
_
max x
Varijablu max moramo prije ulaza u petlju inicijalizirati. Ako znamo da ce korisnik
upisati pozitivne brojeve, mozemo max postaviti na 0. Medutim, nije iskljuceno da ce
svi upisani brojevi biti negativni. Tada bi program ispisao 0, sto nije najveci od ucitanih
brojeva. Rjesenje je da prvi broj ucitamo direktno u max, a nakon toga iducih n 1
brojeva ucitavamo u petlji. Osim toga na pocetku programa treba ucitati n, a na kraju
ispisati max.
ucitaj n
ucitaj max
za i = 1 . . . , n 1 radi
_
_
ucitaj x
ako je x > max onda
_
max x
ispisi max
Naredbe koje smo do sada upoznali dovoljne su za zapisivanje svih algoritama kojima
cemo se baviti u ovoj skripti. Nasa verzija pseudojezika ima samo sest naredbi: ucitaj,
ispisi, pridruzivanje , grananje (ako. . .onda. . .inace), for petlju i while petlju. U
sestom poglavlju upoznat cemo se poblize s indeksiranim varijablama (nizovima, odnosno
poljima), koje smo vec susreli u uvodnim primjerima algoritma za zbrajanje i algoritma
iz dokaza teorema 2.2.
U mnogim programskim jezicima osim opisanih naredbi postoji mogucnost deniranja
funkcija, odnosno potprograma (vidi primjere na kraju prethodnog poglavlja). Funkcije i
potprogrami potrebni su za elegantno zapisivanje rekurzivnih algoritama. Time se u ovoj
skripti necemo baviti, pa ne uvodimo u pseudojezik sintaksu za funkcije i potprograme.
Zadaci
Zadatak 4.1. Objasnite razliku izmedu pridruzivanja i usporedivanja =.
Zadatak 4.2. Ako se na ulazu unesu brojevi a = 15 i b = 21, sto ce ispisati sljedeci
program?
ucitaj a, b
a a b
b 2 a + 1
a 3 b 7
ispisi a b
Zadatak 4.3. Istrazite sto radi sljedeci program.
ucitaj x, y
x x y
y x + y
x y x
ispisi x, y
Zadatak 4.4. Nadopunite program za rjesavanje kvadratne jednadzbe (primjer 4.9) tako
da ispisuje kompleksna rjesenja ako je diskriminanta negativna.
Zadatak 4.5. Napisite program za rjesavanje sustava od dvije linearne jednadzbe s dvije
nepoznanice
a x + b y = e
c x + d y = f
.
Program treba raditi ispravno u svim mogucim slucajevima (jedinstveno rjesenje, beskonacno
mnogo rjesenja, bez rjesenja).
Zadatak 4.6. Za zadani n, napisite formulu za najveci prirodan broj i za koji je i
2
n.
Rijesite zadatak iz primjera 4.11 s pomocu for petlje.
Zadatak 4.7. Napisite program koji ucitava prirodan broj n i ispisuje prvih n parnih
prirodnih brojeva.
Zadatak 4.8. Napisite program koji ucitava prirodan broj n i ispisuje prvih n prirodnih
brojeva koji pri dijeljenju s 3 daju ostatak 1.
Zadatak 4.9. Napisite program koji ucitava prirodan broj n i ispisuje sve brojeve iz skupa
1, 2, . . . , n koji su djeljivi s 5.
Zadatak 4.10. Napisite program koji ucitava prirodan broj n i ispisuje sve brojeve iz
skupa 1, 2, . . . , n koji su parni, ali nisu djeljivi s 4.
Zadatak 4.11. Napisite program koji ucitava n prirodnih brojeva i ispisuje sumu svih
ucitanih brojeva koji su parni.
Zadatak 4.12. Napisite program koji ucitava brojeve sve dok se ne ucita nula. Program
treba ispisati produkt svih negativnih ucitanih brojeva.
Zadatak 4.13. Napisite program koji ucitava cijele brojeve sve dok se ne ucita nula.
Program treba ispisati koliko medu ucitanim brojevima ima neparnih.
37
treba ispisati geometrijsku sredinu ucitanih brojeva (osim nule):
G =
n
x
1
x
2
x
n
.
Zadatak 4.15. Rijesite prethodni zadatak za kvadratnu sredinu
K =
_
x
2
1
+ x
2
2
+ . . . + x
2
n
n
i harmonijsku sredinu
H =
n
1
x
1
+
1
x
2
+ . . . +
1
xn
.
treba ispisati najmanji pozitivan broj od ucitanih. Ako nije ucitan niti jedan pozitivan
broj, program treba ispisati poruku o tome.
Zadatak 4.17. Napisite program koji ucitava cijele brojeve sve dok se ne ucita nula.
Program treba ispisati najveci neparni ucitani broj. Ako nije ucitan niti jedan neparni
broj, program treba ispisati poruku o tome.
Zadatak 4.18. Niz Fibonaccijevih brojeva deniran je rekurzivno. Prva dva clana niza
su F
1
= F
2
= 1, a svaki sljedeci je zbroj dva prethodna: F
n
= F
n1
+ F
n2
, za n 2.
Napisite program koji ucitava n i ispisuje prvih n clanova tog niza.
Zadatak 4.19. Napisite program koji ucitava prirodan broj n i ispisuje sve Fibonaccijeve
brojeve iz skupa 1, . . . , n.
Zadatak 4.20. Napisite program koji ucitava prirodan broj n i ispisuje n-ti Fibonaccijev
broj F
n
.
Zadatak 4.21. Napisite program koji ucitava prirodan broj n i ispisuje najveci Fibo-
naccijev broj koji je manji ili jednak od n.
Zadatak 4.22. Napisite program koji ucitava prirodan broj n i ispisuje najmanji Fibo-
naccijev broj koji je veci ili jednak od n.
Poglavlje 5
Neki algoritmi za prirodne brojeve
U ovom poglavlju upoznat cemo neke algoritme koji rade s prirodnim brojevima. Pocinjemo
s problemima o znamenkama zadanog prirodnog broja. Ako zelimo ispisati znamenke
jednu po jednu, koristimo algoritam koji smo upoznali u drugom poglavlju:
ucitaj n
dok je n ,= 0 radi
_
ispisi n mod 10
n n div 10
Ovaj algoritam ispisuje dekadske znamenke, ali ga jednostavno mozemo modicirati tako
da radi s bilo kojom bazom b. Primijetimo da se znamenke ispisuju s desna na lijevo, tj.
od namanje znacajne prema znacajnijima (prvo znamenka jedinice, zatim desetice, stotice
itd.). Koristili smo while petlju jer ne znamo unaprijed koliko ce biti znamenaka.
Osnovnu petlju po znamenkama zadanog prirodnog broja sad cemo koristiti za prob-
leme kakve smo imali u prethodnom poglavlju prebrojavanje, izracunavanje sume,
trazenje maksimuma. . .
Primjer 5.1. Napisite program koji ucitava prirodan broj n i ispisuje koliko n ima zna-
menaka.
Rjesenje. Modiciramo prethodni algoritam tako da se umjesto ispisivanja znamenaka
povecava brojac.
ucitaj n
br 0
dok je n ,= 0 radi
_
br br + 1
n n div 10
ispisi br
Ako smijemo koristiti logaritamsku funkciju i funkciju najvece cijelo, problem mozemo
rijesiti bez petlje.
ucitaj n
ispisi log n| + 1
39
40 POGLAVLJE 5. NEKI ALGORITMI ZA PRIRODNE BROJEVE
Primjer 5.2. Napisite program koji ucitava prirodan broj n i ispisuje sumu njegovih
znamenaka.
Rjesenje.
ucitaj n
s 0
dok je n ,= 0 radi
_
s s + (n mod 10)
n n div 10
ispisi s
Primjer 5.3. Napisite program koji ucitava prirodan broj n i ispisuje njegovu najvecu
znamenku.
Rjesenje.
ucitaj n
max 0
dok je n ,= 0 radi
_
_
z n mod 10
ako je z > max onda max z
n n div 10
ispisi max
Primjer 5.4. Napisite program koji ucitava prirodan broj n i denira prirodan broj m koji
se sastoji od istih znamenaka kao n, ali u obrnutom redoslijedu. Naprimjer, ako korisnik
unese n = 123, program treba ispisati m = 321.
Rjesenje.
ucitaj n
m 0
dok je n ,= 0 radi
_
_
z n mod 10
m m 10 + z
n n div 10
ispisi m
Iduca grupa algoritama radi s djeliteljima zadanog prirodnog broja. Ako zelimo ispisati
sve djelitelje od n, najprirodnije rjesenje je for petlja od 1 do n:
ucitaj n
za d = 1, . . . , n radi
_
ako je n mod d = 0 onda ispisi d
Broj d je djelitelj od n ako je ostatak pri dijeljenju n sa d jednak nuli, tj. ako vri-
jedi n mod d = 0. Slijedi nekoliko primjera koji se rjesavaju s pomocu petlje po svim
djeliteljima.
41
Primjer 5.5. Napisite program koji ucitava prirodan broj n i ispisuje koliko n ima
djelitelja.
Rjesenje.
ucitaj n
br 0
za d = 1, . . . , n radi
_
ako je n mod d = 0 onda br br + 1
ispisi br
Primjer 5.6. Napisite program koji ucitava prirodan broj n i ispisuje sumu svih djelitelja
od n.
Rjesenje.
ucitaj n
s 0
za d = 1, . . . , n radi
_
ako je n mod d = 0 onda s s + d
ispisi s
Primjer 5.7. Napisite program koji ucitava prirodan broj n i ispisuje njegov najmanji
djelitelj veci od 1 i najveci djelitelj manji od n.
Rjesenje. Najmanji djelitelj svakog prirodnog broja je 1, a najveci on sam. Zato smo ta
dva djelitelja iskljucili iz razmatranja. Za ovaj problem dat cemo elegantnije rjesenje od
for petlje po svim djeliteljima s pomocnim varijablama min i max. Takva petlja pronalazi
djelitelje redom od manjih prema vecima. Prvi kojeg pronade nakon 1 je trazeni najmanji
djeljitelj, pa mozemo odmah izaci iz petlje i ispisati ga.
ucitaj n
d 2
dok je n mod d ,= 0 radi d d + 1
ispisi d
Primijetimo da je najmanji djelitelj d uvijek prost broj. U suprotnom bismo d mogli
napisati kao d = a b za neke a, b < d, pa bi a i b bili jos manji djelitelji od n. Za najveci
djelitelj koristimo silaznu petlju:
ucitaj n
d n 1
dok je n mod d ,= 0 radi d d 1
ispisi d
Program mozemo uciniti ekasnijim tako da petlja krece od n div 2 umjesto od n 1:
ucitaj n
d n div 2
dok je n mod d ,= 0 radi d d 1
ispisi d
Naime, niti jedan broj izmedu n div 2 i n ne moze biti djelitelj od n. Ako zelimo ispisati
najmanji i najveci djelitelj, ne moramo imati obje petlje (uzlaznu i silaznu). Najveci
djeljitelj ocito je jednak broju n podijeljenim s najmanjim djeliteljem.
ucitaj n
d 2
dok je n mod d ,= 0 radi d d + 1
ispisi d
ispisi n div d
Primjer 5.8. Napisite program koji ucitava prirodne brojeve m i n te ispisuje sve njihove
zajednicke djelitelje.
Rjesenje.
ucitaj m, n
za d = 1, . . . , m radi
_
ako je (m mod d = 0) i (n mod d = 0) onda ispisi d
Primjer 5.9. Napisite program koji ucitava prirodne brojeve m i n te ispisuje njihov
najveci zajednicki djelitelj.
Rjesenje.
ucitaj m, n
d m
dok je (m mod d ,= 0) ili (n mod d ,= 0) radi d d 1
ispisi d
Prethodni primjer rjesili smo slicno kao primjer 5.7. Ponudeno rjesenje je vrlo jednos-
tavno; korektnost slijedi direktno iz denicije najveceg zajednickog djelitelja. Za problem
najveceg zajednickog djelitelja postoji manje trivijalan, ali ekasniji i ljepsi algoritam. To
je poznati Euklidov algoritam:
ucitaj m, n
dok je n ,= 0 radi
_
_
pom n
n m mod n
m pom
ispisi m
Algoritam ucitava prirodne brojeve m i n. Pretpostavljamo da je prvi broj veci ili jednak
od drugog, m n. Petlja se izvodi dok je manji broj razlicit od nule. U tijelu petlje
varijabli n se pridruzuje ostatak pri dijeljenju m sa n, a varijabli m stara vrijednost od n.
Primijetimo da je prethodno stara vrijednost od n pohranjena u pomocnu varijablu pom,
slicno kao kod zamjene varijabli. Kad varijabla n postane nula, algoritam izlazi iz petlje
i ispisuje m.
43
Primjer 5.10. Opisimo rad Euklidova algoritma za ulaz m = 30, n = 21. U prvom
prolazu kroz petlju u varijablu pom se pohranjuje 21, varijabla n postaje 30 mod 21 = 9,
a u m se prepisuje broj pohranjen u pom. Vrijednosti varijabli su tada m = 21, n = 9.
Buduci da n nije nula, drugi puta se izvodi tijelo petlje. Vrijednosti varijabli postaju
m = 9, n = 21 mod 9 = 3. U trecem prolazu kroz petlju varijable postaju m = 3,
n = 9 mod 3 = 0. Tada algoritam izlazi iz petlje i ispisuje m = 3, sto je najveci zajednicki
djelitelj od 30 i 21.
Korektnost Euklidova algoritma nije ocita. Trebamo se uvjeriti da algoritam zavrsava
u konacno mnogo koraka za bilo koje brojeve m, n na ulazu te da je broj kojeg ispisuje na
kraju zaista najveci zajednicki djelitelj od m i n. Konacnost slijedi iz teorema o dijeljenju
s ostatkom (teorem 2.3). U svakom koraku zamjenjujemo n s ostatkom pri dijeljenju m sa
n, koji je strogo manji od n. Dobivamo strogo padajuci niz nenegativnih cijelih brojeva,
koji ima konacno mnogo clanova prije nego sto dode do nule. Tada algoritam izlazi iz
petlje, ispisuje m i zavrsava s radom.
Najveci zajednicki djelitelj oznacavat cemo NZM(m, n) (prema najveca zajednicka
mjera). Ako je m djeljiv s n, ocito je NZM(m, n) = n. Ako m nije djeljiv s n, moze
se pokazati da vrijedi NZM(m, n) = NZM(n, m mod n). Iz toga slijedi da je broj kojeg
Euklidov algoritam ispisuje upravo NZM(m, n). Algoritam unutar petlje zamjenjuje m
i n redom s n i m mod n. Pritom se ne mijenja najveci zajednicki djelitelj brojeva
pohranjenih u varijablama m i n. U zadnjem prolazu kroz petlju n postaje nula, a to
znaci da je prethodno m bio djeljiv s n. Ispisuje se vrijednost varijable m u zadnjem
koraku, koja je jednaka vrijednosti n u prethodnom koraku. Tada je m bio djeljiv s n, pa
je vrijedilo n = NZM(m, n). Dakle, Euklidov algoritam ispisuje NZM(m, n).
Najveci zajednicki djelitelj naziva se i najvecom zajednickom mjerom, a Euklidov
algoritam duboko je povezan s problemom mjerenja. Pretpostavimo da su zadane dvije
duzine duljina a i b. Brojevi a i b su pozitivni realni brojevi za koje pretpostavljamo
a > b, tj. da je prva duzina veca od druge. Izmjeriti prvu duzinu drugom znaci ispitati
koliko puta druga duzina stane u prvu:
a
b
b b b o
Slika 5.1: Mjerenje duzine a duzinom b.
Ako a nije cjelobrojni visekratnik od b, ostat ce nam dio kraci od b (ostatak).
Postupak mozemo opisati sljedecim algoritmom, koji uzastopno oduzima b od a dok a ne
postane manji od b.
ucitaj a, b
k 0
dok je a b radi
_
a a b
k k + 1
ispisi k, a
Algoritam ispisuje cijeli broj k, koji nam kaze koliko puta b stane u a, i duljinu ostatka.
To je zapravo dokaz tvrdnje o egzistenciji iz sljedece generalizacije teorema o dijeljenju s
ostatkom.
Teorem 5.11. Neka su a, b > 0 pozitivni realni brojevi. Tada postoje jedinstveni brojevi
k N
0
i o R, 0 o < b takvi da je a = k b + o.
Problem mjerenja sastoji se u pronalazenju zajednicke mjere kojom mozemo izmje-
riti obje duzine bez ostatka. To je duzina duljine d takve da su a i b njezini cjelobrojni
visekratnici: a = m d i b = n d za neke m, n N. Tada je razlomak
m
n
odgovor na
pitanje koliko puta b stane u a.

Sto je zajednicka mjera d veca, to su brojnik i nazivnik
manji i mjerenje nam je prakticnije. Zato trazimo najvecu zajednicku mjeru.
a
b
d
Slika 5.2: Zajednicka mjera d duzina a i b.
Euklidov algoritam je pokusaj da se problem mjerenja sustavno rijesi. U prvom koraku
mjerimo vecu duzinu a manjom duzinom b. Ako ostatak o
1
nije nula, nastavljamo mjeriti
manju duzinu b s ostatkom o
1
. Ako ni u drugom koraku ostatak o
2
nije nula, mjerimo
o
1
s ostatkom o
2
i tako dalje. Kada dobijemo ostatak nula, sve promatrane velicine su
cjelobrojni visekratnici zadnjeg pozitivnog ostatka. Tako nalazimo najvecu zajednicku
mjeru duzina a i b.
Vidjeli smo da se jedno mjerenje svodi na uzastopno oduzimanje manje duzine od
vece. Prosirenje tog postupka daje nam drugu verziju Euklidova algoritma. Oduzimamo
b od a dok a ne postane manji od b. Tada nastavljamo oduzimati a od b, i tako dalje sve
dok se a i b ne izjednace.
45
ucitaj a, b
dok je a ,= b radi
_
ako je a > b onda a a b
inace b b a
ispisi a
Ova verzija Euklidova algoritma zasniva se na oduzimanju. Za prirodne brojeve
a, b N ispisuje isti rezultat kao prva verzija Euklidova algoritma, u kojoj smo racunali
ostatke pri dijeljenju. Algoritam s oduzimanjem obicno treba vise koraka od prve verzije
algoritma, ali ga mozemo primijeniti na pozitivne realne brojeve, a ne samo na prirodne
brojeve.
Postavlja se pitanje hoce li algoritam zavrsiti u konacno mnogo koraka za bilo koje
realne brojeve a, b > 0 na ulazu? Ako algoritam pronade najvecu zajednicku mjeru d,
onda je
a
b
=
md
nd
=
m
n
racionalan broj. Prema tome, ako je omjer brojeva na ulazu
iracionalan, algoritam ne zavrsava.
Denicija 5.12. Za realne brojeve a, b ,= 0 kazemo da su sumjerljivi ako je njihov omjer
a
b
racionalan broj. U suprotnom kazemo da su nesumjerljivi.
Starogrcki matematicari bili su zapanjeni otkricem nesumjerljivih velicina, naprimjer
stranice i dijagonale kvadrata. Za takve duzine ne postoji zajednicka mjera, a Euklidov
algoritam izvodio bi se beskonacno. Naravno, svako mjerenje u stvarnom zivotu nuzno
ukljucuje pogresku i kao rezultat daje aproksimaciju. Medutim, ovo pokazuje da cak ni
idealizirano mjerenje ne moze biti egzaktno.
Vratimo se algoritmima za prirodne brojeve. U sljedecim primjerima koristimo se
Euklidovim algoritmom.
Primjer 5.13. Napisite program koji ucitava dva prirodna broja i ispisuje poruku o tome
jesu li relativno prosti.
Rjesenje. Brojevi su relativno prosti ako je njihov najveci zajednicki djelitelj 1. Izracunavamo
ga Euklidovim algoritmom i usporedujemo s 1:
ucitaj m, n
dok je n ,= 0 radi
_
_
pom n
n m mod n
m pom
ako je m = 1 onda
_
ispisi "Brojevi su relativno prosti"
inace
_
ispisi "Brojevi nisu relativno prosti"
Primjer 5.14. Napisite program koji ucitava brojnik i nazivnik razlomka i ispisuje ga u
do kraja skracenom obliku.
Rjesenje. Trebamo podijeliti brojnik i nazivnik njihovom najvecom zajednickom mjerom.
Buduci da Euklidov algoritam mijenja vrijednosti varijabli m i n, pohranit cemo pocetne
vrijednosti u pomocne varijable.
ucitaj m, n
a m
b n
dok je n ,= 0 radi
_
_
pom n
n m mod n
m pom
ispisi a div m, " / ", b div m
Primjer 5.15. Napisite program koji ucitava dva prirodna broja i ispisuje njihov najmanji
zajednicki visekratnik.
Rjesenje. Najmanji zajednicki visekratnik dobijemo tako da pomnozimo brojeve i podi-
jelimo produkt s najvecim zajednickim djeliteljem.
ucitaj m, n
p m n
dok je n ,= 0 radi
_
_
pom n
n m mod n
m pom
ispisi p div m
Vazan matematicki pojam je pojam prostog broja. Za prirodan broj n > 1 kazemo
da je prost ako su mu jedini djelitelji 1 i n. Mozemo reci da je n prost ako ima tocno dva
djelitelja. Brojeve s vise od dva djelitelja nazivamo slozenim, a broj 1 nije niti prost niti
slozen. Sljedeci algoritam ucitava n i provjerava je li prost.
ucitaj n
br 0
za d = 1, . . . , n radi
_
ako je n mod d = 0 onda br br + 1
ako je br = 2 onda
_
ispisi "Broj je prost"
inace
_
ispisi "Broj nije prost"
Algoritam prebrojava djelitelje od n. Ako ima tocno dva djelitelja onda je prost, a u
suprotnom je n = 1 ili je n slozen broj.

Cim nademo prvi djelitelj izmedu 1 i n, znamo da
je rijec o slozenom broju. Ovaj algoritam napisan je s for petljom i nastavlja prebrojavati
47
djelitelje. S while petljom mozemo napisati ekasniji algoritam, koji ce prekinuti potragu
kad nade prvi djelitelj. U primjeru 5.7 vec smo spomenuli da brojevi izmedu (n div 2) i
n ne mogu biti djelitelji, pa ih ne moramo provjeravati.
ucitaj n
ako je n = 1 onda
_
ispisi "Broj nije ni prost ni slo zen"
inace
_
_
d 2
dok je (n mod d ,= 0) i (d n div 2) radi d d + 1
ako je d n div 2 onda
_
ispisi "Broj je slo zen"
inace
_
Algoritam mozemo uciniti jos ekasnijim tako da potragu za djeliteljima ogranicimo do
n. Naime, moze se pokazati da najmanji djelitelj izmedu 1 i n ne moze biti veci od

n
(ako postoji).
ucitaj n
ako je n = 1 onda
_
ispisi "Broj nije ni prost ni slo zen"
inace
_
_
d 2
dok je (n mod d ,= 0) i (d
2
n) radi d d + 1
ako je d
2
n onda
_
ispisi "Broj je slo zen"
inace
_
Primjer 5.16. Ako korisnik unese n = 17, prebrojimo za koliko brojeva d prethodna
tri algoritma provjeravaju jesu li djelitelji od n. Prvi algoritam provjerava sve brojeve
od 1 do n, dakle napravi ukupno 17 provjera. Drugi algoritam trazi djelitelje od 2 do
17 div 2 = 8, dakle napravi 7 provjera. Treci algoritam provjerava brojeve d 2 koji
zadovoljavaju d
2
17, tj. brojeve od 2 do 4. Nakon samo tri provjere ispravno zakljucuje
da je 17 prost broj.
Prema osnovnom teoremu aritmetike, svaki prirodan broj moze se prikazati kao pro-
dukt prostih brojeva. Prikaz je jedinstven do na poredak faktora. Nije tesko napisati
algoritam koji ucitava prirodan broj n i ispisuje njegove proste faktore. Koristit cemo
primjedbu iz primjera 5.7 prema kojoj je najmanji djelitelj veci od 1 nuzno prost. Dok
je n > 1, ispisivat cemo najmanji djelitelj d i podijeliti n sa d. Tako dobivamo proste
faktore od n u rastucem redoslijedu. Pritom ne moramo provjeravati jesu li brojevi koje
ispisujemo prosti.
ucitaj n
d 2
dok je n > 1 radi
_
_
dok je n mod d = 0 radi
_
ispisi d
n n div d
d d + 1
Primjer 5.17. Opisimo kako prethodni algoritam nalazi proste faktore broja n = 84. Pri
ulazu u vanjsku petlju vrijednosti varijabli su n = 84, d = 2. Unutarnja petlja se izvodi
dok je n mod d = 0, sto je ispunjeno. Pri prvom prolazu kroz unutarnju petlju ispisuje se
2 i n postaje 42. Uvjet n mod d = 0 i dalje je ispunjen, pa algoritam jos jednom prolazi
kroz unutarnju petlju. Ponovo ispisuje 2 i postavlja n na 21. Taj broj vise nije djeljiv s 2,
pa algoritam izlazi iz unutarnje petlje i povecava d za jedan. Nakon prvog prolaza kroz
vanjsku petlju vrijednosti varijabli su n = 21, d = 3.
Buduci da je n > 1, algoritam drugi puta ulazi u vanjsku petlju. Unutarnja petlja
ispisuje 3 i postavlja n na 7. Po izlazu iz unutarnje petlje povecava se d, pa su vrijednosti
varijabi n = 7, d = 4.
Nakon drugog prolaza kroz vanjsku petlju algoritam povecava d od 4 do 6. Broj n = 7
nije djeljiv s tim brojevima, pa algoritam ne ulazi u unutarnju petlju. U sestom prolazu
kroz vanjsku petlju d je 7, unutarnja petlja ispisuje 7 i postavlja n na 1, a zatim se d poveca
na 8. Algoritam izlazi iz vanjske petlje i zavrsava s radom. Ispisao je redom brojeve 2, 2,
3, 7, a to su prosti faktori od 84.
U ovom poglavlju nastojali smo razviti ekasne algoritme, koji zavrsavaju s radom u
sto manje koraka. Buduci da moderna racunala izvode operacije fantasticnim brzinama,
postavlja se pitanje je li to uopce bitno? Pretpostavimo da se u jednoj sekundi izvodi
milijardu (10
9
) koraka algoritma. To je usporedivo s mogucnostima danasnjih procesora,
iako se u stvarnosti svi koraci ne izvode jednakom brzinom. Razmotrit cemo koliko vre-
mena treba za tri karakteristicna problema: izracunavanje najveceg zajednickog djelitelja,
provjera je li broj prost i rastavljanje na proste faktore. Na ulazu cemo pretpostavljati
velike prirodne brojeve s oko 50 znamenaka, tj. reda velicine 10
50
.
U primjeru 5.9 dali smo prvi algoritam za najveci zajednicki djelitelj. Ako na ulazu
imamo relativno proste brojeve reda velicine 10
50
, algoritam smanjuje varijablu d od 10
50
do 1 i tek tada ispisuje najveci zajednicki djelitelj 1. Dakle, treba mu oko 10
50
koraka.
To znaci da bi izvodenje algoritma trajalo oko 10
41
sekundi, tj. oko 3.2 10
33
godina. Za
usporedbu, starost svemira procjenjuje se na 1.4 10
10
godina (prema [26]).
Brojevi s 50 znamenaka ipak nisu izvan dosega danasnjih racunala. Euklidov algoritam
vrlo brzo nalazi najveci zajednicki djelitelj cak i tako velikih brojeva. Netrivijalan je, ali
dugo poznat rezultat [16] da Euklidovom algoritmu treba najvise koraka ako su na ulazu
uzastopni Fibonaccijevi brojevi. Tocnije, najmanji brojevi za koje Euklidov algoritam n
puta prolazi kroz petlju su F
n+2
i F
n+1
. Prva dva Fibonaccijeva broja veca od 10
50
su
F
241
i F
242
. Euklidov algoritam izracunava njihov najveci zajednicki djelitelj nakon 240
prolaza kroz petlju. Ako jedan prolaz brojimo kao tri koraka (zbog tri pridruzivanja unutar
petlje), algoritam zavrsava za 7.2 10
7
sekundi, tj. u vremenu kracem od mikrosekunde
49
(milijuntog dijela sekunde). U stvarnosti za operacije s tako velikim brojevima treba vise
vremena nego sto smo pretpostavili, ali cijeli racun zaista zavrsava u djelicu sekunde.
Za algoritam koji provjerava je li prirodan broj prost, najgori slucaj je kad zadamo
prost broj. Prva verzija algoritma na str. 46 provjerava sve brojeve iz skupa 1, . . . , n.
Dakle, za broj s 50 znamenaka treba oko 10
50
koraka i vrijeme izvodenja je 3.2 10
33
godina. Ekasnija verzija algoritma na str. 47 provjerava brojeve do

n. Za prost broj s
50 znamenaka treba oko 10
25
koraka, ili 3.2 10
8
godina. To je krace od starosti svemira,
ali je takoder duze nego sto bismo zeljeli cekati.
Postoje ekasni algoritmi za provjeru prostosti, koji brojeve s 50 znamenaka rjesavaju
brzo. Prvi takav algoritam u smislu kojeg koristimo u ovoj skripti opisan je 2004. godine
u clanku [1]. Od ranije su poznati randomizirani algoritmi i algoritmi kojima korektnost
ovisi o nedokazanim hipotezama o prostim brojevima (vidi [29]). Ti su algoritmi relativno
komplicirani i necemo se njima baviti.
Za problem rastavljanja zadanog prirodnog broja na proste faktore do danas nije
poznat niti jedan ekasan algoritam. Nas algoritam na str. 48 za prost broj reda velicine
10
50
treba vrijeme dulje od starosti svemira. Poznati su znatno ekasniji algoritmi, ali
niti jedan na danasnjim racunalima ne moze brzo faktorizirati brojeve s 200 znamenaka.
Opcenito, najgori slucaj za faktorizaciju su brojevi koji su produkt dvaju velikih prostih
brojeva.
Racunski problemi s velikim prirodnim brojevima nisu samo od teorijskog znacaja.
Neki od kriptografskih algoritama koji se koriste u praksi za bankovne transakcije putem
interneta i drugo zasnivaju se upravo na problemima koje smo razmatrali. Oni ne bi bili
moguci da ne mozemo brzo racunati najvecu zajednicku mjeru i provjeravati prostost, a
sigurnost im se zasniva na nemogucnosti faktorizacije velikih prirodnih brojeva.
U sljedecem poglavlju opisat cemo kako se procjenjuje ekasnost algoritama bez racu-
nanja vremena izvodenja za konkretne ulazne vrijednosti.
Zadaci
Zadatak 5.1. Napisite program koji ucitava prirodne brojeve n i b 2 te ispisuje zna-
menke broja n u bazi b.
Zadatak 5.2. Napisite program koji ucitava prirodne brojeve n i b 2 te ispisuje arit-
meticku sredinu znamenaka broja n u bazi b.
Zadatak 5.3. Napisite program koji ucitava prirodne brojeve n i b 2 te ispisuje koliko
znamenaka razlicitih od nule ima u zapisu broja n u bazi b.
Zadatak 5.4. Napisite program koji ucitava prirodan broj n i ispisuje bazu b u kojoj n
ima najvise znamenaka razlicitih od nule.
Zadatak 5.5. Napisite program koji ucitava prirodne brojeve n i b 2 te ispisuje zna-
menke broja n u bazi b s lijeva na desno, tj. od najznacajnije prema manje znacajnima.
Zadatak 5.6. Napisite program koji ucitava prirodan broj n i ispisuje produkt svih djelitelja
od n.
Zadatak 5.7. Napisite program koji ucitava prirodan broj n i ispisuje aritmeticku sredinu
svih djelitelja od n.
Zadatak 5.8. Dokazite: za svaki prirodan broj n, najmanji broj d > 1 koji dijeli n je
prost.
Zadatak 5.9. Dokazite: za svaki prirodan broj n, brojevi izmedu (n div 2) i n nisu
djelitelji od n.
Zadatak 5.10. Istrazite sto ce se dogoditi ako u Euklidov algoritam na str. 42 upisemo
brojeve m < n.
Zadatak 5.11. Dokazite: ako je prirodan broj n djelitelj od m, onda vrijedi NZM(m, n) =
n.
Zadatak 5.12. Dokazite: ako prirodan broj n nije djelitelj od m, onda vrijedi NZM(m, n) =
NZM(n, m mod n).
Zadatak 5.13. Dokazite teorem 5.11.
Zadatak 5.14. Opisite rad verzije Euklidova algoritma s oduzimanjem (na str. 45) za
ulaz m = 30, n = 21. Koliko prolaza kroz petlju treba tom algoritmu, a koliko Euklidovu
algoritmu na str. 42?
Zadatak 5.15. Dokazite da su duljina stranice i duljina dijagonale kvadrata nesumjerljivi
brojevi.
Zadatak 5.16. Napisite program koji ucitava dva razlomka i ispisuje njihov produkt u do
kraja skracenom obliku.
Zadatak 5.17. Napisite program koji ucitava dva razlomka i ispisuje njihov zbroj u do
kraja skracenom obliku.
Zadatak 5.18. Neka je NZM(m, n) najveci zajednicki djelitelj, a NZV(m, n) najmanji
zajednicki visekratnik brojeva m i n. Dokazite da za sve prirodne brojeve m, n vrijedi
NZM(m, n) NZV(m, n) = m n.
Zadatak 5.19. Napisite program koji ucitava prirodne brojeve sve dok se ne ucita nula.
Program treba ispisati najveci zajednicki djelitelj svih ucitanih brojeva (osim nule).
Zadatak 5.20. Eulerova funkcija (n) denira se kao broj prirodnih brojeva k n koji
su relativno prosti s n. Napisite program koji ucitava prirodan broj n i ispisuje (n).
Zadatak 5.21. Neka je n slozen broj. Ako je d njegov najmanji djelitelj veci od 1, dokazite
da je d

n.
Zadatak 5.22. Napisite program koji ucitava prirodan broj n i ispisuje sve proste brojeve
iz skupa 1, . . . , n.
Zadatak 5.23. Napisite program koji ucitava prirodan broj n i ispisuje prvih n prostih
brojeva.
51
Zadatak 5.24. Napisite program koji ucitava prirodan broj n i ispisuje n-ti po redu prost
broj.
Zadatak 5.25. Napisite program koji ucitava prirodan broj n i ispisuje najmanji prost
broj p n.
Zadatak 5.26. Napisite program koji ucitava prirodan broj n 2 i ispisuje najveci prost
broj p n.
Zadatak 5.27. Prisjetite se algoritma za racunanje najveceg zajednickog djelitelja iz os-
novne skole: brojeve m i n rastavimo na proste faktore, trazimo zajednicke proste faktore
i pomnozimo ih. Pokusajte precizno zapisati taj algoritam! Bi li taj algoritam bio ekasan
za velike prirodne brojeve m i n?
Poglavlje 6
Nizovi i sortiranje
Nizovi ili polja (eng. arrays) su indeksirane varijable.

Cesto je u algoritmu potrebno
pamtiti veci broj podataka, koji moze ovisiti o instanci problema kojeg rjesavamo. Tada
ih nije prakticno pohraniti u varijable ksnih imena a, b, c, . . ., nego ih pohranjujemo
u niz varijabli a
1
, a
2
, . . . , a
n
. Duljina niza n takoder moze biti varijabla.
U uvodnom poglavlju vec smo se susreli s nizovima varijabli. Algoritam za zbrajanje
prirodnih brojeva kao ulaz je uzimao dva niza znamenaka pribrojnika, a izlaz je bio niz
znamenaka zbroja. Oznacavali smo ih a
1
, . . . , a
n
, b
1
, . . . , b
n
i c
1
, . . . , c
n+1
. Ubuduce cemo
indekse nizova pisati u uglatim zagradama: a[1], . . . , a[n], b[1], . . . , b[n] i c[1], . . . , c[n +1].
Takva notacija koristi se u mnogim programskim jezicima (vidi primjere na str. 24).
U klasicnim programskim jezicima kao sto su FORTRAN, Pascal i C potrebno je
deklarirati tip podataka koji se spremaju u niz (npr. cijeli brojevi, realni brojevi ili
znakovi) i maksimalnu duljinu niza. Racunalo rezervira odgovarajucu kolicinu memo-
rije za pohranjivanje podataka u nizu, obicno na uzastopnim memorijskim lokacijama. U
Pythonu je interna reprezentacija nizova drugacija i moguce je tijekom izvodenja programa
rezervirati dodatnu memoriju za podatke u nizu. Na razini pseudojezika necemo se baviti
takvim detaljima. Pretpostavljat cemo da nizovi mogu imati po volji velik (konacan) broj
clanova i necemo im deklarirati tip i maksimalnu duljinu.
Jos jedan detalj koji ovisi o programskom jeziku je pocetni indeks niza. U nekim
programskim jezicima nizovi su indeksirani od 1, tj. niz duljine n sastoji se od clanova
a[1], . . . , a[n]. U drugim programskim jezicima pocetni indeks je 0, a niz duljine n sadrzi
clanove a[0], . . . , a[n 1]. U pseudojeziku cemo nekad koristiti jednu, a nekad drugu
konvenciju.
Susreli smo se s algoritmima koji na ulazu uzimaju niz brojeva (primjeri 4.124.16).
Svi dosadasnji primjeri probleme su rjesavali obradujuci clanove niza onim redom kojim
se unose. U bilo kojem trenutku izvodenja programa u varijablama je bio pohranjen samo
jedan clan niza, ili najvise dva uzastopna clana u algoritmima s Fibonaccijevim brojevima
(zadaci 4.184.22). Ako zelimo ispisati podatke u obrnutom redoslijedu od unesenog, ili
ih algoritam obraduje u nekom drugom redoslijedu, potrebno je istovremeno pamtiti sve
podatke u nizu varijabli.
Primjer 6.1. Program koji ucitava prirodan broj n i niz od n brojeva te ih ispisuje u
obrnutom redoslijedu.
53
54 POGLAVLJE 6. NIZOVI I SORTIRANJE
Rjesenje. Ako indeksi niza pocinju od 1, program izgleda ovako:
ucitaj n
za i = 1, . . . , n radi ucitaj a[i]
za i = 0, . . . , n 1 radi ispisi a[n i]
Ovo je rjesenje ako niz pocinje s indeksom 0:
ucitaj n
za i = 0, . . . , n 1 radi ucitaj a[i]
za i = 1, . . . , n radi ispisi a[n i]
Slika 6.1: Pocinju li indeksi nizova od 1 ili od 0?
1
U sljedecih nekoliko primjera nizove cemo indeksirati od 1. U iducem primjeru duljina
niza se ne ucitava na pocetku, nego se zadaje unosenjem dogovorenog podatka (nule) koji
oznacava kraj niza.
Primjer 6.2. Program koji ucitava brojeve i sprema ih u niz sve dok se ne ucita nula.
Na kraju ispisuje duljinu niza, prvi i zadnji clan niza.
Rjesenje.
n 0
ucitaj x
dok je x ,= 0 radi
_
_
n n + 1
a[n] x
ucitaj x
ispisi n, a[1], a[n]
1
Strip je preuzet s web stranice http://xkcd.com/163/
55
Algoritmi iz primjera 5.15.4 rade sa znamenkama zadanog prirodnog broja. Redo-
slijed kojim dolaze do znamenaka i obraduju ih ide od najmanje znacajne prema znacaj-
nijima. Ako znamenke zelimo ispisati u prirodnom redoslijedu, od najznacajnije prema
manje znajajnima, mozemo ih pohraniti u niz.
Primjer 6.3. Program ucitava prirodne brojeve n i b 2. Sprema znamenke broja n u
bazi b u niz i ispisuje ih od najznacajnije prema manje znacajnima.
Rjesenje.
ucitaj n, b
k 0
dok je n ,= 0 radi
_
_
k k + 1
z[k] n mod b
n n div b
za i = 0, . . . , k 1 radi ispisi z[k i]
Vazno je razlikovati clanove niza a[1], . . . , a[n] od njihovih indeksa 1, . . . , n. Iduca tri
primjera ilustriraju tu razliku.
Primjer 6.4. Program ucitava niz od n cijelih brojeva i ispisuje sve parne clanove niza.
Rjesenje.
ucitaj n
za i = 1, . . . , n radi
_
ako je a[i] mod 2 = 0 onda ispisi a[i]
Ako korisnik unese niz brojeva 4, 7, 2, 6, 9, 3, 10, prethodni program ispisuje 4, 2,
6, 10.
Primjer 6.5. Program ucitava niz od n cijelih brojeva i ispisuje indekse svih parnih
clanova niza.
Rjesenje.
ucitaj n
za i = 1, . . . , n radi
_
ako je a[i] mod 2 = 0 onda ispisi i
Za isti ulaz 4, 7, 2, 6, 9, 3, 10, ovaj program ispisuje 1, 3, 4, 7.
Primjer 6.6. Program ucitava niz od n cijelih brojeva i ispisuje sve clanove niza s parnim
indeksom.
Rjesenje.
ucitaj n
i 2
dok je i n radi
_
ispisi a[i]
i i + 2
Ovaj program za ulaz 4, 7, 2, 6, 9, 3, 10 ispisuje brojeve 7, 6, 3. U problemima u
kojima se trazi najveci clan niza cesto je vazan ne samo maksimum, nego i mjesto na
kojem se on nalazi u nizu.
Primjer 6.7. Program ucitava niz od n brojeva, ispisuje najveci clan niza i indeks mjesta
na kojem se on nalazi.
Rjesenje.
ucitaj n
max a[1]
imax 1
za i = 2, . . . , n radi
_
_
ako je a[i] > max onda
_
max a[i]
imax i
ispisi "Najve ci clan je", max
ispisi "Nalazi se na mjestu", imax
Tocnije, ako se najveci broj javlja nekoliko puta u nizu, ovaj program ispisuje prvi po
redu od indeksa na kojima se nalazi. Naprimjer, ako je niz 3, 10, 4, 8, 10, 7, program
ispisuje broj 10 i indeks 2. Program iz iduceg primjera ispisuje sve indekse na kojima se
nalazi najveci broj, tj. u ovom slucaju indekse 2 i 5.
Primjer 6.8. Program ucitava niz od n brojeva, ispisuje najveci clan niza i indekse svih
mjesta na kojima se on nalazi.
Rjesenje.
ucitaj n
max a[1]
za i = 2, . . . , n radi
_
ako je a[i] > max onda max a[i]
ispisi "Najve ci clan je", max
ispisi "Nalazi se na mjestima:"
za i = 1, . . . , n radi
_
ako je a[i] = max onda ispisi i
57
Sljedecih nekoliko primjera ilustrira kako mozemo promijeniti niz, tj. zamijeniti re-
doslijed nekih njegovih clanova.
Primjer 6.9. Program ucitava niz od n brojeva, zamjenjuje prvi i zadnji clan niza i
ispisuje promijenjeni niz.
Rjesenje.
ucitaj n
pom a[1]
a[1] a[n]
a[n] pom
za i = 1, . . . , n radi ispisi a[i]
Ako korisnik unese niz 3, 10, 4, 8, 9, 7, prethodni program ispisuje 7, 10, 4, 8, 9, 3.
Primjer 6.10. Program ucitava niz od n brojeva i okrece ga tako da na prvo mjesto
dode zadnji clan, na drugo mjesto predzadnji clan itd. Program ispisuje promijenjeni niz.
Rjesenje.
ucitaj n
za i = 1, . . . , (n div 2) radi
_
_
pom a[i]
a[i] a[n + 1 i]
a[n + 1 i] pom
Za niz 3, 10, 4, 8, 9, 7 na ulazu ovaj program ispisuje 7, 9, 8, 4, 10, 3. Vazno je da
petlja koja mijenja niz ide samo do n div 2, a ne do n. Petlja do n okrenula bi niz dva
puta, pa bi se ispisao isti niz koji je ucitan.
Primjer 6.11. Program ucitava niz od n brojeva i rotira ga za jedno mjesto ulijevo: na
prvo mjesto dolazi drugi clan niza, na drugo mjesto treci clan itd. Prvi clan niza dolazi
na zadnje mjesto. Program ispisuje promijenjeni niz.
Rjesenje.
ucitaj n
pom a[1]
za i = 1, . . . , n 1 radi a[i] a[i + 1]
a[n] pom
Ako korisnik unese niz 3, 10, 4, 8, 9, 7, ovaj program ispisuje 10, 4, 8, 9, 7, 3.
Primjer 6.12. Program ucitava niz od n brojeva, pronalazi najveci clan i zamjenjuje ga
s prvim clanom niza. Program ispisuje promijenjeni niz.
Rjesenje.
ucitaj n
max a[1]
imax 1
za i = 2, . . . , n radi
_
_
_
max a[i]
imax i
pom a[1]
a[1] a[imax]
a[imax] pom
Najveci clan niza 5, 9, 4, 10, 8, 7 je max = 10 i nalazi se na mjestu imax = 4. Nakon
zamjene s prvim clanom program ispisuje niz 10, 9, 4, 5, 8, 7.
Primjer 6.13. Program ucitava niz od n brojeva, pronalazi najveci clan niza i prebacuje
ga na prvo mjesto. Broj na prvom mjestu prebacuje na drugo mjesto, drugi broj na trece
mjesto i tako dalje sve do mjesta na kojem je najveci clan. Program ispisuje promijenjeni
niz.
Rjesenje.
ucitaj n
max a[1]
imax 1
za i = 2, . . . , n radi
_
_
_
max a[i]
imax i
pom a[imax]
za i = 0, . . . , imax 2 radi a[imax i] a[imax i 1]
a[1] pom
Ako je na ulazu niz 5, 9, 4, 10, 8, 7, ovaj program ispisuje 10, 5, 9, 4, 8, 7.
Za niz brojeva a[1], . . . , a[n] kazemo da je rastuci ili uzlazni ako za sve parove indeksa
i < j vrijedi a[i] a[j]. Niz je padajuci ili silazni ako za sve parove ineksa i < j
vrijedi a[i] a[j]. Da bismo po deniciji provjerili je li zadani niz rastuci ili padajuci,
59
usporedujemo clanove a[i] i a[j] za sve parove indeksa i < j. Za to nam trebaju dvije
petlje smjestene jedna unutar druge:
za i = 1, . . . , n 1 radi
_
za j = i + 1, . . . , n radi
_
ispisi i, j
Takve petlje nazivamo ugnijezdenima. Naprimjer, ako je n = 4, vanjska petlja s kontrol-
nom varijablom i izvodi se od 1 do 3. Za i = 1 unutrasnja petlja s kontrolnom varijablom
j izvodi se od 2 do 4. Za i = 2 unutrasnja petlja mijenja j od 3 do 4, a za i = 3 tijelo
unutrasnje petlje izvede se samo jednom, za j = 4. Rezultat je da program ispisuje re-
dom parove (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4). Ako zelimo provjeriti je li niz rastuci,
prije ulaza u petlje ucitavamo niz i postavljamo varijablu raste na 1. S dvije ugnijezdene
petlje generiramo sve parove indeksa i < j i u tijelu unutrasnje petlje provjeravamo je li
a[i] > a[j]. Ako je to ispunjeno bar za jedan par indeksa, niz nije rastuci pa postavljamo
varijablu raste na 0. S druge strane, ako za sve parove indeksa vrijedi a[i] a[j], vrijed-
nost varijable raste ostaje 1. Nakon izlaza iz petlji ispisujemo poruku da je niz rastuci ili
nije ovisno o tome sadrzi li varijabla raste 1 ili 0.
ucitaj n
raste 1
za i = 1, . . . , n 1 radi
_
za j = i + 1, . . . , n radi
_
ako je a[i] > a[j] onda raste 0
ako je raste = 1 onda ispisi "Niz je rastu ci"
inace ispisi "Niz nije rastu ci"
Mozemo ekasnije provjeriti je li niz rastuci, tako da usporedujemo samo susjedne
clanove niza. Niz je rastuci ako za sve indekse i = 1, . . . , n1 vrijedi a[i] a[i +1]. Zbog
tranzitivnosti uredaja medu brojevima tada za sve parove indeksa i < j vrijedi a[i] a[j].
ucitaj n
raste 1
za i = 1, . . . , n 1 radi
_
ako je a[i] > a[i + 1] onda raste 0
ako je raste = 1 onda ispisi "Niz je rastu ci"
Jos ekasniji program usporeduje susjedne clanove niza unutar while petlje i izlazi iz
petlje cim nade prvi par sa svojstvom a[i] > a[i + 1].
ucitaj n
i 1
dok je (i < n) i (a[i] a[i + 1]) radi i i + 1
ako je i = n onda ispisi "Niz je rastu ci"
Problem sortiranja sastoji se od toga da od proizvoljnog niza napravimo rastuci ili
padajuci niz premjestanjem njegovih clanova. Ako je rezultat rastuci niz kazemo da
smo ga sortirali uzlazno, a ako dobivamo padajuci niz govorimo o silaznom sortiranju.
Najjednostavniji algoritam za sortiranje usporeduje svaka dva clana niza i zamjenjuje
ih ako nisu u ispravnom redoslijedu. Taj algoritam zovemo klasicnim algoritmom za
sortiranje.
Primjer 6.14 (Klasicni algoritam za sortiranje). Program uzlazno sortira niz tako da za
sve parove indeksa i < j usporeduje clanove a[i] i a[j] i zamjenjuje ih ako je a[i] > a[j].
Rjesenje.
ucitaj n
za i = 1, . . . , n 1 radi
_
_
za j = i + 1, . . . , n radi
_
_
ako je a[i] > a[j] onda
_
_
pom a[i]
a[i] a[j]
a[j] pom
Za i = 1 unutrasnja petlja usporeduje prvi clan niza sa svim ostalima i zamjenjuje
ga ako nade manji broj. Nakon prvog prolaza kroz vanjsku petlju na prvom mjestu se
nalazi najmanji clan niza. U drugom prolazu usporeduje se drugi clan niza s narednim
clanovima. Na kraju je na drugom mjestu najmanji od preostalih clanova niza, tj. drugi
po velicini u nizu. Kad vanjska petlja dode do kraja niz je uzlazno sortiran.
Mozemo li niz sortirati usporedujuci samo susjedne clanove? Ovako izgleda program
koji jednom prolazi kroz niz i zamjenjuje susjedne clanove ako nisu u ispravnom redo-
slijedu.
za j = 1, . . . , n 1 radi
_
_
ako je a[j] > a[j + 1] onda
_
_
pom a[j]
a[j] a[j + 1]
a[j + 1] pom
Naprimjer, ako ga primijenimo na niz 5, 10, 2, 7, 3, 8, program ce redom raditi ove
zamjene.
j = 1: 5, 10, 2, 7, 3, 8 (nema zamjene jer su 1. i 2. clan u ispravnom redoslijedu)
j = 2: 5, 2, 10, 7, 3, 8 (zamjenjuje 2. i 3. clan)
Vidimo da niz jos nije sortiran, ali je najveci clan dosao na zadnje mjesto. Ako ponovimo
postupak s prvih n 1 clanova niza, na predzadnje mjesto dolazi najveci od tih clanova
61
i tako dalje. Niz ce biti sortiran kad ponovimo postupak n 1 puta.
za i = 1, . . . , n 1 radi
_
_
za j = 1, . . . , n i radi
_
_
_
_
pom a[j]
a[j] a[j + 1]
a[j + 1] pom
Ovaj algoritam naziva se bubble sort (mjehuricasto sortiranje). Unutrasnja petlja
pomice velike elemente prema kraju niza kao sto mjehurici zraka izlaze na povrsinu vode.
Algoritam mozemo uciniti ekasnijim tako da prekinemo izvrsavanje vanjske petlje cim
prodemo kroz unutrasnju petlju bez ijedne zamijene. Tada su svi susjedni elementi u
ispravnom redoslijedu i niz je rastuci.
Primjer 6.15 (Bubble sort). Program uzlazno sortira niz tako da usporeduje susjedne
clanove i zamjenjuje ih ako je prvi veci od drugog. Niz je sortiran kad dodemo do kraja
bez zamjene.
Rjesenje.
ucitaj n
raste 0
i 1
dok je (i < n) i (raste = 0) radi
_
_
raste 1
za j = 1, . . . , n i radi
_
_
_
_
pom a[j]
a[j] a[j + 1]
a[j + 1] pom
raste 0
i i + 1
Da bismo mogli usporedivati algoritme, trebamo ocijeniti njihovu ekasnost. Umjesto
preciznog racunanja vremena izvodenja kao u prethodnom poglavlju, obicno se daje gruba
ocjena brzine rasta vremena izvodenja u ovisnosti o velicini ulaznih podataka. Velicinu
ulaznih podataka ocjenjujemo prirodnim brojem n. Za problem sortiranja n je duljina
niza. Kod algoritama koji na ulazu imaju prirodan broj m, kakve smo imali u prethodnom
poglavlju, za velicinu se uzima broj njegovih binarnih znamenaka n = log
2
m| + 1.
Primijetimo da ulaznih podataka zadane velicine n moze biti puno. Vrijeme izvodenja
algoritma zato moze varirati za ksni n. Obicno se procjenjuje najgori moguci slucaj, tj.
najdulje vrijeme izvodenja za sve ulazne podatke velicine n. Naprimjer, nasi algoritmi
za sortiranje iz primjera 6.14 i 6.15 rade najbrze ako je na ulazu rastuci niz duljine n.
Takav niz je vec sortiran, pa algoritmi niti jednom ne zamjenjuju elemente. Ako je na
ulazu padajuci niz duljine n potreban je najveci broj zamjena, pa je u tom slucaju vrijeme
izvodenja najdulje. Ponekad se umjesto najduljeg vremena ocjenjuje prosjecno vrijeme
izvodenja za ulazne podatke velicine n.
Umjesto preciznog izracunavanja vremena izvodenja procjenjujemo broj operacija koje
algoritam napravi, ili cak samo jedne vrste operacija. Ako algoritam tijekom izvodenja
radi operacije zbrajanja i mnozenja, cesto se procjenjuje samo broj mnozenja jer je to
sporija operacija. Nasi algoritmi za sortiranje izvode operacije usporedivanja eleme-
nata niza i zamjene elemenata niza. Kao procjenu vremena izvodenja uzet cemo broj
usporedivanja, a broj zamjena cemo zanemariti.
Klasicni algoritam za sortiranje usporeduje elemente niza u tijelu unutrasnje petlje.
Za i = 1 unutrasnja petlja se izvodi n 1 puta, za i = 2 izvodi se n 2 puta i tako dalje.
Ukupan broj usporedivanja je
(n 1) + (n 2) + . . . + 2 + 1 =
n(n 1)
2
.
Slicnim razmatranjem vidimo da za padajuci niz duljine n algoritam bubble sort radi isti
broj usporedivanja, pa ta dva algoritma smatramo jednako ekasnima. Ipak, bubble sort
radi manje usporedivanja za rastuce nizove i nizove koji su blizu rastucih.
Broj usporedivanja
n(n1)
2
je kvadratni polinom u varijabli n. To je cesto jedina in-
formacija koja nas zanima kao procjena ekasnosti algoritma. Vrijeme izvodenja ovisi o
koecijentima polinoma, ali bitno nam je samo da vrijeme raste proporcionalno kvadratu
velicine ulaznih podataka n (za dovoljno veliki n linearni clan mozemo zanemariti).
Kazemo da klasicni algoritam za sortiranje i bubble sort algoritam imaju slozenost O(n
2
),
ili kvadratnu slozenost. Tocno znacenje notacije velikog O opisano je sljedecom deni-
cijom.
Denicija 6.16. Neka su f, g : N R funkcije kojima je domena skup prirodnih brojeva,
a kodomena skup realnih brojeva. Pisemo f(n) = O(g(n)) ako postoji realan broj M > 0
i prirodan broj n
0
takav da za sve prirodne brojeve n n
0
vrijedi f(n) M [g(n)[.
U nasem slucaju funkcija f(n) =
n(n1)
2
predstavlja broj usporedivanja pri sortiranju
niza duljine n, a g(n) = n
2
. Ocito za M = 1 i n
0
= 1 vrijedi f(n) n
2
, za sve n 1, pa
je f(n) = O(n
2
). Postoje ekasniji algoritmi za sortiranje kojima je slozenost O(nlog n),
naprimjer mergesort. Vrlo popularan algoritam je takozvani quicksort, kojem prosjecno
vrijeme izvodenja raste kao O(nlog n) (ako se promatra najgori slucaj slozenost mu je
ipak kvadratna). Vise o tim i mnogim drugim algoritmima za sortiranje mozete procitati
u knjigama [15] i [24].
Cesto je potrebno pronaci mjesto na kojem se zadani element nalazi u nizu, ili us-
tanoviti da nije u nizu. Ako niz nije sortiran, usporedujemo zadani element redom s
clanovima niza dok ga ne nademo ili dodemo do kraja niza.
Primjer 6.17. Program ucitava niz od n brojeva i broj x. Ispisuje najmanji indeks i na
kojem se u nizu nalazi x ili poruku o tome da x nije clan niza.
63
Rjesenje.
ucitaj n
ucitaj x
i 1
dok je (i n) i (a[i] ,= x) radi i i + 1
ako je i n onda
_
ispisi i
inace
_
ispisi "Niz ne sadr zi x"
Za ovaj algoritam najgori je slucaj kad x nije u nizu. Tada ga usporedujemo sa svim
elementima niza, pa je slozenost algoritma O(n) (linearna slozenost). Za pretrazivanje
sortiranih nizova postoji ekasniji algoritam logaritamske slozenosti O(log
2
n).
Primjer 6.18 (Binarno pretrazivanje). Program ucitava rastuci niz od n brojeva i broj x.
Usporeduje x sa srednjim elementom niza. Ako je srednji element veci, svi elementi desno
od njega takoder su veci od x i mozemo ih izbaciti iz razmatranja. Ako je srednji element
manji od x, izbacujemo iz razmatrama elemente lijevo od njega, tj. nastavljamo potragu
samo u desnoj polovici niza. Ponavljanjem ovog postupka pronalazimo mjesto na kojem
se nalazi x ili zakljucujemo da x nije clan niza.
Rjesenje.
ucitaj n
ucitaj x
lijevi 1
desni n
srednji (lijevi + desni) div 2
dok je (lijevi < desni) i (x ,= a[srednji]) radi
_
_
ako je x < a[srednji] onda
_
desni srednji 1
inace
_
lijevi srednji + 1
srednji (lijevi + desni) div 2
ako je x = a[srednji] onda
_
ispisi srednji
inace
_
ispisi "Niz ne sadr zi x"
Varijable lijevi i desni oznacavaju granice dijela niza u kojem trazimo x, a srednji
pokazuje na sredinu tog dijela niza. One sadrze indekse clanova niza na koje pokazuju;
takve varijable nazivamo kazaljkama. Ako korisnik unese duljinu n = 9, niz 2, 7, 10, 11,
13, 16, 20, 21, 25 i element x = 10, prije ulaza u petlju vrijednosti kazaljka su lijevi = 1,
desni = 9 i srednji = (1 + 9) div 2 = 5. U petlji usporedujemo x i a[srednji] =
13. Buduci da je manji od srednjeg elementa, postavljamo desni na srednji 1 = 4.
Izracunamo novu vrijednost kazaljke srednji = (1 + 4) div 2 = 2 i drugi puta izvodimo
petlju. Sada je x veci od a[2] = 7, pa postavljamo lijevi na 3 i srednji na (3+4) div 2 = 3.
Buduci da je x = a[3] = 10, izlazimo iz petlje i ispisujemo indeks na kojem se nalazi x.
Promotrimo kako radi algoritam ako u istom nizu trazimo element x = 22. Na pocetku
su vrijednosti kazaljki lijevi = 1, desni = 9, srednji = 5. Varijabla x je veca od srednjeg
elementa, pa u prvom prolazu kroz petlju kazaljke poprimaju vrijednosti lijevi = 6,
desni = 9, srednji = 7. U drugom prolazu kroz petlju x je i dalje veci od a[srednji],
pa kazaljke postaju lijevi = 8, desni = 9, srednji = 8. I u trecem prolazu je x veci
od srednjeg elementa, pa ce se kazaljke izjednaciti: lijevi = desni = srednji = 9. Sad
izlazimo iz petlje jer vise ne vrijedi lijevi < desni i ispisujemo poruku da niz ne sadrzi x.
U prvom primjeru usporedivali smo x = 10 samo s tri clana niza: a[5] = 13, a[2] = 7
i a[3] = 10. Tada smo ga pronasli u nizu koji ima ukupno 9 clanova. U drugom primjeru
usporedivali smo x = 23 s cetiri clana niza: a[5] = 13, a[7] = 20, a[8] = 21 i a[9] = 25.
Tada smo zakljucili da x nije u nizu. Opcenito, svaki prolaz kroz petlju smanjuje aktivni
dio niza (u kojem trazimo x) na pola, pa se tijelo petlje izvodi najvise log
2
n| puta. Zato
binarno pretrazivanje ima logaritamsku slozenost O(log
2
n).
U radu s nizovima pozeljno je da oni budu sortirani jer nam to omogucuje ekasnije
algoritme.

Cesta operacija je spajanje dvaju sortiranih nizova u niz koji takoder treba
biti sortiran. Naprimjer, nastavnik je prilikom ispravljanja podijelio testove u dvije hrpe
prema grupama zadataka koje su ucenici rjesavali. Slozio je te dvije hrpe abecednim
redom i zeli ih spojiti u jednu, takoder slozenu po abecedi.
Naivni pristup bio bi uzeti redom elemente prvog i drugog niza i sortirati spojeni niz.
Ako koristimo neki od nasih algoritama za sortiranje, dobili bismo algoritam kvadratne
slozenosti O(n
2
).

Cak i s ekasnijim algoritmima za sortiranje slozenost bi bila O(nlog n),
a moguce je postici linearnu slozenost O(n). Nastavnik moze staviti pred sebe dvije
sortirane hrpe testova i uzimati s vrha onaj od dvaju testova koji dolazi prije po abecedi.
Kad potrosi jednu hrpu, ostatak druge hrpe stavlja na kraj spojene hrpe testova. Tako
dobiva sve testove u abecednom redu. Odgovarajuci algoritam za nizove zovemo merge.
Primjer 6.19 (Merge). Program ucitava dva rastuca niza a[1], . . . , a[m] i b[1], . . . , b[n].
Spaja ih u rastuci niz c[1], . . . , c[m + n].
Rjesenje.
ucitaj m, n
za i = 1, . . . , m radi ucitaj a[i]
za j = 1, . . . , n radi ucitaj b[j]
i 1
j 1
k 0
65
dok je (i m) i (j n) radi
_
_
k k + 1
ako je a[i] b[j] onda
_
c[k] a[i]
i i + 1
inace
_
c[k] b[j]
j j + 1
dok je i m radi
_
_
k k + 1
c[k] a[i]
i i + 1
dok je j n radi
_
_
k k + 1
c[k] b[j]
j j + 1
za i = 1, . . . , m + n radi ispisi c[i]
Promotrimo kako radi algoritam za m = n = 5, niz a s clanovima 2, 5, 8, 9, 11 i
niz b s clanovima 3, 4, 6, 7, 8. Varijabla i pokazuje na vrh neobradenog dijela niza a,
varijabla j na vrh niza b, a varijabla k sadrzi trenutacni broj elemenata u spojenom nizu c.
Na pocetku je i = j = 1, k = 0. Program se sastoji od tri uzastopne while petlje. Prva
petlja prepisuje elemente nizova a i b u c dok ne dodemo do kraja jednog od ulaznih
nizova. Druga petlja prepisuje ostatak niza a u c, a treca ostatak niza b u c. Ako prva
petlja dode do kraja niza a izvodi se samo treca petlja, a ako dode do kraja niza b izvodi
se samo druga petlja.
Prva petlja usporeduje a[i] s b[j] i prepisuje manji broj u niz c. Ako su jednaki, prvo
prepisuje element iz a. Za nase ulazne nizove varijable se mijenjaju na sljedeci nacin:
1. prolaz: k = 1, c[1] = 2, i = 2
2. prolaz: k = 2, c[2] = 3, j = 2
3. prolaz: k = 3, c[3] = 4, j = 3
4. prolaz: k = 4, c[4] = 5, i = 3
5. prolaz: k = 5, c[5] = 6, j = 4
6. prolaz: k = 6, c[6] = 7, j = 5
7. prolaz: k = 7, c[7] = 8, i = 4
8. prolaz: k = 8, c[8] = 8, j = 6
Program izlazi iz prve petlje jer je j > n i u drugoj petlji prepisuje ostatak niza a u c:
1. prolaz: k = 9, c[9] = 9, i = 5
2. prolaz: k = 10, c[10] = 11, i = 6
U trecu petlju ne ulazi jer i dalje vrijedi j > n. Na kraju program ispisuje elemente
spojenog niza c: 2, 3, 4, 5, 6, 7, 8, 8, 9, 11. Kao procjenu velicine ulaznih podataka
uzimamo ukupan broj clanova oba ulazna niza m + n, a slozenost algoritma merge je
O(m + n). U iducem poglavlju koristit cemo ovaj algoritam za ekasnu implementaciju
operacija sa skupovima.
Zadaci
Zadatak 6.1. Napisite program koji ucitava prirodan broj n i ispisuje sve proste brojeve iz
skupa 1, . . . , n koristeci algoritam poznat kao Eratostenovo sito. Program u niz duljine
n sprema jedinice, osim na prvo mjesto na koje sprema nulu. Uzastopno ispisuje prvi po
redu clan niza razlicit od nule i sve njegove visekratnike postavlja na nulu.
Zadatak 6.2. Napisite dva programa koji provjeravaju je li zadani niz padajuci. Prvi
program neka usporeduje svaka dva clana niza, a drugi program samo susjedne clanove
niza.
Zadatak 6.3. Opisite kojim redom se mijenjaju elementi niza 7, 5, 10, 2, 4 pri uzlaznom
sortiranju klasicnim algoritmom i bubble sort algoritmom.
Zadatak 6.4. Napisite program koji silazno sortira niz s pomocu klasicnog algoritma.
Zadatak 6.5. Napisite program koji silazno sortira niz s pomocu bubble sort algoritma.
Zadatak 6.6. Modicirajte klasicni algoritam za sortiranje tako da unutarnja petlja ne
zamjenjuje elemente niza, nego samo trazi minimalni element. Nakon izlaza iz unutarnje
petlje minimalni element se zamjenjuje s i-tim elementom niza.
Zadatak 6.7. Dokazite: ako postoji konacan limes lim
n
f(n)
g(n)
, onda vrijedi f(n) = O(g(n)).
Zadatak 6.8. Ako je f(n) bilo koji polinom stupnja k, dokazite da je f(n) = O(n
k
).
Zadatak 6.9. Dokazite da za svake dvije baze a, b > 1 vrijedi log
a
n = O(log
b
n).
Zadatak 6.10. Neka su a, b > 1 baze eksponencijalnih funkcija. Dokazite da vrijedi
a
n
= O(b
n
) ako i samo ako je a b.
Zadatak 6.11. Napisite program koji ucitava niz od n brojeva i broj x. Program ispisuje
indekse svih clanova niza koji su jednaki x.
Zadatak 6.12. Mergesort je primjer rekurzivnog algoritma, tj. algoritma koji poziva
samog sebe s drugim ulaznim podacima.

Zelimo sortirati niz duljine n. Ako je n = 1, niz
je vec sortiran. U suprotnom podijelimo ga na dva podniza duljine n div 2 (odnosno, za
neparni n, na prvi podniz duljine n div 2 + 1 i drugi podniz duljine n div 2). Svaki od
ta dva podniza sortiramo algoritmom mergesort i zatim ih spojimo algoritmom merge iz
primjera 6.19. Opisite rad ovog algoritma za niz 6, 10, 2, 7, 5, 4, 8, 3 i pokusajte izvesti
njegovu slozenost.
Poglavlje 7
Jos neki matematicki algoritmi
S pomocu nizova na racunalu mozemo implementirati slozene matematicke objekte kao
sto su skupovi, permutacije, polinomi i matrice. U ovom poglavlju proucit cemo algoritme
za operacije s tim objektima.
Prvo cemo implementirati operacije s konacnim skupovima brojeva. Razlika izmedu
niza i skupa je u tome sto kod skupa redoslijed i ponavljanje pojedinih elemenata nisu
vazni. Naprimjer, 1, 2, 3, 1, 2, 2, 3, 3, 3 i 3, 2, 1 je jedan te isti skup. Zato skupove u
racunalu predstavljamo strogo rastucim nizovima, tj. rastucim nizovima bez ponavljanja.
Provjeru pripada li neki element skupu tada mozemo napraviti binarnim pretrazivanjem
u logaritamskom vremenu. Skupovne operacije cemo realizirati u linearnom vremenu.
Unija skupova A i B je skup koji se sastoji od elemenata koji su u A ili u B:
A B = x [ x A ili x B.
Ako su elementi od A pohranjeni u strogo rastucem nizu a[1], . . . , a[m], a elementi od B
u strogo rastucem nizu b[1], . . . , b[n], uniju C = AB dobivamo algoritmom vrlo slicnim
algoritmu merge. Jedina razlika je u tome sto elemente koji su u oba niza treba prepisati
u niz c samo jednom.
Primjer 7.1. Program ucitava strogo rastuce nizove a i b koji predstavljaju skupove A
i B. Denira i ispisuje niz c koji predstavlja uniju A B.
Rjesenje.
ucitaj m, n
i 1
j 1
k 0
67
68 POGLAVLJE 7. JO
S NEKI MATEMATI
CKI ALGORITMI
_
_
k k + 1
ako je a[i] b[j] onda
_
_
c[k] a[i]
ako je a[i] = b[j] onda j j + 1
i i + 1
inace
_
c[k] b[j]
j j + 1
dok je i m radi
_
_
k k + 1
c[k] a[i]
i i + 1
dok je j n radi
_
_
k k + 1
c[k] b[j]
j j + 1
za i = 1, . . . , k radi ispisi c[i]
Na kraju izvodenja ovog algoritma broj elemenata unije pohranjen je u varijabli k.
Kod algoritma merge iz primjera 6.19 varijabla k na kraju uvijek ima vrijednost m + n,
a u ovom algoritmu je manja od m + n za broj elemenata presjeka A B.
Presjek je skup koji se sastoji od elemenata koji su u A i u B:
A B = x [ x A i x B.
Algoritam za presjek slican je algoritmu merge, ali prepisuje element u c samo ako se
nalazi u oba niza a i b. Druga i treca while petlja nisu potrebne.
i B. Denira i ispisuje niz c koji predstavlja presjek A B.
Rjesenje.
ucitaj m, n
i 1
j 1
k 0
69
_
_
ako je a[i] = b[j] onda
_
_
k k + 1
c[k] a[i]
i i + 1
j j + 1
inace
_
_
ako je a[i] < b[j] onda
_
i i + 1
inace
_
j j + 1
Nakon izvodenja petlje broj elemenata presjeka pohranjen je u varijabli k. Treca
operacija koju cemo implementirati je razlika skupova. Skup A B sadrzi elemente iz A
koji nisu u B:
A B = x [ x A i x , B.
Algoritam prepisuje element iz a u c, osim ako se podudara s elementom iz b. Kad dode
do kraja niza b nastavlja prepisivati preostale elemente iz a u drugoj while petlji, a treca
petlja nije potrebna.
i B. Denira i ispisuje niz c koji predstavlja skupovnu razliku A B.
Rjesenje.
ucitaj m, n
i 1
j 1
k 0
_
_
ako je a[i] < b[j] onda
_
_
k k + 1
c[k] a[i]
i i + 1
inace
_
ako je a[i] = b[j] onda i i + 1
j j + 1
dok je i m radi
_
_
k k + 1
c[k] a[i]
i i + 1
70 POGLAVLJE 7. JO
S NEKI MATEMATI
CKI ALGORITMI
Kao i u prethodna dva algoritma, broj elemenata razlike A B na kraju je pohranjen
u varijabli k. Sva tri algoritma imaju slozenost O(m + n), isto kao algoritam merge iz
primjera 6.19.
Druga vrsta matematickih objekata za koje cemo razviti algoritme su permutacije.
Permutacije su bijekcije sa skupa 1, . . . , n na samog sebe. Opcenito, funkciju f :
1, . . . , m 1, . . . , n mozemo reprezentirati nizom brojeva duljine m. Ako je f(i) = j,
na i-to mjesto niza stavljamo broj j. Da bi funkcija bila bijekcija, mora biti injekcija i sur-
jekcija: razlicite elemente domene mora preslikavati u razlicite elemente kodomene i svaki
element kodomene mora biti pogoden nekim elementom iz domene. To je moguce samo
ako domena i kodomena imaju jednako monogo elemenata, tj. ako je m = n. Osnovna
operacija s permutacijama je kompozicija: (g f)(i) = g(f(i)).
Primjer 7.4. Program ucitava prirodan broj n i nizove f i g koji predstavljaju permutacije
skupa 1, . . . , n. Program denira i ispisuje niz h koji predstavlja njihovu kompoziciju.
Rjesenje.
ucitaj n
za i = 1, . . . , n radi ucitaj f[i]
za i = 1, . . . , n radi ucitaj g[i]
za i = 1, . . . , n radi
_
h[i] g[f[i]]
za i = 1, . . . , n radi ispisi h[i]
U matematici se permutacije ponekad zapisuju kao dva niza brojeva, od kojih je prvi
rastuci i predstavlja domenu. Naprimjer,
f =
_
1 2 3 4
2 4 1 3
_
je permutacija koja preslikava 1 2, 2 4, 3 1 i 4 3. Nasa reprezentacija
permutacija je ekonomicnija jer pamtimo samo donji niz brojeva. Poznato je da svaka
bijekcija ima inverznu funkciju. Inverznu permutaciju od f dobivamo tako da zamijen-
imo donji i gornji niz te sortiramo novi gornji niz uzlazno, uz odgovarajucu promjenu
redoslijeda donjeg niza:
f
1
=
_
2 4 1 3
1 2 3 4
_
=
_
1 2 3 4
3 1 4 2
_
.
Taj algoritam imao bi slozenost O(n
2
), ili O(nlog n) ako se koristimo ekasnijim algorit-
mom za sortiranje. Inverznu permutaciju mozemo dobiti elegantnijim algoritmom linearne
slozenosti O(n).
Primjer 7.5. Program ucitava prirodan broj n i niz f koji predstavlja permutaciju skupa
1, . . . , n. Program denira i ispisuje niz g koji predstavlja inverz ucitane permutacije.
71
Rjesenje.
ucitaj n
za i = 1, . . . , n radi
_
g[f[i]] i
za i = 1, . . . , n radi ispisi g[i]
Druga vazna vrsta funkcija su polinomi. Za funkciju f : R R kazemo da je polinom
ako je oblika f(x) = a
n
x
n
+a
n1
x
n1
+. . . +a
1
x+a
0
. Pritom su a
0
, . . . , a
n
R konstante
koje zovemo koecijentima polinoma. Koecijent a
n
,= 0 zovemo vodecim koecijentom,
a n stupnjem polinoma. Polinom ocito mozemo reprezentirati u racunalu tako da u niz
spremimo njegove koecijente. Uobicajeno je koecijent uz x
i
oznaciti indeksom i, pa
cemo u programima za rad s polinomima nizove indeksirati od nule.
Vaznost polinoma je u tome sto s njima mozemo dobro aproksimirati druge, kom-
pliciranije funkcije. Polinomi su jednostavni jer za dani x R vrijednost f(x) mozemo
izracunati s konacno mnogo zbrajanja i mnozenja realnih brojeva. Buduci da je izracu-
navanje vrijednosti polinoma vrlo cesta operacija, zelimo algoritam koji koristi sto manje
mnozenja i zbrajanja. Nespretni algoritam izgleda ovako.
Primjer 7.6. Program ucitava prirodan broj n, niz koecijenata a[0], . . . , a[n] i broj x te
izracunava i ispisuje vrijednost polinoma f(x). Ovaj program koristi puno vise operacija
zbrajanja i mnozenja nego sto je potrebno.
Rjesenje.
ucitaj n
ucitaj x
f 0
za i = 0, . . . , n radi
_
_
p 1
za j = 1, . . . , i radi p p x
f f + a[i] p
ispisi f
Ovo je algoritam slozenosti O(n
2
) u stupnju polinoma n. U unutrasnjoj petlji izracuna-
vamo vrijednost potencije p = x
i
uzastopnim mnozenjem s x. Potenciju mozemo ekasnije
izracunati uzastopnim kvadriranjem. Naprimjer, x
4
mozemo umjesto kao produkt x x
x x izracunati kao (x
2
)
2
. Uzastopnim kvadriranjem dobivamo potencije od x kojima su
eksponenti potencije od 2: x, x
2
, x
4
, x
8
, x
16
. . . Ako i nije potencija od dva, x
i
treba
prikazati kao produkt takvih potencija, naprimjer x
11
= x
1+2+8
= x x
2
x
8
. Pojavljuju se
eksponenti 2
k
koji odgovaraju jedinicama u binarnom zapisu broja i. Opceniti algoritam
za potenciranje uzastopnim kvadriranjem izgleda ovako.
Primjer 7.7 (Brzo potenciranje). Program ucitava realan broj x R i prirodan broj
i N te uzastopnim kvadriranjem izracunava potenciju p = x
i
.
72 POGLAVLJE 7. JO
S NEKI MATEMATI
CKI ALGORITMI
Rjesenje.
ucitaj x, i
p 1
dok je i ,= 0 radi
_
_
ako je (i mod 2) = 1 onda p p x
x x x
i i div 2
ispisi p
Ako je na ulazu x = 2, i = 11, program postavlja p = 1 i zatim radi ovako:
1. prolaz kroz petlju: p = 2, x = 4, i = 5
Nakon izlaza iz petlje ispisuje p = 2048 = 2
11
. Ovo je algoritam logaritamske slozenosti
O(log
2
n) (za n = i), dok je potenciranje uzastopnim mnozenjem s x (kao u primjeru 7.6)
algoritam linearne slozenosti. Kad bismo u primjeru 7.6 potencije racunali na ovaj nacin,
dobili bismo algoritam za izracunavanje polinoma slozenosti O(nlog
2
n). Medutim, na
puno jednostavniji nacin mozemo dobiti algoritam linearne slozenosti O(n) samo isko-
ristimo potenciju x
i1
iz prethodnog koraka da dobijemo x
i
= x x
i1
.
Primjer 7.8. Program ucitava prirodan broj n, niz koecijenata a[0], . . . , a[n] i broj x te
izracunava i ispisuje vrijednost polinoma f(x). Ovo je program linearne slozenosti, ali
postoji jos ekasniji algoritam.
Rjesenje.
ucitaj n
ucitaj x
f 0
p 1
za i = 0, . . . , n radi
_
f f + a[i] p
p p x
ispisi f
Jos ekasniji algoritam dobivamo ako polinom f(x) = a
n
x
n
+. . . +a
1
x +a
0
zapisemo
na drugi nacin:
f(x) = (( (((a
n
x + a
n1
)x + a
n2
)x + a
n3
)x + + a
2
)x + a
1
)x + a
0
.
Primijetimo da izracunavanje pocinje iznutra, od vodeceg koecijenta prema koeci-
jentima uz nize potencije. Zato cemo u programu trebati silaznu petlju. Ovaj nacin
izracunavanja polinoma naziva se Hornerovim algoritmom.
73
Primjer 7.9 (Hornerov algoritam). Program ucitava prirodan broj n, niz koecijenata
a[0], . . . , a[n] i broj x te izracunava i ispisuje vrijednost polinoma f(x). Ovo je najekasniji
algoritam.
Rjesenje.
ucitaj n
ucitaj x
f 0
za i = n, . . . , 0 radi
_
f f x + a[i]
ispisi f
Slozenost Hornerova algoritma takoder je O(n), ali on koristi upola manje mnozenja
od algoritma iz primjera 7.8. Za izracunavanje vrijednosti polinoma stupnja n algoritam
iz primjera 7.8 koristi 2(n + 1) mnozenja i n + 1 zbrajanja, a Hornerov algoritam samo
n + 1 mnozenja i isto toliko zbrajanja.
Zbroj, produkt i kompozicija polinoma je ponovo polinom. Osim toga polinome
mozemo dijeliti s ostatkom i izracunavati im najvecu zajednicku mjeru Euklidovim al-
goritmom, slicno kao za prirodne brojeve. U iducem primjeru je algoritam za mnozenje
polinoma, a ostale operacije s polinomima ostavljamo za zadatke.
Primjer 7.10. Program ucitava stupnjeve m, n i koecijente a[0], . . . , a[m], b[0], . . . , b[n]
dvaju polinoma te izracunava i ispisuje koecijente njihovog produkta.
Rjesenje.
ucitaj m, n
za i = m + 1, . . . , m + n radi a[i] 0
za i = 0, . . . , n radi ucitaj b[i]
za i = n + 1, . . . , m + n radi b[i] 0
za i = 0, . . . , m + n radi
_
_
c[i] 0
za j = 0, . . . , i radi
_
c[i] c[i] + a[j] b[i j]
za i = 0, . . . , m + n radi ispisi c[i]
Ovo je algoritam slozenosti O((m+n)
2
). Nizove a i b smo nadopunili vodecim nulama
da bi unutrasnja petlja bila jednostavnija. Pokusajte realizirati program bez nadopunja-
vanja nulama, pazeci da indeksi a[j] i b[i j] u untrasnjoj petlji ne predu m, odnosno n.
74 POGLAVLJE 7. JO
S NEKI MATEMATI
CKI ALGORITMI
Matrice su pravokutne tablice brojeva. O njima mozemo razmisljati kao o dvodimen-
zionalnim nizovima, tj. nizovima s dva indeksa:
a[1][1] a[1][2] a[1][3] a[1][n]
a[2][1] a[2][2] a[2][3] a[2][n]
.
.
.
.
.
.
.
.
.
.
.
.
a[m][1] a[m][2] a[m][3] a[m][n]
Prvi indeks oznacava redak, a drugi indeks stupac matrice. Ako matrica ima m redaka
i n stupaca, govorimo o matrici tipa mn. Za ucitavanje elemenata matrice trebaju nam
dvije ugnijezdene petlje:
ucitaj m, n
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi
_
ucitaj a[i][j]
Da bismo ispisali elemente matrice u tablicnom obliku, trebamo kontrolirati format ispisa
i prijelaz u novi red. To u programskim jezicima FORTRAN, Pascal, C i Python mozemo
na sljedeci nacin.
Ispisivanje matrice
FORTRAN Pascal
for i:=1 to m do
DO, i=1,m begin
WRITE(*,"100I4") (a(i,j), j=1,n) for j:=1 to n do
ENDDO write(a[i][j]:4, );
writeln();
end;
C Python
for (i=0; i<m; ++i) for i in range(m):
{ for (j=0; j<n; ++j) for j in range(n):
printf("%4d ",a[i][j]); print {0:4d}.format(a[i][j]),
printf("\n"); print
}
U pseudojeziku necemo brinuti o formatu, nego cemo jednostavno ispisati sve elemente
matrice:
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi
_
ispisi a[i][j]
75
S matricama kao matematickim objektima denirane su operacije zbrajanja, mnozenja
skalarom (brojem) i medusobnog mnozenja matrica. Zbajati mozemo matrice istog tipa,
a zbroj je matrica ciji su elementi zbojevi odgovarajucih elemenata prve i druge matrice.
Primjer 7.11. Program ucitava prirodne brojeve m, n i dvije matrice tipa mn. Denira
i ispisuje zbroj ucitanih matrica.
Rjesenje.
ucitaj m, n
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi ucitaj a[i][j]
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi ucitaj b[i][j]
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi
_
c[i][j] a[i][j] + b[i][j]
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi ispisi c[i][j]
Mnozenje matrice skalarom denirano je slicno, po koordinatama (vidi zadatak 7.16).
Da bismo matrice mogli medusobno mnoziti, one moraju biti ulancane, tj. broj stupaca
prve matrice mora biti jednak broju redaka druge matrice. Element c[i][j] produkta
dobivamo skalarnim mnozenjem i-tog retka prve matrice i j-tog stupca druge matrice:
c[i][j] =
p
k=1
a[i][k] b[k][j].
U linearnoj algebri matrice reprezentiraju linearne operatore, a mnozenje matrica odgo-
vara kompoziciji linearnih operatora.
Primjer 7.12. Program ucitava prirodne brojeve m, p, n, matricu tipa mp i matricu
tipa p n. Denira i ispisuje matricu tipa mn koja je umnozak ucitanih matrica.
Rjesenje.
ucitaj m, p, n
za i = 1, . . . , m radi
_
za j = 1, . . . , p radi ucitaj a[i][j]
za i = 1, . . . , p radi
_
za j = 1, . . . , n radi ucitaj b[i][j]
za i = 1, . . . , m radi
_
_
za j = 1, . . . , n radi
_
_
c[i][j] 0
za k = 1, . . . , p radi
_
c[i][j] c[i][j] + a[i][k] b[k][j]
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi ispisi c[i][j]
76 POGLAVLJE 7. JO
S NEKI MATEMATI
CKI ALGORITMI
Matrice tipa n n zovemo kvadratnim matricama reda n. Kod algoritama za rad
s matricama red se cesto uzima kao velicina ulaznih podataka, iako se matrice zapravo
sastoje od n
2
brojeva. U tom slucaju zbrajanje matrica je operacija slozenosti O(n
2
), a
mnozenje matrica operacija slozenosti O(n
3
) (jer se algoritam sastoji od tri ugnijezdene
petlje). Jos jedna operacija s matricama je transponiranje, tj. zamjena uloge redaka i
stupaca.
Primjer 7.13. Program ucitava kvadratnu matricu reda n, transponira je i ispisuje.
Rjesenje.
ucitaj n
za i = 1, . . . , n radi
_
za i = 1, . . . , n 1 radi
_
_
za j = i + 1, . . . , n radi
_
_
pom a[i][j]
a[i][j] a[j][i]
a[j][i] pom
za i = 1, . . . , n radi
_
za j = 1, . . . , n radi ispisi a[i][j]
U ovom programu vazno je da unutrasnja petlja pocinje od i +1. Kad bismo zamjene
radili za j = 1, . . . , n, time bismo matricu dva puta transponirali pa bi bila jednaka
ucitanoj matrici, slicno kao u primjeru 6.10. Daljnji primjeri algoritama koji rade s
matricama dani su u zadacima 7.197.30.
Vidimo da algoritmi imaju vaznu ulogu u matematici. U primijenjenoj matematici cilj
je ekasno implementirati na racunalu matematicke objekte i racunske operacije s njima,
tako da se izvode sto brze. To je vazno u matematickom modeliranju prirodnih pojava,
simulacijama, racunalnoj graci i primjenama kao sto su digitalne komunikacije, krip-
tograja, geografski informacijski sustavi, navigacija s pomocu racunala, racunalna tomo-
graja i drugo. Pitanje postojanja ekasnih algoritama vazno je i s teorijskog stanovista.
Jedno od najvecih otvorenih pitanja u matematici je takozvani problem P=NP i tice se
postojanja algoritama polinomijalne slozenosti za odredene klase problema (vidi [30]).
Poznati matematicki institut Clay uvrstio je P=NP medu milenijske probleme, za koje
nudi nagradu od milijun americkih dolara [4].
Algoritamski nacin razmisljanja prozima matematiku od njezinih pocetaka. U staro-
grckoj matematici racunanje nije imalo tako istaknutu ulogu, nego je u sredistu interesa
bila geometrija. Euklid u svojim Elementima opisuje mnoge konstrukcije ravnalom i
sestarom (vidi [6] i [13]). S modernog stanovista mozemo reci da su geometrijske kon-
strukcije zapravo algoritmi za crtanje s pomocu ravnala i sestara. Naprimjer, konstrukciju
77
jednakostranicnog trokuta mozemo opisati sljedecim algoritmom.
_
_
ulaz: tocke A, B
nacrtaj duzinu AB
nacrtaj kruznicu k
1
sa sredistem u A koja prolazi kroz B
nacrtaj kruznicu k
2
sa sredistem u B koja prolazi kroz A
oznaci sjeciste kruznica k
1
i k
2
sa C
nacrtaj duzinu BC
nacrtaj duzinu AC
Geometrijske konstrukcije na racunalu mozemo implementirati u programima dinamicke
geometrije kao sto su GeoGebra [9] i The Geometers Sketchpad [10].
Slika 7.1: Konstrukcija jednakostranicnog trokuta u GeoGebri.
78 POGLAVLJE 7. JO
S NEKI MATEMATI
CKI ALGORITMI
Zadaci
Zadatak 7.1. Detaljno opisite rad algoritama za uniju, presjek i skupovnu razliku ako su
na ulazu skupovi A = 2, 5, 8, 10, 12, 15 i B = 4, 5, 6, 10, 11, 12, 20.
Zadatak 7.2. Dokazite da za svaka dva skupa A i B vrijedi (A B) (B A) = (A
B) (A B). Taj skup nazivamo simetricnom razlikom skupova A i B i oznacavamo ga
s AB.
Zadatak 7.3. Napisite program koji ucitava strogo rastuce nizove a i b koji predstavljaju
skupove A i B. Program denira i ispisuje niz c koji predstavlja simetricnu razliku AB.
Zadatak 7.4. Napisite program koji ucitava prirodne brojeve m, n i niz brojeva f[1], . . . ,
f[m] iz skupa 1, . . . , n. Program povjerava i ispisuje je li funkcija f : 1, . . . , m
1, . . . , n reprezentirana tim nizom injekcija, odnosno surjekcija.
Zadatak 7.5. Dokazite da je funkcija f : 1, . . . , n 1, . . . , n injekcija ako i samo
ako je surjekcija.
Zadatak 7.6. Dokazite da je funkcija bijekcija ako i samo ako ima inverznu funkciju.
Na osnovu toga napisite program koji provjerava bijektivnost funkcije f : 1, . . . , n
1, . . . , n u linearnom vremenu O(n).
Zadatak 7.7. Neka je f permutacija skupa 1, . . . , n. Svaki par (i, j) elemenata tog
skupa za koji vrijedi i < j i f(i) > f(j) nazivamo inverzijom permutacije f. Napisite
program koji ucitava permutaciju f i ispisuje broj inverzija te permutacije.
Zadatak 7.8. Ciklicka permutacija ili ciklus (i
1
i
2
i
d
) je permutacija koja preslikava
i
1
i
2
, i
2
i
3
, . . . , i
d1
i
d
, i
d
i
1
, a ostale elemente domene preslikava u same
sebe. Napisite program koji ucitava proizvoljnu permutaciju f i prikazuje f kao produkt
disjunktnih ciklusa.
Zadatak 7.9. Napisite program koji ucitava prirodan broj n i ispisuje sve permutacije
skupa 1, . . . , n.
Zadatak 7.10. Detaljno opisite rad algoritma za brzo potenciranje iz primjera 7.7 za ulaz
x = 3, i = 10.
Zadatak 7.11. Detaljno opisite rad algoritama iz primjera 7.6, 7.8 i 7.9 za izracunavanje
polinoma f(x) = 2x
3
x
2
+ x + 3 u tocki x = 2.
Zadatak 7.12. Napisite program koji ucitava stupnjeve m, n i koecijente a[0], . . . , a[m],
b[0], . . . , b[n] dvaju polinoma te izracunava i ispisuje koecijente njihovog zbroja.
b[0], . . . , b[n] dvaju polinoma te izracunava i ispisuje koecijente njihove kompozicije.
Zadatak 7.14. Dokazite teorem o dijeljenju polinoma s ostatkom: za svaki polinom f(x)
i svaki polinom g(x) razlicit od nulpolinoma postoje jedinstveni polinomi q(x) i r(x) takvi
da je f(x) = q(x) g(x) + r(x) i stupanj od r(x) je manji od stupnja od g(x). Polinom
q(x) nazivamo kvocijentom, a polinom r(x) ostatkom pri dijeljenju tih polinoma.
79
b[0], . . . , b[n] dvaju polinoma te izracunava i ispisuje koecijente kvocijenta i ostatka pri
dijeljenju ta dva polinoma.
Zadatak 7.16. Napisite program koji ucitava matricu tipa mn i skalar (broj). Program
denira i ispisuje produkt ucitane matrice s ucitanim skalarom.
Zadatak 7.17. Napisite program koji ucitava kvadratnu matricu reds n te provjerava i
ispisuje je li ucitana matrica simetricna. Za matricu kazemo da je simetricna ako je
jednaka svojoj transponiranoj matrici, tj. ako za sve indekse vrijedi a[i][j] = a[j][i].
Zadatak 7.18. Sjetite se denicije i svojstava determinante kvadratne matrice (vidi [12]).
Razmislite o tome koja je slozenost algoritama za izracunavanje determinante reda n po
deniciji, Laplaceovim razvojem i svodenjem na gornjetrokutasti oblik.
Zadatak 7.19. Napisite program koji ucitava mn matricu i ispisuje indekse svih redaka
u kojima je zbroj elemenata pozitivan.
Zadatak 7.20. Napisite program koji ucitava mn matricu i ispisuje indekse svih stupaca
u kojima ima paran broj nula.
Zadatak 7.21. Napisite program koji ucitava mn matricu s cjelobrojnim elementima i
ispisuje ukupan broj neparnih elemenata matrice na mjestima s parnim indeksom stupca.
Zadatak 7.22. Napisite program koji ucitava m n matricu i ispisuje indeks retka u
kojem je zbroj elemenata najveci.
Zadatak 7.23. Napisite program koji ucitava m n matricu i ispisuje indeks stupca u
kojem je produkt elemenata najmanji.
Zadatak 7.24. Napisite program koji ucitava m n matricu i ispisuje indeks retka u
kojem ima najvise nula te broj nula u tom retku.
kojem ima najvise negativnih brojeva te broj negativnih brojeva u tom stupcu.
Zadatak 7.26. Napisite program koji ucitava mn matricu s cjelobrojnim elementima
i ispisuje indeks retka u kojem ima najvise parnih brojeva.
kojem je zbroj pozitivnih elemenata najveci.
Zadatak 7.28. Napisite program koji ucitava mn matricu s cjelobrojnim elementima
i ispisuje indeks retka u kojem je zbroj parnih elemenata najmanji.
Zadatak 7.29. Napisite program koji ucitava m n matricu i pronalazi koji je od svih
najvecih elemenata po stupcima najmanji. Program ispisuje taj element i indekse retka i
stupca u kojima se nalazi.
Zadatak 7.30. Napisite program koji ucitava m n matricu i pronalazi koji je od svih
najmanjih elemenata po recima najveci. Program ispisuje taj element i indekse retka i
stupca u kojima se nalazi.
80 POGLAVLJE 7. JO
S NEKI MATEMATI
CKI ALGORITMI
Zadatak 7.31. Binarna realcija na skupu 1, . . . , n je podskup Kartezijeva produkta
R 1, . . . , n 1, . . . , n. Na racunalu je mozemo implementirati kao nn matricu r
popunjenu nulama i jedinicama. Ako je (i, j) R stavljamo r[i][j] = 1, a ako (i, j) , R
stavljamo r[i][j] = 0. Napisite program koji ucitava 0-1 matricu r i provjerava koja od
sljedecih svojstava ima odgovarajuca binarna relacija:
reeksivnost: za svaki i 1, . . . , n, (i, i) R;
simetricnost: za sve i, j 1, . . . , n, ako je (i, j) R, onda je (j, i) R;
antisimetricnost: za sve i, j 1, . . . , n, ako je (i, j) R i (j, i) R, onda je
i = j;
tranzitivnost: za sve i, j, k 1, . . . , n, ako je (i, j) R i (j, k) R, onda je
(i, k) R.
Zadatak 7.32. Opisite u obliku algoritma konstrukciju kvadrata i konstrukciju pravilnog
sesterokuta sa zadanom stranicom AB. Implementirajte konstrukcije u programu GeoGe-
bra [9] ili u nekom drugom programu za dinamicku geometriju.
Zadatak 7.33. Opisite u obliku algoritma i implementirajte na racunalu konstrukcije
pravilnog peterokuta i pravilnog deseterokuta.
Poglavlje 8
Prikaz brojeva u racunalu
U prethodnim poglavljima pretpostavljali smo da algoritmi egzaktno racunaju s cijelim i
s realnim brojevima. To u stvarnosti nije moguce zbog ogranicenog kapaciteta memorije
racunala i zbog prirode realnih brojeva. U ovom poglavlju upoznat cemo se s nacinom na
koji se brojevi prikazuju u racunalu i s ogranicenjima algoritama koja iz toga proizlaze.
Memorija racunala sastoji se od elemenata koji poprimaju jedno od dva moguca stanja.
Radnu memoriju (RAM) cine elektronicki sklopovi bistabili (eng. ip-op), realizirani u
poluvodickim integriranim krugovima. Kad ugasimo racunalo, radna memorija se brise.
Vanjska memorija je trajnog karaktera i za nju postoje razlicita tehnoloska rjesenja: tvrdi
diskovi (magnetne memorije), CD-i i DVD-i (opticki mediji), a u novije vrijeme ash
memorije, tzv. solid state diskovi. Svim tipovima memorije zajednicko je da se podaci
pamte kao nizovi binarnih znamenaka, bitova magnetiziranjem povrsine diska u suprot-
nim smjerovima, mikroskopskim udubinama i izbocinama na optickom mediju, ili s dvije
razine napona u elektronickim sklopovima. Zato je binarni brojevni sustav osnova za
prikaz brojeva i drugih podataka u racunalu.
Memorija je organizirana u nizove od osam bitova koje nazivamo bajtovima (eng. byte).
Bajt moze poprimiti 2
8
= 256 stanja. Vece jedinice za kolicinu memorije su kilobajt (kB)
10
3
bajtova, megabajt (MB) 10
6
bajtova, gigabajt (GB) 10
9
bajtova i terabajt (TB)
10
12
bajtova. Preksi kilo, mega, giga i tera u SI sustavu oznacavaju potencije od 10. U
racunarstvu se umjesto toga cesto koriste bliske potencije od 2: kibibajt (KiB) oznacava
2
10
= 1024 bajtova, a mebibajt (MiB), gibibajt (GiB) i tebibajt (TiB) redom 2
20
, 2
30
i
2
40
bajtova. Osobna racunala danas tipicno imaju nekoliko gigabajta radne memorije i
tvrde diskove od nekoliko stotina gigabajta do nekoliko terabajta.
Procesor racunala ne moze direktno racunati s brojevima u radnoj memoriji, nego ih
prethodno mora dohvatiti u registre. Kapacitet procesorskih registara obicno iznosi 32 ili
64 bita. Ako za racunanje koristimo aritmetiku ugradenu u procesor, ograniceni smo na
32 ili 64 binarne znamenke. Moguce je napisati vlastite algoritme za racunanje s velikim
brojevima, ali su oni znatno sporiji od procesorske aritmetike. Objasnit cemo ogranicenja
te, strojne aritmetike.
Kolicina memorije koja stane u registar naziva se rijec (eng. word). Oznacimo s w
broj bitova u jednoj rijeci (u praksi je najcesce w = 32 ili w = 64). Niz bitova jedne rijeci
mozemo shvatiti kao prikaz prirodnog broja ili nule u binarnom sustavu. Tome odgovara
tip podataka unsigned integer u programskom jeziku C i nekim drugim programskim
81
82 POGLAVLJE 8. PRIKAZ BROJEVA U RA
CUNALU
jezicima. Najmanji prikazivi broj je tada 0, a najveci 2
w
1.
Kod prikaza cijelih brojeva vodeci bit oznacava predznak: 0 za prirodne brojeve i nulu,
a 1 za negativne cijele brojeve. Negativni brojevi prikazuju se s pomocu dvojnog komple-
menta (eng. twos complement). Binarne znamenke se komplementiraju, tj. zamijene se
znamenke 0 i 1, te se rezultat uveca za 1. Naprimjer, prikaz broja 22 u rijeci duljine
w = 8 dobije se od niza binarnih znamenaka 00010110 komplementiranjem 11101001 i
dodavanjem 1:
11101010
Niz bitova kojim je broj prikazan u racunalu oznacavat cemo pravokutnim okvirom.
Ovaj nacin prikazivanja cijelih brojeva odgovara tipu integer u klasicnim programskim
jezicima. Prednost prikaza s dvojnim komplementom je u tome sto nije potreban poseban
algoritam za oduzimanje (i odgovarajuci aritmeticki sklopovi procesora), nego se koristi
isti algoritam kao za zbrajanje. Naprimjer, razliku 10022 u 8-bitnoj aritmetici racunamo
tako da zbrojimo prikaze brojeva 100 i 22:
01100100
11101010
+
1 01001110
Prijenos u deveti bit zanemarujemo, pa prikaz 01001110 odgovara broju 78 = 100 22.
Analogna metoda oduzimanja funkcionira u pozicionom sustavu s bilo kojom bazom b,
a ne samo u binarnom sustavu. Komplementiranje je zamjena znamenaka koje u sumi
daju b 1. Naprimjer, u sustavu s bazom 10 zamjenjujemo 0 9, 1 8, 2 7, 3 6
i 4 5. Ako zelimo izracunati razliku 253219 38492, nadopunimo drugi broj nulom i
komplementiramo ga: 961507. Dodamo jedan i zbrojimo 961508 s prvim brojem:
253219
+ 961508
,1 214727
Zanemarujemo vodecu jedinicu i tako dobijemo razliku 214727. Nije tesko razumjeti
zasto posupak funkcionira; komplement 961507 je zapravo razlika 999999 38492, a kad
ga uvecamo za jedan razlika 1000000 38492. Zbrajanjem s 253219 i zanemarivanjem
vodece jedinice 1000000 dobivamo 25321938492. Objasnjenje je analogno u binarnom
i u drugim sustavima.
Najveci prikazivi broj u rijeci duljine w na ovaj nacin je 2
w1
1 i ima prikaz 011 11 .
Broj 0 i broj 1 imaju redom prikaze 000 00 i 111 11 . Najmanji prikazivi broj je
2
w1
, s prikazom 100 00 . Naprimjer, u 32-bitnoj aritmetici najmanji prikazivi cijeli
broj je 2
31
= 2147483648, a najveci prikazivi broj je 2
31
1 = 2147483647. U to se
mozemo uvjeriti ako prevedemo i pokrenemo sljedeci C program na 32-bitnom racunalu.
83
#include <stdio.h>
int main()
{ int n;
n=1;
while (n>0) n=n+1;
printf("Najmanji prikazivi broj: %d\n",n);
n=n-1;
printf("Najveci prikazivi broj : %d\n",n);
}
Program bi u pseudojeziku glasio ovako:
n 1
dok je n > 0 radi n n + 1
ispisi "Najmanji prikazivi broj:", n
n n 1
ispisi "Najveci prikazivi broj :", n
Varijabla n inicijalizira se na 1 i povecava sve dok je pozitivna. Kad bismo imali egzaktnu
aritmetiku, to bi bila beskonacna petlja. Medutim, zbog ogranicenog broja bitova u rijeci
varijabla n ce dosegnuti najveci prikazivi cijeli broj 011 11 . Iduca naredba n n+1
pretvara ga u broj s prikazom 100 00 . To je najmanji prikazivi broj i negativan je,
pa program izlazi iz petlje i ispisuje ga. Naredba n n 1 ponovo vraca n na najveci
prikazivi cijeli broj i zatim ga program ispisuje. Na ekranu dobivamo sljedeci ispis.
Najmanji prikazivi broj: -2147483648
Najveci prikazivi broj : 2147483647
Odgovarajuci program u Pythonu izgleda ovako:
n = 1
while n>0:
n = n + 1
print "Najmanji prikazivi broj:", n
n = n - 1
print "Najveci prikazivi broj:", n
Ovaj program zaista se ponasa kao beskonacna petlja jer Python koristi vlastite al-
goritme za racunanje s velikim cijelim brojevima u radnoj memoriji (RAM-u). Za jako
velike brojeve ni radna memorija ne bi bila dovoljna, ali varijabla n raste presporo da
bismo to docekali. Za usporedbu, na procesoru od 2 GHz program u C-u dostize najveci
prikazivi broj 2147483647 u vremenu od oko 1.5 sekundi.
Realne brojeve nije moguce egzaktno implementirati na racunalu. Problem su ira-
cionalni brojevi, koji imaju beskonacne neperiodicne decimalne zapise, naprimjer
2 ili
. Za ta dva broja moguce je napisati algoritme koji ispisuju njihove znamenke i to je
na neki nacin njihova konacna egzaktna reprezentacija. Medutim, postoji jednostavan
CUNALU
argument da to nije moguce napraviti za sve iracionalne brojeve: algoritama ima manje
nego iracionalnih brojeva.
U praksi nije vazno sto ne mozemo egzaktno reprezentirati realne brojeve jer mjere-
njem uvijek dobivamo samo konacno mnogo tocnih znamenaka. Svaki realni broj x ,= 0
mozemo zapisati u obliku x = 0.z
1
z
2
z
3
. . . 10
e
, pri cemu su z
i
0, . . . , 9 znamenke i
z
1
,= 0, a e je cijeli broj. Naprimjer, 156.2846 zapisujemo kao 0.1562846 10
3
, a 0.000123
kao 0.123 10
3
. Pamtimo konacno mnogo znamenaka z
1
, . . . , z
k
i reprezentiramo cijeli
broj e u konacnoj aritmetici (kao sto smo objasnili). Broj m = 0.z
1
. . . z
k
naziva se
mantisa, a e Z eksponent.
U racunalu se koristi binarni sustav umjesto dekadskog; aproksimacija za x prikazuje
se u obliku (0.z
1
. . . z
k
)
2
2
e
, z
i
0, 1, z
1
,= 0. Buduci da je z
1
uvijek 1, u memo-
riji racunala pamti se samo preostale binarne znamenke mantise z
2
, . . . , z
k
i eksponent e
reprezentiran ksnim brojem bitova. Za predznak je takoder potreban jedan bit. Ovaj
nacin reprezentacije pribliznih realnih brojeva naziva se aritmetika s pomicnim zarezom
1
(eng. oating-point arithmetic). U single precision aritmetici za prikaz se koristi 32
bita, od cega je 23 za mantisu, 8 za eksponent i jedan za predznak. Koristi se i dou-
ble precision aritmetika s 64 bitova i quadruple precision aritmetika sa 128 bitova.
Detalji implementacije opisani su medunarodnim standardom IEEE 754 [28]. Postoje
softverske implementacije artimetike s pomicnim zarezom u kojima korisnik proizvoljno
zadaje tocnost racunanja, npr. u programskom sustavu Mathematica [17]. U tom slucaju
ogranicenja su dostupna radna memorija racunala i brzina izvodenja operacija, koja je
znatno sporija nego kad se koriste algoritmi ugradeni u aritmeticke sklopove procesora.
Opisat cemo neka ogranicenja oating point aritmetike, koja se pojavljuju bez obzira
na tocnost. Promotrimo najprije kako su na brojevnom pravcu rasporedeni prikazivi realni
brojevi. Obzirom da koristimo konacan broj bitova, skup prikazivih brojeva takoder je
konacan. Pretpostavimo da imamo samo 2 bita za mantisu, 2 bita za eksponent i 1 bit
za predznak. Moguce mantise su (0.100)
2
=
1
2
, (0.101)
2
=
5
8
, (0.110)
2
=
3
4
i (0.111)
2
=
7
8
.
Ako se eksponent sprema u 2-bitnoj cjelobrojnoj aritmetici koju smo opisali,
2
moguci
eksponenti su 2, 1, 0 i 1. To znaci da binarnu decimalnu tocku mozemo pomaknuti
jedno ili dva mjesta ulijevo i jedno mjesto udesno. Zajedno s predznakom imamo 32
prikazva broja koji su rasporedeni kao na slici 8.1 gore.
Vidimo da su prikazivi brojevi gusto rasporedeni blizu nule, a rjede dalje od nule.
Ako zaokruzimo broj 0.1234 na dvije znacajne znamenke (tj. na 0.12) napravili smo malu
pogresku 0.0034, a ako zaokruzimo 1234 na dvije znacajne znamenke (tj. na 1200) pogreska
je 34. Slicno je kod binarne aritmetike s pomicnim zarezom. Povecavanjem broja bitova
za mantisu raste gustoca prikazivih brojeva, a povecavanjem broja bitova za eksponent
prosiruje se interval u kojem leze prikazivi brojevi. Na slici 8.1 dolje vidimo prikazive
realne brojeve s 4 bita u mantisi i 3 bita u eksponentu. U oating point aritmetici s 32,
64 i 128 bita gustoca prikazivih brojeva je veca i interval u kojem leze je znatno siri, ali
raspored izgleda slicno.
1
Kao sto smo vec napomenuli u drugom poglavlju, po pravopisu se pise decimalni zarez umjesto
decimalne tocke. U ovoj skripti ipak pisemo decimalnu tocku zbog citljivosti nizova i formula u kojima
se pojavljuju decimalni brojevi.
2
Zapravo se eksponenti spremaju drugacije, npr. u single precision aritmetici koristi se 8 bitova, a
prikazivi eksponenti su od 126 do 127.
85
Slika 8.1: Prikazivi realni brojevi uz mantisu od 2 bita i eksponent od 2 bita (gore), odn.
mantisu od 4 bita i eksponent od 3 bita (dolje).
U aritmetici s pomicnim zarezom neke operacije su opasne jer dovode do gubitka
tocnosti. Jedna takva operacija je oduzimanje dva bliska broja. Recimo da u dekad-
skom sustavu racunamo s cetiri znacajne znamenke i zelimo oduzeti brojeve 0.4697 i
0.4613. Rezultat 0.0084 pamtit ce se u obliku 0.8400 10
2
, ali zadnje dvije znamenke
nisu pouzdane i mogu biti bilo sto. Zapravo smo izgubili dvije znacajne znamenke. Na
to nas racunalo nece upozoriti, nego moramo sami voditi racuna o pouzdanosti rezultata.
Posljedica konacne tocnosti jest i gubitak svojstava aritmetickih operacija na koja smo
navikli, npr. asocijativnosti. Recimo da zelimo izracunati pribliznu sumu reda
n
i=1
a
i
pozitivnih realnih brojeva u padajucem redoslijedu a
1
> a
2
> a
3
> . . .. Zbrajanjem u
navedenom redoslijedu (((a
1
+a
2
) +a
3
) + +a
n1
) +a
n
dobit cemo vecu pogresku nego
zbrajanjem u suprotnom redoslijedu a
1
+(a
2
+(a
3
+ +(a
n1
+a
n
))). Naime, moze se
dogoditi da suma velikih clanova na pocetku bude znatno veca od narednih malih clanova,
pa je oni zbog ogranicenog broja znamenaka mantise vise ne mogu promijeniti. U oating
point aritmetici postoji pozitivan broj > 0 sa svojstvom 1+ = 1 (najveci takav naziva
se strojnom tocnoscu). Ako zbrajamo od manjih clanova reda prema vecima, parcijalna
suma sporije raste i svi zbrojeni clanovi utjecu na rezultat, pa je pogreska manja.
U numerickoj matematici mora se voditi racuna i o problemima koji proizlaze iz
konacne tocnosti strojne aritmetike. Osim brzine izvodenja algoritama bitna je njihova
numericka stabilnost, tj. ocjena pouzdanosti rezultata koje daju. Numericki nestabilni al-
goritmi dovode do gomilanja pogresaka i gubitka znacajnih znamenaka. Nekoliko primjera
vezanih uz to dano je u zadacima.
Zadaci
Zadatak 8.1. Odredite prikaze brojeva 9734, 423 i 23456 u 16-bitnoj aritmetici.
Zadatak 8.2. Koji brojevi u 8-bitnoj aritmetici imaju prikaze 01101111 , 11111110 i
CUNALU
10000101 ?
Zadatak 8.3. Koji je najveci, a koji najmanji prikazivi cijeli broj u 16-bitnoj aritmetici
i koji su njihovi prikazi?
Zadatak 8.4. Koji je najveci, a koji najmanji prikazivi cijeli broj u 64-bitnoj aritmetici?
Zadatak 8.5. U 8-bitnoj binarnoj aritmetici izracunajte razliku 99 55.
Zadatak 8.6. U 16-bitnoj binarnoj aritmetici izracunajte razliku 4235 16777.
Zadatak 8.7. Metodom analognom dvojnom komplementu izracunajte razliku (212201)
3
(21102)
3
u ternarnom sustavu.
Zadatak 8.8. Metodom analognom dvojnom komplementu izracunajte razliku (312203)
4
(21302)
4
Zadatak 8.9. Napisite program koji ispisuje najveci i najmanji prikazivi pozitivan realni
broj. Inicijalizirajte realnu varijablu na 1.0 i mnozite, odnosno dijelite je s 2 dok se ne
prestane mijenjati. Ispisite zadnji broj prije nego sto se niz stabilizira.
Zadatak 8.10. Napisite program koji ispisuje strojnu tocnost, tj. najveci pozitivni broj
> 0 sa svojstvom 1.0 + = 1.0 u aritmetici s pomicnim zarezom vaseg racunala.
Zadatak 8.11. Napisite program za izracunavanje sume reda
n=1
1
n
4
. Program treba pri-
brajati clanove od vecih prema manjima dok se suma ne prestane mijenjati. Zatim treba
sumirati 10 puta vise clanova u obrnutom redoslijedu, od manjih prema vecima. Ispisite
prvu i drugu sumu i usporedite ih s tocnim rezultatom,

4
90
.
Poglavlje 9
Rjesenja nekih zadataka
Zadatak 1.1. Najveci n-znamenkasti prirodni broj je 10
n
1. Zbroj bilo koja dva n-
znamenkasta broja manji je od dvostrukog najveceg n-znamenkastog broja, 2 (10
n
1).
Lako se vidi da je to manje od najmanjeg (n + 2)-znamenkastog broja, 10
n+1
. Dakle,
zbroj bilo koja dva n-znamenkasta broja nema vise od n + 1 znamenaka.
Zadatak 2.3. Broj znamenaka prirodnog broja n u sustavu s bazom b je log
b
n| + 1.
Pritom je . | funkcija najvece cijelo.
Zadatak 2.4. (100110111)
2
= 311, (1201221)
3
= 1267, (42310)
5
= 2830, (2147)
8
= 1127,
(DEDA)
16
= 57050.
Zadatak 2.5. 5790 = (1011010011110)
2
= (21221110)
3
= (13236)
8
= (169E)
16
.
Zadatak 2.6. (8D6E)
16
= (106556)
8
.
Zadatak 2.7. (1111011)
2
+ (10110)
2
= (10010001)
2
, (122)
3
+ (211)
3
+ (101)
3
+ (120)
3
+
(222)
3
= (10100)
3
, (BABA)
16
+ (DEDA)
16
= (19994)
16
.
Zadatak 2.8. (110011011)
2
(110110)
2
= (101100101)
2
, (1302)
4
(123)
4
= (1113)
4
.
Zadatak 2.9. (1101)
2
(101)
2
= (1000001)
2
, (21201)
3
(1022)
3
= (100222122)
3
.
Zadatak 2.10. (110323)
5
: (401)
5
= (123)
5
, (1101)
2
: (110)
2
= (1.0001)
2
.
Zadatak 2.12. (102.21)
3
= 106/9 = 11.7, (0.4)
7
= 4/7 = 0.571428, (3.032)
5
= 157/50 =
3.14.
Zadatak 2.13. 17.3125 = (100001.0101)
2
= (122.0221)
3
.
Zadatak 2.15. (123.4567)
8
= (1010011.100101110111)
2
, (10111011.101)
2
= (BB.A)
16
,
(443.5274)
8
= (123.ABC)
16
.
87
88 POGLAVLJE 9. RJE
SENJA NEKIH ZADATAKA

Zadatak 2.16. b = 8.
Zadatak 2.17. (102342)
5
.
Zadatak 2.18. b = 7.
Zadatak 2.19. (bbb)
b
2 = (101010)
b
, (b.b)
b
2 = (10.1)
b
.
Zadatak 2.21. Vidi 8. poglavlje knjige [5].
Zadatak 3.1. Rijec je o Euklidovu algoritmu, koji izracunava najvecu zajednicku mjeru
brojeva a i b.
Zadatak 4.2. Ispisat ce broj 440.
Zadatak 4.3. Program zamjenjuje brojeve pohranjene u varijablama x i y bez koristenja
pomocne varijable. Ovaj nacin zamjene funkcionira samo ako varijable sadrze brojeve.
Osim toga moze doci do pogresaka zbog netocnog prikaza brojeva u racunalu. Zato
savjetujemo da se zamjena varijabli radi s pomocnom varijablom, kao u primjeru 4.8.
Zadatak 4.7.
ucitaj n
za i = 1, . . . , n radi
_
ispisi 2 i
Zadatak 4.9. Rjesenje s for petljom:
ucitaj n
za i = 1, . . . , n radi
_
ako je (i mod 5) = 0 onda
_
ispisi i
Rjesenje s while petljom:
ucitaj n
i 5
dok je i n radi
_
ispisi i
i i + 5
Zadatak 4.11.
ucitaj n
s 0
za i = 1, . . . , n radi
_
_
ucitaj k
ako je (k mod 2) = 0 onda
_
s s + k
ispisi s
89
Zadatak 4.13.
br 0
ucitaj k
dok je k ,= 0 radi
_
_
ako je (k mod 2) = 1 onda
_
br br + 1
ucitaj k
ispisi br
Zadatak 4.16.
ucitaj x
dok je x < 0 radi
_
ucitaj x
ako je x = 0 onda
_
ispisi "Nije ucitan niti jedan pozitivan broj"
inace
_
_
min x
ucitaj x
dok je x ,= 0 radi
_
_
ako je (x > 0) i (x < min) onda
_
min x
ucitaj x
ispisi "Najmanji pozitivan u citani broj je", min
Zadatak 4.18.
ucitaj n
prethodni 0
sadasnji 1
za i = 1, . . . , n radi
_
_
ispisi sadasnji
pom sadasnji
sadasnji sadasnji + prethodni
prethodni pom
Zadatak 4.19.
ucitaj n
prethodni 1
sadasnji 1
dok je sadasnji n radi
_
_
ispisi sadasnji
pom sadasnji
sadasnji sadasnji + prethodni
prethodni pom
90 POGLAVLJE 9. RJE

Zadatak 5.3.
ucitaj n, b
br 0
dok je n ,= 0 radi
_
ako je (n mod b) ,= 0 onda br br + 1
n n div b
ispisi br
Zadatak 5.4.
ucitaj n
max 0
za b = 2, . . . , n radi
_
_
m n
br 0
dok je m ,= 0 radi
_
ako je (m mod b) ,= 0 onda br br + 1
m m div b
ako je br > max onda
_
max br
baza b
ispisi baza
Zadatak 5.5.
ucitaj n, b
p 1
dok je p n radi p p b
dok je p > 1 radi
_
_
p p div b
z n div p
ispisi z
n n z p
Zadatak 5.14. Na pocetku korisnik unese brojeve a = 30, b = 21. Algoritam ulazi u
petlju i redom mijenja vrijednosti varijabli u a = 9, b = 21; a = 9, b = 12; a = 9, b = 3;
a = 6, b = 3; a = 3, b = 3. Nakon pet prolaza kroz petlju ispisuje najveci zajednicki
djelitelj 3. Verzija Euklidova algoritma na str. 42 treba tri prolaza kroz petlju.
91
Zadatak 5.19.
ucitaj k
m k
dok je k ,= 0 radi
_
_
ucitaj k
ako je k ,= 0 radi
_
_
n k
dok je n ,= 0 radi
_
_
pom n
n m mod n
m pom
ispisi m
Zadatak 5.20.
ucitaj n
fi 1
k 2
dok je k < n radi
_
_
a n
b k
dok je b ,= 0 radi
_
_
pom b
b a mod b
a pom
ako je a = 1 onda fi = fi + 1
k k + 1
ispisi fi
Zadatak 5.21. Pretpostavimo suprotno, da je d >

n. Buduci da je d djelitelj od n,
postoji e N takav da je d e = n. Broj n je slozen, pa je d < n i e > 1. Pretpostavili
smo da je d najmanji djelitelj veci od 1, pa je e d >

n. No tada je d e >

n
n = n,
sto je kontradikcija.
Zadatak 5.22.
ucitaj n
za i = 2, . . . , n radi
_
_
d 2
dok je (i mod d ,= 0) i (d
2
i) radi d d + 1
ako je d
2
> i onda ispisi i
92 POGLAVLJE 9. RJE

Zadatak 5.23.
ucitaj n
i 2
br 0
dok je br < n radi
_
_
d 2
dok je (i mod d ,= 0) i (d
2
i) radi d d + 1
ako je d
2
> i onda
_
ispisi i
br br + 1
i i + 1
Zadatak 6.1.
ucitaj n
za i = 1, . . . , n radi a[i] 1
a[1] 0
p 2
dok je p n radi
_
_
ako je a[p] = 0 onda p p + 1
inace
_
_
ispisi p
v p
dok je v n radi
_
a[v] 0
v v + p
Zadatak 6.3. Klasicni algoritam sortira niz 7, 5, 10, 2, 4 na sljedeci nacin:
i = 1, j = 2: 5, 7, 10, 2, 4 (usporeduje i zamjenjuje 1. i 2. clan)
i = 1, j = 3: 5, 7, 10, 2, 4 (usporeduje 1. i 3. clan, nema zamjene)
Bubble sort algoritam radi zamjene ovim redoslijedom:
93
Zadatak 6.6.
ucitaj n
za i = 1, . . . , n 1 radi
_
_
min i
za j = i + 1, . . . , n radi
_
ako je a[j] < a[min] onda min j
pom a[i]
a[i] a[min]
a[min] pom
Zadatak 6.11.
ucitaj n
ucitaj x
za i = 1, . . . , n radi
_
ako je a[i] = x onda ispisi i
Zadatak 6.12. Izvod slozenosti algoritma mergesort nalazi se u poglavlju 2.5 skripte [18].
Zadatak 7.6. Ideja je pokusati denirati inverz zadane funkcije kao u primjeru 7.5. Ako
neki element niza u kojeg spremamo inverz deniramo dva ili vise puta, zadana funkcija
nije bijekcija.
ucitaj n
za i = 1, . . . , n radi g[i] 0
bij ISTINA
i 1
dok je i n i bij radi
_
_
bij g[f[i]] = 0
g[f[i]] i
i i + 1
ako je bij onda ispisi "Funkcija je bijekcija"
inace ispisi "Funkcija nije bijekcija"
94 POGLAVLJE 9. RJE

Zadatak 7.8.
ucitaj n
i 1
dok je i n radi
_
_
ako je f[i] ,= 0 onda
_
_
ispisi "(", i
j f[i]
f[i] 0
dok je j ,= i radi
_
_
ispisi j
k f[j]
f[j] 0
j k
ispisi ")"
i i + 1
Zadatak 7.9. Ovaj algoritam ispisuje permutacije u leksikografskom poretku.
ucitaj n
za i = 1, . . . , n radi f[i] i
i 1
dok je i > 0 radi
_
_
za i = 1, . . . , n radi ispisi f[i]
i n 1
dok je i > 0 i f[i] > f[i + 1] radi i i 1
ako je i > 0 onda
_
_
j n
dok je f[j] < f[i] radi j j 1
pom f[i]
f[i] f[j]
f[j] pom
za j = 1, . . . , (n i) div 2 radi
_
_
pom f[i + j]
f[i + j] f[n + 1 j]
f[n + 1 j] pom
95
Zadatak 7.16.
ucitaj m, n
za i = 1, . . . , m radi
_
ucitaj s
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi
_
b[i][j] s a[i][j]
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi ispisi b[i][j]
Zadatak 7.19.
ucitaj m, n
za i = 1, . . . , m radi
_
za i = 1, . . . , m radi
_
_
s 0
za j = 1, . . . , n radi s s + a[i][j]
ako je s > 0 onda ispisi i
Zadatak 7.20.
ucitaj m, n
za i = 1, . . . , m radi
_
za j = 1, . . . , n radi
_
_
br 0
za i = 1, . . . , m radi
_
ako je a[i][j] = 0 onda br br + 1
ako je (br mod 2) = 0 onda ispisi j
Zadatak 7.21.
ucitaj m, n
za i = 1, . . . , m radi
_
br 0
za i = 1, . . . , m radi
_
_
j 2
dok je j n radi
_
ako je (a[i][j] mod 2) = 1 onda br br + 1
j j + 2
ispisi br
96 POGLAVLJE 9. RJE

Zadatak 7.22.
ucitaj m, n
za i = 1, . . . , m radi
_
s 0
za j = 1, . . . , n radi s s + a[1][j]
max s
maxi 1
za i = 2, . . . , m radi
_
_
s 0
za j = 1, . . . , n radi s s + a[i][j]
ako je s > max onda
_
max s
maxi i
ispisi maxi
Zadatak 7.25.
ucitaj m, n
za i = 1, . . . , m radi
_
br 0
za i = 1, . . . , m radi
_
ako je a[i][1] < 0 onda br br + 1
max br
maxj 1
za j = 2, . . . , n radi
_
_
br 0
za i = 1, . . . , m radi
_
ako je a[i][j] < 0 onda br br + 1
ako je br > max onda
_
max br
maxj j
ispisi maxj
97
Zadatak 7.28.
ucitaj m, n
za i = 1, . . . , m radi
_
s 0
za j = 1, . . . , n radi
_
ako je (a[1][j] mod 2) = 0 onda s s + a[1][j]
min s
mini 1
za i = 2, . . . , m radi
_
_
s 0
za j = 1, . . . , n radi
_
ako je (a[i][j] mod 2) = 0 onda s s + a[i][j]
ako je s < min onda
_
min s
mini i
ispisi mini
Zadatak 7.29.
ucitaj m, n
za i = 1, . . . , m radi
_
max a[1][1]
maxi 1
za i = 2, . . . , m radi
_
_
ako je a[i][1] > max onda
_
max a[i][1]
maxi i
minmax max
mmi maxi
mmj 1
za j = 2, . . . , n radi
_
_
max a[1][j]
maxi 1
za i = 2, . . . , m radi
_
_
ako je a[i][j] > max onda
_
max a[i][j]
mmi i
ako je max < minmax onda
_
_
minmax max
mmi maxi
mmj j
ispisi minmax, mmi, mmj
Zadatak 7.33. Konstrukcije pravilnog peterokuta i deseterokuta opisane su u poglavlju
7.4 knjige [21].
98 POGLAVLJE 9. RJE

Zadatak 8.1. 0010011000000110 , 1111111001011001 i 1010010001100000 .
Zadatak 8.2. 111, 2 i 123.
Zadatak 8.3. 2
15
1 = 32767 i 2
15
= 32768 s prikazima
0111111111111111 i 1000000000000000 .
Zadatak 8.4. 2
63
1 = 9223372036854775807 i 2
63
= 9223372036854775808.
Zadatak 8.5. Brojevi 99 i 55 imaju prikaze 01100011 i 11001001 . Zbrajanjem i
zanemarivanjem prijenosa dobivamo 00101100 , a to je prikaz broja 44.
Zadatak 8.6. Brojevi 4235 i 16777 imaju prikaze
0001000010001011 i 1011111001110111 .
Zbrajanjem dobivamo 1100111100000010 , a to je prikaz broja 12542.
Zadatak 8.7. Komplement broja (021102)
3
je (201120)
3
, a kad ga uvecamo za jedan
(201121)
3
. Zbrajanjem s (212201)
3
uz zanemarivanje vodece znamenke (prijenosa) dobi-
vamo (121022)
3
.
Zadatak 8.9.
x 1.0
y 0.0
dok je x! = y radi
_
_
z y
y x
x 2 x
ispisi "Najveci prikazivi pozitivan broj je", z
x 1.0
y 0.0
dok je x! = y radi
_
_
z y
y x
x x/2
ispisi "Najmanji prikazivi pozitivan broj je", z
Implementirajte ovaj algoritam na vasem racunalu i pogledajte rezultat. Autor je u
programskom jeziku Python dobio brojeve 8.98846567431 10
307
i 4.94065645841 10
324
.
U progamskom jeziku C s tipom oat dobio je 1.70141 10
38
i 1.4013 10
45
, a s tipom
double iste vrijednosti kao u Pythonu.
99
Zadatak 8.10.
jedan 1.0
epsilon 1.0
dok je jedan + epsilon ,= jedan radi
_
epsilon epsilon/2
ispisi epsilon
programskim jezicima Python i C dobio broj 1.11022302463 10
16
.
Zadatak 8.11.
s 0.0
p 1.0
n 1
dok je s ,= p radi
_
_
p s
s s + 1/n
4
n n + 1
ispisi s
n 10 n
s 0.0
dok je n > 0 radi
_
s s + 1/n
4
n n 1
ispisi s
programskom jeziku Python za prvu sumu dobio 1.082323233710861, a za drugu sumu
1.0823232337111379. Prema programu Mathematica [17] broj

4
90
je 1.08232323371113819
na 17 decimala.
100 POGLAVLJE 9. RJE

Bibliograja
[1] M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, Annals of Mathematics, Second
Series 160 (2004), 781-793.
[2] Bloodshed Software, Dev-C++. http://www.bloodshed.net/devcpp.html
[3] L. Budin, Informatika: udzbenik za 1. razred gimnazije, Element, Zagreb, 1996.
[4] Clay Mathematics Institute, The Millennium Prize Problems.
http://www.claymath.org/millennium/
[5] A. Dujella, Fibonaccijevi brojevi, Hrvatsko matematicko drustvo, Zagreb, 2000.
[6] Euklid, Elementi IVI, KruZak, Hrvatski Leskovac, 1999.
[7] Free Pascal. http://www.freepascal.org/
[8] GCC, the GNU Compiler Collection. http://gcc.gnu.org/
[9] GeoGebra. http://www.geogebra.org/cms/
[10] The Geometers Sketchpad Resource Center. http://www.dynamicgeometry.com/
[11] GNU Pascal. http://www.gnu-pascal.de/
[12] K. Horvatic, Linearna algebra, II. dio, Sveuciliste u Zagrebu, 2001.
[13] D.E. Joyce, Euclids Elements.
http://aleph0.clarku.edu/~djoyce/java/elements/elements.html
[14] B. Klaic, Veliki rjecnik stranih rijeci, izraza i kratica, Zora, Zagreb, 1968.
[15] D.E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching,
Addison-Wesley, 1975.
[16] G. Lame, Note sur la limite du nombre des divisions dans la recherche du plus
grand commun diviseur entre deux nombres entiers, Comptes rendus des seances de
lAcademie des Sciences 19 (1844), 867-870.
[17] Mathematica. http://www.wolfram.com/mathematica/
[18] I. Nakic, Diskretna matematika, skripta, PMF-Matematicki odsjek, 2009.
http://web.math.hr/nastava/komb/
101
102 BIBLIOGRAFIJA
[19] J.J. OConnor, E.F. Robertson, Abu Jafar Muhammad ibn Musa Al-Khwarizmi,
The MacTutor History of Mathematics archive, 1999.
http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Khwarizmi.html
[20] J.J. OConnor, E.F. Robertson, Babylonian numerals, The MacTutor History of
Mathematics archive, 2000.
http://www-history.mcs.st-andrews.ac.uk/HistTopics/Babylonian_numerals.html
[21] B. Pavkovic, D. Veljan, Elementarna matematika I, Tehnicka knjiga, Zagreb, 1992.
[22] Python Programming Language. http://www.python.org/
[23] Scratch. http://scratch.mit.edu/
[24] R. Sedgewick, Algorithms, Addison-Wesley, 1984.
[25] The University of Chicago School Mathematics Project, Algorithms in Everiday
mathematics, University of Chicago, 2001.
http://everydaymath.uchicago.edu/about/research/algorithms.pdf
[26] Wikipedia, Age of the universe, listopad 2010.
http://en.wikipedia.org/wiki/Age_of_the_universe
[27] Wikipedia, History of programming languages, listopad 2009.
http://en.wikipedia.org/wiki/History_of_programming_languages
[28] Wikipedia, IEEE 754-2008, prosinac 2010.
http://en.wikipedia.org/wiki/IEEE_754
[29] Wikipedia, Primality test, listopad 2010.
http://en.wikipedia.org/wiki/Primality_test
[30] Wikipedia, P versus NP problem, prosinac 2010.
http://en.wikipedia.org/wiki/P%3DNP

Osnove Algoritama

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Osnove Algoritama

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Osnove Algoritama

Uploaded by

Copyright:

Available Formats

Sveuciliste u Zagrebu

CINI ZAPISIVANJA ALGORITAMA

CINI ZAPISIVANJA ALGORITAMA

CINI ZAPISIVANJA ALGORITAMA

CINI ZAPISIVANJA ALGORITAMA

n. Naime, moze se pokazati da najmanji djelitelj izmedu 1 i n ne moze biti veci od

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

You might also like

Osnove Algoritama

Uploaded by

Document Informationclick to expand document informationDokument objašnjava pojam algoritma kroz primjer zbrajanja dvaju brojeva. Opisuje korake zbrajanja i uvodi tablice za zbrajanje pojedinih znamenaka koje uključuju prijenos.

Document Informationclick to expand document information

Copyright:

Available Formats

Osnove Algoritama

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Osnove Algoritama

Uploaded by

Copyright:

Available Formats

Sveuciliste u Zagrebu

CINI ZAPISIVANJA ALGORITAMA

CINI ZAPISIVANJA ALGORITAMA

CINI ZAPISIVANJA ALGORITAMA

CINI ZAPISIVANJA ALGORITAMA

n. Naime, moze se pokazati da najmanji djelitelj izmedu 1 i n ne moze biti veci od

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

SENJA NEKIH ZADATAKA

You might also like