skripta-spa1-sadrzaj.tex

   1 % skripta-spa1-sadrzaj.tex
   2 % Skripta za predmet Strukture podataka i algoritmi 1, DMI, PMF, NS
   3 % ovaj fajl sadrzi glavni sadrzaj skripte koji se ukljucuje u jedan
   4 % od pomocnih fajlova koji ce primeniti adekvatna formatiranja,
   5 % npr za jednu ili dve kolone
   6
   7 % osnovne informacije koje ce se prikazati na naslovnoj strani,
   8 % kao i u informacijama u generisanom pdfu
   9 \newcommand{\autor}{Vladimir Kurbalija, Milos Radovanovic, Doni Pracner}
  10 \newcommand{\naslov}{Skripta za vezbe iz predmeta "Strukture podataka
  11   i algoritmi 1"}
  12 \newcommand{\datum}{Februar 2014, Novi Sad}
  13 \newcommand{\verzija}{ver 14a-\varijacija}
  14 %varijacija je definisana u fajlu koji ukljucuje ovaj
  15
  16 \title{\naslov -- \verzija}
  17 \author{\autor}
  18 \date{\datum}
  19
  20 %change the default font
  21 \usepackage{lmodern}
  22 \usepackage{beramono}
  23 \renewcommand{\familydefault}{\sfdefault}
  24
  25 \usepackage{pifont}
  26
  27 %podesavanja outputa za pdf verzije
  28 \usepackage[bookmarks,pdffitwindow=false,unicode=true,%
  29 pdftitle={\naslov -- \verzija},%
  30 pdfauthor={\autor}%
  31 ]{hyperref}
  32
  33 \usepackage{graphicx}
  34 \usepackage{listings}
  35 \usepackage{amsthm}
  36 \usepackage{amsmath}
  37 \usepackage{latexsym}
  38 \usepackage{multicol}
  39
  40 \begin{document}
  41
  42 %customize the itemize environments
  43
  44 \let\olditemize=\itemize
  45 \def\itemize{
  46 \olditemize
  47   \setlength{\itemsep}{1pt}
  48   \setlength{\parskip}{0pt}
  49   \setlength{\parsep}{0pt}
  50   \setlength{\topsep}{-1cm}
  51   \setlength{\partopsep}{1pt}
  52 }
  53
  54 %% specijalni blokovi koji služe kao podsetnici u radu ili napomene
  55 \newcommand{\skica}[1]{
  56     \noindent \framebox{\parbox[c]{0.9\textwidth}{  {\small** \textit{#1}  }}
  57     \newline }
  58 }
  59
  60 \newcommand{\skicas}[1]{
  61     \framebox{* \textit{#1} *}
  62 }
  63
  64 %boldovane skice visokog prioriteta
  65 \newcommand{\skicab}[1]{
  66   \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small***
  67         \textbf{#1} }} \newline } }
  68
  69 \newcommand{\kod}[1]{{\small\texttt{#1}}}
  70
  71 % ako je sledeci red odkomentarisan nista od skica nece biti ispisano
  72 % u finalni dokument
  73
  74 % \renewcommand{\skica}[1]{}
  75
  76 % title u skladu sa uobičajenim na Departmanu
  77 \newcommand{\makemytitle}{
  78   \begin{center}
  79         \makebox{%
  80         \includegraphics[width=2cm]{grbPMF}
  81         \parbox[b]{65ex}{\centering
  82                 Univerzitet u Novom Sadu\\
  83                 Prirodno-matematički fakultet\\
  84                 Departman za matematiku i informatiku}
  85         \includegraphics[width=2cm]{grbUNS}
  86         }
  87         \vspace{10ex}
  88
  89         \parbox[b]{\textwidth}{{\Large {\bf
  90               Vladimir Kurbalija, \href{mailto:kurba@dmi.rs}{kurba@dmi.rs}\\
  91               Miloš Radovanović, \href{mailto:radacha@dmi.rs}{radacha@dmi.rs}\\
  92               Doni Pracner, \href{mailto:doni.pracner@dmi.rs}{doni.pracner@dmi.rs}}}}
  93         \vspace{15ex}
  94
  95         {\Large {\bf Skripta za vežbe iz predmeta }}
  96
  97         {\Huge {\bf
  98             \setlength{\baselineskip}{1.5\baselineskip}Strukture
  99               podataka i algoritmi 1}}
 100
 101         \vspace{5ex}
 102         %\vfill
 103
 104         \verzija \ -- \datum
 105
 106         \end{center}
 107         \thispagestyle{plain}
 108 %       \newpage
 109 }
 110
 111 \makemytitle
 112
 113 % theorems, definition etc.
 114 %''''''''''''''''''''''''''
 115
 116 \theoremstyle{definition}
 117 \newtheorem{def1}{Definicija}
 118 \theoremstyle{plain}
 119 \newtheorem{theo}{Teorema}
 120 \newtheorem{lema}{Lema}
 121
 122 \lstloadlanguages{Modula-2}
 123
 124 \lstset{
 125         basicstyle=\footnotesize\ttfamily,
 126         showstringspaces=false,
 127         breaklines=true
 128 }
 129
 130 \lstdefinestyle{codeblock}{
 131         basicstyle=\footnotesize\ttfamily,
 132         keywordstyle=\textbf,
 133         columns=[l]fixed,
 134         breakatwhitespace=true,
 135 %        prebreak=\P,
 136 %        postbreak=\ding{229}\space,
 137         language=Modula-2
 138 }
 139
 140 \lstdefinestyle{numcodeblock}{
 141   style=codeblock,
 142   numbers=left
 143 }
 144
 145 \lstnewenvironment{codeblock}{\lstset{style=codeblock}}{}
 146
 147
 148 % ----------------==================--------------------------------------
 149 %                 Pravi pocetak rada
 150
 151 \vfill
 152
 153 Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula
 154 2'. Za verzije pre 2.60 je neophodno dodatno instalirati i TSCP (Top
 155 Speed Compatibility Pack), pošto je potreban za neke od modula koji se
 156 ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi
 157 moduli uključeni u standardnu instalaciju.
 158
 159 Sav sadržaj se može koristiti u skladu sa {\ttfamily CC-BY-NC-SA} licencom. \\
 160 \url{http://creativecommons.org/licenses/by-nc-sa/3.0/}
 161
 162 \newpage
 163
 164 \tableofcontents
 165
 166 \mainstart
 167
 168 \sectionbreak
 169
 170 \section{Ilustracija efikasnosti algoritma}
 171
 172 \subsection{Zadatak: Pronaći sve pitagorine
 173 trojke do zadate granice}
 174
 175 Pitagorina trojka su tri broja $a,b,c$ za koje važi $a^2 + b^2 = c^2\\$
 176
 177 \begin{lstlisting}[style=codeblock]
 178 MODULE Trojke1;
 179 (* Pitagorine trojke koriscenjem "Brute-force" *)
 180 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 181 CONST
 182   Gr = 100;
 183 VAR
 184   a, b, c : [1 .. Gr];
 185 BEGIN
 186   FOR a := 1 TO Gr DO
 187     FOR b := 1 TO Gr DO
 188       FOR c := 1 TO Gr DO
 189         IF a*a + b*b = c*c THEN
 190           WriteLn;
 191           WriteString('a = ');
 192           WriteCard(a,2);
 193           WriteString(', b = ');
 194           WriteCard(b,2);
 195           WriteString(', c = ');
 196           WriteCard(c,2)
 197         END
 198       END
 199     END
 200   END
 201 END Trojke1.
 202 \end{lstlisting}
 203
 204 \begin{codeblock}
 205 MODULE Trojke2;
 206 (*Pitagorine trojke koriscenjem zaokrugljivanja*)
 207 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 208 FROM MathLib0 IMPORT sqrt;
 209 CONST
 210   Gr = 100;
 211 VAR
 212   a, b, c : CARDINAL;
 213   creal : REAL;
 214 BEGIN
 215   FOR a := 1 TO Gr DO
 216     FOR b := 1 TO Gr DO
 217       creal := FLOAT(a*a) + FLOAT(b*b);
 218       creal := sqrt(creal);
 219       c := TRUNC(creal);
 220       IF creal = FLOAT(c) THEN
 221         WriteLn;
 222         WriteString(' a = ');
 223         WriteCard(a,2);
 224         WriteString(', b = ');
 225         WriteCard(b,2);
 226         WriteString(', c = ');
 227         WriteCard(c,2)
 228       END
 229     END
 230   END
 231 END Trojke2.
 232 \end{codeblock}
 233
 234 Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup.
 235 Ako uzmemo neka dva prirodna broja $m$ i $n$, tada se iz njih može
 236 izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove:
 237 \[
 238 \begin{array}{l}
 239 a = 2mn\\
 240 b = m^2 - n^2\\
 241 c = m^2 + n^2
 242 \end{array}
 243 \]
 244 Odnosno kad probamo da proverimo da li je ovo
 245 Pitagorina trojka dobijamo:
 246 \[
 247 \begin{array}{r@=l}
 248 a^2 + b^2 & c^2\\
 249 (2mn)^2 + (m^2 - n^2)^2 & (m^2 + n^2)^2
 250 \end{array}
 251 \]
 252
 253 \manbreakJK
 254 \begin{codeblock}
 255 MODULE Trojke3;
 256 (* Pitagorine trojke koriscenjem teoreme *)
 257 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 258 CONST
 259   Gr = 10;
 260 VAR
 261   a, b, c, m, n : CARDINAL;
 262 BEGIN
 263   FOR m := 1 TO Gr DO
 264     FOR n := 1 TO m-1 DO
 265       a := 2*m*n;
 266       b := m*m - n*n;
 267       c := m*m + n*n;
 268       WriteLn;
 269       WriteString('a = ');
 270       WriteCard(a,2);
 271       WriteString(', b = ');
 272       WriteCard(b,2);
 273       WriteString(', c = ');
 274       WriteCard(c,2)
 275     END
 276   END
 277 END Trojke3.
 278 \end{codeblock}
 279
 280 Sledeća dva metoda traže trojke sa nekim specifičnim osobinama.
 281
 282 \begin{codeblock}
 283 MODULE Trojke4;
 284 (* Pitagorine trojke kod kojih je razlika
 285    izmedju katete i hipotenuze tacno 1 *)
 286 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 287 CONST
 288   Gr = 10;
 289 VAR
 290   a, b, c, m, n : CARDINAL;
 291 BEGIN
 292   FOR m := 2 TO Gr DO
 293     n := m - 1;
 294     a := 2*m*n;
 295     b := m*m - n*n;
 296     c := m*m + n*n;
 297     WriteLn;
 298     WriteString('a = ');
 299     WriteCard(a,2);
 300     WriteString(', b = ');
 301     WriteCard(b,2);
 302     WriteString(', c = ');
 303     WriteCard(c,2)
 304   END
 305 END Trojke4.
 306 \end{codeblock}
 307
 308 \begin{lstlisting}[style=codeblock]
 309 MODULE Trojke5;
 310 (* Pitagorine trojke kod kojih je razlika
 311    izmedju kateta jedan *)
 312 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 313 CONST
 314   Gr = 7;
 315 VAR
 316   a, b, c, m, n, w, i, temp : CARDINAL;
 317 BEGIN
 318   w := 1;
 319   n := 0;
 320   FOR i := 1 TO Gr DO
 321     m := n + w;
 322     a := 2*m*n;
 323     b := m*m - n*n;
 324     c := m*m + n*n;
 325     WriteLn;
 326     WriteString('a = ');
 327     WriteCard(a,2);
 328     WriteString(', b = ');
 329     WriteCard(b,2);
 330     WriteString(', c = ');
 331     WriteCard(c,2);
 332     temp := w;
 333     w := 3*w + 4*n;
 334     n := 2*temp + 3*n
 335   END
 336 END Trojke5.
 337 \end{lstlisting}
 338
 339 \subsection[Zadatak: Maksimalna suma susednih elemenata u
 340 nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u
 341   nizu celih brojeva}
 342
 343 \begin{lstlisting}[style=codeblock]
 344 MODULE MaxNiza1;
 345 (* Prvo resenje. Brute Force: O(n^3)  *)
 346 FROM InOut IMPORT WriteString,ReadInt,
 347            WriteInt,WriteCard,WriteLn;
 348 CONST
 349   N = 10;
 350 TYPE
 351   Interval = [1..N];
 352 VAR
 353   Max, Suma : INTEGER;
 354   d,g,i,Ood,Doo : Interval;
 355   X : ARRAY Interval OF INTEGER;
 356 BEGIN
 357   WriteString(' Unesite niz X ');
 358   WriteLn;
 359   FOR i := 1 TO N DO
 360     ReadInt(X[i]);
 361     WriteLn
 362   END;
 363   Max := 0;
 364   FOR d := 1 TO N DO
 365     FOR g := 1 TO N DO
 366       Suma := 0;
 367       FOR i := d TO g DO
 368         Suma := Suma + X[i]
 369       END;
 370       IF Suma > Max THEN
 371         Max := Suma;
 372         Ood := d;
 373         Doo := g
 374       END
 375     END
 376   END;
 377   WriteLn;
 378   WriteString(' Maksimum je ');
 379   WriteInt(Max,3);
 380   WriteString(' u intervalu od ');
 381   WriteCard(Ood,3);
 382   WriteString(' do ');
 383   WriteCard(Doo,3)
 384 END MaxNiza1.
 385
 386 MODULE MaxNiza2;
 387 (* Drugo resenje: O(n^2).
 388    Koristi se cinjenica da je suma X[d..g]
 389    izracunljiva iz X[d..g-1].  *)
 390 FROM InOut IMPORT WriteString,ReadInt,
 391            WriteInt,WriteCard,WriteLn;
 392 CONST
 393   N = 10;
 394 TYPE
 395   Interval = [1..N];
 396 VAR
 397   Max, Suma : INTEGER;
 398   d,g,i,Ood,Doo : Interval;
 399   X : ARRAY Interval OF INTEGER;
 400 BEGIN
 401   WriteString(' Unesite niz X ');
 402   WriteLn;
 403   FOR i := 1 TO N DO
 404     ReadInt(X[i]);
 405     WriteLn
 406   END;
 407   Max := 0;
 408   FOR d := 1 TO N DO
 409     Suma := 0;
 410     FOR g := d TO N DO
 411       Suma := Suma + X[g];
 412       IF Suma > Max THEN
 413         Max := Suma;
 414         Ood := d;
 415         Doo := g
 416       END
 417     END
 418   END;
 419   WriteLn;
 420   WriteString(' Maksimum je ');
 421   WriteInt(Max,3);
 422   WriteString(' u intervalu od ');
 423   WriteCard(Ood,3);
 424   WriteString(' do ');
 425   WriteCard(Doo,3)
 426 END MaxNiza2.
 427 \end{lstlisting}
 428
 429 \begin{codeblock}
 430 MODULE MaxNiza3;
 431 (* Trece resenje: O(n^2).
 432    Koristi pomocni niz u kome je na i-tom mestu
 433    suma podniza x[1..i] *)
 434 FROM InOut IMPORT WriteString,ReadInt,
 435            WriteInt,WriteCard,WriteLn;
 436 CONST
 437   N = 10;
 438 TYPE
 439   Interval = [1..N];
 440 VAR
 441   Max, Suma : INTEGER;
 442   d,g,i,Ood,Doo : Interval;
 443   X : ARRAY Interval OF INTEGER;
 444   Pom : ARRAY [0..N] OF INTEGER;
 445 BEGIN
 446   WriteString(' Unesite niz X ');
 447   WriteLn;
 448   FOR i := 1 TO N DO
 449     ReadInt(X[i]);
 450     WriteLn
 451   END;
 452   Pom[0] := 0;
 453   FOR i := 1 TO N DO
 454     Pom[i] := Pom[i-1] + X[i]
 455   END;
 456   Max := 0;
 457   FOR d := 1 TO N DO
 458     FOR g := d TO N DO
 459       Suma := Pom[g] - Pom[d-1];
 460       IF Suma > Max THEN
 461         Max := Suma;
 462         Ood := d;
 463         Doo := g
 464       END
 465     END
 466   END;
 467   WriteLn;
 468   WriteString(' Maksimum je ');
 469   WriteInt(Max,3);
 470   WriteString(' u intervalu od ');
 471   WriteCard(Ood,3);
 472   WriteString(' do ');
 473   WriteCard(Doo,3)
 474 END MaxNiza3.
 475 \end{codeblock}
 476
 477 \begin{codeblock}
 478 MODULE MaxNiza4;
 479 (* Cetvrto resenje. Najbolje moguce: O(n)  *)
 480 FROM InOut IMPORT WriteString,ReadInt,
 481            WriteInt,WriteCard,WriteLn;
 482 CONST
 483   N = 10;
 484 TYPE
 485   Interval = [1..N];
 486 VAR
 487   Max, MaxDovde : INTEGER;
 488   i,d,Ood,Doo : Interval;
 489   X : ARRAY Interval OF INTEGER;
 490 BEGIN
 491   WriteString(' Unesite niz X ');
 492   WriteLn;
 493   FOR i := 1 TO N DO
 494     ReadInt(X[i]);
 495     WriteLn
 496   END;
 497   Max := 0;
 498   MaxDovde := 0;
 499   FOR i := 1 TO N DO
 500     IF MaxDovde = 0 THEN
 501       d := i
 502     END;
 503     MaxDovde := MaxDovde + X[i];
 504     IF MaxDovde < 0 THEN
 505       MaxDovde := 0
 506     END;
 507     IF MaxDovde > Max THEN
 508       Ood := d;
 509       Doo := i;
 510       Max := MaxDovde
 511     END
 512   END;
 513   WriteLn;
 514   WriteString(' Maksimum je ');
 515   WriteInt(Max,3);
 516   WriteString(' u intervalu od ');
 517   WriteCard(Ood,3);
 518   WriteString(' do ');
 519   WriteCard(Doo,3)
 520 END MaxNiza4.
 521 \end{codeblock}
 522
 523 \sectionbreak
 524 \section{Stringovi}
 525
 526
 527 Stringovi -- odnosno nizovi znakova -- ne postoje kao ugrađeni tip u
 528 jeziku Modula 2. Ovo daje slobodu da se niz znakova definiše na dužinu
 529 najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr:
 530 \begin{codeblock}
 531   TYPE
 532      String = ARRAY [1..30] OF CHAR;
 533 \end{codeblock}
 534
 535 Operacije nad stringovima se najčešće uvoze iz modula \kod{Str}. One
 536 sve prihvataju \emph{otvorene nizove znakova} (strukture definisane sa
 537 \kod{ARRAY OF CHAR}), tako da im se može proslediti niz proizvoljne
 538 dužine.
 539
 540 Određivanje stvarne dužine stringa (tj koliko od maksimalnog
 541 kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na
 542 sledeći način:
 543 \begin{codeblock}
 544      duzina := Length(str)
 545 \end{codeblock}
 546
 547 Leksikografsko poređenje dva stringa se ne može vršiti standardnim
 548 operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o
 549 nizovima, a delom i zato što se ne vidi direktno koji deo niza je
 550 popunjen stvarnim sadržajem. Za ovo se koristi komanda \kod{Compare},
 551 koja prihvata dva stringa kao parametre, a vraća broj koji predstavlja
 552 njihov odnos. Taj broj će biti 0 ako su stringovi jednaki, veći
 553 od nule ako je prvi string ``veći'', i manji od nule ako je prvi
 554 string ``manji''. Ovo se lako pamti kad primetimo da je odnos
 555 između \kod{Compare} i 0 isti kao i između prvog i drugog stringa.
 556
 557 \begin{codeblock}
 558   IF    Compare(str1, str2) > 0 THEN
 559      WriteString("Prvi string je veci");
 560   ELSIF Compare(str1, str2) < 0 THEN
 561      WriteString("Prvi string je manji");
 562   ELSE (* moraju biti jednaki *)
 563      WriteString("Jednaki su");
 564   END;
 565 \end{codeblock}
 566
 567 Postoji i modul \kod{Strings} koji ima nešto drugačije definisane
 568 procedure, no na njih se sada nećemo fokusirati.
 569
 570 \sectionbreak
 571 \section{Rad sa fajlovima}
 572
 573 \subsection{Modul FIO}
 574
 575 U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
 576 sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
 577 kao što uvozimo i komande).
 578
 579 \emph{U primerima se pretpostavlja da je ``f'' tipa \kod{File},
 580   ``str'' niz znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa
 581   \kod{CARDINAL} i ``ch'' tipa \kod{CHAR}. Dodatna promenljiva ``n''
 582   tipa \kod{INTEGER} služi za formatiranje slično kao u modulu
 583   \kod{InOut}, odnosno za ispis će biti zauzeto bar ``n'' znakova.}
 584
 585
 586 Ako otvaramo već postojeći fajl, poželjno je prvo proveriti da li on
 587 postoji -- u suprotnom naš program će se srušiti pri izvršavanju.
 588 Funkcija \kod{Exists(str)} vraća da li fajl postoji.
 589
 590 Promenljiva tipa \kod{File} se mora vezati za neki fajl
 591 jednom od sledećih komandi:
 592 \begin{itemize}
 593 \item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje
 594 \item \kod{f := Create(str);} -- kreira se fajl za pisanje; ako je već
 595   postojao, biće zamenjen
 596 \item \kod{f := Append(str);} -- otvara se postojeći fajl za
 597   dopisivanje na kraj
 598 \end{itemize}
 599
 600 Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo:
 601 \begin{itemize}
 602 \item \kod{Close(f);}
 603 \end{itemize}
 604
 605 Procedure za čitanje i pisanje su vrlo slične onima iz modula
 606 \kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
 607 fajl sa kojim se radi.
 608 \begin{itemize}
 609 \item \kod{RdStr(f,str)} -- učitava ceo red u string str
 610 \item \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava
 611   znakove iz fajla dok ne naiđe na separator)
 612 \item \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se
 613   dobija kao rezultat procedure
 614 \item   \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
 615 \end{itemize}
 616
 617 Bitno je obratiti pažnju na specifičnost da postoje dve komande za
 618 čitanje stringova iz fajla i da se one ponašaju različito.  Budući da
 619 razmak spada u separatore to znači da se korišćenjem \kod{RdItem} ne
 620 može učitati string koji ima u sebi razmake.
 621
 622 Analogne su i procedure za pisanje različitih tipova u fajl:
 623 \begin{itemize}
 624 \item \kod{WrStr(f,str);}
 625 \item \kod{WrInt(f,i,n);}
 626 \item \kod{WrCard(f,c,n);}
 627 \item \kod{WrChar(f,ch);}
 628 \end{itemize}
 629
 630 Treba primetiti da ne postoje dve komande za ispis stringa u fajl --
 631 potpuno je svejedno da li on ima razmake u sebi ili ne.
 632
 633 Prelom reda se eksplicitno upisuje u fajl komandom
 634 \begin{itemize}
 635 \item \kod{WrLn(f);}.
 636 \end{itemize}
 637
 638
 639 Da bi odredili da li smo stigli do kraja fajla možemo koristiti
 640 \kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
 641 FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
 642 operacijom čitanja stigli do kraja fajla.  Ne menja joj se vrednost
 643 pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
 644 tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
 645 radu.
 646
 647 \subsubsection*{Mogući problemi}
 648
 649 U ovoj glavi će biti navedeni neki česti problemi koji se mogu desiti
 650 pri korišćenju FIO modula, a koji su vezani za konkretnu
 651 implementaciju u XDS distribuciji kompajlera.
 652
 653 \paragraph{\kod{RdStr} i drugi pozivi} Prilikom čitanja iz fajlova
 654 može doći do neobičnih rezultata ako se kombinuju pozivi \kod{RdStr}
 655 sa drugima. Problem je u različitom tretiranju separatora. Komanda
 656 \kod{RdStr} uvek čita do kraja reda i pri tome premesti poziciju za
 657 čitanje odmah iza znaka za razdvajanje redova. Ostale komande prvo
 658 preskaču separatore i čitaju sadržaj dok ne naiđu na novi separator
 659 (što može biti novi red, a može biti i razmak, tabulator i neki drugi
 660 znaci) i staju sa čitanjem \emph{pre} tog separatora. Kombinaovanje
 661 ova dva pristupa može dovesti do toga da \kod{RdStr} nakon neke druge
 662 komande učita samo kraj trenutnog reda, a ne sledeći red kao što bi
 663 bilo očekivano.
 664
 665 \paragraph{EOF i prazan red na kraju fajla} Svako čitanje iz fajla
 666 postavlja \kod{EOF} u skladu sa tim da li je komanda stigla do kraja
 667 fajla ili ne. Nažalost kod svih komandi za čitanje (osim \kod{RdStr})
 668 postoji problem ukoliko je na kraju prazan red ili neki dodatni
 669 separator. Tada učitavanje poslednjeg elementa nije zapravo došlo do
 670 kraja fajla. Ako se nakon toga proba još jedno učitavanje sa takvom
 671 komandom ona će probati da preskoči separator i da učita neki sadržaj,
 672 ali će se zaglaviti jer ne može da ga nađe. Ovo ponašanje je greška u
 673 implementaciji FIO modula u okviru XDS distribucije.
 674
 675
 676 \subsection{Zadatak: ispis sadržaja fajla na ekran}
 677
 678 Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 679
 680 \lstinputlisting[style=codeblock]{kodovi/fajlovi/ispis.mod}
 681
 682 \subsection{Zadatak: spisak studenata}
 683
 684 Napraviti program koji iz fajla učitava podatke o studentima, dodaje
 685 novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
 686 podatak o jednom studentu, redom prezime, ime i godina rođenja,
 687 razdvojeni razmacima.
 688
 689 \lstinputlisting[style=codeblock]{kodovi/fajlovi/nizslog.MOD}
 690
 691 \sectionbreak
 692 \section{Liste i pokazivači}
 693
 694 Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure
 695 \kod{ALLOCATE} i \kod{DEALLOCATE}. U kodu se tada mogu koristiti i njihovi
 696 skraćeni oblici \kod{NEW} i \kod{DISPOSE}.
 697
 698 \subsection{Zadatak: Formiranje, štampanje i brisanje listi}
 699
 700
 701 \begin{lstlisting}[style=codeblock]
 702 MODULE liste;
 703 FROM InOut IMPORT WriteString, WriteLn, WriteInt,
 704         ReadInt, ReadCard;
 705 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 706 TYPE
 707   brojevi = POINTER TO brojSlog;
 708   brojSlog = RECORD
 709       info:INTEGER;
 710       veza:brojevi;
 711   END;
 712 VAR
 713   n,i:CARDINAL;
 714   lista : brojevi;
 715   br:INTEGER;
 716
 717 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 718 (* dodaje broj br na pocetak liste *)
 719 VAR
 720   temp:brojevi;
 721 BEGIN
 722   NEW(temp);
 723   temp^.info := br;
 724   temp^.veza := lista;
 725   lista := temp;
 726 END DodajPoc;
 727
 728 PROCEDURE Stampaj(lista:brojevi);
 729 VAR
 730   temp:brojevi;
 731 BEGIN
 732   temp:=lista;
 733   WHILE temp # NIL DO
 734       WriteInt(temp^.info,0);
 735       WriteLn;
 736       temp := temp^.veza;
 737   END;
 738 END Stampaj;
 739
 740 PROCEDURE Unisti(VAR lista:brojevi);
 741 VAR
 742   temp:brojevi;
 743 BEGIN
 744   temp:=lista;
 745   WHILE temp # NIL DO
 746         lista:=lista^.veza;
 747         DISPOSE(temp);
 748         temp:=lista;
 749   END;
 750 END Unisti;
 751
 752 BEGIN
 753   lista := NIL;
 754   WriteString('unesite n (broj brojeva): ');
 755   ReadCard(n);
 756   WriteString('unesite brojeve: ');
 757   WriteLn;
 758   FOR i:= 1 TO n DO
 759       ReadInt(br);
 760       DodajPoc(lista,br);
 761   END;
 762   WriteString('sadrzaj liste:');
 763   WriteLn;
 764   Stampaj(lista);
 765   Unisti(lista);
 766   WriteString('memorija je oslobodjena');
 767   WriteLn;
 768 END liste.
 769 \end{lstlisting}
 770
 771 Alternativno je poziv \kod{DodajPoc} moguće zameniti pozivom jedne od
 772 sledeće dve procedure čime se dobija dodavanje elementa na kraj liste,
 773 ili kreiranje sortirane liste:
 774
 775 \begin{lstlisting}[style=codeblock]
 776 PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
 777 (* dodaje element na kraj liste *)
 778 VAR
 779   tekuci, temp :brojevi;
 780 BEGIN
 781   NEW(temp);
 782   temp^.info := br;
 783   temp^.veza := NIL;
 784   IF lista = NIL THEN
 785      (* prazna lista *)
 786      lista:=temp;
 787   ELSE
 788      tekuci := lista;
 789      WHILE tekuci^.veza#NIL DO
 790         tekuci:=tekuci^.veza;
 791      END;
 792      tekuci^.veza := temp;
 793   END;
 794 END DodajKraj;
 795
 796 PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
 797 (* dodaje broj tako da lista ostane sortirana
 798    (podrazumeva se da je vec sortirana) *)
 799 VAR
 800   temp, tekuci : brojevi;
 801 BEGIN
 802   NEW(temp);
 803   temp^.info:=br;
 804   temp^.veza:=NIL;
 805   IF (lista = NIL) OR (lista^.info>=br) THEN
 806   (*prazna lista ili na pocetak*)
 807     temp^.veza:=lista;
 808     lista := temp;
 809   ELSE
 810   (*negde u listi*)
 811     tekuci:= lista;
 812     WHILE (tekuci^.veza # NIL) AND
 813           (tekuci^.veza^.info<=br) DO
 814       tekuci:=tekuci^.veza;
 815     END;
 816     temp^.veza := tekuci^.veza;
 817     tekuci^.veza:=temp;
 818   END;
 819 END DodajSort;
 820 \end{lstlisting}
 821
 822 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 823
 824 \begin{lstlisting}[style=codeblock]
 825 MODULE liste2;
 826 FROM InOut IMPORT WriteString, WriteLn,
 827            WriteCard, ReadCard;
 828 FROM IO IMPORT RdKey;
 829 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 830 TYPE
 831   skupZn = SET OF CHAR;
 832   brojevi = POINTER TO brojSlog;
 833   brojSlog = RECORD
 834       info:CARDINAL;
 835       veza:brojevi;
 836   END;
 837 VAR
 838   lista : brojevi;
 839   menu,prazno:CHAR;
 840
 841 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 842 (* dodaje broj pom na pocetak liste *)
 843 VAR
 844   temp:brojevi;
 845 BEGIN
 846   (* kreiramo novi element *)
 847   NEW(temp);
 848   temp^.info := br;
 849   (* treba da pokazuje na ostatak liste *)
 850   temp^.veza := lista;
 851   (* pocetak liste je novi element *)
 852   lista := temp;
 853 END DodajPoc;
 854
 855 PROCEDURE Unos(VAR lista:brojevi);
 856 (* dodaje n brojeva u listu *)
 857 VAR
 858   n,i,br:CARDINAL;
 859 BEGIN
 860   WriteString('unesite n (broj brojeva): ');
 861   ReadCard(n);
 862   FOR i:= 1 TO n DO
 863       WriteString("unesite broj ");
 864       WriteCard(i,0);
 865       WriteString(": ");
 866       ReadCard(br);
 867       DodajPoc(lista,br);
 868   END;
 869 END Unos;
 870
 871 (* -- procedure za stampu -- *)
 872
 873 PROCEDURE Stampaj(lista:brojevi);
 874 (* stampa sadrzaj liste na ekran *)
 875 VAR
 876   temp:brojevi;
 877 BEGIN
 878   WriteLn;
 879   WriteString("Sadrzaj liste:");
 880   WriteLn;
 881   temp:=lista;
 882   WHILE temp # NIL DO
 883       WriteCard(temp^.info,0);
 884       WriteLn;
 885       temp := temp^.veza;
 886   END;
 887 END Stampaj;
 888
 889 PROCEDURE StampajK(VAR lista:brojevi);
 890 (* stampa k-ti element (k unosi korisnik) *)
 891 VAR
 892   temp:brojevi;
 893   k,brojac:CARDINAL;
 894 BEGIN
 895   WriteString("unesite redni broj elementa:");
 896   ReadCard(k);
 897   temp:=lista;
 898   brojac := 1;
 899   WHILE (temp# NIL) AND (k>brojac) DO
 900     temp:=temp^.veza;
 901     INC(brojac);
 902   END;
 903   IF (temp#NIL) THEN
 904     WriteCard(temp^.info,2);
 905   ELSE
 906     WriteString("greska! - ne postoji element");
 907     WriteString(" u listi sa rednim brojem ");
 908     WriteCard(k,2);
 909   END;
 910   WriteLn();
 911 END StampajK;
 912
 913 PROCEDURE StampajMinimum(VAR lista:brojevi);
 914 (* nalazi i stampa minimalni element liste *)
 915 VAR
 916   temp:brojevi;
 917   min:CARDINAL;
 918 BEGIN
 919   IF (lista=NIL) THEN
 920     WriteString("prazna lista!");
 921   ELSE
 922     min:=lista^.info;
 923     temp:=lista^.veza;
 924     WHILE temp # NIL DO
 925       IF temp^.info < min THEN
 926         min := temp^.info;
 927       END;
 928       temp := temp^.veza;
 929     END;
 930     WriteString("Minimalni element liste je ");
 931     WriteCard(min,0);
 932   END;
 933   WriteLn;
 934 END StampajMinimum;
 935
 936 (* -- pomocne procedure, bez ispisa  -- *)
 937
 938 PROCEDURE UListi(lista:brojevi;
 939                  br: CARDINAL):BOOLEAN;
 940 (* vraca da li se 'br' nalazi u listi 'lista' *)
 941 VAR
 942   temp:brojevi;
 943 BEGIN
 944   temp:=lista;
 945   WHILE (temp # NIL) AND (temp^.info # br) DO
 946     (* dok ne dodjemo do kraja liste
 947        ili ne nadjemo broj *)
 948       temp := temp^.veza;
 949   END;
 950   IF temp#NIL THEN
 951     (* znaci da nismo na kraju liste,
 952        tj da je nadjen broj *)
 953     RETURN TRUE;
 954   ELSE (* temp = NIL *)
 955     RETURN FALSE;
 956   END;
 957 END UListi;
 958
 959 PROCEDURE IzbaciIzListe(VAR lista:brojevi;
 960                         br: CARDINAL):BOOLEAN;
 961 (* izbacuje broj 'br' iz liste, naravno ako
 962    postoji i vraca da li je operacija uspesno
 963    obavljena *)
 964 VAR
 965   temp,prethodni:brojevi;
 966 BEGIN
 967   (* proverimo da li je prvi element *)
 968   IF (lista # NIL) AND (lista^.info = br) THEN
 969     temp:=lista;
 970     lista :=lista^.veza;
 971     DISPOSE(temp);
 972     RETURN TRUE;
 973   ELSE
 974   (* trazimo u ostatku liste *)
 975     temp:=lista;
 976     prethodni:=NIL;
 977     WHILE (temp # NIL) AND (temp^.info # br) DO
 978         (* dok ne dodjemo do kraja liste
 979            ili ne nadjemo broj *)
 980         prethodni:=temp;
 981         temp := temp^.veza;
 982     END;
 983     IF temp#NIL THEN
 984       (* znaci da nismo na kraju liste,
 985          odnosno da smo nasli broj *)
 986       (* prevezemo listu oko elementa *)
 987       prethodni^.veza:=temp^.veza;
 988       DISPOSE(temp);
 989       RETURN TRUE;
 990     ELSE
 991       RETURN FALSE;
 992     END;
 993   END;
 994 END IzbaciIzListe;
 995
 996 PROCEDURE IzbaciIzListeSve(VAR lista:brojevi;
 997                         br: CARDINAL):CARDINAL;
 998 (* izbacuje sve brojeve 'br' iz liste, naravno ako
 999    postoje i vraca koliko ih je bilo *)
1000 VAR
1001   temp,prethodni:brojevi;
1002   brojac : CARDINAL;
1003 BEGIN
1004   brojac := 0;
1005   (* uklanjamo sa pocetka koliko je potrebno *)
1006   WHILE (lista # NIL) AND (lista^.info = br) DO
1007     temp:=lista;
1008     lista :=lista^.veza;
1009     DISPOSE(temp);
1010     INC(brojac);
1011   END;
1012   (* trazimo u ostatku liste *)
1013   IF (lista # NIL) THEN
1014     temp:=lista;
1015     WHILE (temp^.veza # NIL)  DO
1016         (* idemo do poslednjeg elementa liste *)
1017         prethodni:=temp;
1018         temp := temp^.veza;
1019         IF temp^.info = br THEN
1020           (* prevezemo listu oko elementa *)
1021           prethodni^.veza:=temp^.veza;
1022           DISPOSE(temp);
1023           INC(brojac);
1024           (* vracamo se jedan korak da bi
1025           u novom krugu proverili i ovaj element *)
1026           temp := prethodni;
1027         END;
1028     END;
1029   END;
1030   RETURN brojac;
1031 END IzbaciIzListeSve;
1032
1033 (* - procedure sa interakcijom sa korisnikom - *)
1034
1035 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1036 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1037 VAR
1038   br:CARDINAL;
1039 BEGIN
1040   WriteString("unesite broj za izbacivanje: ");
1041   ReadCard(br);
1042   IF IzbaciIzListe(lista,br) THEN
1043     WriteString("broj je izbacen iz liste");
1044   ELSE
1045     WriteString("greska! - broj ne postoji");
1046   END;
1047   WriteLn;
1048 END IzbacivanjeEl;
1049
1050 PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
1051 (* izbacuje sve primeke unetog broj iz liste
1052    koristeci proceduru IzbaciIzListeSve *)
1053 VAR
1054   br, ukupno:CARDINAL;
1055 BEGIN
1056   WriteString("unesite broj za izbacivanje: ");
1057   ReadCard(br);
1058   ukupno := IzbaciIzListeSve(lista,br);
1059   WriteString("Iz liste je izbaceno ");
1060   WriteCard(ukupno,3);
1061   WriteString(" el.");
1062   WriteLn;
1063 END IzbacivanjeElSvi;
1064
1065 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1066 (* izbacuje k-ti element iz liste *)
1067 VAR
1068   temp,tekuci:brojevi;
1069   k,brojac:CARDINAL;
1070 BEGIN
1071   IF lista=NIL THEN
1072     WriteString("lista je prazna, nema ");
1073     WriteString("elemenata za izbacivanje");
1074   ELSE
1075     WriteString("unesite redni broj elementa");
1076     WriteString(" koji zelite izbaciti:");
1077     ReadCard(k);
1078     IF k=1 THEN (*izbacivanje prvog *)
1079       temp:=lista;
1080       lista := lista^.veza;
1081       DISPOSE(temp);
1082     ELSE
1083       tekuci := lista;
1084       brojac := 2; (*gledamo jedan unapred*)
1085       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1086         (* idemo kroz listu do k-tog el *)
1087         tekuci:=tekuci^.veza;
1088         INC(brojac);
1089       END;
1090       IF (tekuci^.veza#NIL) THEN
1091          (* pamtimo element za brisanje *)
1092          temp:=tekuci^.veza;
1093          (* prevezujemo listu oko njega*)
1094          tekuci^.veza:=tekuci^.veza^.veza;
1095          DISPOSE(temp);
1096       ELSE
1097         WriteString("greska! - ne postoji el ");
1098         WriteString("u listi sa rednim brojem ");
1099         WriteCard(k,2);
1100       END;
1101       WriteLn();
1102     END;
1103   END;
1104 END IzbacivanjeK;
1105
1106 PROCEDURE Pretraga(lista:brojevi);
1107 (* provera da li se uneti broj nalazi u listi *)
1108 VAR
1109   br:CARDINAL;
1110 BEGIN
1111   WriteString("unesite trazeni broj");
1112   ReadCard(br);
1113   IF UListi(lista,br) THEN
1114     WriteString("broj postoji u listi");
1115   ELSE
1116     WriteString("broj ne postoji u listi");
1117   END;
1118   WriteLn;
1119 END Pretraga;
1120
1121 (* -- oslobadjanje memorije -- *)
1122
1123 PROCEDURE Unisti(VAR lista:brojevi);
1124 VAR
1125   temp:brojevi;
1126 BEGIN
1127   temp:=lista;
1128   WHILE temp # NIL DO
1129         lista:=lista^.veza;
1130         DISPOSE(temp);
1131         temp:=lista;
1132   END;
1133 END Unisti;
1134
1135 BEGIN
1136   (* pocinjemo od prazne liste *)
1137   lista := NIL;
1138   REPEAT
1139      WriteLn;
1140      WriteString("Ilustracija rada sa");
1141      WriteString(" listama brojeva");
1142      WriteLn;
1143      WriteString("=============================");
1144      WriteLn;
1145      WriteString("s - Stampa");WriteLn;
1146      WriteString("u - Unos");WriteLn;
1147      WriteString("i - Izbacivanje br iz liste");
1148      WriteLn;
1149      WriteString("v - izbacivanje svih br iz liste");
1150      WriteLn;
1151      WriteString("e - izbacivanje k-tog El.");
1152      WriteLn;
1153      WriteString("k - stampanje k-tog elementa");
1154      WriteLn;
1155      WriteString("m - Minimalni broj u listi");
1156      WriteLn;
1157      WriteString("p - Pretraga el. u listi");
1158      WriteLn;
1159      WriteLn;
1160      WriteString("q - kraj rada (Quit)");WriteLn;
1161       REPEAT
1162         menu := CAP(RdKey());
1163       UNTIL menu IN skupZn{'S','U','E','I','V',
1164                            'M','K','P','Q'};
1165       IF menu#'Q' THEN
1166         CASE menu OF
1167          'S' : Stampaj(lista);|
1168          'U' : Unos(lista);|
1169          'I' : IzbacivanjeEl(lista);|
1170          'V' : IzbacivanjeElSvi(lista);|
1171          'E' : IzbacivanjeK(lista);|
1172          'K' : StampajK(lista); |
1173          'M' : StampajMinimum(lista); |
1174          'P' : Pretraga(lista);|
1175         END;
1176         WriteLn;
1177         WriteString("--- pritisnite bilo koji ");
1178         WriteString("taster za povratak u meni");
1179         prazno:=RdKey();
1180       ELSE
1181         WriteString("Kraj rada")
1182       END;
1183       WriteLn;
1184   UNTIL menu='Q';
1185   Unisti(lista);
1186 END liste2.
1187 \end{lstlisting}
1188
1189
1190 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1191
1192 \begin{lstlisting}[style=codeblock]
1193 MODULE Radnici;
1194
1195 FROM InOut IMPORT WriteString, ReadString,
1196            WriteLn, WriteCard, ReadCard, Done;
1197 FROM IO IMPORT RdKey;
1198 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1199
1200 TYPE
1201   skupZn = SET OF CHAR;
1202   str = ARRAY [1..20] OF CHAR;
1203   radnici = POINTER TO slog;
1204   slog = RECORD
1205            ime, prez : str;
1206            broj : CARDINAL;
1207            sled : radnici
1208          END;
1209 VAR
1210   meni, pom : CHAR;
1211   rad : radnici;
1212
1213   PROCEDURE Clear();
1214   VAR
1215     br: CARDINAL;
1216   BEGIN
1217     FOR br:=1 TO 100 DO
1218       WriteLn;
1219     END;
1220   END Clear;
1221
1222   PROCEDURE Spisak(rad : radnici);
1223   BEGIN
1224     WHILE rad # NIL DO
1225       WriteString(rad^.ime);
1226       WriteString(' ');
1227       WriteString(rad^.prez);
1228       WriteCard(rad^.broj, 8);
1229       WriteLn;
1230       rad := rad^.sled
1231     END
1232   END Spisak;
1233
1234   PROCEDURE Zaposli(VAR rad : radnici);
1235   VAR
1236     novi, tek : radnici;
1237     nadjen : BOOLEAN;
1238   BEGIN
1239     NEW(novi);
1240     REPEAT
1241       WriteString('Ime, prezime i jedinstveni');
1242       WriteString(' broj novog radnika: ');
1243       WriteLn;
1244       ReadString(novi^.ime);
1245       ReadString(novi^.prez);
1246       ReadCard(novi^.broj);
1247       nadjen := FALSE;
1248       tek := rad;
1249       WHILE NOT nadjen AND (tek # NIL) AND
1250             (tek^.broj <= novi^.broj) DO
1251         IF novi^.broj = tek^.broj THEN
1252           nadjen := TRUE
1253         ELSE
1254           tek := tek^.sled
1255         END
1256       END
1257     UNTIL Done AND NOT nadjen;
1258     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1259       novi^.sled := rad;
1260       rad := novi
1261     ELSE
1262       tek := rad;
1263       WHILE (tek^.sled # NIL) AND
1264             (tek^.sled^.broj < novi^.broj) DO
1265         tek := tek^.sled
1266       END;
1267       novi^.sled := tek^.sled;
1268       tek^.sled := novi
1269     END
1270   END Zaposli;
1271
1272   PROCEDURE Otpusti(VAR rad : radnici);
1273   VAR
1274     tek, pom : radnici;
1275     br : CARDINAL;
1276   BEGIN
1277     REPEAT
1278       WriteLn;
1279       WriteString('Unesite redni broj radnika:');
1280       ReadCard(br)
1281     UNTIL Done;
1282     WriteLn;
1283     IF rad = NIL THEN
1284       WriteString('Greska.')
1285     ELSIF br = rad^.broj THEN
1286       pom := rad;
1287       rad := rad^.sled;
1288       DISPOSE(pom)
1289     ELSE
1290       tek := rad;
1291       WHILE (tek^.sled # NIL) AND
1292             (tek^.sled^.broj < br) DO
1293         tek := tek^.sled
1294       END;
1295       IF (tek^.sled = NIL) OR
1296          (tek^.sled^.broj > br) THEN
1297         WriteString('Greska.')
1298       ELSE
1299         pom := tek^.sled;
1300         tek^.sled := tek^.sled^.sled;
1301         DISPOSE(pom)
1302       END
1303     END
1304   END Otpusti;
1305
1306   PROCEDURE Inform(rad : radnici);
1307   VAR
1308     br : CARDINAL;
1309   BEGIN
1310     REPEAT
1311       WriteLn;
1312       WriteString('Unesite redni broj radnika:');
1313       ReadCard(br)
1314     UNTIL Done;
1315     WriteLn;
1316     WHILE (rad # NIL) AND (rad^.broj < br) DO
1317       rad := rad^.sled
1318     END;
1319     IF (rad = NIL) OR (rad^.broj # br) THEN
1320       WriteString('Greska.')
1321     ELSE
1322       WriteString(rad^.ime);
1323       WriteString(' ');
1324       WriteString(rad^.prez)
1325     END
1326   END Inform;
1327
1328   PROCEDURE Bankrot(VAR rad : radnici);
1329   VAR
1330     pom : radnici;
1331   BEGIN
1332     WHILE rad # NIL DO
1333       pom := rad;
1334       rad := rad^.sled;
1335       DISPOSE(pom)
1336     END
1337   END Bankrot;
1338
1339 BEGIN
1340   rad := NIL;
1341   REPEAT
1342     Clear;
1343     WriteString('s - spisak svih zaposlenih');
1344     WriteLn;
1345     WriteString('z - zaposljavanje radnika');
1346     WriteLn;
1347     WriteString('o - otpustanje radnika');
1348     WriteLn;
1349     WriteString('i - informacije o radniku');
1350     WriteLn;
1351     WriteString('b - bankrot firme');
1352     WriteLn;
1353     WriteString('k - kraj rada');
1354     WriteLn;
1355     REPEAT
1356       meni := RdKey();
1357     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1358                               'I', 'B', 'K'};
1359     Clear;
1360     IF CAP(meni) # 'K' THEN
1361       CASE CAP(meni) OF
1362         'S' : Spisak(rad)|
1363         'Z' : Zaposli(rad)|
1364         'O' : Otpusti(rad)|
1365         'I' : Inform(rad)|
1366         'B' : Bankrot(rad)
1367       END;
1368       WriteLn;
1369       WriteString('-- pritisnite bilo koji ');
1370       WriteString('taster za nastavak --');
1371       pom := RdKey()
1372     END
1373   UNTIL CAP(meni) = 'K'
1374 END Radnici.
1375 \end{lstlisting}
1376
1377 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1378
1379 \begin{lstlisting}[style=codeblock]
1380   PROCEDURE Spisak(rad : radnici);
1381   BEGIN
1382     IF rad # NIL THEN
1383       WriteString(rad^.ime);
1384       WriteString(' ');
1385       WriteString(rad^.prez);
1386       WriteCard(rad^.broj, 8);
1387       WriteLn;
1388       Spisak(rad^.sled)
1389     END
1390   END Spisak;
1391 \end{lstlisting}
1392
1393 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1394   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1395   težini}
1396
1397 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1398 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1399 uređenje i po visini i po težini.
1400
1401 \begin{lstlisting}[style=codeblock]
1402 MODULE VisTez;
1403 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1404 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1405 FROM SYSTEM IMPORT TSIZE;
1406 TYPE
1407   pok = POINTER TO element;
1408   element = RECORD
1409               visina, tezina : CARDINAL;
1410               Vveza, Tveza : pok
1411             END;
1412 VAR
1413   pocV, pocT : pok;
1414   vis, tez : CARDINAL;
1415 PROCEDURE Ispisi(pocV, pocT : pok);
1416 VAR
1417   tek : pok;
1418 BEGIN
1419   tek := pocV;
1420   WrStr('Po visini:');
1421   WrLn;
1422   WHILE tek # NIL DO
1423     WrCard(tek^.visina, 6);
1424     tek := tek^.Vveza
1425   END;
1426   WrLn;
1427   tek := pocT;
1428   WrStr('Po tezini:');
1429   WrLn;
1430   WHILE tek # NIL DO
1431     WrCard(tek^.tezina,6);
1432     tek := tek^.Tveza
1433   END
1434 END Ispisi;
1435
1436 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1437                 vis, tez : CARDINAL);
1438 VAR
1439   novi, tek, iza : pok;
1440   nadjen : BOOLEAN;
1441 BEGIN
1442   IF pocV = NIL THEN
1443     ALLOCATE(pocV, TSIZE(element));
1444     pocV^.visina := vis;
1445     pocV^.tezina := tez;
1446     pocV^.Vveza := NIL;
1447     pocV^.Tveza := NIL;
1448     pocT := pocV
1449   ELSE
1450     ALLOCATE(novi, TSIZE(element));
1451     novi^.visina := vis;
1452     novi^.tezina := tez;
1453     tek := pocV;
1454     nadjen := FALSE;
1455     WHILE (tek # NIL) AND NOT nadjen DO
1456       nadjen := vis <= tek^.visina;
1457       IF NOT nadjen THEN
1458         iza := tek;
1459         tek := tek^.Vveza
1460       END
1461     END;
1462     novi^.Vveza := tek;
1463     IF tek = pocV THEN
1464       pocV := novi
1465     ELSE
1466       iza^.Vveza := novi
1467     END;
1468     tek := pocT;
1469     nadjen := FALSE;
1470     WHILE (tek # NIL) AND NOT nadjen DO
1471       nadjen := tez <= tek^.tezina;
1472       IF NOT nadjen THEN
1473         iza := tek;
1474         tek := tek^.Tveza
1475       END
1476     END;
1477     novi^.Tveza := tek;
1478     IF tek = pocT THEN
1479       pocT := novi
1480     ELSE
1481       iza^.Tveza := novi
1482     END
1483   END
1484 END Ubaci;
1485
1486 BEGIN
1487   pocV := NIL;
1488   pocT := NIL;
1489   WrStr('Unesite visinu ---- ');
1490   vis := RdCard();
1491   WHILE vis > 0 DO
1492     WrStr('Unesite tezinu ---- ');
1493     tez := RdCard();
1494     Ubaci(pocV, pocT, vis, tez);
1495     WrLn;
1496     WrStr('Unesite visinu ---- ');
1497     vis := RdCard()
1498   END;
1499   WrLn;
1500   Ispisi(pocV, pocT)
1501 END VisTez.
1502 \end{lstlisting}
1503
1504 \sectionbreak
1505 \section{Polinomi preko listi}
1506
1507 \subsection{Moduli}
1508
1509 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1510 \kod{Polinom} je definisan u globalnom modulu.
1511
1512 \paragraph{PolinomL.DEF} \
1513
1514 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.DEF}
1515
1516 \paragraph{PolinomL.MOD} \
1517
1518 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.MOD}
1519
1520 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1521
1522 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1523
1524 \lstinputlisting[style=codeblock]{kodovi/polinomi/polinom.MOD}
1525
1526 \subsection{Zadatak: Suma k polinoma}
1527
1528 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1529 toga izracunava njihovu sumu
1530
1531 \lstinputlisting[style=codeblock]{kodovi/polinomi/PolSuma.MOD}
1532
1533 \sectionbreak
1534 \section{Stek i red opsluživanja}
1535
1536 \subsection{Primer: osnovno korišćenje steka i reda opsluživanja}
1537
1538 \lstinputlisting[style=codeblock]{kodovi/stek-redopsl/stekred.mod}
1539
1540 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
1541
1542 \begin{lstlisting}[style=codeblock]
1543 DEFINITION MODULE QueueInfo;
1544 CONST
1545   Maxqueue = 100;
1546 TYPE
1547   InfoTip = CHAR;
1548
1549 END QueueInfo.
1550
1551 IMPLEMENTATION MODULE QueueInfo;
1552 END QueueInfo.
1553
1554 DEFINITION MODULE RedOpsl1;
1555 FROM QueueInfo IMPORT InfoTip,Maxqueue;
1556 TYPE
1557   Niz = ARRAY[1..Maxqueue] OF InfoTip;
1558   RedOpslTip = RECORD
1559         Prvi, Zadnji : CARDINAL;
1560         Element : Niz
1561   END;
1562
1563 PROCEDURE MakeNull(VAR q : RedOpslTip);
1564 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1565 PROCEDURE First(VAR q : RedOpslTip;
1566                 VAR x : InfoTip;
1567                 VAR ok : BOOLEAN);
1568 PROCEDURE PopFirst(VAR q : RedOpslTip;
1569                    VAR ok : BOOLEAN);
1570 PROCEDURE AddRear(VAR q : RedOpslTip;
1571                   x : InfoTip;
1572                   VAR ok : BOOLEAN);
1573
1574 END RedOpsl1.
1575
1576 IMPLEMENTATION MODULE RedOpsl1;
1577 FROM QueueInfo IMPORT Maxqueue,InfoTip;
1578
1579 PROCEDURE MakeNull(VAR q : RedOpslTip);
1580 BEGIN
1581   WITH q DO
1582     Prvi := 0;
1583     Zadnji := 0
1584   END
1585 END MakeNull;
1586
1587 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1588 BEGIN
1589   RETURN q.Zadnji = 0
1590 END Empty;
1591
1592
1593 PROCEDURE First(VAR q : RedOpslTip;
1594                 VAR x : InfoTip;
1595                 VAR ok : BOOLEAN);
1596 BEGIN
1597   IF Empty(q) THEN
1598     ok := FALSE
1599   ELSE
1600     ok := TRUE;
1601     WITH q DO
1602       x := Element[Prvi]
1603     END
1604   END
1605 END First;
1606
1607 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
1608 BEGIN
1609   IF i = Maxqueue THEN
1610     RETURN 1
1611   ELSE
1612     RETURN i+1
1613   END
1614 END AddOne;
1615
1616 PROCEDURE PopFirst(VAR q : RedOpslTip;
1617                    VAR ok : BOOLEAN);
1618 BEGIN
1619   IF Empty(q) THEN
1620     ok := FALSE
1621   ELSE
1622     ok := TRUE;
1623     WITH q DO
1624       IF Prvi = Zadnji THEN
1625         MakeNull(q)
1626       ELSE
1627         Prvi := AddOne(Prvi)
1628       END
1629     END
1630   END
1631 END PopFirst;
1632
1633 PROCEDURE AddRear(VAR q : RedOpslTip;
1634                   x : InfoTip;
1635                   VAR ok : BOOLEAN);
1636 BEGIN
1637   WITH q DO
1638     IF AddOne(Zadnji) = Prvi THEN
1639       ok := FALSE
1640     ELSE
1641       ok := TRUE;
1642       IF Empty(q) THEN
1643         Prvi := 1;
1644         Zadnji := 1
1645       ELSE
1646         Zadnji := AddOne(Zadnji)
1647       END;
1648       Element[Zadnji] := x
1649     END
1650   END
1651 END AddRear;
1652
1653 END RedOpsl1.
1654
1655 MODULE Bafer;
1656 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
1657 FROM FIO IMPORT File,WrChar, Create, Close;
1658 IMPORT IO;
1659
1660 CONST
1661   ImeIzlaza = 'izlaz.txt';
1662
1663 VAR
1664   izlaz : File;
1665   znak : CHAR;
1666   buffer : RedOpslTip;
1667
1668 PROCEDURE IsprazniBafer(VAR dat : File;
1669                         VAR buf : RedOpslTip);
1670 VAR
1671   znak : CHAR;
1672   ok : BOOLEAN;
1673 BEGIN
1674   WHILE NOT Empty(buf) DO
1675     First(buf, znak, ok);
1676     PopFirst(buf, ok);
1677     WrChar(dat, znak)
1678   END
1679 END IsprazniBafer;
1680
1681 PROCEDURE BaferWrite(VAR dat : File;
1682                      VAR buf : RedOpslTip;
1683                      znak : CHAR);
1684 VAR
1685   ok : BOOLEAN;
1686 BEGIN
1687   AddRear(buf, znak, ok);
1688   IF NOT ok THEN
1689     IsprazniBafer(dat, buf);
1690     AddRear(buf, znak, ok)
1691   END
1692 END BaferWrite;
1693
1694 BEGIN
1695   izlaz := Create(ImeIzlaza);
1696   MakeNull(buffer);
1697   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
1698   IO.WrStr(ImeIzlaza);
1699   IO.WrChar('.');
1700   IO.WrLn;
1701   IO.WrStr('Unos zavrsite tackom.');
1702   IO.WrLn;
1703   znak := IO.RdChar();
1704   WHILE znak # '.' DO
1705     BaferWrite(izlaz, buffer, znak);
1706     znak := IO.RdChar();
1707   END;
1708   IsprazniBafer(izlaz, buffer);
1709   Close(izlaz)
1710 END Bafer.
1711 \end{lstlisting}
1712
1713 \subsection%
1714 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
1715
1716 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
1717 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
1718
1719 \begin{lstlisting}[style=codeblock]
1720 DEFINITION MODULE Stek;
1721 CONST
1722   Maxstack = 100;
1723 TYPE
1724   Niz = ARRAY [1..Maxstack] OF CHAR;
1725   StekTip = RECORD
1726             Top : CARDINAL;
1727             Element : Niz
1728           END;
1729 PROCEDURE MakeNull(VAR s : StekTip);
1730 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1731
1732 PROCEDURE Top(VAR s : StekTip;
1733               VAR x : CHAR;
1734               VAR ok : BOOLEAN);
1735 PROCEDURE Pop(VAR s : StekTip;
1736               VAR ok : BOOLEAN);
1737 PROCEDURE Push(VAR s : StekTip;
1738                x : CHAR;
1739                VAR ok : BOOLEAN);
1740 END Stek.
1741
1742
1743 IMPLEMENTATION MODULE Stek;
1744
1745 PROCEDURE MakeNull(VAR s : StekTip);
1746 BEGIN
1747   s.Top := 0
1748 END MakeNull;
1749
1750 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1751 BEGIN
1752   RETURN s.Top = 0
1753 END Empty;
1754
1755 PROCEDURE Top(VAR s : StekTip;
1756               VAR x : CHAR;
1757               VAR ok : BOOLEAN);
1758 BEGIN
1759   IF Empty(s) THEN
1760     ok := FALSE
1761   ELSE
1762     ok := TRUE;
1763     WITH s DO
1764       x := Element[Top]
1765     END
1766   END
1767 END Top;
1768 \end{lstlisting}
1769
1770 \begin{codeblock}
1771 PROCEDURE Pop(VAR s : StekTip;
1772               VAR ok : BOOLEAN);
1773 BEGIN
1774   IF Empty(s) THEN
1775     ok := FALSE
1776   ELSE
1777     ok := TRUE;
1778     DEC(s.Top)
1779   END
1780 END Pop;
1781
1782 PROCEDURE Push(VAR s : StekTip;
1783                x : CHAR;
1784                VAR ok : BOOLEAN);
1785 BEGIN
1786   WITH s DO
1787     IF Top = Maxstack THEN
1788       ok := FALSE
1789     ELSE
1790       ok := TRUE;
1791       INC(Top);
1792       Element[Top] := x
1793     END
1794   END
1795 END Push;
1796 END Stek.
1797
1798 MODULE wcw;
1799 (* Da li rec pripada gramatici wcw+. *)
1800 FROM Stek IMPORT StekTip, MakeNull, Empty,
1801                  Top, Pop, Push;
1802 FROM InOut IMPORT Read, Write, WriteString, EOL;
1803 TYPE
1804   slova = SET OF CHAR;
1805 VAR
1806   S : StekTip;
1807   Ch, C : CHAR;
1808   ok : BOOLEAN;
1809 BEGIN
1810   MakeNull(S);
1811   Read(Ch);
1812   ok := TRUE;
1813   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
1814     Push(S, Ch, ok);
1815     Read(Ch);
1816   END;
1817   IF NOT ok THEN
1818     WriteString('Greska - mali stek')
1819   ELSIF Ch # 'c' THEN
1820     WriteString('Pogresan string')
1821   ELSE
1822     Read(Ch);
1823     WHILE ok AND (Ch # EOL) DO
1824       Top(S, C, ok);
1825       ok := ok AND (C = Ch);
1826       IF ok THEN
1827         Pop(S, ok);
1828         Read(Ch);
1829       END
1830     END;
1831     IF NOT (ok AND Empty(S)) THEN
1832       WriteString('Pogresan string')
1833     ELSE
1834       WriteString('String pripada jeziku L')
1835     END
1836   END
1837 END wcw.
1838 \end{codeblock}
1839
1840 \manbreakJK
1841
1842 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
1843
1844
1845 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
1846 koji figurišu u izrazu su jednocifreni.
1847
1848 \begin{lstlisting}[style=codeblock]
1849 MODULE PostFix;
1850
1851 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
1852 FROM InOut IMPORT Read, Write, WriteInt, EOL;
1853 TYPE
1854   slova = SET OF CHAR;
1855 VAR
1856   S : StekTip;
1857   Ch : CHAR;
1858   Op1, Op2 : INTEGER;
1859   ok : BOOLEAN;
1860 PROCEDURE Conv(Ch : CHAR) : INTEGER;
1861 BEGIN
1862   RETURN  ORD(Ch) - ORD('0')
1863 END Conv;
1864
1865 BEGIN
1866   MakeNull(S);
1867   Read(Ch);
1868   WHILE Ch # EOL DO
1869     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
1870       Top(S, Op2, ok);
1871       Pop(S, ok);
1872       Top(S, Op1, ok);
1873       Pop(S, ok);
1874       CASE Ch OF
1875         '+' : Op1 := Op1 + Op2 |
1876         '-' : Op1 := Op1 - Op2 |
1877         '*' : Op1 := Op1 * Op2 |
1878         '/' : Op1 := Op1 DIV Op2 |
1879         '%' : Op1 := Op1 MOD Op2
1880       END;
1881       Push(S, Op1, ok)
1882     ELSE
1883       Push(S, Conv(Ch), ok)
1884     END;
1885     Read(Ch);
1886   END;
1887   Top(S, Op1, ok);
1888   Write('=');
1889   WriteInt(Op1,5)
1890 END PostFix.
1891 \end{lstlisting}
1892
1893 \sectionbreak
1894 \section{Simulacija rekurzije}
1895
1896
1897 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
1898 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
1899
1900 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
1901 mesta poziva, a u skladu sa tim se kreira InfoTip.
1902
1903 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
1904 rekurzivnih poziva.
1905
1906 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
1907 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
1908 pozivi.
1909
1910 \begin{lstlisting}
1911 MakeNull(S);
1912 REPEAT
1913   WHILE treba_rekurzija DO
1914     -prepisati sve od pocetka originalne
1915      procedure do prvog rekurzivnog poziva
1916     -staviti na stek potrebne
1917      lokalne promenljive, parametre procedure i
1918      adresu mesta poziva
1919     -podesiti vrednosti parametara da budu
1920      kao u rekurzivnom pozivu procedure
1921   END;
1922   trivijalan poziv
1923   umesto RETURN x pisati rez := x
1924   jos := TRUE;
1925   WHILE jos AND NOT Empty(S) DO
1926     Top(S, el, ok);
1927     Pop(S, ok);
1928     -restauriramo vrednosti sa steka
1929     -u zavisnosti od adrese poziva nastavimo
1930      prepisivanje originalne procedure sa
1931      tog mesta
1932     -ako se dodje do novog rek. poziva tada:
1933        -sacuvati na steku vrednosti
1934        -podesiti vrednosti parametara da budu
1935         kao u rekurzivnom pozivu procedure
1936        -ici na pocetak koda
1937         (ovo se postize sa jos := FALSE)
1938     -inace
1939        ako se naidje na RETURN x pisati rez := x
1940   END
1941 UNTIL Empty(S);
1942 \end{lstlisting}
1943
1944 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
1945
1946 \subsection*{ZADACI}
1947
1948 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
1949
1950 \subsection{Primer 1 -- faktorijel}
1951
1952
1953 \begin{lstlisting}[style=codeblock]
1954 MODULE Fakto;
1955 (* InfoTip = CARDINAL; *)
1956
1957 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
1958 FROM StekC IMPORT StekTip, MakeNull, Empty,
1959                   Top, Pop, Push;
1960 VAR
1961   n : CARDINAL;
1962 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
1963 BEGIN
1964   IF n <= 1 THEN
1965     RETURN 1
1966   ELSE
1967     RETURN n * RFakto(n-1)
1968   END
1969 END RFakto;
1970
1971
1972 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
1973 VAR
1974   s : StekTip;
1975   rez : CARDINAL;
1976   OK : BOOLEAN;
1977 BEGIN
1978   MakeNull(s);
1979   WHILE n > 1 DO
1980     Push(s,n,OK);
1981     DEC(n)
1982   END;
1983   rez := 1;
1984   WHILE NOT Empty(s) DO
1985     Top(s, n, OK);
1986     Pop(s, OK);
1987     rez := n * rez
1988   END;
1989   RETURN rez
1990 END SFakto;
1991
1992 BEGIN
1993   WrStr('n = ');
1994   n := RdCard();
1995   WrLn
1996   WrStr('n! = ');
1997   WrCard(RFakto(n), 1);
1998   WrStr(' = ');
1999   WrCard(SFakto(n), 1)
2000 END Fakto.
2001 \end{lstlisting}
2002
2003 \subsection{Primer 2 -- stepenovanje}
2004
2005 \begin{lstlisting}[style=codeblock]
2006 MODULE Step;
2007 (* InfoTip = RECORD
2008                 x : REAL;
2009                 n : CARDINAL;
2010                 adr : (par, nepar)
2011              END;
2012 *)
2013 FROM IO IMPORT WrStr, WrLn, WrReal,
2014         RdReal, RdCard;
2015 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2016              Top, Pop, Push, InfoTip, AdrTip;
2017 VAR
2018   n : CARDINAL;
2019   x : REAL;
2020
2021 PROCEDURE Sqr(y : REAL) : REAL;
2022 BEGIN
2023   RETURN y * y
2024 END Sqr;
2025
2026 PROCEDURE RStep(x : REAL;
2027                 n : CARDINAL) : REAL;
2028 BEGIN
2029   IF n = 0 THEN
2030     RETURN 1.
2031   ELSIF ODD(n) THEN
2032     RETURN x * Sqr( RStep(x, n DIV 2) )
2033   ELSE
2034     RETURN Sqr( RStep(x, n DIV 2) )
2035   END
2036 END RStep;
2037
2038 PROCEDURE SStep(x : REAL;
2039                 n : CARDINAL ) : REAL;
2040 VAR
2041   s : StekTip;
2042   OK : BOOLEAN;
2043   rez : REAL;
2044   el : InfoTip;
2045 BEGIN
2046   MakeNull(s);
2047   WHILE n > 0 DO
2048     el.x := x;
2049     el.n := n;
2050     IF ODD(n) THEN
2051       el.adr := nepar;
2052     ELSE
2053       el.adr := par
2054     END;
2055     Push(s,el,OK);
2056     n := n DIV 2
2057   END;
2058   rez := 1.;
2059   WHILE NOT Empty(s) DO
2060     Top(s, el, OK);
2061     Pop(s, OK);
2062     x := el.x;
2063     n := el.n;
2064     IF el.adr = nepar THEN
2065       rez := x * Sqr(rez)
2066     ELSE
2067       rez := Sqr(rez)
2068     END
2069   END;
2070   RETURN rez
2071 END SStep;
2072
2073 BEGIN
2074   WrStr('x =? ');
2075   x := RdReal();
2076   WrLn;
2077   WrStr('n =? ');
2078   n := RdCard();
2079   WrStr('x^n = ');
2080   WrReal(RStep(x, n), 10, 1);
2081   WrStr(' = ');
2082   WrReal(SStep(x, n), 10, 1)
2083 END Step.
2084 \end{lstlisting}
2085
2086 \subsection{Primer 3 -- Fibonači}
2087
2088 \begin{lstlisting}[style=codeblock]
2089 MODULE Fib;
2090 (* InfoTip = RECORD
2091                 n : CARDINAL;
2092                 PrviSab : CARDINAL;
2093                 adr : (prvi, drugi)
2094              END;
2095 *)
2096
2097 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2098 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2099        Top, Pop, Push, InfoTip, AdrTip;
2100 VAR
2101   n : CARDINAL;
2102
2103 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2104 BEGIN
2105   IF n <= 1 THEN
2106     RETURN n
2107   ELSE
2108     RETURN RFib(n-1) + RFib(n-2)
2109   END
2110 END RFib;
2111
2112 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2113 VAR
2114   s : StekTip;
2115   OK, jos : BOOLEAN;
2116   rez, PrviSab : CARDINAL;
2117   el : InfoTip;
2118 BEGIN
2119   MakeNull(s);
2120   REPEAT
2121     WHILE n > 1 DO
2122       el.n := n;
2123       el.adr := prvi;
2124       Push(s,el,OK);
2125       DEC(n)
2126     END;
2127     rez := (n);
2128     jos := TRUE;
2129     WHILE (NOT Empty(s)) AND jos DO
2130       Top(s, el, OK);
2131       Pop(s, OK);
2132       n := el.n;
2133       IF el.adr = prvi THEN
2134         PrviSab := rez;
2135         el.n := n;
2136         el.adr := drugi;
2137         el.PrviSab := PrviSab;
2138         Push(s, el, OK);
2139         DEC(n, 2);
2140         jos := FALSE
2141       ELSE
2142         PrviSab := el.PrviSab;
2143         rez := PrviSab + rez
2144       END
2145     END
2146   UNTIL Empty(s);
2147   RETURN rez
2148 END SFib;
2149
2150 BEGIN
2151   WrStr('n =? ');
2152   n := RdCard();
2153   WrStr('F(n) = ');
2154   WrCard(RFib(n), 1);
2155   WrStr(' = ');
2156   WrCard(SFib(n), 1)
2157 END Fib.
2158 \end{lstlisting}
2159
2160 \subsection{Primer 4 -- faktorijel 2}
2161
2162
2163 \begin{lstlisting}[style=codeblock]
2164 MODULE Faktor;
2165 (* InfoTip = CARDINAL; *)
2166 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2167 FROM StekC IMPORT StekTip, MakeNull, Empty,
2168                   Top, Pop, Push;
2169 VAR
2170   n,rez : CARDINAL;
2171
2172 PROCEDURE RFakto(n : CARDINAL;
2173                  VAR rez : CARDINAL);
2174 BEGIN
2175   IF n = 0 THEN
2176     rez := 1
2177   ELSE
2178     RFakto(n-1, rez);
2179     rez := n * rez
2180   END
2181 END RFakto;
2182
2183 PROCEDURE SFakto(n : CARDINAL;
2184                  VAR rez : CARDINAL);
2185 VAR
2186   s : StekTip;
2187   OK : BOOLEAN;
2188 BEGIN
2189   MakeNull(s);
2190   WHILE n > 0 DO
2191     Push(s,n,OK);
2192     DEC(n)
2193   END;
2194   rez := 1;
2195   WHILE NOT Empty(s) DO
2196     Top(s, n, OK);
2197     Pop(s, OK);
2198     rez := n * rez
2199   END
2200 END SFakto;
2201
2202 BEGIN
2203   WrStr('n =? ');
2204   n := RdCard();
2205   WrLn;
2206   WrStr('n! = ');
2207   RFakto(n, rez);
2208   WrCard(rez, 1);
2209   WrStr(' = ');
2210   SFakto(n, rez);
2211   WrCard(rez, 1)
2212 END Faktor.
2213 \end{lstlisting}
2214
2215 \subsection{Primer 5 (ispitni)}
2216
2217
2218 \begin{lstlisting}[style=codeblock]
2219 MODULE Rek1;
2220 (* InfoTip = RECORD
2221                 d, g, m1, m2 : INTEGER;
2222                 adr : (prvi, drugi)
2223              END;
2224 *)
2225 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2226          MakeNull, Empty, Top, Pop, Push;
2227 IMPORT IO;
2228 VAR
2229   X : ARRAY [1..20] OF INTEGER;
2230
2231 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2232 VAR
2233   m1, m2 : INTEGER;
2234 BEGIN
2235   IF d>g THEN
2236     RETURN MIN(INTEGER)
2237   ELSIF d=g THEN
2238     RETURN X[d]
2239   ELSE
2240     m1 := Max(d, (d+g) DIV 2);
2241     m2 := Max((d+g) DIV 2 +1, g);
2242     IF m1 > m2 THEN
2243       RETURN m1
2244     ELSE
2245       RETURN m2
2246     END
2247   END
2248 END Max;
2249
2250 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2251 VAR
2252   S : StekTip;
2253   el : InfoTip;
2254   ok, jos : BOOLEAN;
2255   m1, m2, rez : INTEGER;
2256 BEGIN
2257   MakeNull(S);
2258   REPEAT
2259     WHILE d<g DO
2260       el.d := d;
2261       el.g := g;
2262       el.adr := prvi;
2263       Push(S, el, ok);
2264       g := (d+g) DIV 2
2265     END;
2266     IF d>g THEN
2267       rez := MIN(INTEGER)
2268     ELSE (* d=g *)
2269       rez := X[d]
2270     END;
2271     jos := TRUE;
2272     WHILE jos AND NOT Empty(S) DO
2273       Top(S, el, ok);
2274       Pop(S, ok);
2275       d := el.d;
2276       g := el.g;
2277       m1 := el.m1;
2278       IF el.adr = prvi THEN
2279         m1 := rez;
2280         el.m1 := m1;
2281         el.adr := drugi;
2282         Push(S, el, ok);
2283         d := (d+g) DIV 2 + 1;
2284         jos := FALSE
2285       ELSE (*el.adr = drugi*)
2286         m2 := rez;
2287         IF m1 > m2 THEN
2288           rez := m1
2289         ELSE
2290           rez := m2
2291         END
2292       END
2293     END
2294   UNTIL Empty(S);
2295   RETURN rez
2296 END SMax;
2297
2298 BEGIN (* glavni program *)
2299   X[1] := 3;
2300   X[2] := 2;
2301   X[3] := 5;
2302   X[4] := -7;
2303   X[5] := 0;
2304   IO.WrCard(Max(1, 5), 3);
2305   IO.WrLn;
2306   IO.WrCard(SMax(1, 5), 3);
2307   IO.WrLn
2308 END Rek1.
2309 \end{lstlisting}
2310
2311 \subsection{Primer 6 (ispitni)}
2312
2313
2314 \begin{lstlisting}[style=codeblock]
2315 MODULE Rek2;
2316 (* InfoTip = RECORD
2317                 x, y, n : CARDINAL;
2318                 adr : (prvi, drugi, treci, cetvrti)
2319              END;
2320 *)
2321 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2322            MakeNull, Empty, Top, Pop, Push;
2323 IMPORT IO;
2324
2325 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2326             n : CARDINAL) : CARDINAL;
2327 BEGIN
2328   IF n < 3 THEN
2329     RETURN x + y
2330   ELSIF ODD(n) THEN
2331     RETURN g(g(x+1, y, n-2), y, n-3)
2332   ELSE
2333     RETURN g(x, g(x, y+1, n-2), n-3)
2334   END
2335 END g;
2336
2337 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2338              n : CARDINAL) : CARDINAL;
2339 VAR
2340   S : StekTip;
2341   el : InfoTip;
2342   ok, jos : BOOLEAN;
2343   rez : CARDINAL;
2344 BEGIN
2345   MakeNull(S);
2346   REPEAT
2347     WHILE n >= 3 DO
2348       IF ODD(n) THEN
2349         el.x := x;
2350         el.y := y;
2351         el.n := n;
2352         el.adr := prvi;
2353         Push(S, el, ok);
2354         INC(x);
2355         DEC(n, 2)
2356       ELSE
2357         el.x := x;
2358         el.y := y;
2359         el.n := n;
2360         el.adr := treci;
2361         Push(S, el, ok);
2362         INC(y);
2363         DEC(n, 2)
2364       END
2365     END;
2366     rez := x+y;
2367     jos := TRUE;
2368     WHILE jos AND NOT Empty(S) DO
2369       Top(S, el, ok);
2370       Pop(S, ok);
2371       x := el.x;
2372       y := el.y;
2373       n := el.n;
2374       IF el.adr = prvi THEN
2375         el.adr := drugi;
2376         Push(S, el, ok);
2377         x := rez;
2378         DEC(n, 3);
2379         jos := FALSE
2380       ELSIF el.adr = treci THEN
2381         el.adr := cetvrti;
2382         Push(S, el, ok);
2383         y := rez;
2384         DEC(n, 3);
2385         jos := FALSE
2386       END
2387     END
2388   UNTIL Empty(S);
2389   RETURN rez
2390 END Sg;
2391
2392 BEGIN (* glavni program *)
2393   IO.WrCard(g(2, 3, 10), 3);
2394   IO.WrCard(Sg(2, 3, 10), 3);
2395 END Rek2.
2396 \end{lstlisting}
2397
2398 %\columnbreak
2399
2400 \appendix
2401
2402 \sectionbreak
2403 \pagenumbering{Roman}
2404 \input{xds-uputstvo}
2405
2406 \mainend
2407
2408
2409
2410 %%% Local Variables:
2411 %%% mode: latex
2412 %%% TeX-master: "skripta-spa1-jk"
2413 %%% End: