CIKLUSI SA PREDUSLOVOM

ZADACI SA USLOVNIM CIKLUSIMA

Primer 1:

Napisati program koji učitani broj n transformiše tako što mu uklanja nule sa desne strane (npr. od 130000 pravi 13)

Uslov za izvršavanje ciklusa je da je broj deljiv sa 10 tj. da ima nulu sa desne strane.  U svakom ponavljanju ciklusa eliminišemo po jednu nulu celobrojnim deljenjem sa 10. Iz ciklusa se izlazi kada ostatak celobrojnog deljenja više nije nula.

Primer 2:

Napisati program za približno računanje sume:

Sabirati do člana čija je vrednost manja od zadate tačnosti (tj. određujemo u stvari na koliko decimala nam treba tačna suma).

Inače, ova suma je u stvari vrednost  eksponencijalne funkcije o kojoj puno slušamo za vreme ove epidemije virusa Korona.

  Ciklus se izvršava sve dok je tekući član sume veći od tačnosti   tj. dovoljno veliki da utiče na sumu

Primer 3: Za uneti broj n prebrojati koliko ima cifara

Uneti broj celobrojno delimo sa 10. Istovremeno sa svakim deljenjem brojač uvećavamo za 1. Ciklus se izvršava dok ne dobijemo nulu kao rezultat, što je znak da smo došli do poslednje cifre. Praktično, sa svakim okretanjem ciklusa, tj. sa svakim deljenjem, odbacujemo po jednu cifru i istovremeno brojač cifara uvećavamo za 1.

Primer 4: Za uneti broj n ispitati da li je palindrom

Unosimo prirodan broj. Palindrom je ako ima istu vrednost i ako se čita naopačke, npr 1221 je palindrom. Zadatak ćemo rešiti tako što ćemo formirati drugi broj, kome ćemo obrnuti cifre. Ako su uneti i novodobijeni broj jednaki, to znači da je broj palindrom. Na primer, od broja 1234 napravićemo 4321, a pošto su uneti i dobijeni broj različiti, ovaj broj nije palindrom.

Pošto nam uneti broj n treba na kraju za upoređivanje, sačuvaćemo njegovu vrednost i koristiti pomoćnu promenljivu m koju ćemo menjati u ciklusu.

S je novodobijeni broj sa obrnutim ciframa.

U ciklusu uzimamo  ostatak deljenja broja sa 10 ( to nam je uvek preostala poslednja cifra broja sa desne strane, tj cifra jedinica)

m=1234   m%10=4

Znači u prvom prolasku kroz ciklus novodobijeni broj je 4.

Sada m delimo sa 10 i dobijamo 123

U sledećem prolasku s=s*10+m%10 što znači da od 4 dobijamo 40 i na to dodajemo 3 pa nam je novodobijeni broj 43, a m dobija novu vrednost 12 posle m=123//10.

U sledećem prolasku s=s*10+m%10 što znači da od 43 dobijamo 430 i na to dodajemo 2 pa nam je novodobijeni broj 432, a m dobija novu vrednost 1 posle m=12//10.

U sledećem prolasku s=s*10+m%10 što znači da od 432 dobijamo 4320 i na to dodajemo 1 pa nam je novodobijeni broj 4321, a m dobija novu vrednost 0 posle m=1//10.

Sada je jasno zašto nam je uslov za izvršavanje ciklusa da je m>0. Kada je m=0 "potrošili" smo sve cifre i dobili novi broj čije su cifre obrnute od unetog.

Na izlazu, ako su uneti i novodobijeni broj jednaki, broj je palindrom, ako nisu, nije.

Napomena: Ovim smo završili predavanja za ovu školsku godinu. Posle predloga zaključnih ocena koji ću vam poslati do kraja nedelje, dogovorićemo se oko odgovaranja u školi ako bude potrebe.

CIKLIČNE ALGORITAMSKE STRUKTURE (3)

