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

KONCENTRIČNI CIKLUSI

KONCENTRIČNI CIKLUSI

Ciklusi mogu da se kombinuju jedan sa drugim.

Najprostiji primer je kada treba odštampati brojeve:

11    12   13

21   22    23

31   32    33

Ovde možemo da primetimo da se drugi indeks menja brže od prvog, i to se može rešiti sa dve  ciklične for petlje:

for i=1 do 3

for j=1 do 3

prikaži (i,j);

Unutrašnja petlja se izvršava (“vrti”) brže od  spoljašnje. Dok je i=1, j promeni sve svoje vrednosti (ovde 1-3); i postaje 2, j opet promeni svoje vrednosti od 1 do 3; i postaje 3, j opet promeni svoje vrednosti od 1-3.

Ako u spoljašnjoj petlji i uzima vrednosti od 1-N, a j od 1-M,  naredbe  unutar petlji će se izvršiti N*M puta – u ovom slučaju 3*3=9 puta.

Koncentrični ciklusi mogu da budu kombinacija  sa drugim ciklusima. Najčešće se koriste kod rada sa matricama, ali i u drugim primerima.

Primer 1:

Naći sve parove prirodnih brojeva a i b, koji zadovoljavaju jednakost 2a^b − b = 1997

for a in range(1,12):

    for b in range(1,12):

        if 2*a**b-b==1997:

            print('a=',a,'b=',b)

U ovom zadatku vidimo da je do rešenja vrlo jednostavno doći računarom. Jednostavno izvrtimo sve kombinacije za a i b i vidimo za koju važi data jednakost. Jedina nedoumica je do koje granice postaviti ciklus.

Pošto nam na desnoj strani figuriše 1997, može se zaključiti da je 11 dovoljno jer je 2¹¹ već 2048.

Primer 2:

Naći cifre X i Y tako da važi jednakost:

X25Y+X11=X9YX

Izgleda kao razbijanje neke šifre, ali ovde znamo da X uzima vrednosti od 1 do 9 a Y od 0 do 9.

Uslov će biti da je 1000*X+2*100+5*10+Y+100*X …..itd

Ako malo sredimo izraz dobijamo da je 11*X-Y=71

for x in range(1,10):

    for y in range(0,10):

        if 11*x-y==71:

            print('x=',x,'y=',y)

Primer 3:

Naći sve trocifrene brojeve čiji je zbir cifara 7.

Ovde  nam ne trebaju cifre veće od 7, a cifra stotina s takođe kreće od 1.

for s in range(1,8):

    for d in range(0,8):

        for j in range(0,8):

            if s+d+j==7:

                print(100*s+10*d+j,end=' ')

Treba uočiti upotrebu opcionog argumenta end = ' ', koji specificira da se, posle

prikaza željenog teksta, ostane u istom redu (prazan tekst kao separator izmedu dva

ispisa), odnosno da će sledeći ispis započeti odmah do prethodnog. Ako se ovaj

argument izostavi,  kao u prethodnim zadacima, sledeći ispis započinje u novoj liniji.

Primer ispisa:

ZADACI ZA VEŽBU:

1. Izračunati aritmetičku sredinu cifara svakog trocifrenog broja.
2. U skupu celih brojeva rešiti jednačinu x² - x*y + y² = x²*y². (cikluse postaviti do 100)
3. Naći sve parove prirodnih brojeva (a, b) za koje važi 6a^b − b = 2055.

WHILE PETLJA (3)

REŠENJA I OBJAŠNJENJA ZADATAKA TREĆE VEŽBE

Zadaci treće lekcije ciklusa su se pokazali kao najlošije urađeni do sada, ne zbog težine nego zbog znatnog pada vaše koncentracije i nemilosrdnog korišćenja copy/paste opcije. Zato vas molim da dobro izanalizirate ova objašnjenja i uvidite greške koje ste napravili. Vrlo je važno da ovo naučite jer će nam ciklusi biti nephodan deo programa koje budemo radili.

1. Napisati program koji za dati prirodan broj n ispituje da li je stepen broja 3.

Uputstvo: Uslov za izvršavanje je da je broj deljiv sa 3

U ciklusu broj transformišemo u njegov količnik sa brojem tri

n=int(input("unesite n"))

while n%3==0:

    n=n//3

