Razgranati algoritmi
Razgranata algoritamska struktura je ona kod koje se svaki korak izvršava jednom ili nijednom. Stvar je u tome da, kada zadatak zahteva da se neke vrednosti unesu u promenljive, jednostavno, ne možemo da znamo koje će to vrednosti biti. U linijskim algoritmima smo pokazali različite načine kako da dođemo do rezultata na osnovu unetih vrednosti, ali u mnogo većem broju slučajeva problem ne možemo rešiti jednostavnim nizom koraka.
Prosto, potreban nam je neki korak pomoću koga možemo da postavimo pitanje "šta ako", ili možda tačnije "da li je". Ovakav korak predstavlja "račvanje" izvršavanja programa. U našem algoritmu pripremamo dve odvojene grane, i zavisno od provere na "raskrsnici" izvršiće se koraci u jednoj ili u drugoj. Zbog toga kažemo da se neki koraci izvrše jednom, a neki nijednom.
Međutim, šta ako je potrebno imati više od dve mogućnosti? Tj. šta ako je potrebno da se algoritam odvaja u više od dve grane? Pa, jednostavno - svaku granu uvek možemo ponovo da "račvamo". Takođe, za specifičan tip problema, možemo koristiti višestruko grananje.
Kako program odlučuje?
Korak koji služi za "račvanje", u sebi sadrži izraz logičkog tipa. To znači da se u ovom koraku zadaje neki uslov. Njegova vrednost može biti "tačno" (true) ili "netačno" (false). Najjednostavnija vrsta ovakvog izraza su relacioni izrazi, odnosno upoređivanja.
X > 5
10 <= Y
A == "Pera"
Inače svejedno da li pišemo:
X > 5
5 < X
Odgovor na ovakvu "pitalicu" je uvek "da" ili "ne", i na osnovu toga se izvršava jedna od dve grane algoritma. Uslovi mogu biti i kompleksni - tj. možemo ih sastaviti povezivanjem dva ili više prostih uslova. Ovo povezivanje se vrši logičkim operatorima. Dva najkorišćenija su AND i OR.
Operator AND predstavlja logičku konjukciju i u jezicima poput C-a, JavaScripta, pa i u našim algoritmima, označava se i simbolom &&. Služi za povezivanje neka dva uslova i kao rezultat će vratiti vrednost true samo ako su oba uslova zadovoljena.
Operator OR predstavlja logičku disjunkciju i takođe se označava i simbolom ||. Takođe povezuje dva uslova i kao rezultat će vratiti vrednost true u slučaju ako je makar jedan uslov zadovoljen.
Osim ova dva, koristi se i operator NOT koji predstavlja logičku negaciju i označava se još kao ! (znak uzvika). On ne povezuje dva, već se stavlja ispred jednog uslova i vraća vrednost true u slučaju ako uslov nije zadovoljen.
Kompleksni uslovi
Evo primera gde početnici često greše. Potrebno je sastaviti uslov kojim se proverava da li je vrednost promenljive X u intervalu od 0 do 9. Matematički je sasvim opravdano napisati:
0 <= X <= 9
Međutim, u programiranju je ovo pogrešno! Računar bi prvo ispitao da li je 0 manje od X, a onda dobijenu vrednost (true ili false) uporedio sa 9. U nekim programskim jezicima bi ovo bilo prijavljeno kao greška, a u nekim bi računar nastavio da radi, ali bismo dobili pogrešan rezultat (true bi prepoznao kao 1, a false kao 0 pa bi to uvek bilo manje od 10). U programiranju bismo morali da napišemo npr. ovakav uslov:
(X >= 0) && (X <= 9)
Dakle, proveravamo da li važi da je X veće ili jednako 0 i istovremeno X manje ili jednako 10. Ova dva uslova povezujemo operatorom AND. Hajdemo korak dalje. Recimo da treba ispitati da li je X van ovog intervala. Pazite, kreiranje "obrnutog" uslova nije trivijalan zadatak. Rešenje bi bilo:
(X < 0) || (X > 9)
Znači pitamo da li važi da je X manje od 0 ili možda da je X veće od 9. Kao što vidimo, ne možemo baš samo da "obrnemo znakove". Primećujemo da za povezivanje uslova koristimo operator OR, koji vraća vrednost "tačno" ako je zadovoljen bilo prvi, bilo drugi uslov. Ako je problem samo "obrtanje" postojećeg uslova, mnogo je lakše da koristimo operator NOT:
!((X >= 0) && (X <= 9))
Inače, u razgranatim strukturama mogu učestvovati svi koraci koje smo do sada naučili (ulaz, izlaz i obrada podataka), kao i strukture koje ćemo tek učiti. Pošto se u "pitalici" navodi logički izraz, obavezno obnovite izraze.
Pored primera koji su ovde dati, pripremili smo vam još dosta zanimljivih zadataka iz razgranatih algoritama, sa rešenjima.
Prosto grananje
Primer: Provera broja
Za uneti broj X treba proveriti da li je pozitivan, negativan ili jednak nuli.
Da vidimo kako ovo funkcioniše. Na početku se unosi neki broj i smešta se u promenljivu X. Onda dolazimo do prvog grananja gde se proverava da li je X možda veće od 0. Primećujete da iz ovog koraka idu dve grane - jedna za da (desno) i jedna za ne (dole). Znači ako je uslov zadovoljen, odnosno njegova vrednost je true, izvršava se korak koji se nalazi u desnom ogranku. Taj korak je ispis reči "Pozitivan". Pošto je u ovom slučaju zadatak rešen, vidimo da se više ne izvršavaju nikakvi drugi koraci - ova grana nas "vodi" na kraj programa.
Međutim, šta ako X nije bilo veće od nule? U tom slučaju se desna grana ignoriše, a program se nastavlja izvršavanjem donje grane. E, sada imamo dodatnu komplikaciju. Prva pitalica je razdvojila izvršavanje programa zavisno od toga da li X jeste ili nije veće od 0. Ako je program "upao" u granu za "ne", samo znamo da X nije veće od nule, ali i dalje ne znamo kakav je X.
Zato u ovoj grani moramo da napravimo još jedno "podgrananje", odnosno da pitamo da li je X manje od 0. I iz ovog koraka vidimo da se odvajaju dve grane (u stvari iz "pitalice" uvek idu dve grane). Ako se ispostavi da X jeste manje od nule, izvršiće se korak u desnom ogranku (ispis reči "Negativan"). Međutim ako ni ovaj uslov nije zadovoljen izvršiće se korak u donjoj grani, koji ispisuje reč "Nula".
Hmmm... Kako to da smo sigurni da je X jednko 0? Zar ne bismo trebali i to da proverimo nekom trećom pitalicom? Pa u stvari - ne. Upravo zato smo koristili "grananje unutar grananja" - kada program stigne do ove grane, znamo da je tu stigao zato što X nije bio veći od nule i odmah posle X nije bio ni manji od nule, što znači da je jedina preostala mogućnost da je X jednak nuli!
Rešenje koje smo opisali je mnogo praktičnije nego što bi bilo nešto na primer ovakvo:
Iako će rezultat biti isti, izbegavajte ovakva rešenja - postoji mnogo veća šansa da pogrešite jer ćete se u bilo kakvom složenijem zadatku "izgubiti" pokušavajući da navedete sve moguće pitalice. Da ne pominjemo što ovde ima više koraka koji se izvršavaju (uvek tri pitalice, umesto jedne ili dve), zbog čega će ovakav program biti sporiji.
Višestruko grananje
Iako se svaki problem može rešiti sistemom pitalica koje smo upravo savladali, nekada je problem takav da nam uslovi budu prave "kobasice" - ispostavlja se da imamo ogroman broj povezanih uslova tipa "ako je OVO ili ONO ili ONO...", što može biti prilično frustrirajuće.
Zbog toga postoji jedan poseban korak - višestruko grananje, koji razdvaja izvršavanje programa ne samo na dve, već na proizvoljan broj mogućih grana. Ovaj algoritamski korak nije uopšte težak za upotrebu, ali ipak ne može da zameni običnu "pitalicu". Stvar je u tome što se ovim korakom mogu razrešiti samo specifični upiti, odnosno provera jednakosti.
Drugim rečima ako imamo slučaj koji bi se mogao opisati kao:
- ako je izraz jednak ovome, uradi jednu stvar
- ako je jednak onome, uradi drugu stvar
- ako je jednak nečemu trećem ili četvrtom, uradi neku sasvim drugačije
- ...
- ako nije jednak ničemu od navedenog, uradi ovo ovde
Višestruko grananje
Primer: Kretanje vozila
Unosi se komanda za kretanje vozila, kao jedan znak (malim slovom). Znak "a" znači ubrzanje, znak "b" znači kočenje a znakovi "l" i "r" znače obilaženje. Ispisati aktivnost vozila.
Ovaj algoritam suštinski zamenjuje prilično nezgodnu razgranatu konstrukciju. Na početku se unosi neki znak u promenljivu K. Odmah zatim ulazimo u proveru. U korak za višestruko grananje unosimo neki izraz, koji uobičajeno nije logički (mada nema nikakve prepreke ni da bude). Svaka grana će se odvajati na osnovu neke od mogućih vrednosti izraza.
U prvoj grani se navodi vrednost "a", koja označava ubrzanje vozila. Ako je izraz iz koraka višestrukog grananja jednak zadatoj vrednosti, izvršiće se koraci iz te grane, odnosno korak izlaza koji ispisuje reč "Ubrzavanje". Ovo je isto kao da smo napravili grananje na osnovu uslova:
k == "A"
Sledeća grana se odnosi na mogućnost da je zadati izraz jednak vrednosti "b". U tom slučaju će se ispisati reč "Kočenje". Efektivno, ovo je kao obično grananje sa uslovom:
k == "B"
Poslednja grana nam je važna pošto u njoj imamo primer kako se zadaje više mogućih vrednosti. Naime, bilo da je vrednost u promenljivoj K jednaka "l" ili "r". Svaku od mogućih vrednosti odvajammo obavezno tačka-zarezom. Ovo je mnogo jednostavnije nego da smo pravili uslov koji bi glasio:
(k == "L") || (k == "R")
Ako vrednost izraza nije pronađena ni u jednoj od grana, izvršava se grana koja se spušta direktno ispod koraka višestrukog grananja, označena kao DEF (default). U ovom slučaju će se ispisati poruka "Neispravna komanda". Ovo je praktično kao grana za vrednost "NE" u prostom grananju.
Na osnovu svega, verovatno možete primetiti i veliki nedostatak višestrukog grananja - možemo odvajati različite grane samo u slučajevima jednakosti izraza i vrednosti. Ako su uslovi za odvajanje grana iole komplikovaniji, ako se zahteva upoređivanje tipa "manje od" ili "veće od", ne možemo se osloniti na ovakav tip odlučivanja.