predavanja
prof. dr Diana Protić
ALGORITMI I STRUKTURE PODATAKA
1. UVOD
Def.: Algoritam je metod (postupak) za rješavanje problema koji je prihvatljiv za
kompjutersku implementaciju.
Def.: Algoritam je metod (postupak) koji:
1.
ukoliko problem ima rješenje, daje rješenje tog problema,
2.
ukoliko problem nema rješenje, daje odgovor da problem nema rješenje.
Ovo je generalna definicija algoritma.
Program je implemntacija algoritma.
Riječ algoritam potiće iz IX vijeka, od bagdadskog astronoma i matematičara
Muhameda ibni Musa El-Havarizmije koji je na zapadu poznat kao Al-Gorezmije.
Primjer 1:
Euklidov algoritam za traženje najvećeg zajedničkog djelioca dva broja:
Zadata su dva pozitivna cijela broja. Naći najveći zajednički djelilac tj. najveći
pozitivni cijeli broj koji djeli ta dva zadata broja.
Neka su m i n ta dva broja:
1.
Obezbijedi da je m
n. Ako je m<n, onda zamijeni m i n,
2.
Podijeli m sa n i neka r bude ostatak djeljenja, r će biti pozitivan cijeli
broj (0
r<n),
3.
Ispitati da li je r=0. Ako je r=0, algoritam terminira (završava se) i u tom
slučaju je rješenje broj n. Ako je r
0, onda ćemo zamijeniti m i n a na
mjesto n staviti r i vratiti se na korak 2.
Ponavljamo postupak i on nas treba dovesti do rješenja.
Recimo, zadati su brojevi 544 i 119.
I prolaz
1. m=544, n=119,
2. 544:119=4 ostatak 68, r=68,
3. ? r=0, NE, m=119, n=68,
II prolaz
2. 119:68=1 ostatak 51, r=51
3. ? r=0, NE, m=68, n=51,
III prolaz
2. 68:51=1 ostatak 17, r=17
3. ? r=0, NE, m=51, n=17,
IV prolaz
2. 51:17=3 ostatak 0, r=0,
3. ? r=0, DA, NZD=n=17.
Osobine algoritma:
2. t=14 nije ispunjen uslov 2,
3. t=13 nije ispunjen uslov 2,
4. t=12 nije ispunjen uslov 2,
5. t=11 nije ispunjen uslov 2,
...
11. t=5 ispunjen je uslov 2 i NZD=t=5.
Trebalo je izvršiti 10 koraka.
Da smo koristili Euklidov algoritam imali bi dva prolaza:
I prolaz
20:15=1 ostatak 5, m=15, n=5
II prolaz
15:5=3 ostatak 0, NZD=5.
Ovo je elegantnije i brže.
Načini davanja algoritama mogu biti u:
1. tekstualnom obliku,
2. pseudokodu (npr. IF r=0 THEN ... ELSE ...),
3. grafičkom obliku (strukturni dijagrami, dijagrami toka – FLOW
CHART).
Neki od simbola, kod grafičkog davanja algoritma, su:
Primjer grafičkog zadavanja euklidovog algoritma za traženje najvećeg
zajedničkog djelioca dva broja:
Osnovne operacije sa rad na listama možemo grupisati u sljedeće tri grupe:
- operacije kreiranja liste (konstruktorske operacije),
- operacije postavljanja upita nad listom (predikatske operacije),
- operacije selekcije dijelova liste (selektorske operacije).
Listu ćemo označavati sa LIST a element liste sa LISTELEMENT.
TYPE LIST, LISTELEMENT
Konstruktori:
1. Kreiranje prrazne liste.
Ulazni parametri: nema,
Izlazni parametri:: struktura tipa LIST (prazna lista),
PROCEDURE NewList():LIST;
2. Dodavanje jeednog elementa u zadanu listu.
Ulazni parametri: - struktura tipa LIST (lista u koju se dodaje),
- podatak tipa LISTELEMENT (element koji se dodaje),
- podatak tipa CARDINAL (pozicija u listi na koju se dodaje
element),
Izlazni parametri:: struktura tipa LIST (ažurirana ulazna lista),