USLOVNI CIKLUSI

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,  sve dok je odgovor na pitanje 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.

 Da bi uslov koji je u nekoliko iteracija bio zadovoljen, odjednom 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 seodgovarajući momenat, da bi se ciklus završio. Ilustracija bi bila klima uređaj koji se uključuje kada spoljašna temperatura pređe zadatu vrednost, a isključuje ako ne pređe.

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  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. Takođe, pošto ćemo učiti Python, naši zadaci biće sa preduslovom.

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.

Primer 1

Unose se celi brojevi dok se ne unese 0. Izračunati i ispisati zbir recipročnih  vrednosti unetih brojeva. Npr. za unete brojeve 5, 3 i 9, dobijamo zbir 1/5 + 1/3 + 1/9.

Na početku programa unosimo prvi broj. Ciklus kreće ako broj nije nula. Recipročnu vrednost broja dodajemo na sumu i unosimo sledeći broj. Opet se ispituje uslov i ako je ispunjen izvršava se telo ciklusa. Kada unesemo nulu, uslov više nije ispunjen i iz ciklusa se izlazi.

Primer 2

Nacrtati algoritamsku šemu za nalaženje aritmetičke sredine cifara prirodnog broja N.

Na početku programa postavljamo dve promenljive na nulu. S koja će nam predstavljati zbir cifara i promenljivu i koja će predstavljati broj cifara. Uslov za izvršavanje ciklusa je da je broj N veći ili jednak od 1. Kada N postane nula, iz ciklusa se izlazi.

U telu ciklusa najpre tražimo ostatak deljenja broja N sa 10. Tako dobijamo cifru jedinica. Nju dodajemo na sumu cifara. Zatim broj N celobrojno delimo sa 10, da bi eliminisali cifru jedinica jer smo je već sabrali.

Promenljivu i tj. broj cifara uvećavamo za 1 i vraćamo se u ciklus. Sve se izvršava sve dok nam ne ostane jedna cifra, i kada nju podelimo sa 10 dobijamo količnik nula. To je znak da se iz ciklusa izlazi. Tada računamo prosek kao količnik zbira cifara i broja cifara.

Test primer:

Unosimo broj  N-3678

I=0

S=0

Prva iteracija

N>=1 da

CIF=N%10 tj CIF=8

S=S+CIF tj S=0+CIF tj S=8

N=N//10 tj N=3678 // 10 tj N=367

I=i+1 tj i=0+1 tj i=1

Druga iteracija

Trenutna vrednost N je 367

N>=1 da

CIF=N%10 tj CIF=7

S=S+CIF tj S=8+CIF tj S=8+7=15

N=N//10 tj N=367 // 10 tj N=36

I=i+1 tj i=1+1 tj i=2

Treća iteracija

Trenutna vrednost N je 36

N>=1 da

CIF=N%10 tj CIF=6

S=S+CIF tj S=15+CIF tj S=15+6=21

N=N//10 tj N=36 // 10 tj N=3

I=i+1 tj i=2+1 tj i=3

Četvrta iteracija

Trenutna vrednost N je 3

N>=1 da

CIF=N%10 tj CIF=3

S=S+CIF tj S=21+CIF tj S=21+3=24

N=N//10 tj N=3 // 10 tj N=0

I=i+1 tj i=3+1 tj i=4

Peta iteracija

Trenutna vrednost N je 0

N>=1 ne – iz ciklusa se izlazi

Prosek = S/i  tj Prosek=24/4 tj. Prosek=6

Zadaci za vežbu:

1. Unosi se niz proizvoljnih brojeva. Za kraj unosa uneti nulu ( kao u primeru 1 ). Izračunati posebno zbir pozitivnih ZP i zbir negativnih brojeva ZN.

2. Ispisati sve delioce unetog celog pozitivnog broja X.

