Algoritmi

Algoritam je konačan uređen niz precizno formulisanih pravila  kojima se rešava jedan problem  ili čitava klasa problema.

Algoritam može biti napisan na jeziku ljudske komunikacije, ali može nastati problem kod složenijih problema gde bi takav algoritam postao težak za tumačenje.

Teško tumačenje složenih tekstualnih algoritama dovelo je do grafičkog prikaza algoritma. U tu svrhu koristi se niz grafičkih simbola za pojedine algoritamske  korake.

Algoritamske strukture:

  • Linijski algoritmi su oni kod kojih se naredbe  izvršavaju sekvencijalno jedna za drugom.
  • Razgranati algoritmi su oni kod kojih se u zavisnosti  od ispunjenosti  uslova program  nastavlja jednom od dve grane
  • Ciklični algoritmi sadrže niz instrukcija koje se ponavljaju više  puta.

PROGRAMSKI JEZIK PASCAL

Programski jezik Pascalje viši programski jezik kojeg je kreirao  švajcarski matematičar Niklaus Wirth. Sređena  verzija  Pascala  predstavljena  je 1974. godine u knjizi Jensen, K&Wirth N:”Pascal user manual and report“, Springer – Verlag, New York,1974.

Pascal je  nastao kao programski jezik za učenje principa programiranja.

Firma Borland je proizvela seriju Turbo Pascal  proizvoda koji su poslužili kao osnova za razvoj objektno orijentisanog programskog jezika za projektovanje aplikacija  pod nazivom Delphi.

Simboli  pascal-a

SLOVA

engleski alfabet: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, R, S, T, U, V, W, X, Y, Z, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, r, s, t, u, v, w, x, y, z,

CIFRE: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

SPECIJALNI ZNACI: + – * / = < > [ ] . , ; : ^ ( ) ‘ { } znak za prazninu, znak za enter, znak za tabulaciju, itd.

REZERVISANE REČI

and, array, begin, case, const, div, downtt, do, else, end, file, for, function, goto, if, in, label, mod, nil, not, of, or, procedure, program, record, repeat, set, then, to, type, until, var, while, with.

Rezervisane reči imaju uvek isto značenje.

IMENA ILI IDENTIFIKATORI

Imena ili identifikatori se koriste za označavanje osnovnih objekata jezika: promenjivih, konstanti, tipova, funkcija i procedura.

Ime u Pascal-u može biti sastavljeno samo od brojeva i slova. PRVI ZNAK MORA BITI SLOVO.. Za ime se ne sme koristiti znak za prazninu koja može biti zamenjena podvučenom crtom. Ne sme da se koriste rezervisane reči, ni standardna imena koja se koriste za označavanje standardnih funkcija (abs, sin, cos, sqr, trunc…) i za standardnih  tipova podataka (integer, real, string…).

Primeri:

ispravno: x ,  x1,  broj,   broj_prvi,   br3333

neispravno: 3b,    broj-1,   real,     array,     x+y

BROJEVI

U Pascal-u se koristi dekadni zapis za predstavljanje brojeva koji mogu biti celi i realni. Kod pozitivnog broja se može izostaviti znak +.

Celi brojevi: niz cifara ispred kojeg može da stoji znak + ili -. Npr +2,3,-456…

Realni brojevi: kod predstavljanja realnog broja može da se koristi zapis sa fiksnom decimalnom tačkom ili sa pokretnom decimalnom tačkom.

Fiksna decimalna tačka: 4.23, -0.234, 0.7

Realni brojevi sa fiksnom tačkomse sastoje od celog dela, razlomljenog dela (decimale) i tačke koja ih razdvaja. Zapis ne sme da počinje i da se završava decimalnom tačkom.

Pokretna decimalna tačka: 1.5E9      3.5E-6 -0.5E4

Simbol E se čita “pomnožiti sa 10 na”, a  koji je stepen u pitanju predstavlja broj  iza E. Npr. E2 znači 102,  E-2 znači 10-2 i sl. Ovaj zapis se koristi za vrlo male ili vrlo velike brojeve.

Primeri:

2.3E5 2.3*105=230000   23E4
0.2E-4 0.2*10-4 =0.00002     2E-5
123.55E6 123.55*106 =123550000    1.2355E8
0.5E-10 0.5*10-10 =0.00000000005     5E-11
-1.6E2 -160

SEPARATOR

Separator ima ulogu da pokaže gde je kraj jedne naredbe i početak sledeće. Ulogu separatora u Pascal-u ima ;

KOMENTAR

Komentar se piše radi bolje razumljivosti programa. Može se pisati bilo gde u programu i ni na koji način ne utiče na tok programa. Komentar se piše u velikim zagradama { , } ili (* , *).

APSTRAKCIJE PODATAKA I PROSTI TIPOVI PODATAKA