if n==1:

     print("Broj je stepen broja 3")

else:

     print("Broj nije stepen broja 3")

Dato vam je uputstvo kog se velika većina uopšte nije pridržavala. Najveća greška je bila, kao i u ostala dva zadatka, definisanja n kao float. Ako sam zadala da je broj deljiv sa 3, onda je po logici jasno da je broj ceo i koristimo celobrojno deljenje i ostatak. Znači n=n//3 Mnogi su imali n/3, n*(1/3) i slične konstrukcije. Objašnjavala sam da operacije sa realnim brojevima imaju određenu tačnost i razlikuju se od operacija sa celim brojevima. Npr. može se desiti da umesto 0 dobijemo rezultat 0.000001. Većina bi pomislila – možeš misliti razlike - ali ako je u pitanju radioaktivni uranijum, razlika je ogromna.

2.     Napisati program koji će iz niza brojeva nepoznate dužine izračunati posebno sumu parnih i  proizvod neparnih brojeva.

print('unesite broj, za kraj niza unesite nulu')

sp=0

pn=1

x=int(input('x='))

while x!=0:

    if x%2==0:

        sp=sp+x

    else:

        pn=pn*x

    x=int(input('x='))

print('proizvod neparnih',pn)

print('suma parnih',sp)

I u ovom zadatku masovno ste unosili x kao float, a onda ispitivali da li je paran.

3.     Odrediti najmanji broj uzastopnih  brojeva počevši od 1 čija je suma veća od  unetog broja N

Uputstvo: Uslov za izvršavanje je da je suma <=N

U ciklusu računamo sumu, uvećavamo broj za 1 i brojač za 1

n=int(input('unesite granicu'))

s=0

i=1

br=0

while s<=n:

    s=s+i

    br=br+1

    i=i+1

print('Ima',br,'sabiraka')

U ovom zadatku pitanje je bilo, ako npr. unesem broj 32, koliko najmanje brojeva saberem počevši od 1 da dobijem broj oko 32 ( tj. kad vrednost sume pređe datu granicu stajemo sa ciklusom)

Iako je u uputstvu naglašeno da je suma <=N, velika većina je pisala uslov da je i<=n što nema nikakvog smisla.

S=1+2+3+4+5+6+7 U ovom slučaju rezultat bi bio 7 sabiraka. Opet je velika većina kao rezultat navodila vrednost promenljive i koji nije tačan, jer se u ciklusu i još jednom uveća za jedan. Zato je trebalo uvesti brojač koji počinje od nule, kao u ovom rešenju, ili eventualno kao rezultat dati i-1.

Znači, zaključak je da treba dobro razmisliti o zadatku, rešiti ga, isprobati na nekolilo test-primera i videti da li korektno radi. Ako vam neko od drugova pošalje rešenja, ne uzeti ih zdravo za gotovo već uočiti greške, jer se većina ovih grešaka mogla videti pukim testiranjem.

DOMAĆI ZADATAK:

Pročitati lekciju o tipovima podataka za prvi razred, dobro će vam doći.

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.

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.

While petlja(2)

While petlja(2)

  

Primer 4: Za uneti broj x ispitati da li je prost.

prost=True

i=2

x=int(input('unesite x '))

n=round(x**(1/2))

while i<=n and prost:

    if x%i==0:

        prost=False

    i=i+1

if prost:

    print('broj je prost')

else:

    print('broj nije prost')

Postavljamo promenljivu prost na vrednost tačno jer nam je to jedan od uslova za izvršavanje ciklusa. Ovaj zadatak nam je ujedno i ilustracija rada sa konstantama i promenljivima logičkog tipa.

Da se podsetimo, broj je prost ako nije deljiv ni sa jednim brojem osim sa samim sobom.

Međutim, ciklus ne mora da se izvršava do vrednosti samog broja, već je dovoljno ići do korena. Ako broj do korena nema delilaca, neće ih imati ni nadalje. Pošto je za koren moguća realna vrednost, zaokružili smo ga na ceo sa round.

Uslov za while je da je mogući delilac i ( koji smo na početku stavili na dvojku) manji od korena i da je vrednost promenljive prost tačno.

U ciklusu ispitujemo da li je broj deljiv sa i. Ako jeste, broj automatski nije prost, tako da promenljiva prost dobija vrednost netačno i iz ciklusa se izlazi.