Uputstvo: Proveriti da li je uneti celi pozitivan broj prost, tj proveriti da li je deljiv prvo sa 2, pa sa 3 itd.  Proveru prekinuti onog trenutka kada se naiđe na delilac.

CIKLIČNE ALGORITAMSKE STRUKTURE (2)

BROJAČKI CIKLUSI 

Tipičan problem koji se rešava brojačkim ciklusom je računanje funkcije n!

Faktorijel je proizvod svih prirodnih brojeva od 1 do n, tj. 1*2*3*....*n

Kada posmatramo faktorijele redom:

1!=1

2!=1*2

3!=1*2*3

4!=1*2*3*4

Uočavamo  pravilnost, da je n! = (n-1)!*n

Međutim, ako ovu  formulu prevedemo na jezik programiranja, dobijamo konstrukciju:

novi faktorijel=prethodni faktorijel*tekuća vrednost broja

Računanje ćemo ostvariti u brojačkom ciklusu gde će brojačka promenljiva i uzimati vrednosti od 1 do n , a u telu ciklusa prethodna konstrukcija imaće oblik

fakt=fakt*i .

Ovde primećujemo da je sa leve strane izraza nova vrednost promenljive fakt, a sa desne strane stara vrednost. Kod korišćenja ciklusa naročito dolazi do izražaja ta osobina aritmetičke naredbe o kojoj smo govorili u prošloj lekciji.

Obavezno je zapamtiti da promenljiva fakt pre ulaska u ciklus mora dobiti vrednost 1, jer ako ima početnu vrednost 0, u ciklusu će nam se stalno množiti sa nulom i krajnji rezultat je uvek nula.

Primer 2:

Izračunati zbir svih parnih brojeva do 100.

U ovom primeru vršimo sabiranje u ciklusu. Početna vrednost promenljive S je nula, a u svakoj iteraciji na nju dodajemo vrednost brojačke promenljive i.

Parne brojeve dobićemo tako što korak podesimo na 2, tako da će brojačka promenljiva dobiti vrednosti 2,4,6,8,...do 100.

Primer 3:

Prebrojati koliko ima brojeva deljivih sa 3 u intervalu od m do n.

Promenljiva br će nam biti brojač koji ćemo uvećati za 1 svaki put kada u ciklusu naiđemo na broj koji je deljiv sa 3.

Broj je deljiv sa tri ako je ostatak celobrojnog deljenja sa 3 jednak nuli.

M i n su početna i krajnja vrednost ciklusa koje učitavamo na početku programa.

Zadaci za vežbu:

1. Izračunati zbir recipročnih vrednosti brojeva od m do n.

Uputstvo:

S=1/m + 1/(m+1) + 1/(m+2) +.....+ 1/n

2. Unose se vrednosti za x i n. Izračunati xⁿ.

Uputstvo:

P=x*x*x*x*x*....*x   n puta

CIKLIČNE ALGORITAMSKE STRUKTURE (1)

CIKLIČNE ALGORITAMSKE STRUKTURE (1)

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 strukturama. 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.

Postoje tri vrste ciklusa : brojački, ciklus sa preduslovom i ciklus sa postuslovom.

BROJAČKI CIKLUS

Č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 razlika u tome da li se brojačka promenljiva menja u nekom skupu vrednosti redom, npr. 1,2,3,4,5,6… ili može da se definiše korak po kome će se menjati vrednosti, npr 3,6,9,12,15…… korak je 3.

Grafički prikaz brojačkog ciklusa:

Pogledajte kako se brojački ciklus zadaje u Python-u i sličnim jezicima.

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.

Drugi iskaz je uslov iteracije. On se izvršava pre početka svake iteracije. Ako je njegov rezultat true, iteracija će se izvršiti. U suprotnom, ciklus "iskače" i prelazi se na prvu naredbu koja dolazi posle ciklusa.

Treći iskaz se izvršava na kraju svake iteracije. Obično se koristi za promenu vrednosti brojačke promenljive.

