среда, 20. мај 2020.

RАD SА TЕKSTUАLNIM DАTОTЕKАMА


RАD SА TЕKSTUАLNIM DАTОTЕKАMА

Dаtоtеkа (ili fајl) је prоizvоlјnо dugаčаk niz pоdаtаkа kојi sе nаlаzi nа spоlјаšnjој mеmоriјi, nајčеšćе disku. Pоstоје rаznе vrstе dаtоtеkа, а mi ćеmо sе u оvоj lekciji bаviti tеkstuаlnim dаtоtеkаmа.
Теkstuаlnа dаtоtеkа је niz simbоlа kао štо su slоvа, brојеvi, znаci intеrpunkciје i sličnо, kојi sе nаlаzi nа spоlјаšnjој mеmоriјi. Nа primеr, kаdа u nеkоm еditоru kао štо је Notepad оtkucаmо nеki tеkst


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.








четвртак, 14. мај 2020.

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 xn.
Uputstvo:
P=x*x*x*x*x*....*x   n puta




RAD SA LISTAMA


ZADACI  SA  LISTAMA

U ovoj lekciji videćemo nekoliko primera rada sa listama gde se elementi liste učitavaju sa tastature.

Primer 1: Unose se  visine n učenika. Prebrojati koliko učenika ima veću visinu od prosečne.

n= int(input ("Unesite broj učenika: "))
L=[]
for i in range(0,n):
    x=int(input("unesite visinu "))
    L.append(x)
pr=sum(L)/n
print("prosečna visina je: ",pr)
br=0
for i in range (0,n):
    if L[i]>pr:
        br=br+1
print("više od proseka je ",br," učenika" )

Visine učenika smo na ulazu dodavali sa append u listu L. Po izlasku iz ciklusa izračunali smo prosečnu visinu. U drugom ciklusu smo prošli kroz elemente liste, i svaki put kada naiđemo na visinu veću od proseka, uvećavamo brojač br za 1.

Primer 2: Unosi se proizvoljan niz pozitivnih brojeva. Kraj unosa će biti kad unesemo nulu. Izračunati geometrijsku sredinu elemenata liste.

print("Unesite prirodan broj,za kraj unosa nulu ")
L=[]
pro=1
x=int(input("broj= "))
while x!=0:
    L.append(x)
    pro=pro*x
    x=int(input("broj= "))
gs=pro**(1/len(L))
print("Ulazna lista",L )
print("Geometrijska sredina",gs)

U ovom zadatku smo unosili nepoznat broj elemenata. Za kraj unosa stavili smo nulu. Pošto ne znamo koliko ima brojeva, formirali smo while ciklus koji se izvršava sve dok ne unesemo nulu, tada se prekida. U ciklusu smo množili unete brojeve, jer je geometrijska sredina n - ti koren iz proizvoda n elemenata. Koliko smo brojeva uneli, saznali smo iz dužine liste len(L).

Primer 3: Unosi se lista n proizvoljnih celih brojeva. Formirati drugu listu u kojoj će biti samo parni brojevi.

n= int(input ("Unesite broj elemenata liste: "))
L=[]
LP=[]
for i in range(0,n):
    x=int(input("unesite ceo broj "))
    L.append(x)
    if x%2==0:
        LP.append(x)
print("Ulazna lista",L )
print("Lista parnih brojeva", LP)

U ovom zadatku smo brojeve sa ulaza upisali u listu L. Zatim smo ispitali da li je broj paran, i ako jeste, upisali ga u listu LP, ako nije, preskočili ga. Na kraju ciklusa imamo formirane dve liste - L ulaznih brojeva i LP parnih brojeva.

Zadaci za vežbu:

1. Unosi se lista n proizvoljnih celih brojeva. Formirati drugu listu u kojoj će biti samo negativni brojevi.

2. Unosi se lista L od n proizvoljnih celih brojeva. Formirati drugu listu L1 u kojoj će biti kvadrat elementa iz L ako je negativan, a koren ako je pozitivan.

