Ciklični algoritmi
Ciklična algoritamska struktura je ona kod koje se koraci mogu izvršiti više puta. Slično kao kod razgranate sturkture, vrlo lako se može desiti da ne znamo koje će vrednosti korisnik uneti, ili čak koliko će ih biti.
Ogroman broj zadataka koje rešavamo u programiranju zahteva da se podatak za podatkom obrađuje na isti način. To sa stanovišta algoritma znači da se jedni isti koraci ponavljaju više puta. Kao što smo se upoznali sa različitim tipovima grananja, sada ćemo se upoznati sa nekoliko tipova ciklusa. Svim koracima kojima definišemo cikluse zajedničko je to što imaju "strelicu unazad". Na taj način "vraćaju" izvršavanje algoritma/programa nekoliko koraka unazad čime smo napravili ciklus ili petlju.
Svako ponavljanje ciklusa, naziva se iteracija. Koraci unutar ciklusa su uvek isti, ali vrednosti sa kojima se radi se menjaju. To je u stvari i poenta rada sa ciklusima.
Naravno, ovo se podrazumeva, ali da ipak pomenemo - ciklusi se mogu kombinovati sa svim algoritamskim strkturama. To znači da možemo imati grananja unutar ciklusa ili cikluse unutar grananja. U stvari, najveći broj zadataka koji su pred nama će biti upravo takav.
Kako ciklus funkcioniše?
Sećate se razgranatih algoritama i koraka u kome smo "račvali" izvršenje programa na dve grane? E, sad zamislite da se izvršenje programa ne deli na dve mogućnosti, već se vraća unazad. Korak koji definiše ciklus, takođe sadrži izraz logičkog tipa, odnosno uslov. Pitanje koje se postavlja više nije "ako je (tačno)...", već "dok je (tačno), ponavljaj to-i-to". Sve što smo ranije pisali za uslove u razgranatim algoritmima važi i ovde. To znači da možemo zadati i kompleksne uslove.
Ovo su takozvani uslovni ciklusi.
Dakle, zaključili smo - sve dok je odgovor na pitalicu unutar koraka ciklusa, "da", ciklus će se ponavljati. To znači da do kraja ciklusa dolazimo kada uslov više nije zadovoljen. Tada se nastavlja sa normalnim izvršavanjem koraka koji dolaze posle ciklusa.
Ovo nas dovodi do jedne važne stvari. Da bi uslov koji je u nekoliko iteracija bio zadovoljen, odjedanput prestao da važi, mora doći do neke promene. Nosioci vrednosti u našim algoritmima su promenljive. Kroz ciklus, ta vrednost može (i treba) da se menja - posebno onih promenljivih koje učestvuju u uslovu. Praktično, čeka se "kap koja je prelila čašu", da bi se ciklus završio.
Mesto provere uslova
Uslov može da se proverava na početku ili na kraju ciklusa. Tako razlikujemo ciklus sa preduslovom i ciklus sa postuslovom. Možda vam se čini da je svejedno da li proveravamo uslov pre ili posle "tela" ciklusa, ali verujte, postoji jedna jako bitna razlika.
Kod ciklusa sa preduslovom, može da se desi da uslov već na početku ne bude zadovoljen. Tako je moguće da se ciklus ne izvrši ni jednom. Sa druge strane, kod ciklusa sa postuslovom, ciklus mora da se izvrši jednom, da bi uopšte došlo do provere uslova i odluke da li će se ciklus ponavljati.
U praksi ćete birati ciklus koji vam više odgovara za trenutni problem, ali pošto se isti zadaci vrlo često mogu rešiti i jednom i drugom metodom, programeri se najčešće odlučuju za cikluse sa preduslovom.
Objašnjenje uslovnih ciklusa
Ciklus sa preduslovom
Dakle, ovako izgleda ciklus koji se može izvršiti jednom, ni jednom ili više puta. Primećujete da se uslov proverava na početku. Ako je zadovoljen (vrednost true), izvršiće se iteracija ciklusa.
To znači da ako uslov nije zadovoljen več pri prvoj proveri, ceo ciklus se preskače - neće se izvršiti ni jedanput. Ovaj uslov se proverava svaki put na "ulasku" u iteraciju i sve dok je zadovoljen, naredbe ciklusa će se ponavljati.
Ciklus sa postuslovom
Ovakav ciklus će se izvršiti bar jednom ili više puta. Uslov se sada nalazi na kraju ciklusa, kao "ventil" koji određuje da li će izvršavanje ciklusa "skočiti" nazad na telo ciklusa, ili će se ciklus završiti.
Zbog toga se čak iako uslov nije zadovoljen pre ciklusa, telo ciklusa izvrši bar jednom, pre nego što dođe do provere.
Pogledajmo sada par primera.
Primeri
Stepeni dvojke
Ispisati sve stepene broja dva koji su manji ili jednaki nekoj unetoj vrednosti A.
Da vidimo kako ovo funkcioniše... Na početku postavljamo početne vrednosti. Promenljiva st dobija vrednost 0 (počinjemo od "nultog" stepena), a promenljiva rez dobija vrednost 1 (to je početna vrednst za rezultat stepenovanja). U trećem koraku se zahteva da korisnik unese vrednost do koje se računa i to se smešta u promenljivu a.
Sada konačno kreće ciklus. Ciklus će se izvršavati sve dok je rezultat rez manji ili jednak broju a. Ako se desi da je to već na početku - to je to. Ciklus se neće izvršavati, preći će se odmah na kraj programa.
Unutar ciklusa prvo ispisujemo rezultat. To će najpre biti početna vrednost 2^0 = 1. Međutim, onda se stepen st povećava za jedan i računa se novi rezultat rez, tako što se dotadašnji rez prosto pomnoži sa 2.
Ovako "spremljen" rezultat se vraća na proveru uslova. Ako je i dalje manji od a, ponavljaju se koraci ciklusa, ispisuje se rezultat, računa se novi stepen, itd. U suprotnom, izlazi se iz ciklusa i tu je kraj programa.
Prosek neparnih brojeva
Unose se celi brojevi dok se ne unese 0. Izračunati i ispisati prosek (aritmetičku sredinu) unetih neparnih brojeva, korišćenjem ciklusa sa postuslovom.
I na početku ovog algoritma moramo da postavimo neke početne vrednosti. Pošto se prosek računa kao količnik zbira vrednosti i njihovog broja, trebaće nam promenljiva zbir u kojoj sabiramo brojeve i promenljiva br u kojoj brojimo sabirke. Obe promenljive na početku imaju vrednost 0.
Prva stvar koju radimo kada uđemo u ciklus je da unesemo neki broj x. Da li ćemo taj broj sabirati ili ne? Zavisi od toga da li je neparan. Ispitujemo ostatak celobrojnog deljenja sa 2, x % 2. Ako je ovaj ostatak različit od nule (tačnije, kada delimo sa 2 može da ima samo još vrednost 1), tumači se kao true, a to istovremeno znači da x nije deljiv sa 2, tj da je neparan.
Kada bismo radili u nekom "strožem" jeziku, morali bismo da napišemo baš-baš ispravan logički izraz, kao npr. x % 2 != 0. Međutim jezik C i njegovi "srodnici" koji nas ovde interesuju će nam dozvoliti i da malo "uhvatimo krivinu". Ako niste baš srećni sa ovakvim izrazima, slobodno se potrudite da radite "ispravno". Ovo i jeste jedna od dobrih strana Pascala - nateraće vas da stalno razmišljate o tipovima.
Ako je broj x neparan, dodaćemo ga u zbir i povećaćemo brojač br za jedan.
Došli smo do kraja ciklusa, gde smo naišli na uslov. Ovaj uslov proverava da li je x bilo različito od nule. Ako jeste, znači da moramo da se vratimo na početak ciklusa. U suprotnom, petlja se završava.
Ostatk algoritma je trivijalan. Sada kada imamo zbir i broj sabiraka, računamo prosek pros i ispisujemo ga.
Ovde smo želeli da specifično isprobamo ciklus sa postuslovom. Možda bi ovaj zadatak prirodnije trebao da se rešava ciklusom sa preduslovom. U stvari smo imali sreće, pošto kada se unese 0 (što je uslov za kraj), to ne utiče na rezultat (nula je parna).
Mrtva petlja
Mrtva petlja je ciklus koji ne može da se zaustavi. Zove se još i beskonačni ciklus. To je situacija kada je uslov za ponavljanje ciklusa uvek zadovoljen, tako da ciklus nikada ne dođe do svog kraja.
Ovo je u 99% slučajeva rezultat greške programera. Moguće je da smo pogrešili u uslovu tako da on uvek vraća isti rezultat, ili u samom ciklusu ako zaboravimo da promenimo vrednosti promenljivih koje bi dovele do kraja ciklusa, ili to uradimo pogrešno.
Postoje i retke situacije kada želimo da napravimo beskonačni ciklus. Na primer, zatrebaće nam ako pravimo animaciju koja treba neprestano da se "vrti". Takođe može da se desi i da je uslov za izlazak iz ciklusa toliko kompleksan, da je programeru lakše da na više mesta unutar ciklusa zada nasilni prekid. Međutim, ovo se ne smatra "dobrom programerskom praksom" i u Algoritmima nije moguće.
Ovo je prvi put da pravimo takve algoritme koji mogu da "zaglave" računar! Budite jako, jako oprezni.
Primeri beskonačnih ciklusa
Namerno-beskonačan ciklus
Ako želimo da napravimo beskonačan ciklus, najjednostavniji način je uslovni ciklus sa uslovom true. To je svakako uslov koji je uvek ispunjen.
Greška u ciklusu
Pogledajte sada ovaj algoritam. Na prvi pogled, sve izgleda u redu. Algoritam bi trebao da ispiše brojeve od 0 do 9. Imamo promenljivu N koja počinje od 0, imamo ciklus koji se "vrti" sve dok je N manje od 10 i unutar ciklusa imamo promenu vrednosti N.
Međutim, ako obratimo pažnju, videćemo da je ta promena vrednosti promenljive N njeno umanjivanje. Znači u svakoj iteraciji ciklusa N postaje sve manje i manje: -1, -2, -3.... U stvari nikada neće stići do 10, pa će se tako ovaj ciklus izvršavati beskonačno (ili bar dok računar ne stigne do granične vrednosti za broj, što može potrajati.
Brojački ciklus
Kada u algoritmu računar stigne do uslovnog ciklusa, uglavnom je to situacija kada ne može da se zna koliko će se puta ciklus izvršiti. Dakle, ciklus će se "vrteti" sve dok je uslov zadovoljen, nepoznat broj puta.
Međutim, često se u programu zna (ili se može izračunati) broj ponavljanja ciklusa. To su npr. situacije kada u programu postoji informacija o broju elemenata niza ili se od korisnika unapred traži da unese maksimalan broj ponavljanja. Tada je mnogo optimalnije koristiti brojački ciklus.
Ovaj ciklus funkcioniše na pricipu brojačke promenljive, koja ima definisanu početnu i krajnju vrednost. U jednom koraku se objedinjuje postavljanje početne vrednosti, provera da li je dostignuta krajnja vrednost i računanje nove vrednosti brojača.
Brojački ciklus se u različitim programskim jezicima optimizuje na različite načine, ali gotovo uvek je njegovo izvršavanje brže od običnog uslovnog ciklusa.
Objašnjenje brojačkog ciklusa
Pogledajte kako se brojački ciklus zadaje u C-u i sličnim jezicima. Objasnićemo njegovo funkcionisanje na primeru petlje koja se "vrti" 10 puta i to za vrednosti brojačke promenljive i, od 1 do 10. Šta sam ciklus "radi" - u ovom slučaju nije bitno. Zanima nas samo mehanika izvršavanja ciklusa.
Na primeru se vidi da se u jednom koraku zadaju tri iskaza. Prvi je iskaz za inicijalizaciju ciklusa. On se izvršava samo jednom, pre početka ciklusa. Obično se koristi za postavljanje početne vrednosti brojačke promenljive. Ovde vidimo da je to iskaz i=1, što znači da će promenljiva i dobiti početnu vrednost 1.
Drugi iskaz je uslov iteracije. On se izvršava pre početka svake iteracije i predstavlja ekvivalent uslovu iz uslovnih ciklusa. Ako je njegov rezultat true (ili bilo šta što se ne tumači kao false), iteracija će se izvršiti. U suprotnom, ciklus "iskače" i prelazi se na prvu naredbu koja dolazi posle ciklusa. U primeru je to uslov i<=10, što znači da će se ciklus izvršavati sve dok je i manje ili jednako 10.
Treći iskaz se izvršava na kraju svake iteracije. Obično se koristi za promenu vrednosti brojačke promenljive. U ovom primeru i++ znači da će se posle svake iteracije i povećati za 1.
Programski jezici (kao npr. JavaScript) su prilično fleksibilni sa ovim iskazima, u smislu da ih je moguće i izostavljati.
Ovaj ciklus možemo posmatrati kao specijalnu varijantu ciklusa sa preduslovom. Evo kako bismo morali da napravimo uslovni ciklus, koji bi bio ekvivalentan brojačkom ciklusu iz primera:
Kada ovako razložimo iskaze brojačkog ciklusa na korake algoritma sa uslovnim ciklusom, više i ne izgleda tako strašno.
U Algoritmima smo se odlučili za mnogo jednostavniji brojački ciklus koji se uklapa u Pascal ili Basic stil programiranja.
Ovakav ciklus može biti samo rastući, a ako nam treba brojačka promenljiva koja se smanjuje, možemo unutar ciklusa da vršimo kalkulaciju ili da prosto koristimo uslovni ciklus.
Ugnježdena petlja
Da li može da se desi da u algoritmu imamo takvu situaciju da u svakom ponavljanju, određene korake treba još i opet ponoviti više puta? O, da! Sasvim je moguće da unutar ciklusa opet imamo ciklus. I to ne samo ciklus-unutar-ciklusa, već i više nivoa koncentričnih petlji.
Tipičan primer kada bismo koristili unutrašnje cikluse je obrada podataka koji se nalaze u "dvodimenzionalnoj" strukturi, kao što je npr. matrica (dvodimenzionalni ili višedimenzionalni niz). Matrica se često definiše kao nizovi-unutar-niza (za sada je najbolje da matricu zamislite kao tablicu podataka sa kolonama i redovima). Koja bi bolja algoritamska struktura služila za rad sa tim podacima ako ne ciklus-unutar-ciklusa?
Primer koncentričnih ciklusa
Ispisati tablicu množenja brojeva od 1 do 10, tako da se isti parovi brojeva ne ponavljaju. Dakle, ako ispisujemo rezultat za npr. 3*6, ne treba da ispisujemo i za 6*3.
Ovo je jedan zaista jednostavan primer. Pošto se u trenutku početka ciklusa (pa čak i pre početka programa) tačno zna koliko puta će se izvršiti ciklus, najoptimalnije je da koristimo brojačke cikluse.
Možete videti da se spoljašnji ciklus zasniva na promenljivoj i, koja uzima vrednosti od 1 do 10 (počinje od 1 i povećava se sve dok ne stigne do 10). Unutrašnji ciklus sa brojačem j se "vrti" za svako pojedino i. Primetite da j ne ide od 1, već od i do 10. Tako za npr. i=5, j dobija vrednosti 5,6,7,8,9 i 10. Tako smo sprečili da se isti činioci ponove.