Unutar tela ciklusa su komande koje treba da se izvrše više puta.

Primer 1:

Ispisati prvih 10 prirodnih brojeva.

U ovom zadatku jasno je sledeće:

Potrebni su nam brojevi od 1 do 10.

Ciklus će se izvršiti 10 puta.

Početna vrednost brojačke promenljive biće 1.

Brojevi idu redom, tj. brojačka promenljiva se uvećava za 1.

Iz ciklusa se izlazi kada brojačka promenljiva dobije vrednost 11, tj. ciklus se izvršava sve dok je brojačka promenljiva <=10.

U telu ciklusa, komanda koja se izvršava više puta je štampaj broj.

Ovde vidimo da je broj koji se štampa u stvari brojačka promenljiva. Ona može da se koristi u izrazima sa desne strane, tj. njena vrednost može da učestvuje u izrazu. Ono što se u brojačkom ciklusu ne sme, jeste promena brojačke promenljive, tj. da ona stoji sa leve strane izraza. Tada “veštački” menjamo vrednost brojačke promenljive što dovodi do nekorektnog izvršavanja programa.

Primer 2:

Nacrtati algoritamsku šemu za izračunavanje sume brojeva od n do k.

U ovom zadatku jasno je sledeće:

Početna vrednost sume biće nula.

Početna vrednost brojačke promenljive biće  broj n koji ćemo učitati.

Krajnja vrednost brojačke promenljive biće  broj k koji ćemo učitati.

U telu ciklusa ćemo u svakoj iteraciji na trenutnu vrednost sume dodavati novi sabirak.

Ono što je novo i neobično u ovom zadatku je konstrukcija S=S+i. U matematici je ovo nemoguće osim kad je i nula, ali moramo shvatiti da u programiranju = nije relacioni operator kao u matematici, tj. ne pokazuje da je leva strana jednaka desnoj. Sada nam je to relacioni operator = =.

=  nam je sada aritmetička naredba, naredba dodele ili “postaje”.

Setimo se prvih lekcija iz računarstva kada smo govorili o memoriji. Svi podaci koji se obrađuju u računaru imaju svoju memorijsku lokaciju koja je adresirana, isto kao što svako od nas ima svoju kućnu adresu. Računar pronalazi podatke na njihovoj adresi isto kao što nas pronalazi poštar.

U programiranju je ime promenljive u stvari simbolička adresa memorijske lokacije na kojoj se taj podatak nalazi. Znači, na početku programa, kada smo napisali S=0, na toj memorijskoj lokaciji upisali smo početnu vrednost 0.

Kada ciklus počne da se izvršava, početna vrednost brojačke promenljive je n. U prvoj iteraciji dolazimo do komande S=S+i, tj. S=S+n. Tada se umesto vrednosti nula koja je bila na početku programa, u memorijsku lokaciju S upisuje vrednost 0+n tj. n.

Dakle, aritmetička naredba ima sledeći oblik:

promenljiva=izraz, gde se prvo računa vrednost izraza sa desne strane, pa se ta novodobijena vrednost šalje na memorijsku lokaciju promenljive sa leve strane.

Stoga i  na levoj i na desnoj strani može stajati ista promenljiva, ali im vrednost nije ista. Sa leve strane je nova, a sa desne strane stara vrednost.

Konstrukcija izraz= promenljiva nije dozvoljena.

Zadaci za vežbu:

U Word ili sličnom tekstualnom dokumentu odgovori na sledeća pitanja:

1.  Šta je ciklična algoritamska struktura?

2.  Šta je iteracija?

3.  Šta je brojačka promenljiva?

4.  Ako u zadatku zadam da treba raditi sa trocifrenim brojevima deljivim sa tri, koliki bi bili početna       i krajnja vrednost  brojačke promenljive i korak?