(npr L=[1, -2 , 4 , 2 , -3 , 0 , 3] onda je L1=[1, 4 , 2 , 1.41 , 9 , 0 , 1.73]




среда, 6. мај 2020.

SLOŽENE STRUKTURE PODATAKA (2)


RAD SA LISTAMA

U prošloj lekciji smo u primerima imali liste definisane u samom programu. Međutim, u praksi se elementi liste unose standardnim ulazom sa tastature ili čitanjem iz fajla. Na početku se, kao i za promenljivu, inicijalizuje početna vrednost, najčešće prazna lista.

L = [ ]
Između uglastih zagrada nema razmaka.

Često se  koristi petlja za prolazak kroz svaku vrednost u listi. Ako je L lista, komanda

for x in L: «telo petlje»


radi sledeće: prvo x dobija vrednost prvog elementa iz liste L, i izvršava se telo: onda u sledećem krugu x predstavlja drugu vrednost u L, i izvršava se telo; takav postupak se nastavlja za sve članove L

Dodavanje i brisanje elemenata

U mnogim programskim jezicima, veličina niza je fiksna, te se navodi prilikom njegovog kreiranja, pa ako se preračunate, završićete sa mnogo neiskorišćenog prostora ili sa elementima koje ne možete smestiti u niz. Ako koristite indeks veći od postojećeg, program javlja grešku prekoračenja.

Liste u Pythonu nisu fiksne veličine, već rastu i smanjuju se po potrebi, prilikom dodavanja, odnosno brisanja elemenata. Za dodavanje elemenata, koristićemo funkcije append, za dodavanje na kraj, odnosno insert, za umetanje elementa na određenu poziciju u nizu. Da bi se napravilo mesta za element koji se ubacuje u niz, svi elementi koji su desno od novog elementa se "pomere" za jedno mesto u desno. Za brisanje bilo kog od elemenata, tu je naredba del.

pocetnaLista = [14, 8, 7, 12, 11]

# Dodamo element na kraj
pocetnaLista.append(999)
print('Nakon dodavanja na kraj:', pocetnaLista)
Nakon dodavanja na kraj: [14, 8, 7, 12, 11, 999]


# Umetnemo element na poziciju 2
pocetnaLista.insert(2, 100)
print('Nakon umetanja na poziciju 2:', pocetnaLista)
Nakon umetanja na poziciju 2: [14, 8, 100, 7, 12, 11, 999]



# Obrišimo ono što smo dodali:
del pocetnaLista[-1] # Element na kraju
del pocetnaLista[2]  # Element na poziciji 2


 Ovde ne možemo preterati sa indeksima: Ako je indeks prevelik, element se dodaje na kraj. Ako je indeks previše mali, element se dodaje na početak, npr:

pocetnaLista.insert(200, 'ja sam na kraju')
pocetnaLista.insert(-50, 'ja sam na pocetku')

Nakon umetanja:   ['ja sam na pocetku', 14, 8, 7, 12, 11, 'ja sam na kraju']

Segmentacija liste

Zvanični termin za ovu operaciju je slice. Operacija je jednostavna - iz liste iseći određeni deo. Kad će mi to trebati? Pa recimo:

Zanima vas ekstenzija fajla - odsečete poslednja tri karaktera.
Zanima vas godina nečijeg rođenja, a imate njegov matični broj - odsečete sve od petog do osmog karaktera
Zanima vas 5 najboljih i 5 najgorih rezultata na Olimpijadi
I još mnogo toga
Slično indeksiranju, koristi se operator [ ], ali ovaj put ne navodimo jedan broj, već dva, koje predstavljaju granice onog što želimo da isečemo, a odvojene sa dvotačkom ( : ). Važno je za napomenuti, sečenje uzima sve elemente počevši od prvog, do ali ne uključujući poslednjeg. Za razliku od indeksiranja, rezultat sečenja je uvek lista, koja u zavisnosti od granica sečenja može biti prazna, imati jedan ili više elemenata.

pocetnaLista = [14, 8, 7, 12, 11]

print('Prva tri elementa', pocetnaLista[0:3])
Prva tri elementa [14, 8, 7]


print('Svi elementi osim poslednjeg', pocetnaLista[0:-1])
Svi elementi osim poslednjeg [14, 8, 7, 12]

# Iako je rezultat samo jedan element, sečenje vraća niz!
print('Samo prvi element', pocetnaLista[0:1])
Samo prvi element [14]


# Ili nekad prazan
print('Nepostojeći isečak', pocetnaLista[100:120])
Nepostojeći isečak []

S obzirom da često želimo prvih nekoliko ili poslednjih nekoliko elemenata, postoji nekoliko skraćenica:

Ako se izostavi prva granica, podrazumeva se da je nula
Ako se izostavi poslednja granica, podrazumeva se da je jednaka dužini niza (ovo se radi da bi bio obuhvaćen i poslednji element)
Ako se izostave obe granice, vraća se kopija liste

pocetnaLista = [14, 8, 7, 12, 11]

print('Prva dva elementa', pocetnaLista[:2])
Prva dva elementa [14, 8]

print('Poslednja dva elementa', pocetnaLista[-2:])
Poslednja dva elementa [12, 11]


Postoji više ugrađenih funkcija koje rade sa listama. Ovde prikazujemo neke od najkorisnijih:

len     Računa dužinu liste (broj podataka u listi)
sum   Računa sumu podataka u listi
min   Nalazi najmanji podatak u listi
max  Nalazi najveći podatak u listi

Na primer, sledeća naredba izračunava srednju vrednost  brojeva iz liste L:

average = sum(L)/len(L)

append(x)   Dodaje podatak x na kraj liste
sort()           Sortira listu
count(x)      Vraća broj pojavljivanja podatka x u listi
index(x)      Vraća poziciju prvog pojavljivanja podatka x u listi
reverse()     Invertuje listu (obrće redosled podataka u listi)
remove(x)   Ukljanja (briše) prvo pojavljivanje podatka x u listi
insert(p,x)   Ubacuje podatak x na poziciju p u listi


Primer 1:

Napišite program koji generiše listu L od 50 slučajnih brojeva između 1 i 100.

from random import randint
L = [ ]
for i in range(50):
    L.append(randint(1,100))

Iz Excela se sećamo funkcije randint koja generiše slučajne brojeve. Ovde takođe postoji, samo je pozivamo iz biblioteke random.
Koristili smo funkciju append za dodavanje podataka u praznu listu, [].

Primer 2:

Zamenite svaki podatak iz liste L sa njegovim kvadratom.

for i in range(len(L)):
    L[i] = L[i]**2

Primer 3:

Prebrojte koliko podataka iz liste L je veće od 50.

brojac = 0
for pod in L:
    if pod>50:
        brojac = brojac+1

Primer 4:

Iz datog niza brojeva izdvojiti parne i upisati u drugu listu

    rez = [ ]
    for x in L:
        if x %2== 0:
            rez.append(x)
   
Primer 5:

Napiši program koji učitava broj ocena učenika, a zatim i pojedinačne ocene (svaku u posebnom redu) i na kraju određuje i ispisuje prosečnu ocenu tog učenika.

Elemente u listu možemo učitati tako što na početku krenemo od prazne liste (liste [ ]), a zatim u petlji učitavamo jedan po jedan element i dodajemo ga u listu funkcijom append.


broj_ocena = int(input("Unesi broj ocena:"))
ocene = [ ]
for i in range(broj_ocena):
    ocena = int(input("Unesi ocenu:"))
    ocene.append(ocena)
prosek = sum(ocene) / len(ocene)
print("Prosek:", prosek)

Zadaci za vežbu:

Ako je lista zadata naredbom a=[9,5,2,7,4,6], šta će biti rezultati izraza:
1. len(a)
2. min(a)
3. del(a[4])
4. del(a[:4])
5. a.append(3)
6. Može li lista podataka biti prazna? Ako može, kako se kreira?


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)2-11