Pod tipom podataka se podrazumeva  skup vrednosti koje može dobti neka promenljiva  i skup operacija  dozvoljenih  nad datom promenljivom. Svaka promenljiva se definiše tipom.

Tipovi podataka mogu biti

  • Prosti (skalarni ili standardni) : celobrojni (integer), realni (real), logički (boolean) i znakovni (char)
  • Složeni (strukturirani)

Prosti tipovi se ne mogu razlagati na elementarnije tipove i predstavljaju osnovu za građenje složenih tipova.

Celobrojni tip podataka (integer)

Celobrojni tip je podskup skupa celih brojeva.

Skup celih brojeva je skup koji obuhvata sve prirodne brojeve, nulu (0), kao sve negativne brojeve (prirodni brojevi sa predznakom -). Celi brojevi ne smeju imati decimalni nastavak. Svii prirodni brojevi se nazivaju pozitivni celi brojevi, 0 je neutralan broj, a brojevi manji od 0 se zovu negativni celii brojevi. Negativni brojevi imaju ispred predznak minus (-) i oni su manji od 0. Pozitivni brojevi imaju predznak plus(+), koji se ne piše i oni su uvijek veći od 0.

Operacije:

1) sabiranje (+)

2) oduzimanje (-)

3) množenje (*)

4) DIV (celobrojno deljenje)

5) MOD (ostatak celobrojnog deljenja)

Funkcije:

Sqr(x)  – kvadrat broja x

Abs(x) – apsolutna vrednost

Succ(x)-sledbenik broja x

pred(x) –predhodnik broja x

Relacije:

=, <, >,<= (manje ili jednako), >= (veće lili jednako), <> (različito)

Realni tip podataka (real)

Podskup skupa realnih brojeva.

Operacije nad realnim operandima koje daju relan rezultat:

  1. Množenje (*)
  2. Deljenje( /)
  3. Sabiranje (+)
  4. Oduzimanje (-)

U ovim operacijama jedan operand može biti ceo broj. Ako je izraz sastavljen od celobrojnih i realnih vrednosti, rezultat je realan broj.

Funkcije

  • koje daju realne vrednosti:
    • Abs(x)
    • sqr(x)
    • sin(x)
    • cos(x)
    • arctan(x)
    • ln(x)
    • exp(x)
    • sqrt(x)
    • Frac(x) vraća razljomeni deo x;  frac(1.23)=0.23
  • koje daju celobrojne vrednosti:
    • Trunc(x) -izdvaja celobrojni deo realnog broja

trunc(3.236)=3    trunc(-1.15)=-1

    • Round(x)- matematičko zaokruživanje

round(4.678)=5    round(-5.35)=-5

LINIJSKE STRUKTURE

Kod proste linijske algoritamske strukture naredbe se izvršavaju jedna iza druge onim redom kako su napisane, bez grananja, ponavljanja itd.

Primer1. Napisati algoritam i program koji će sabrati 2 uneta broja.

Plan:

Ulazne (poznate vrednosti) – 2 broja npr. a,b.

Obrazac za računanje:     c=a+b

Izlazna vrednost: c

Program sabiranje;

VAR a,b,c:integer;

BEGIN

writeln(‘sabiranje’);

writeln(‘unesi dva broja’);

readln(a,b);

c:=a+b;

writeln(‘c=’,c);

END.

 

Primer2. Napisati algoritam i program koji će izračunati prosečnu ocenu ako se  unose  ocene sa pismenog zadatka, kontrolne vežbe i usmenog odgovora iz matematike

Program prosek;

VAR pz,kv,uo:integer;

BEGIN

writeln(‘prosečna ocena iz matematike’);

writeln(‘unesi ocenu sa pismenog zadatka’);

readln(pz);

writeln(‘unesi ocenu sa kontrolne vezbe’);

readln(kv);

writeln(‘unesi ocenu sa usmenog odgovora’);

readln(uo);

po:=(pz+kv+uo)/3

writeln(‘po=’,po);

END.

 

Možete primetiti da je struktura algoritma u oba primera ista. Suština je da u problemu uočite ulazne (poznate) vrednosti,  obrazac za izračunavanje i izlazne vrednosti.

Primer3. Data je površina pravougaonika i stranica a.  Izračunati obim i dijagonalu.

U ovom primeru, pre izračunavanja izlaznih vrednosti potrebno je izračunati  stranicu b koja nam je potrebna za izračunavanje  dijagonale i obima pravougaonika.

Program pravougaonik;

VAR      p,a,o:integer;   d:real;

BEGIN

writeln(‘pravougaonik ’);

writeln(‘Unesi površinu i stranicu a’);

readln(p,a);

b:=p/a;

O:=2*a+2*b;

d:=sqrt(sqr(a)+sqr(b));

writeln(‘O=’,O);

writeln(‘d=’,d:5:2);

end.