5. Kolika će biti stara, a kolika nova vrednost promenljive y posle izvršavanja ovih naredbi:

    X=5

    Y=6

    Y=(X+2)²-11

RAZGRANATA ALGORITAMSKA STRUKTURA (2)

ALGORITMI RAZGRANATE STRUKTURE (2)

U prošloj lekciji radili smo klasičnu razgranatu strukturu u kojoj postoje dve grane, jedna za vrednost uslova True, druga za False. Kada se izvrši jedna od te dve grane, nastavlja se sa sledećom komandom koja je na redu. Međutim, postoji i skraćena varijanta kod koje se za vrednost uslova  False jednostavno nastavlja dalje, nema posebne komande za tu situaciju. U svim programskim jezicima postoji takva varijanta naredbe grananja.

 Primer 1:

Unose se tip paketa 1, 2 ili 3, minuti razgovora i cena po minutu. Izračunati iznos računa ako su u tarifi 3  penzioneri kojima se račun umanjuje za 20%.

U stvarnim problemima se vrlo često pojavljuje i opcija više mogućnosti, kada se u okviru jednog grananja pojavljuje još jedno. Takva situacija se dešava kada imamo tri mogućnosti:

Primer 2:

Unose se tip paketa 1, 2 ili 3, minuti razgovora i cena po minutu. Izračunati iznos računa ako su u tarifi 2 studenti kojima se umanjuje račun za 10% a u tarifi 3  penzioneri kojima se račun umanjuje za 20%.

Takođe u raznim programskim jezicima postoje različiti oblici višestrukog grananja, tj. broj mogućnosti je više od četiri i samim tim je obično grananje isuviše komplikovano. Takve zadatke nećemo vežbati sada, već kad budemo radili konkretan programski jezik jer se strukture takvih komandi bitno razlikuju u zavisnosti od jezika.

Primer 3:

 Za unetu brojčanu ocenu učenika štampati tekstualnu.

Zadaci za vežbu:

1. Za tačku  M(x,y) ispisati u kom je kvadrantu koordinatnog sistema.
    Uputstvo: x>0 and y>0 prvi kvadrant, x<0 and y>0 drugi itd.

2. Za  unete stranice trougla a, b, c  ispitati kakav je:
   Uputstvo:
    a²+ b²> c² -oštrougli   a²+ b²= c² -pravougli   a²+ b² <  c^{2 -} tupougli

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. 

TIPOVI PODATAKA

TIPOVI PODATAKA

Pre nego što krenemo dalje u rešavanje problema, upoznaćemo se sa osnovnim tipovima podataka koji se koriste u računarstvu. Raznovrsni podaci koji se pomoću računara obrađuju, nisu posledica razvoja samih računara, već savremenog društva u celini. Procedure koje su do pre par godina spadale u naučnu fantastiku (sken oka, prepoznavanje lica, 3D štampa) sada spadaju u svakodnevne.

Naravno, sada u prvom razredu nećemo učiti o svim tipovima podataka, već ćemo postupno, učeći sve složeniju obradu, upoznavati i složene tipove. Samim tim, tipovi koje ćemo prvo upoznati nazivaju se prosti tipovi.

Prva obrada podataka koja se može nazvati računarskom obradom, odnosila se na obradu brojeva. Imate dovoljno znanja iz matematike da prepoznajete različite  vrste brojeva – prirodne, cele, racionalne, iracionalne, realne... I u računarstvu se koriste različite vrste brojeva za različite obrade.  Nekada je sasvim svejedno sa kojom vrstom broja radite, a nekada imate ograničenja. Npr kada merite dužinu puta od Sombora do Novog Sada, taj broj nije apsolutno tačan tako da ga možete prikazati kilometrima, metrima, kao ceo broj ili realan na nekoliko decimala. Međutim, mesec rođenja mora biti ceo broj, i ne samo to, već ceo broj od 1 do 12.