четвртак, 30. април 2020.

SLOŽENE STRUKTURE PODATAKA (1)


TORKE I LISTE

U svim programima koje smo do sada pisali, podatke smo čuvali u pojedinačnim promenljivima. To su bili obično pojedinačni brojevi ili eventualno kraći delovi teksta (npr. ime ili prezime). Elementarni podaci koje smo do sada sretali bili su celi brojevi (tipa int), realni brojevi (tipa float), logičke vrednosti (tipa bool) i niske (tipa str). U mnogim realnim primenama imamo potrebu da u programu zapamtimo, a kasnije i obradimo veće količine podataka. U tim situacijama korišćenje pojedinačnih promenljivih za pamćenje svakog pojedinačnog podataka nije praktično ili čak nije moguće i potrebno je koristiti strukture podataka koje nam omogućavaju da pomoću jedne promenljive predstavimo čitave kolekcije podataka, koje se sastoje od više vrednosti nekog jednostavnijeg tipa. U zavisnosti od podataka koje želimo da sačuvamo i operacija koje sa njima želimo da sprovedemo, biramo koju od nekoliko različitih vrsta struktura podataka koje imamo na raspolaganju treba da upotrebimo.
Zapitajmo se kako bismo u programu mogli predstaviti spisak imena košarkaša u jednom timu? Neka je to naša košarkaška reprezentacija,  Pretpostavićemo da svaki igrač ima svoj redni broj i to od 1 do 12.

