RAZGRANATA ALGORITAMSKA STRUKTURA (1)

RAZGRANATA ALGORITAMSKA STRUKTURA (1)

Razgranata algoritamska struktura je ona kod koje se svaki korak izvršava jednom ili nijednom.

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 "grananje" 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. Ove probleme razmatraćemo u sledećoj lekciji.

Kako program odlučuje?

Korak koji služi za grananje, 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 je 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 . Služi za povezivanje više uslova i kao rezultat će vratiti vrednost true samo ako su svi uslovi zadovoljeni.

Operator OR predstavlja logičku disjunkciju .Takođe povezuje više 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.

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) and (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.

Recimo da treba ispitati da li je X van ovog intervala. Pazite, kreiranje "obrnutog" uslova nije jednostavno. Rešenje bi bilo:

(X < 0) or (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:

NOT((X >= 0) AND (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.

Simbol za grananje je šestougaonik

Primer 1

Za uneti ceo broj X, proveriti i ispisati da li je paran ili neparan.

Potrebno je uraditi jednu od dve stvari - ispisati reč "Paran" ili "Neparan", zavisno od toga kakav je uneti broj. Problem je u tome što unapred ne znamo kakav broj će biti unet. Znači da moramo da izvršimo proveru da li je deljiv sa 2 (paran) ili ne (neparan).

Za ovo imamo specijalan algoritamski korak - grananje. U tom koraku se proverava neki logički uslov, tj. neki izraz koji ima vrednost true ili false (ili makar vrednost koja se tako može protumačiti, kao npr. 1 i 0).

Iz ovog koraka se odvajaju dve grane - izvršavanje će krenuti jednim od ta dva puta, zavisno od toga kakva bude situacija u tom trenutku, odnosno - kakav broj unese korisnik tokom izvršavanja.

Da li je broj paran ustanovićemo pomoću celobrojnog deljenja, tj. operacije ostatka. Ako je prilikom deljenja broja sa 2 ostatak 0 onda je paran, ako nije, onda je neparan. Ovako se inače u programiranju ispituje deljivost dva broja, ne razmatraju se matematička pravila sa zbirom cifara, poslednjom cifrom itd. Ovaj način je, kad radimo računarom, mnogo lakši i brži. 

Primer 2

Izračunati idealnu težinu, ako se unose pol i visina. Za muškarce, idealna težina je visina minus 100, a za žene visina minus 110.

Zadaci za vežbu:

1. Za unete tri duži ispitati da li mogu biti stranice trougla, i ako mogu, izračunati mu obim i površinu. Ako ne mogu, napisati odgovarajuću poruku.

Uputstvo: Da bi duži činile trougao, mora zbir dve stranice biti veći od treće. Ispitati sve tri kombinacije stranica i vezati ih sa and .

Površina trougla ako su date sve tri stranice računa se Heronovom formulom:

gde je S polovina obima, tj.O/2

2. Za unetu promenljivu X izračunati vrednost funkcije Y.

Uputstvo: Funkcija nije definisana za X za koje je imenilac nula. Ne mora se tražiti X, jednostavno za ceo imenilac pitamo da li je nula, pa neka računar računa.