Mi ćemo za sada definisati dva tipa brojeva - cele i realne. Realni brojevi su gotovo isti kao oni na koje smo navikli u matematici. U računarstvu nema beskonačno mnogo decimala- broj mora biti zaokružen. Takođe, ne piše se sa decimalnim zarezom već sa decimalnom tačkom. Znači, -2.33, +1.41345621, 0.5 su realni brojevi. Za njih važe iste operacije kao u matematici, ali nešto drugačije zapisane:

+   sabiranje

-         oduzimanje

*   množenje

/    deljenje

Rezultat izraza u kome učestvuju realni brojevi je realan broj. Ako nam je iz nekog razloga potreban rezultat koji je ceo broj, dobijamo ga nekom od funkcija konverzije ili zaokruživanja.

          Celi brojevi , brojevi bez decimalnih mesta, u izrazima mogu da daju realan ili celobrojni rezultat. Korišćene jedne ili druge opcije zavisi od prirode problema koji rešavamo. Ako su nam potrebni celobrojni rezultati, moramo koristiti i operacije sa celim brojevima:

+   sabiranje

-         oduzimanje

*   množenje

//    količnik celobrojnog deljenja

%  ostatak celobrojnog deljenja

Operacije koje se razlikuju su kod deljenja jer nemamo decimalnih mesta. Neke podatke ne možemo deliti na delove ( npr ljude, ne možemo imati 1.34 čoveka) Zato imamo količnik i ostatak. Na primer, imamo 33 bombona koje delimo na sedmoro dece.

33//7=4 svako dete dobiće 4 bombone

33%7=5 ostaće nam 5 bombona.

Tekstualni podaci su važan deo računarske obrade i sa njima se rade različite operacije: spajanje, razdvajanje, izdvajanje delova teksta itd. Više o tome saznaćemo kada budemo radili konkretan programski jezik.

Logički podaci su podaci koji su vrlo važni u računarskoj obradi, a način na koji se sa njima radi videćemo već od sledeće lekcije kada budemo radili algoritme razgranate strukture.

Imamo dve logičke konstante True - tačno i False- netačno

Operacije sa logičkim promenljivima su:

and - logičko i - svi članovi moraju biti tačni da bi izraz bio tačan

or – logičko ili – bar jedan član mora biti tačan da bi izraz bio tačan

not – logičko ne – negacija

Vrednost tačno ili netačno imaju i izrazi kod kojih se javljaju relacioni operatori:

= = jednako

! = različito

<= manje ili jednako

<  manje

>= veće ili jednako

>  veće

DOMAĆI ZADATAK:

Na sednici se spominjalo da iz raznih predmeta radite prezentacije, tako da  ko ima, može mi poslati, jer je to i vežba iz informatike pa može da se dobije plus i iz tog dela.

Algoritmi linijske strukture

Algoritmi linijske strukture

Zadaci koje ste poslali imali su veoma različita i interesantna rešenja. Primetili ste da kada treba rečima da se opiše neki postupak, nije jednostavno postići preciznost u izražavanju. Sa druge strane, simbolički zapis algoritma je precizniji, ali je veliki broj vas koristio simbole koji su vam se dopali, a ne simbole koji bi odgovarali trenutnom koraku. Da se podsetimo:

Algoritam je konačna i precizno definisana procedura, niz dobro definisanih pravila, kojom se ulazne vrednosti transformišu u izlazne, ili se opisuje izvršavanje nekog postupka.

Kada smo učili kako radi procesor, spominjali smo programske jezike. Procesor može izvršiti samo apsolutno formalan zapis, ne tolerišući ni najmanje nepreciznosti. Zbog toga su razvijeni posebni jezici koji omogućavaju zapis algoritma korišćenjem skupa konstrukcija koje se ne mogu višeznačno i proizvoljno tumačiti.

 Dakle, programski jezik je skup sredstava i pravila predstavljanja algoritma u obliku pogodnom za izvršavanje na računaru. Program je zapis algoritma u programskom jeziku.