Jedan mogući način bi bio da uvedemo puno zasebnih promenljivih:

igrac1 = "Nikola Jokić"

igrac2 = "Bogdan Bogdanović"

igrac3 = "Nemanja Bjelica"

igrac4 = "Vasilije Micić"

...
Međutim, ovakav prikaz podataka nije zgodan jer ne možemo jednostavno da odgovorimo na razna interesantna pitanja o košarkašima (na primer, koliko ukupno ima igrača, ko nosi broj koji se unosi sa ulaza, koji broj nosi neki dati igrač i slično). Bolji način da predstavimo spisak igrača je da upotrebimo torku ili listu. Na primer, torku imena košarkaša možemo definisati na sledeći način:

igraci = ("Stefan Jović", "Vasilije Micić", "Bogdan Bogdanović", "Marko Gudurić", "Marko Simonović", "Vladimir Lučić", "Stefan Birčević", "Nemanja Bjelica", "Nikola Jokić","Boban Marjanović", "Miroslav Raduljica", "Nikola Milutinov")

Zapis oblika (35, 128) se u matematici naziva uređeni par, zapis oblika (250, 120, 310) uređena trojka, zapis oblika (135, 22, 83, 57) uređena četvorka itd. Kada dužina nije poznata, kaže se uređena n-torka (uređena entorka), ali u programiranju je odomaćeno kraće ime - torka.

Dakle, torku definišemo tako što između običnih malih zagrada  ( i ) navodimo elemente razdvojene zarezima. Primetimo da je lista imena košarkaša veoma dugačka, tako da smo je preglednosti radi razbili u više redova. Iako u opštem slučaju nije dopušteno deliti naredbe na više linija, to je moguće ako je sadržaj tih linija okružen nekim zagradama (pošto je u prvoj liniji otvorena zagrada (, nakon čitanja prve automatski se čitaju i druga i treća i četvrta linija, sve dok se ne naiđe na zatvorenu zagradu )).

Definisanje liste bi se razlikovalo od definisanja torke samo po tome što bi se umesto običnih malih zagrada (...) upotrebile uglaste zagrade  [...].

igraci = ["Stefan Jović", "Vasilije Micić", "Bogdan Bogdanović", "Marko Gudurić", "Marko Simonović", "Vladimir Lučić", "Stefan Birčević", "Nemanja Bjelica", "Nikola Jokić", "Boban Marjanović", "Miroslav Raduljica", "Nikola Milutinov"]

Suštinska razlika između torke i liste je to što je torka imutabilna što znači da joj ne možemo menjati vrednosti kada je jednom definišemo. Sa druge strane, liste dopuštaju da im menjamo pojedinačne elemente, uklanjamo elemente, dodajemo nove i slično. Sve operacije u kojima se vrši analiza sadržaja biće identične bez obzira da li se radi o listi ili o torki i opisaćemo ih u sledećoj lekciji (iako ćemo u primerima koristiti torke, sve one se na potpuno isti način mogu primeniti i na liste). Operacije u kojima se vrši promena su specifične za liste i nije ih moguće sprovesti nad torkama i njih ćemo opisati zasebno.
Pojedinačni članovi torke ili liste nazivaju se i elementi. Elementi mogu biti niske (kao u ovom primeru), ali i brojevi, druge torke ili liste i bilo šta drugo. Čak je moguće u istu torku tj. listu postaviti elemente različitog tipa. Kao primer torke brojeva, formirajmo torku visina ovih naših košarkaša.

visine = (198, 197, 198, 198, 203, 203, 210, 208, 213, 221, 213, 212)