Ako nije, uvećavamo i za 1 i nastavljamo ispitivanje deljivosti.

Uglavnom, čim se u ciklusu pojavi neki delilac broja, završava se, jer broj tada nije prost.

Interesantna je izlazna if. Nema klasičnog uslova nego je stavljena samo promenljiva prost.

Ako joj je vrednost True broj je prost, a ako je False, broj nije prost.

Primer 5: Za uneti broj n prebrojati koliko ima cifara

n=int(input('unesite n '))

k=0

while n>0:

    n=n//10

    k=k+1

print('broj cifara je ',k)

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 6: Za uneti broj n ispitati da li je palindrom

n=int(input('unesite n '))

m=n

s=0

while m>0:

    s=s*10+m%10

    m=m//10

if s==n:

    print('Broj je palindrom')

else:

    print('Broj nije 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.

DOMAĆI ZADATAK:

Dobro proučiti ova tri primera i isprobati ih u Pajtonu. Pomoći će vam da shvatite i prethodna tri WHILE zadatka. Ko nije do sada uradio, neka uradi i pošalje prethodne domaće zadatke.

Srećni uskršnji praznici!

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! 

While petlja ( 1 )

While petlja ( 1 )

While petlja je programska struktura koja ima istu namenu kao i for petlja.To znači da while petlja isto omogućava ponavljanje određenog bloka naredbi. Naravno, razlika između ove petlje i for petlje je u tome što while petlja ne sadrži brojač koji sadrži for petlja. Brojač for petlji omogućava određivanje  broja ponavljanja nekog bloka naredbi. While petlja nema brojač, ali kao i for petlja ima uslov. Taj uslov joj omogućava da se izvršavaju naredbe. Tako dugo dok je uslov ispunjen ponavljaj blok naredbi. Ako uslov nije ispunjen, nemoj ponavljati taj blok naredbi. Tako bismo mogli prevesti funkcionalnost while petlje.

While petlja je vrlo jednostavna petlja koja omogućava ponavljanje kada je određeni uslov ispunjen. Uslov u while petlji može biti određen: relacionim operatorima, logičkim operatorima i aritmetičkim operatorima.

Primer 1.

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

n=int(input('unesite broj'))

while n%10==0:

      n=n//10

print(n)

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 funkcije e^x , eksponencijalne funkcije o kojoj puno slušamo za vreme ove epidemije virusa Korona.

x=int(input('unesite x '))

tac=float(input('unesite tacnost '))

s=0

i=1

a=1 #prvi clan sume

while a>=tac:

    s=s+a

    a=a*x/i #tekuci clan sume

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

    i=i+1

print('s=',s)

Primer ispisa:

unesite x 1

unesite tacnost 1E-20

s= 2.7182818284590455

>>> 

Pošto je uneta  velika tačnost dobijamo broj e na 16 tačnih decimala.

Primer 3:

Napisati program koji će iz niza brojeva nepoznate dužine izračunati posebno sume pozitivnih i negativnih brojeva.

Pošto ne znamo koliko ima brojeva, unosićemo brojeve dok se ne unese vrednost koja označava kraj. U ovom slučaju, završetak niza brojeva može biti nula, jer ona svakako ne utiče na rezultat. Znači da će nam uslov za izvršavanje ciklusa biti da uneti broj nije nula.

sp=0

sn=0

print('unesite broj, za kraj niza unesite nulu')

x=float(input('unesite x '))

while x!=0:

    if x<0:

        sn=sn+x

    else:

        sp=sp+x

    x=float(input('unesite x '))

print('suma pozitivnih',sp)   

print('suma negativnih',sn)

ZADACI ZA VEŽBU:

1.     Napisati program koji za dati prirodan broj n ispituje da li je stepen broja 3.

Uputstvo: Uslov za izvršavanje je da je broj deljiv sa 3

U ciklusu broj transformišemo u njegov količnik sa brojem tri

2.     Napisati program koji će iz niza brojeva nepoznate dužine izračunati posebno sumu parnih i  proizvod neparnih brojeva.

3.     Odrediti najmanji broj uzastopnih  brojeva počevši od 1 čija je suma veća od  unetog broja N

Uputstvo: Uslov za izvršavanje je da je suma <=N

U ciklusu računamo sumu, uvećavamo broj za 1 i brojač za 1