Naš zadatak je da naučimo da razlažemo probleme na korake, tako da svaki korak jednoznačno odgovara jednoj komandi programskog jezika.

Ovaj simbol označava početak i kraj programa. To nisu samo formalne oznake, već se na različitim nivoima složenosti programa javlja različit niz komandi koje se pišu na početku i na kraju.

Pravougaonik označava obradu podataka. Znači u njega se pišu komande u kojima se nešto računa ili izvršava.

Obrnuti trapez označava učitavanje ulaznih podataka. To su podaci koje poznajemo i saopštavamo ih računaru.

Trapez označava izdavanje izlaznih podataka. To su podaci koje smo  dobili izvršavanjem programa i saopštavamo ih korisniku.

Primer:

Pretvoriti dužinu u inčima u dužinu u centimetrima.

Sada programeru nije teško bukvalno ’’prevesti’’ algoritam na bilo koji programski jezik jer je sve jednoznačno definisano:

Početni segment

Ulaz

Obrada

Izlaz

Završni segment

Ovakve algoritamske strukture gde se sve komande izvršavaju redom od početka do kraja, nazivaju se linijske strukture. Kod njih se svaka naredba programa izvrši tačno jednom. Znači nema preskakanja, nema više puta nego jednom.

Zadatak za vežbu:

Oba zadatka iz prošle vežbe (trougao i valjak) sada uraditi u obliku algoritma striktno poštujući odgovarajuće simbole i pravila. Možete ih uraditi u jednom dokumentu i  poslati kada vam odgovara, jer treba malo i da se odmorite.

Srećni uskršnji praznici! 

Prvi razred – uvod u programiranje

Algoritam

Algoritam je u matematiku uveo iranski matematičar Muhamed Al Horezmi. Napisao je knjigu Al Horezmi o indijskoj veštini računanja gde u islamsku matematiku uvodi indijske cifre i decimalni brojni sistem. Ova knjiga biva kasnije prevedena na latinski kao Algoritmi de numero indorum. Od lošeg latinskog prevoda njegovog prezimena i potiče reč algoritam, i dugo je označavala postupak za račun sa decimalnim brojnim sistemom (i indijskim odnosno, kako se kasnije pričalo, arapskim ciframa)

 Danas, algoritam je konačna i precizno definisana procedura, niz dobro definisanih pravila, kojom se ulazne vrednosti transformišu u izlazne, ili se opisuje izvršavanje nekog postupka.

Reč algoritam se često vezuje za pojam računarstva mada uopšteno algoritam možemo smatrati kao uputstvo kako rešiti neki zadatak ili problem. Tako se i uputstvo za slanje rakete u svemir i uputstvo za pravljenje ruske salate sastoji od niza koraka, postupaka, koje treba uraditi i koji vode ispunjenju cilja ili rešavanju problema. Uputstvo može sadržati korake koji se ponavljaju više puta ili korake kada treba doneti neku odluku, na osnovu nekog kriterijuma. Dobro uputstvo predviđa i postupak kada nisu svi uslovi ispunjeni npr. raketa je izgorela pri testiranju, ili nema majoneza u frižideru a počeli smo da kuvamo povrće. Korektno izvršavanje svakog koraka ne rešava zadatak ako je algoritam bio pogrešan.

Različiti algoritmi mogu rešiti isti problem različitim nizom postupaka uz manje ili više napora, za kraće ili duže vreme. Obzirom da je rezultat isti, algoritmi se mogu porediti po svojoj efikasnosti, brzini ili kompleksnosti.

Primer algoritma iz svakodnevnog života je kuvanje čaja. Svaki korak pripremanja čaja mora biti izvršen pravilno kako bi se moglo preći na sledeći i u konačnom vremenu dobili skuvan čaj.