Dvočlane torke (uređeni parovi) i višečlane torke ( uređene trojke, četvorke itd.) se najčešće koriste za grupisanje tek nekoliko pojedinačnih podataka. Na primer, poziciju figure na šahovskoj tabli možemo predstaviti pomoću uređenog para koji čini oznaka vrste (slova od a do h) i oznaka kolone (broja od 1 do 8). Na primer, ("b", 6). Slično, pozicije na geografskoj karti se opisuju pomoću geografske širine i dužine tj. pomoću para realnih brojeva. Tako se grad Pariz nalazi na poziciji koja se može opisati pomoću para (48.8566, 2.3522). Vreme možemo predstaviti pomoću uređene trojke koju čine sat, minut i sekund (na primer, (7, 25, 37)).

Za grupisanje većeg broja podataka češće se koriste liste, pogotovo ako nije unapred poznato koliko takvih podataka može biti tj. ako se broj podataka može izmeniti tokom rada programa. Na primer, ako želimo da predstavimo ocene učenika češće bismo upotrebili listu, jer učenik može da dobije još neku ocenu, pa je listu njegovih ocena potrebno proširiti, što nije moguće ako se ocene predstave torkom.

Izdvajanje elemenata

Elementima torke (ili liste) pristupa se na osnovu njihove pozicije tj. indeksa. Brojanje kreće od nule. Prvi element liste se nalazi na poziciji 0, drugi na poziciji 1 i tako dalje. 
Na primer, elementi u listi a = [3, 7, 4, 2, 5] se broje na sledeći način

Indeks             0 1 2 3 4

Vrednost         3 7 4 2 5

Zato je prvom elementu moguće pristupiti sa a[0] i vrednost toga izraza je 3 (jer se na poziciji 0 u listi nalazi broj 3), drugom elementu sa a[1] i vrednost tog izraza je 7 i tako dalje.

Negativni indeksi upućuju na brojanje od kraja (s desna na levo), pa -1 označava poslednji element, -2 pretposlednji i tako dalje.

Indeks             -5 -4 -3 -2 -1

Vrednost          3  7  4   2   5

Zato je poslednjem elementu moguće pristupiti pomoću a[-1], pretposlednjem pomoću a[-2] itd.

Još jedna korisna operacija je izdvajanje dela torke tj. liste. Elementima između pozicija x i y uključujući poziciju x, ali isključujući poziciju y moguće je pristupiti pomoću a[x:y].

Na primer, ime[1:4] izdvaja elemente imena na pozicijama 1, 2 i 3 (raspon [1:4] je poluotvoren tj. pozicija 1 je uračunata, a pozicija 4 nije). Ako je a = [3, 7, 4, 2, 5] tada je a[1:4] lista čija je vrednost [7, 4, 2]. Ako se izostavi broj iza dvotačke, izdvajaju se elementi do kraja. Na primer a[2:] je lista koja ima vrednost [4, 2, 5].

Primer:

Poznat je spisak igrača u timu. Oni nose dresove sa brojevima od 1 pa na dalje. Napiši program koji za dati broj dresa određuje igrača koji igra pod tim rednim brojem.

Pošto se unose brojevi od 1 do dužine torke (ili liste), a indeksi se kreću od 0 pa do prethodnika dužine torke, nakon učitavanja broja dresa pristupiće se elementu čiji je indeks za 1 manji od broja dresa.

igraci = ("Stefan Jović", "Vasilije Micić", "Bogdan Bogdanović",
          "Marko Gudurić", "Marko Simonović", "Vladimir Lučić",
          "Stefan Birčević", "Nemanja Bjelica", "Nikola Jokić",
          "Boban Marjanović", "Miroslav Raduljica", "Nikola Milutinov")
dres = int(input("Broj dresa: "))
print(igraci[dres - 1])

Zadatak za vežbu:

Odgovori na sledeća pitanja:

1. Zbog čega se uvode složene strukture podataka?

2. U čemu je razlika između torke i liste?

3. visine = (198, 197, 198, 198, 203, 203, 210, 208, 213, 221, 213, 212)
   Šta će biti vrednosti  sledećih izraza:
   visine[2:6], visine[4:8], visine[5:], visine[0], visine[-3]



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:
    a2+ b2> c2 -oštrougli   a2+ b2= c2 -pravougli   a2+ b2 <  c2 - tupougli



четвртак, 23. април 2020.

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.