Očigledno je da je  redosled izvršavanja operacija  bitan. Stranica b mora da se izračuna pre obima i dijagonale jer se koristi za njihovo izračunavanje.

Pascal ne pravi  razliku između malih i velikih slova tako da nije greška to što u deklaraciji stoji malo  slovo o a u opisu algoritma veliko.

Dokumenti  sa zadacima za vežbu:

RAZGRANATE STRUKTURE

Naredba IF

Jednostruki izbor podrazumeva da računar prvo proverava vrednost logičkog izraza (uslova), a zatim ako je izraz istinit izvršava određenu naredbu. Ako usov  nije ispunjen naredba se ne izvršava, već se izvodi naredna naredba u programu.

U pascalu jednostruki izbor je predstavljen pomoću naredbe IF  koja je oblika:

IF uslov THEN

Naredba;

 

Naredba IF ima još jedan oblik:

IF uslov THEN

Naredba1

ELSE

Naredba2;

Ako je uslov ispunjen (tačan) izvršava se naredba1, a ako nije ispunjen (netačan) izvršava se naredba2.

Primer1. NAIP koji će učitati ceo broj. Ispitati da li je broj koji je unet manji od 100  ili nije.

Program prviif;

Var x:integer;

BEGIN

If x<100 then

Writeln(‘Broj nije veci od 100’)

Else

Writeln(‘Broj je veci od 100’);

END.

Crveno je označena naredba IF. Pre ELSE se NIKAD ne stavlja ; jer tu nije kraj IF naredbe.

Dokumenti sa zadacima za vežbanje:

NAREDBE CIKLUSA

Ponavljanje bloka naredbi više puta omogućen je naredbama ciklusa  (naredbama ponavljanja ili repetativnim naredbama ili petljama).

U Pascalu postoje tri naredbe ciklusa:

  • FOR – bezuslovna naredba ciklusa.
  • WHILE- naredba sa preduslovom
  • REPEAT – naredba sa postuslovom.

FOR..TO..DO

i – brojačka (kontrolna)  promenljiva

pv – početna vrednost

kv – konačna vrednost

N – naredba

FOR i:=pv  TO kv  DO N;

„Sve dok  promenljiva i prima vrednost od početne vrednosti  do konačne vrednosti  izvršava se naredba N.“

Kontrolna (brojačka)  promenljiva odbrojava broj prolaza kroz petlju menjajući se od početne do konačne vrednosti s jediničnim korakom. Kontrolna promenljiva mora biti prethodno deklarisana i može biti  CHAR, BOOLEAN, INTEGER ili neki intervalni tip. Tip vrednosti početne, konačne vrednsti i kontrolne promenljive  moraju se slagati.

Vrednost kontrolne promenljive nije dopušteno menjati unutar FOR naredbe.

Koraci izvršenja naredbe for:

  1. Kontrolnoj promenljivoj i dodeljuje se početna vrednost
  2. Ako je i>kv završava se izvršenje naredbe FOR
  3. ako je i<=kv, izvršava se naredba N
  4. Kontrolna promenljiva prima vrednost za svog sledbenika (ako je u pitanju celobrojna vrednost za jedan veću od prethodne)     i:=succ(i)
  5. Nastavlja se izvršenje petlje od tačke 2

FOR naredba može imati oblik:

FOR  i:=pv DOWNTO kv DO N;

U ovom slučaju koraci izvršenja naredbe izgledaju ovako:

  1. Kontrolnoj promenljivoj i dodeljuje se početna vrednost
  2. Ako je i<kv završava se izvršenje naredbe FOR
  3. ako je i>kv, izvršava se naredba N
  4. Kontrolna promenljiva prima vrednost za svog prethodnika (ako je u pitanju celobrojna vrednost za jedan manju od prethodne)     i:=pred(i)
  5. Nastavlja se izvršenje petlje od tačke 2

Primer 1.Sastaviti algoritam i program koji će naći zbir prvih n prirodnih brojeva.

Program prviFor;

Var n,s,i:integer;

BEGIN

Writeln(‘do kog broja sabiramo’);

Readln(n);

S:=0; {S prima vrednost nula. To je početna vrednost koja se upisuje u memorijsku lokacijuna adresi s, da bi donji izraz S:=S+i imao smisla u prvom koraku kada je i=1}

FOR i:=1 TO n DO

S:=S+i; {Na staru vrednost promenljive s dodaje se trenutna vrednost kontrolne promenljive i }

Writeln (‘S=’,S);     Readln;

END.

 

… nastavak sledi

Preuzmite rešene zadatke:

reseni zadaci 1

Jednodimenzionalni nizovi

Pogledajte prezentaciju sa objašnjenjem jednodimenzionalnih nizova:  Nizovi 

Preuzmite zadatke za vežbanje:

Jednodimenzionalni nizovi

nizovi vežbe

Advertisements