Algoritam kuvanja čaja glasi:

Uzeti lonče i sipati vodu.

Uključiti ringlu.

Sačekati dok voda ne proključa.

Kad voda proključa, skinuti lonče i isključiti ringlu.

Staviti kesicu čaja u lonče.

Po želji, dodati kašiku šećera, mleko ili limun.

Sipati čaj u šolju.

Iz ovog jednostavnog primera može se videti postupnost i konačnost algoritma. Naime, nema previše koristi od algoritma koji se nikada ne završava ili algoritma čije se naredbe izvode nepredvidljivo ili im je rezultat nepredvidljiv.

Primer kompleksnijeg algoritma je Euklidov algoritam za određivanje najvećeg zajedničkog delioca:

• Podeliti broj a brojem b pri čemu se dobija količnik c i ostatak r
• Broj a uzima vrednost broja b
• Broj b uzima vrednost r
• Ponavljati sve dok ostatak r ne bude jednak 0. Najveći zajednički delilac je trenutna vrednost broja a

Prvi algoritam koji se može smatrati procedurom čija je namena račun na automatskoj mašini je napisala Ejda Bajron 1842. godine. U pitanju je algoritam za račun Bernulijevih brojeva na analitičkoj mašini Čarlsa Bebidža. Danas se to priznaje kao prvi računarski algoritam, a Ejda Bajron, ledi Lavlejs, je priznata kao prvi programer u istoriji. U njenu čast je i jedan od programskih jezika dobio naziv Ada.

Značajan napredak u formalizaciji uvođenja algoritma u matematiku i logiku je učinio Alan Tjuring u svojim radovima definisanjem Tjuringove mašine. To je virtuelna mašina, misaona tvorevina, ali poseduje mogućnost izvođenja nekoliko operacija koje su dovoljne za izvođenje skoro svih algoritama. Čerč-Tjuringova teza tvrdi da se svaki algoritam koji je dobro definisan može izvršiti na takvoj mašini. Tako se, i pored jednostavnosti ove mašine, začela teorija konačnih automata kao nova oblast.

Osobine

Algoritmi poseduju sledeće osobine:

Definisanost - svaki korak mora biti jednoznačno definisan, ne ostavljajući mesta za proizvoljna i nejasna tumačenja;

Diskretnost - u odvojenim koracima se izvršavaju diskretne operacije algoritma koji vode ka konačnom cilju;

Rezultativnost - označava sposobnost algoritma da posle konačnog broja koraka daje izlazne podatke;

Determinisanost - za iste ulazne podatke algoritam uvek generiše iste vrednosti na izlazima

Masovnost - algoritam je primenljiv na veći broj ulaznih vrednosti.

Algoritmi i strukture podataka

Svaki algoritam se sastoji od početka i kraja, dok se između toga nalaze elementi koji predstavljaju osnovne delove koji sadrže definisani put ka rešenju problema. Da bismo uopšte počeli sa rešavanjem problema, prvo moramo da ga definišemo i postavimo rešenje.

Algoritam može biti opisan na više načina: prirodnim jezikom, dijagramima, pseudokodom i programskim jezikom. Dijagrami su možda i najpopularniji način, jer se na jednostavan a slikovit način predstavlja problem i njegovo rešavanje. Za to vam nije potreban kompjuter, već prosto olovka i papir na kojem ćemo iscrtati algoritamsku šemu, tj. grafički prikaz algoritma.

Primer:

Nacrtati algoritam za računanje obima i površine kruga.

 Zadaci za vežbu:

1. Napisati rečima koristeći numeričko nabrajanje (numbering) niz koraka za izračunavanje obima i površine pravouglog trougla ako su mu date katete.
2. Nacrtati algoritam za računanje površine i zapremine valjka ako su nam dati poluprečnik osnove r i visina H. Možete ga uraditi u istom dokumentu gde je i prvi zadatak koristeći shapes