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 Budući da Modula 2 definiše mogućnost korišćenja \emph{otvorenih
 536   nizova}, lako je moguće definisati procedure koje kao parametre
 537 primaju bilo koji tip koji je definisan kao niz znakova.
 538
 539 \begin{codeblock}
 540    PROCEDURE ObradaStringa(str: ARRAY OF CHAR);
 541 \end{codeblock}
 542
 543 Konkretne promenljive u programu moraju biti definisane dužine.
 544
 545 Operacije nad stringovima se najčešće uvoze iz modula \kod{Str} i one
 546 su sve definisane da prihvataju \emph{otvorene nizove znakova} kao što
 547 je malopre objašnjeno.
 548
 549 Određivanje stvarne dužine stringa (tj koliko od maksimalnog
 550 kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na
 551 sledeći način:
 552 \begin{codeblock}
 553      duzina := Length(str)
 554 \end{codeblock}
 555
 556 Leksikografsko poređenje dva stringa se ne može vršiti standardnim
 557 operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o
 558 nizovima, ali značajnije i zato što se ne vidi direktno koji deo niza
 559 je popunjen ``stvarnim'' sadržajem. Za ovo se koristi komanda
 560 \kod{Compare}, koja prihvata dva stringa kao parametre, a vraća broj
 561 koji predstavlja njihov odnos. Taj broj će biti 0 ako su stringovi
 562 jednaki, veći od nule ako je prvi string ``veći'', i manji od nule ako
 563 je prvi string ``manji''.
 564
 565 \begin{codeblock}
 566   IF    Compare(str1, str2) > 0 THEN
 567      WriteString("Prvi string je veci");
 568   ELSIF Compare(str1, str2) < 0 THEN
 569      WriteString("Prvi string je manji");
 570   ELSE (* moraju biti jednaki *)
 571      WriteString("Jednaki su");
 572   END;
 573 \end{codeblock}
 574
 575 Ovo se lako pamti kad primetimo da je odnos između \kod{Compare} i 0
 576 isti kao i između prvog i drugog stringa.
 577
 578 Postoji i modul \kod{Strings} koji ima nešto drugačije definisane
 579 procedure, no na njih se sada nećemo fokusirati.
 580
 581 \sectionbreak
 582 \section{Rad sa fajlovima}
 583
 584 \subsection{Modul FIO}
 585
 586 U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
 587 sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
 588 kao što uvozimo i komande).
 589
 590 \emph{U primerima se pretpostavlja da je ``f'' tipa \kod{File},
 591   ``str'' niz znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa
 592   \kod{CARDINAL} i ``ch'' tipa \kod{CHAR}. Dodatna promenljiva ``n''
 593   tipa \kod{INTEGER} služi za formatiranje slično kao u modulu
 594   \kod{InOut}, odnosno za ispis će biti zauzeto bar ``n'' znakova.}
 595
 596
 597 Ako otvaramo već postojeći fajl, poželjno je prvo proveriti da li on
 598 postoji -- u suprotnom naš program će se srušiti pri izvršavanju.
 599 Funkcija \kod{Exists(str)} vraća da li fajl postoji.
 600
 601 Promenljiva tipa \kod{File} se mora vezati za neki fajl
 602 jednom od sledećih komandi:
 603 \begin{itemize}
 604 \item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje
 605 \item \kod{f := Create(str);} -- kreira se fajl za pisanje; ako je već
 606   postojao, biće zamenjen
 607 \item \kod{f := Append(str);} -- otvara se postojeći fajl za
 608   dopisivanje na kraj
 609 \end{itemize}
 610
 611 Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo:
 612 \begin{itemize}
 613 \item \kod{Close(f);}
 614 \end{itemize}
 615
 616 Procedure za čitanje i pisanje su vrlo slične onima iz modula
 617 \kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
 618 fajl sa kojim se radi.
 619 \begin{itemize}
 620 \item \kod{RdStr(f,str)} -- učitava ceo red u string str
 621 \item \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava
 622   znakove iz fajla dok ne naiđe na separator)
 623 \item \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se
 624   dobija kao rezultat procedure
 625 \item   \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
 626 \end{itemize}
 627
 628 Bitno je obratiti pažnju na specifičnost da postoje dve komande za
 629 čitanje stringova iz fajla i da se one ponašaju različito.  Budući da
 630 razmak spada u separatore to znači da se korišćenjem \kod{RdItem} ne
 631 može učitati string koji ima u sebi razmake.
 632
 633 Analogne su i procedure za pisanje različitih tipova u fajl:
 634 \begin{itemize}
 635 \item \kod{WrStr(f,str);}
 636 \item \kod{WrInt(f,i,n);}
 637 \item \kod{WrCard(f,c,n);}
 638 \item \kod{WrChar(f,ch);}
 639 \end{itemize}
 640
 641 Treba primetiti da ne postoje dve komande za ispis stringa u fajl --
 642 potpuno je svejedno da li on ima razmake u sebi ili ne.
 643
 644 Prelom reda se eksplicitno upisuje u fajl komandom
 645 \begin{itemize}
 646 \item \kod{WrLn(f);}.
 647 \end{itemize}
 648
 649
 650 Da bi odredili da li smo stigli do kraja fajla možemo koristiti
 651 \kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
 652 FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
 653 operacijom čitanja stigli do kraja fajla.  Ne menja joj se vrednost
 654 pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
 655 tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
 656 radu.
 657
 658 \subsubsection*{Mogući problemi}
 659
 660 U ovoj glavi će biti navedeni neki česti problemi koji se mogu desiti
 661 pri korišćenju FIO modula, a koji su vezani za konkretnu
 662 implementaciju u XDS distribuciji kompajlera.
 663
 664 \paragraph{\kod{RdStr} i drugi pozivi} Prilikom čitanja iz fajlova
 665 može doći do neobičnih rezultata ako se kombinuju pozivi \kod{RdStr}
 666 sa drugima. Problem je u različitom tretiranju separatora. Komanda
 667 \kod{RdStr} uvek čita do kraja reda i pri tome premesti poziciju za
 668 čitanje odmah iza znaka za razdvajanje redova. Ostale komande prvo
 669 preskaču separatore i čitaju sadržaj dok ne naiđu na novi separator
 670 (što može biti novi red, a može biti i razmak, tabulator i neki drugi
 671 znaci) i staju sa čitanjem \emph{pre} tog separatora. Kombinaovanje
 672 ova dva pristupa može dovesti do toga da \kod{RdStr} nakon neke druge
 673 komande učita samo kraj trenutnog reda, a ne sledeći red kao što bi
 674 bilo očekivano.
 675
 676 \paragraph{EOF i prazan red na kraju fajla} Svako čitanje iz fajla
 677 postavlja \kod{EOF} u skladu sa tim da li je komanda stigla do kraja
 678 fajla ili ne. Nažalost kod svih komandi za čitanje (osim \kod{RdStr})
 679 postoji problem ukoliko je na kraju prazan red ili neki dodatni
 680 separator. Tada učitavanje poslednjeg elementa nije zapravo došlo do
 681 kraja fajla. Ako se nakon toga proba još jedno učitavanje sa takvom
 682 komandom ona će probati da preskoči separator i da učita neki sadržaj,
 683 ali će se zaglaviti jer ne može da ga nađe. Ovo ponašanje je greška u
 684 implementaciji FIO modula u okviru XDS distribucije.
 685
 686
 687 \subsection{Zadatak: ispis sadržaja fajla na ekran}
 688
 689 Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 690
 691 \lstinputlisting[style=codeblock]{kodovi/fajlovi/ispis.mod}
 692
 693 \subsection{Zadatak: spisak studenata}
 694
 695 Napraviti program koji iz fajla učitava podatke o studentima, dodaje
 696 novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
 697 podatak o jednom studentu, redom prezime, ime i godina rođenja,
 698 razdvojeni razmacima.
 699
 700 \lstinputlisting[style=codeblock]{kodovi/fajlovi/nizslog.MOD}
 701
 702 \sectionbreak
 703 \section{Liste i pokazivači}
 704
 705 Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti
 706 procedure za dinamičko zauzimanje i oslobađanje
 707 memorije \kod{ALLOCATE} i \kod{DEALLOCATE}.
 708
 709 U kodu se mogu koristiti i skraćeni oblici \kod{NEW} i \kod{DISPOSE}
 710 koji se direktno prevode u prethodno pomenute procedure.
 711
 712 \begin{codeblock}
 713 ALLOCATE(point, SIZE(point));   (* isto kao NEW(point)     *)
 714 DEALLOCATE(point, SIZE(point)); (* isto kao DISPOSE(point) *)
 715 \end{codeblock}
 716
 717 \subsection{Zadatak: Formiranje, štampanje i brisanje listi}
 718
 719
 720 \begin{lstlisting}[style=codeblock]
 721 MODULE liste;
 722 FROM InOut IMPORT WriteString, WriteLn, WriteInt,
 723         ReadInt, ReadCard;
 724 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 725 TYPE
 726   brojevi = POINTER TO brojSlog;
 727   brojSlog = RECORD
 728       info:INTEGER;
 729       veza:brojevi;
 730   END;
 731 VAR
 732   n,i:CARDINAL;
 733   lista : brojevi;
 734   br:INTEGER;
 735
 736 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 737 (* dodaje broj br na pocetak liste *)
 738 VAR
 739   temp:brojevi;
 740 BEGIN
 741   NEW(temp);
 742   temp^.info := br;
 743   temp^.veza := lista;
 744   lista := temp;
 745 END DodajPoc;
 746
 747 PROCEDURE Stampaj(lista:brojevi);
 748 VAR
 749   temp:brojevi;
 750 BEGIN
 751   temp:=lista;
 752   WHILE temp # NIL DO
 753       WriteInt(temp^.info,0);
 754       WriteLn;
 755       temp := temp^.veza;
 756   END;
 757 END Stampaj;
 758
 759 PROCEDURE Unisti(VAR lista:brojevi);
 760 VAR
 761   temp:brojevi;
 762 BEGIN
 763   temp:=lista;
 764   WHILE temp # NIL DO
 765         lista:=lista^.veza;
 766         DISPOSE(temp);
 767         temp:=lista;
 768   END;
 769 END Unisti;
 770
 771 BEGIN
 772   lista := NIL;
 773   WriteString('unesite n (broj brojeva): ');
 774   ReadCard(n);
 775   WriteString('unesite brojeve: ');
 776   WriteLn;
 777   FOR i:= 1 TO n DO
 778       ReadInt(br);
 779       DodajPoc(lista,br);
 780   END;
 781   WriteString('sadrzaj liste:');
 782   WriteLn;
 783   Stampaj(lista);
 784   Unisti(lista);
 785   WriteString('memorija je oslobodjena');
 786   WriteLn;
 787 END liste.
 788 \end{lstlisting}
 789
 790 Alternativno je poziv \kod{DodajPoc} moguće zameniti pozivom jedne od
 791 sledeće dve procedure čime se dobija dodavanje elementa na kraj liste,
 792 ili kreiranje sortirane liste:
 793
 794 \begin{lstlisting}[style=codeblock]
 795 PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
 796 (* dodaje element na kraj liste *)
 797 VAR
 798   tekuci, temp :brojevi;
 799 BEGIN
 800   NEW(temp);
 801   temp^.info := br;
 802   temp^.veza := NIL;
 803   IF lista = NIL THEN
 804      (* prazna lista *)
 805      lista:=temp;
 806   ELSE
 807      tekuci := lista;
 808      WHILE tekuci^.veza#NIL DO
 809         tekuci:=tekuci^.veza;
 810      END;
 811      tekuci^.veza := temp;
 812   END;
 813 END DodajKraj;
 814
 815 PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
 816 (* dodaje broj tako da lista ostane sortirana
 817    (podrazumeva se da je vec sortirana) *)
 818 VAR
 819   temp, tekuci : brojevi;
 820 BEGIN
 821   NEW(temp);
 822   temp^.info:=br;
 823   temp^.veza:=NIL;
 824   IF (lista = NIL) OR (lista^.info>=br) THEN
 825   (*prazna lista ili na pocetak*)
 826     temp^.veza:=lista;
 827     lista := temp;
 828   ELSE
 829   (*negde u listi*)
 830     tekuci:= lista;
 831     WHILE (tekuci^.veza # NIL) AND
 832           (tekuci^.veza^.info<=br) DO
 833       tekuci:=tekuci^.veza;
 834     END;
 835     temp^.veza := tekuci^.veza;
 836     tekuci^.veza:=temp;
 837   END;
 838 END DodajSort;
 839 \end{lstlisting}
 840
 841 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 842
 843 \begin{lstlisting}[style=codeblock]
 844 MODULE liste2;
 845 FROM InOut IMPORT WriteString, WriteLn,
 846            WriteCard, ReadCard;
 847 FROM IO IMPORT RdKey;
 848 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 849 TYPE
 850   skupZn = SET OF CHAR;
 851   brojevi = POINTER TO brojSlog;
 852   brojSlog = RECORD
 853       info:CARDINAL;
 854       veza:brojevi;
 855   END;
 856 VAR
 857   lista : brojevi;
 858   menu,prazno:CHAR;
 859
 860 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 861 (* dodaje broj pom na pocetak liste *)
 862 VAR
 863   temp:brojevi;
 864 BEGIN
 865   (* kreiramo novi element *)
 866   NEW(temp);
 867   temp^.info := br;
 868   (* treba da pokazuje na ostatak liste *)
 869   temp^.veza := lista;
 870   (* pocetak liste je novi element *)
 871   lista := temp;
 872 END DodajPoc;
 873
 874 PROCEDURE Unos(VAR lista:brojevi);
 875 (* dodaje n brojeva u listu *)
 876 VAR
 877   n,i,br:CARDINAL;
 878 BEGIN
 879   WriteString('unesite n (broj brojeva): ');
 880   ReadCard(n);
 881   FOR i:= 1 TO n DO
 882       WriteString("unesite broj ");
 883       WriteCard(i,0);
 884       WriteString(": ");
 885       ReadCard(br);
 886       DodajPoc(lista,br);
 887   END;
 888 END Unos;
 889
 890 (* -- procedure za stampu -- *)
 891
 892 PROCEDURE Stampaj(lista:brojevi);
 893 (* stampa sadrzaj liste na ekran *)
 894 VAR
 895   temp:brojevi;
 896 BEGIN
 897   WriteLn;
 898   WriteString("Sadrzaj liste:");
 899   WriteLn;
 900   temp:=lista;
 901   WHILE temp # NIL DO
 902       WriteCard(temp^.info,0);
 903       WriteLn;
 904       temp := temp^.veza;
 905   END;
 906 END Stampaj;
 907
 908 PROCEDURE StampajK(VAR lista:brojevi);
 909 (* stampa k-ti element (k unosi korisnik) *)
 910 VAR
 911   temp:brojevi;
 912   k,brojac:CARDINAL;
 913 BEGIN
 914   WriteString("unesite redni broj elementa:");
 915   ReadCard(k);
 916   temp:=lista;
 917   brojac := 1;
 918   WHILE (temp# NIL) AND (k>brojac) DO
 919     temp:=temp^.veza;
 920     INC(brojac);
 921   END;
 922   IF (temp#NIL) THEN
 923     WriteCard(temp^.info,2);
 924   ELSE
 925     WriteString("greska! - ne postoji element");
 926     WriteString(" u listi sa rednim brojem ");
 927     WriteCard(k,2);
 928   END;
 929   WriteLn();
 930 END StampajK;
 931
 932 PROCEDURE StampajMinimum(VAR lista:brojevi);
 933 (* nalazi i stampa minimalni element liste *)
 934 VAR
 935   temp:brojevi;
 936   min:CARDINAL;
 937 BEGIN
 938   IF (lista=NIL) THEN
 939     WriteString("prazna lista!");
 940   ELSE
 941     min:=lista^.info;
 942     temp:=lista^.veza;
 943     WHILE temp # NIL DO
 944       IF temp^.info < min THEN
 945         min := temp^.info;
 946       END;
 947       temp := temp^.veza;
 948     END;
 949     WriteString("Minimalni element liste je ");
 950     WriteCard(min,0);
 951   END;
 952   WriteLn;
 953 END StampajMinimum;
 954
 955 (* -- pomocne procedure, bez ispisa  -- *)
 956
 957 PROCEDURE UListi(lista:brojevi;
 958                  br: CARDINAL):BOOLEAN;
 959 (* vraca da li se 'br' nalazi u listi 'lista' *)
 960 VAR
 961   temp:brojevi;
 962 BEGIN
 963   temp:=lista;
 964   WHILE (temp # NIL) AND (temp^.info # br) DO
 965     (* dok ne dodjemo do kraja liste
 966        ili ne nadjemo broj *)
 967       temp := temp^.veza;
 968   END;
 969   IF temp#NIL THEN
 970     (* znaci da nismo na kraju liste,
 971        tj da je nadjen broj *)
 972     RETURN TRUE;
 973   ELSE (* temp = NIL *)
 974     RETURN FALSE;
 975   END;
 976 END UListi;
 977
 978 PROCEDURE IzbaciIzListe(VAR lista:brojevi;
 979                         br: CARDINAL):BOOLEAN;
 980 (* izbacuje broj 'br' iz liste, naravno ako
 981    postoji i vraca da li je operacija uspesno
 982    obavljena *)
 983 VAR
 984   temp,prethodni:brojevi;
 985 BEGIN
 986   (* proverimo da li je prvi element *)
 987   IF (lista # NIL) AND (lista^.info = br) THEN
 988     temp:=lista;
 989     lista :=lista^.veza;
 990     DISPOSE(temp);
 991     RETURN TRUE;
 992   ELSE
 993   (* trazimo u ostatku liste *)
 994     temp:=lista;
 995     prethodni:=NIL;
 996     WHILE (temp # NIL) AND (temp^.info # br) DO
 997         (* dok ne dodjemo do kraja liste
 998            ili ne nadjemo broj *)
 999         prethodni:=temp;
1000         temp := temp^.veza;
1001     END;
1002     IF temp#NIL THEN
1003       (* znaci da nismo na kraju liste,
1004          odnosno da smo nasli broj *)
1005       (* prevezemo listu oko elementa *)
1006       prethodni^.veza:=temp^.veza;
1007       DISPOSE(temp);
1008       RETURN TRUE;
1009     ELSE
1010       RETURN FALSE;
1011     END;
1012   END;
1013 END IzbaciIzListe;
1014
1015 PROCEDURE IzbaciIzListeSve(VAR lista:brojevi;
1016                         br: CARDINAL):CARDINAL;
1017 (* izbacuje sve brojeve 'br' iz liste, naravno ako
1018    postoje i vraca koliko ih je bilo *)
1019 VAR
1020   temp,prethodni:brojevi;
1021   brojac : CARDINAL;
1022 BEGIN
1023   brojac := 0;
1024   (* uklanjamo sa pocetka koliko je potrebno *)
1025   WHILE (lista # NIL) AND (lista^.info = br) DO
1026     temp:=lista;
1027     lista :=lista^.veza;
1028     DISPOSE(temp);
1029     INC(brojac);
1030   END;
1031   (* trazimo u ostatku liste *)
1032   IF (lista # NIL) THEN
1033     temp:=lista;
1034     WHILE (temp^.veza # NIL)  DO
1035         (* idemo do poslednjeg elementa liste *)
1036         prethodni:=temp;
1037         temp := temp^.veza;
1038         IF temp^.info = br THEN
1039           (* prevezemo listu oko elementa *)
1040           prethodni^.veza:=temp^.veza;
1041           DISPOSE(temp);
1042           INC(brojac);
1043           (* vracamo se jedan korak da bi
1044           u novom krugu proverili i ovaj element *)
1045           temp := prethodni;
1046         END;
1047     END;
1048   END;
1049   RETURN brojac;
1050 END IzbaciIzListeSve;
1051
1052 (* - procedure sa interakcijom sa korisnikom - *)
1053
1054 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1055 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1056 VAR
1057   br:CARDINAL;
1058 BEGIN
1059   WriteString("unesite broj za izbacivanje: ");
1060   ReadCard(br);
1061   IF IzbaciIzListe(lista,br) THEN
1062     WriteString("broj je izbacen iz liste");
1063   ELSE
1064     WriteString("greska! - broj ne postoji");
1065   END;
1066   WriteLn;
1067 END IzbacivanjeEl;
1068
1069 PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
1070 (* izbacuje sve primeke unetog broj iz liste
1071    koristeci proceduru IzbaciIzListeSve *)
1072 VAR
1073   br, ukupno:CARDINAL;
1074 BEGIN
1075   WriteString("unesite broj za izbacivanje: ");
1076   ReadCard(br);
1077   ukupno := IzbaciIzListeSve(lista,br);
1078   WriteString("Iz liste je izbaceno ");
1079   WriteCard(ukupno,3);
1080   WriteString(" el.");
1081   WriteLn;
1082 END IzbacivanjeElSvi;
1083
1084 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1085 (* izbacuje k-ti element iz liste *)
1086 VAR
1087   temp,tekuci:brojevi;
1088   k,brojac:CARDINAL;
1089 BEGIN
1090   IF lista=NIL THEN
1091     WriteString("lista je prazna, nema ");
1092     WriteString("elemenata za izbacivanje");
1093   ELSE
1094     WriteString("unesite redni broj elementa");
1095     WriteString(" koji zelite izbaciti:");
1096     ReadCard(k);
1097     IF k=1 THEN (*izbacivanje prvog *)
1098       temp:=lista;
1099       lista := lista^.veza;
1100       DISPOSE(temp);
1101     ELSE
1102       tekuci := lista;
1103       brojac := 2; (*gledamo jedan unapred*)
1104       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1105         (* idemo kroz listu do k-tog el *)
1106         tekuci:=tekuci^.veza;
1107         INC(brojac);
1108       END;
1109       IF (tekuci^.veza#NIL) THEN
1110          (* pamtimo element za brisanje *)
1111          temp:=tekuci^.veza;
1112          (* prevezujemo listu oko njega*)
1113          tekuci^.veza:=tekuci^.veza^.veza;
1114          DISPOSE(temp);
1115       ELSE
1116         WriteString("greska! - ne postoji el ");
1117         WriteString("u listi sa rednim brojem ");
1118         WriteCard(k,2);
1119       END;
1120       WriteLn();
1121     END;
1122   END;
1123 END IzbacivanjeK;
1124
1125 PROCEDURE Pretraga(lista:brojevi);
1126 (* provera da li se uneti broj nalazi u listi *)
1127 VAR
1128   br:CARDINAL;
1129 BEGIN
1130   WriteString("unesite trazeni broj");
1131   ReadCard(br);
1132   IF UListi(lista,br) THEN
1133     WriteString("broj postoji u listi");
1134   ELSE
1135     WriteString("broj ne postoji u listi");
1136   END;
1137   WriteLn;
1138 END Pretraga;
1139
1140 (* -- oslobadjanje memorije -- *)
1141
1142 PROCEDURE Unisti(VAR lista:brojevi);
1143 VAR
1144   temp:brojevi;
1145 BEGIN
1146   temp:=lista;
1147   WHILE temp # NIL DO
1148         lista:=lista^.veza;
1149         DISPOSE(temp);
1150         temp:=lista;
1151   END;
1152 END Unisti;
1153
1154 BEGIN
1155   (* pocinjemo od prazne liste *)
1156   lista := NIL;
1157   REPEAT
1158      WriteLn;
1159      WriteString("Ilustracija rada sa");
1160      WriteString(" listama brojeva");
1161      WriteLn;
1162      WriteString("=============================");
1163      WriteLn;
1164      WriteString("s - Stampa");WriteLn;
1165      WriteString("u - Unos");WriteLn;
1166      WriteString("i - Izbacivanje br iz liste");
1167      WriteLn;
1168      WriteString("v - izbacivanje svih br iz liste");
1169      WriteLn;
1170      WriteString("e - izbacivanje k-tog El.");
1171      WriteLn;
1172      WriteString("k - stampanje k-tog elementa");
1173      WriteLn;
1174      WriteString("m - Minimalni broj u listi");
1175      WriteLn;
1176      WriteString("p - Pretraga el. u listi");
1177      WriteLn;
1178      WriteLn;
1179      WriteString("q - kraj rada (Quit)");WriteLn;
1180       REPEAT
1181         menu := CAP(RdKey());
1182       UNTIL menu IN skupZn{'S','U','E','I','V',
1183                            'M','K','P','Q'};
1184       IF menu#'Q' THEN
1185         CASE menu OF
1186          'S' : Stampaj(lista);|
1187          'U' : Unos(lista);|
1188          'I' : IzbacivanjeEl(lista);|
1189          'V' : IzbacivanjeElSvi(lista);|
1190          'E' : IzbacivanjeK(lista);|
1191          'K' : StampajK(lista); |
1192          'M' : StampajMinimum(lista); |
1193          'P' : Pretraga(lista);|
1194         END;
1195         WriteLn;
1196         WriteString("--- pritisnite bilo koji ");
1197         WriteString("taster za povratak u meni");
1198         prazno:=RdKey();
1199       ELSE
1200         WriteString("Kraj rada")
1201       END;
1202       WriteLn;
1203   UNTIL menu='Q';
1204   Unisti(lista);
1205 END liste2.
1206 \end{lstlisting}
1207
1208
1209 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1210
1211 \begin{lstlisting}[style=codeblock]
1212 MODULE Radnici;
1213
1214 FROM InOut IMPORT WriteString, ReadString,
1215            WriteLn, WriteCard, ReadCard, Done;
1216 FROM IO IMPORT RdKey;
1217 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1218
1219 TYPE
1220   skupZn = SET OF CHAR;
1221   str = ARRAY [1..20] OF CHAR;
1222   radnici = POINTER TO slog;
1223   slog = RECORD
1224            ime, prez : str;
1225            broj : CARDINAL;
1226            sled : radnici
1227          END;
1228 VAR
1229   meni, pom : CHAR;
1230   rad : radnici;
1231
1232   PROCEDURE Clear();
1233   VAR
1234     br: CARDINAL;
1235   BEGIN
1236     FOR br:=1 TO 100 DO
1237       WriteLn;
1238     END;
1239   END Clear;
1240
1241   PROCEDURE Spisak(rad : radnici);
1242   BEGIN
1243     WHILE rad # NIL DO
1244       WriteString(rad^.ime);
1245       WriteString(' ');
1246       WriteString(rad^.prez);
1247       WriteCard(rad^.broj, 8);
1248       WriteLn;
1249       rad := rad^.sled
1250     END
1251   END Spisak;
1252
1253   PROCEDURE Zaposli(VAR rad : radnici);
1254   VAR
1255     novi, tek : radnici;
1256     nadjen : BOOLEAN;
1257   BEGIN
1258     NEW(novi);
1259     REPEAT
1260       WriteString('Ime, prezime i jedinstveni');
1261       WriteString(' broj novog radnika: ');
1262       WriteLn;
1263       ReadString(novi^.ime);
1264       ReadString(novi^.prez);
1265       ReadCard(novi^.broj);
1266       nadjen := FALSE;
1267       tek := rad;
1268       WHILE NOT nadjen AND (tek # NIL) AND
1269             (tek^.broj <= novi^.broj) DO
1270         IF novi^.broj = tek^.broj THEN
1271           nadjen := TRUE
1272         ELSE
1273           tek := tek^.sled
1274         END
1275       END
1276     UNTIL Done AND NOT nadjen;
1277     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1278       novi^.sled := rad;
1279       rad := novi
1280     ELSE
1281       tek := rad;
1282       WHILE (tek^.sled # NIL) AND
1283             (tek^.sled^.broj < novi^.broj) DO
1284         tek := tek^.sled
1285       END;
1286       novi^.sled := tek^.sled;
1287       tek^.sled := novi
1288     END
1289   END Zaposli;
1290
1291   PROCEDURE Otpusti(VAR rad : radnici);
1292   VAR
1293     tek, pom : radnici;
1294     br : CARDINAL;
1295   BEGIN
1296     REPEAT
1297       WriteLn;
1298       WriteString('Unesite redni broj radnika:');
1299       ReadCard(br)
1300     UNTIL Done;
1301     WriteLn;
1302     IF rad = NIL THEN
1303       WriteString('Greska.')
1304     ELSIF br = rad^.broj THEN
1305       pom := rad;
1306       rad := rad^.sled;
1307       DISPOSE(pom)
1308     ELSE
1309       tek := rad;
1310       WHILE (tek^.sled # NIL) AND
1311             (tek^.sled^.broj < br) DO
1312         tek := tek^.sled
1313       END;
1314       IF (tek^.sled = NIL) OR
1315          (tek^.sled^.broj > br) THEN
1316         WriteString('Greska.')
1317       ELSE
1318         pom := tek^.sled;
1319         tek^.sled := tek^.sled^.sled;
1320         DISPOSE(pom)
1321       END
1322     END
1323   END Otpusti;
1324
1325   PROCEDURE Inform(rad : radnici);
1326   VAR
1327     br : CARDINAL;
1328   BEGIN
1329     REPEAT
1330       WriteLn;
1331       WriteString('Unesite redni broj radnika:');
1332       ReadCard(br)
1333     UNTIL Done;
1334     WriteLn;
1335     WHILE (rad # NIL) AND (rad^.broj < br) DO
1336       rad := rad^.sled
1337     END;
1338     IF (rad = NIL) OR (rad^.broj # br) THEN
1339       WriteString('Greska.')
1340     ELSE
1341       WriteString(rad^.ime);
1342       WriteString(' ');
1343       WriteString(rad^.prez)
1344     END
1345   END Inform;
1346
1347   PROCEDURE Bankrot(VAR rad : radnici);
1348   VAR
1349     pom : radnici;
1350   BEGIN
1351     WHILE rad # NIL DO
1352       pom := rad;
1353       rad := rad^.sled;
1354       DISPOSE(pom)
1355     END
1356   END Bankrot;
1357
1358 BEGIN
1359   rad := NIL;
1360   REPEAT
1361     Clear;
1362     WriteString('s - spisak svih zaposlenih');
1363     WriteLn;
1364     WriteString('z - zaposljavanje radnika');
1365     WriteLn;
1366     WriteString('o - otpustanje radnika');
1367     WriteLn;
1368     WriteString('i - informacije o radniku');
1369     WriteLn;
1370     WriteString('b - bankrot firme');
1371     WriteLn;
1372     WriteString('k - kraj rada');
1373     WriteLn;
1374     REPEAT
1375       meni := RdKey();
1376     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1377                               'I', 'B', 'K'};
1378     Clear;
1379     IF CAP(meni) # 'K' THEN
1380       CASE CAP(meni) OF
1381         'S' : Spisak(rad)|
1382         'Z' : Zaposli(rad)|
1383         'O' : Otpusti(rad)|
1384         'I' : Inform(rad)|
1385         'B' : Bankrot(rad)
1386       END;
1387       WriteLn;
1388       WriteString('-- pritisnite bilo koji ');
1389       WriteString('taster za nastavak --');
1390       pom := RdKey()
1391     END
1392   UNTIL CAP(meni) = 'K'
1393 END Radnici.
1394 \end{lstlisting}
1395
1396 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1397
1398 \begin{lstlisting}[style=codeblock]
1399   PROCEDURE Spisak(rad : radnici);
1400   BEGIN
1401     IF rad # NIL THEN
1402       WriteString(rad^.ime);
1403       WriteString(' ');
1404       WriteString(rad^.prez);
1405       WriteCard(rad^.broj, 8);
1406       WriteLn;
1407       Spisak(rad^.sled)
1408     END
1409   END Spisak;
1410 \end{lstlisting}
1411
1412 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1413   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1414   težini}
1415
1416 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1417 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1418 uređenje i po visini i po težini.
1419
1420 \begin{lstlisting}[style=codeblock]
1421 MODULE VisTez;
1422 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1423 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1424 FROM SYSTEM IMPORT TSIZE;
1425 TYPE
1426   pok = POINTER TO element;
1427   element = RECORD
1428               visina, tezina : CARDINAL;
1429               Vveza, Tveza : pok
1430             END;
1431 VAR
1432   pocV, pocT : pok;
1433   vis, tez : CARDINAL;
1434 PROCEDURE Ispisi(pocV, pocT : pok);
1435 VAR
1436   tek : pok;
1437 BEGIN
1438   tek := pocV;
1439   WrStr('Po visini:');
1440   WrLn;
1441   WHILE tek # NIL DO
1442     WrCard(tek^.visina, 6);
1443     tek := tek^.Vveza
1444   END;
1445   WrLn;
1446   tek := pocT;
1447   WrStr('Po tezini:');
1448   WrLn;
1449   WHILE tek # NIL DO
1450     WrCard(tek^.tezina,6);
1451     tek := tek^.Tveza
1452   END
1453 END Ispisi;
1454
1455 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1456                 vis, tez : CARDINAL);
1457 VAR
1458   novi, tek, iza : pok;
1459   nadjen : BOOLEAN;
1460 BEGIN
1461   IF pocV = NIL THEN
1462     ALLOCATE(pocV, TSIZE(element));
1463     pocV^.visina := vis;
1464     pocV^.tezina := tez;
1465     pocV^.Vveza := NIL;
1466     pocV^.Tveza := NIL;
1467     pocT := pocV
1468   ELSE
1469     ALLOCATE(novi, TSIZE(element));
1470     novi^.visina := vis;
1471     novi^.tezina := tez;
1472     tek := pocV;
1473     nadjen := FALSE;
1474     WHILE (tek # NIL) AND NOT nadjen DO
1475       nadjen := vis <= tek^.visina;
1476       IF NOT nadjen THEN
1477         iza := tek;
1478         tek := tek^.Vveza
1479       END
1480     END;
1481     novi^.Vveza := tek;
1482     IF tek = pocV THEN
1483       pocV := novi
1484     ELSE
1485       iza^.Vveza := novi
1486     END;
1487     tek := pocT;
1488     nadjen := FALSE;
1489     WHILE (tek # NIL) AND NOT nadjen DO
1490       nadjen := tez <= tek^.tezina;
1491       IF NOT nadjen THEN
1492         iza := tek;
1493         tek := tek^.Tveza
1494       END
1495     END;
1496     novi^.Tveza := tek;
1497     IF tek = pocT THEN
1498       pocT := novi
1499     ELSE
1500       iza^.Tveza := novi
1501     END
1502   END
1503 END Ubaci;
1504
1505 BEGIN
1506   pocV := NIL;
1507   pocT := NIL;
1508   WrStr('Unesite visinu ---- ');
1509   vis := RdCard();
1510   WHILE vis > 0 DO
1511     WrStr('Unesite tezinu ---- ');
1512     tez := RdCard();
1513     Ubaci(pocV, pocT, vis, tez);
1514     WrLn;
1515     WrStr('Unesite visinu ---- ');
1516     vis := RdCard()
1517   END;
1518   WrLn;
1519   Ispisi(pocV, pocT)
1520 END VisTez.
1521 \end{lstlisting}
1522
1523 \sectionbreak
1524 \section{Polinomi preko listi}
1525
1526 \subsection{Moduli}
1527
1528 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1529 \kod{Polinom} je definisan u globalnom modulu. Redosled parametara kod
1530 svih procedura je takav da varijabilni parametri dolaze na kraju.
1531
1532 \paragraph{PolinomL.DEF} \
1533
1534 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.DEF}
1535
1536 \paragraph{PolinomL.MOD} \
1537
1538 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.MOD}
1539
1540 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1541
1542 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1543
1544 \lstinputlisting[style=codeblock]{kodovi/polinomi/polinom.MOD}
1545
1546 \subsection{Zadatak: Suma k polinoma}
1547
1548 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1549 toga izracunava njihovu sumu
1550
1551 \lstinputlisting[style=codeblock]{kodovi/polinomi/PolSuma.MOD}
1552
1553 \sectionbreak
1554 \section{Stek i red opsluživanja}
1555
1556 \subsection{Primer: osnovno korišćenje steka i reda opsluživanja}
1557
1558 \lstinputlisting[style=codeblock]{kodovi/stek-redopsl/stekred.mod}
1559
1560 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
1561
1562 \begin{lstlisting}[style=codeblock]
1563 DEFINITION MODULE QueueInfo;
1564 CONST
1565   Maxqueue = 100;
1566 TYPE
1567   InfoTip = CHAR;
1568
1569 END QueueInfo.
1570
1571 IMPLEMENTATION MODULE QueueInfo;
1572 END QueueInfo.
1573
1574 DEFINITION MODULE RedOpsl1;
1575 FROM QueueInfo IMPORT InfoTip,Maxqueue;
1576 TYPE
1577   Niz = ARRAY[1..Maxqueue] OF InfoTip;
1578   RedOpslTip = RECORD
1579         Prvi, Zadnji : CARDINAL;
1580         Element : Niz
1581   END;
1582
1583 PROCEDURE MakeNull(VAR q : RedOpslTip);
1584 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1585 PROCEDURE First(VAR q : RedOpslTip;
1586                 VAR x : InfoTip;
1587                 VAR ok : BOOLEAN);
1588 PROCEDURE PopFirst(VAR q : RedOpslTip;
1589                    VAR ok : BOOLEAN);
1590 PROCEDURE AddRear(VAR q : RedOpslTip;
1591                   x : InfoTip;
1592                   VAR ok : BOOLEAN);
1593
1594 END RedOpsl1.
1595
1596 IMPLEMENTATION MODULE RedOpsl1;
1597 FROM QueueInfo IMPORT Maxqueue,InfoTip;
1598
1599 PROCEDURE MakeNull(VAR q : RedOpslTip);
1600 BEGIN
1601   WITH q DO
1602     Prvi := 0;
1603     Zadnji := 0
1604   END
1605 END MakeNull;
1606
1607 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1608 BEGIN
1609   RETURN q.Zadnji = 0
1610 END Empty;
1611
1612
1613 PROCEDURE First(VAR q : RedOpslTip;
1614                 VAR x : InfoTip;
1615                 VAR ok : BOOLEAN);
1616 BEGIN
1617   IF Empty(q) THEN
1618     ok := FALSE
1619   ELSE
1620     ok := TRUE;
1621     WITH q DO
1622       x := Element[Prvi]
1623     END
1624   END
1625 END First;
1626
1627 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
1628 BEGIN
1629   IF i = Maxqueue THEN
1630     RETURN 1
1631   ELSE
1632     RETURN i+1
1633   END
1634 END AddOne;
1635
1636 PROCEDURE PopFirst(VAR q : RedOpslTip;
1637                    VAR ok : BOOLEAN);
1638 BEGIN
1639   IF Empty(q) THEN
1640     ok := FALSE
1641   ELSE
1642     ok := TRUE;
1643     WITH q DO
1644       IF Prvi = Zadnji THEN
1645         MakeNull(q)
1646       ELSE
1647         Prvi := AddOne(Prvi)
1648       END
1649     END
1650   END
1651 END PopFirst;
1652
1653 PROCEDURE AddRear(VAR q : RedOpslTip;
1654                   x : InfoTip;
1655                   VAR ok : BOOLEAN);
1656 BEGIN
1657   WITH q DO
1658     IF AddOne(Zadnji) = Prvi THEN
1659       ok := FALSE
1660     ELSE
1661       ok := TRUE;
1662       IF Empty(q) THEN
1663         Prvi := 1;
1664         Zadnji := 1
1665       ELSE
1666         Zadnji := AddOne(Zadnji)
1667       END;
1668       Element[Zadnji] := x
1669     END
1670   END
1671 END AddRear;
1672
1673 END RedOpsl1.
1674
1675 MODULE Bafer;
1676 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
1677 FROM FIO IMPORT File,WrChar, Create, Close;
1678 IMPORT IO;
1679
1680 CONST
1681   ImeIzlaza = 'izlaz.txt';
1682
1683 VAR
1684   izlaz : File;
1685   znak : CHAR;
1686   buffer : RedOpslTip;
1687
1688 PROCEDURE IsprazniBafer(VAR dat : File;
1689                         VAR buf : RedOpslTip);
1690 VAR
1691   znak : CHAR;
1692   ok : BOOLEAN;
1693 BEGIN
1694   WHILE NOT Empty(buf) DO
1695     First(buf, znak, ok);
1696     PopFirst(buf, ok);
1697     WrChar(dat, znak)
1698   END
1699 END IsprazniBafer;
1700
1701 PROCEDURE BaferWrite(VAR dat : File;
1702                      VAR buf : RedOpslTip;
1703                      znak : CHAR);
1704 VAR
1705   ok : BOOLEAN;
1706 BEGIN
1707   AddRear(buf, znak, ok);
1708   IF NOT ok THEN
1709     IsprazniBafer(dat, buf);
1710     AddRear(buf, znak, ok)
1711   END
1712 END BaferWrite;
1713
1714 BEGIN
1715   izlaz := Create(ImeIzlaza);
1716   MakeNull(buffer);
1717   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
1718   IO.WrStr(ImeIzlaza);
1719   IO.WrChar('.');
1720   IO.WrLn;
1721   IO.WrStr('Unos zavrsite tackom.');
1722   IO.WrLn;
1723   znak := IO.RdChar();
1724   WHILE znak # '.' DO
1725     BaferWrite(izlaz, buffer, znak);
1726     znak := IO.RdChar();
1727   END;
1728   IsprazniBafer(izlaz, buffer);
1729   Close(izlaz)
1730 END Bafer.
1731 \end{lstlisting}
1732
1733 \subsection%
1734 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
1735
1736 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
1737 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
1738
1739 \begin{codeblock}
1740 DEFINITION MODULE Stek;
1741 CONST
1742   Maxstack = 100;
1743 TYPE
1744   Niz = ARRAY [1..Maxstack] OF CHAR;
1745   StekTip = RECORD
1746             Top : CARDINAL;
1747             Element : Niz
1748           END;
1749 PROCEDURE MakeNull(VAR s : StekTip);
1750 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1751
1752 PROCEDURE Top(VAR s : StekTip;
1753               VAR x : CHAR;
1754               VAR ok : BOOLEAN);
1755 PROCEDURE Pop(VAR s : StekTip;
1756               VAR ok : BOOLEAN);
1757 PROCEDURE Push(VAR s : StekTip;
1758                x : CHAR;
1759                VAR ok : BOOLEAN);
1760 END Stek.
1761
1762
1763 IMPLEMENTATION MODULE Stek;
1764
1765 PROCEDURE MakeNull(VAR s : StekTip);
1766 BEGIN
1767   s.Top := 0
1768 END MakeNull;
1769
1770 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1771 BEGIN
1772   RETURN s.Top = 0
1773 END Empty;
1774
1775 PROCEDURE Top(VAR s : StekTip;
1776               VAR x : CHAR;
1777               VAR ok : BOOLEAN);
1778 BEGIN
1779   IF Empty(s) THEN
1780     ok := FALSE
1781   ELSE
1782     ok := TRUE;
1783     WITH s DO
1784       x := Element[Top]
1785     END
1786   END
1787 END Top;
1788
1789 PROCEDURE Pop(VAR s : StekTip;
1790               VAR ok : BOOLEAN);
1791 BEGIN
1792   IF Empty(s) THEN
1793     ok := FALSE
1794   ELSE
1795     ok := TRUE;
1796     DEC(s.Top)
1797   END
1798 END Pop;
1799
1800 PROCEDURE Push(VAR s : StekTip;
1801                x : CHAR;
1802                VAR ok : BOOLEAN);
1803 BEGIN
1804   WITH s DO
1805     IF Top = Maxstack THEN
1806       ok := FALSE
1807     ELSE
1808       ok := TRUE;
1809       INC(Top);
1810       Element[Top] := x
1811     END
1812   END
1813 END Push;
1814 END Stek.
1815
1816 MODULE wcw;
1817 (* Da li rec pripada gramatici wcw+. *)
1818 FROM Stek IMPORT StekTip, MakeNull, Empty,
1819                  Top, Pop, Push;
1820 FROM InOut IMPORT Read, Write, WriteString, EOL;
1821 TYPE
1822   slova = SET OF CHAR;
1823 VAR
1824   S : StekTip;
1825   Ch, C : CHAR;
1826   ok : BOOLEAN;
1827 BEGIN
1828   MakeNull(S);
1829   Read(Ch);
1830   ok := TRUE;
1831   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
1832     Push(S, Ch, ok);
1833     Read(Ch);
1834   END;
1835   IF NOT ok THEN
1836     WriteString('Greska - mali stek')
1837   ELSIF Ch # 'c' THEN
1838     WriteString('Pogresan string')
1839   ELSE
1840     Read(Ch);
1841     WHILE ok AND (Ch # EOL) DO
1842       Top(S, C, ok);
1843       ok := ok AND (C = Ch);
1844       IF ok THEN
1845         Pop(S, ok);
1846         Read(Ch);
1847       END
1848     END;
1849     IF NOT (ok AND Empty(S)) THEN
1850       WriteString('Pogresan string')
1851     ELSE
1852       WriteString('String pripada jeziku L')
1853     END
1854   END
1855 END wcw.
1856 \end{codeblock}
1857
1858 \manbreakJK
1859
1860 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
1861
1862
1863 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
1864 koji figurišu u izrazu su jednocifreni.
1865
1866 \begin{lstlisting}[style=codeblock]
1867 MODULE PostFix;
1868
1869 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
1870 FROM InOut IMPORT Read, Write, WriteInt, EOL;
1871 TYPE
1872   slova = SET OF CHAR;
1873 VAR
1874   S : StekTip;
1875   Ch : CHAR;
1876   Op1, Op2 : INTEGER;
1877   ok : BOOLEAN;
1878 PROCEDURE Conv(Ch : CHAR) : INTEGER;
1879 BEGIN
1880   RETURN  ORD(Ch) - ORD('0')
1881 END Conv;
1882
1883 BEGIN
1884   MakeNull(S);
1885   Read(Ch);
1886   WHILE Ch # EOL DO
1887     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
1888       Top(S, Op2, ok);
1889       Pop(S, ok);
1890       Top(S, Op1, ok);
1891       Pop(S, ok);
1892       CASE Ch OF
1893         '+' : Op1 := Op1 + Op2 |
1894         '-' : Op1 := Op1 - Op2 |
1895         '*' : Op1 := Op1 * Op2 |
1896         '/' : Op1 := Op1 DIV Op2 |
1897         '%' : Op1 := Op1 MOD Op2
1898       END;
1899       Push(S, Op1, ok)
1900     ELSE
1901       Push(S, Conv(Ch), ok)
1902     END;
1903     Read(Ch);
1904   END;
1905   Top(S, Op1, ok);
1906   Write('=');
1907   WriteInt(Op1,5)
1908 END PostFix.
1909 \end{lstlisting}
1910
1911 \sectionbreak
1912 \section{Simulacija rekurzije}
1913
1914
1915 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
1916 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
1917
1918 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
1919 mesta poziva, a u skladu sa tim se kreira InfoTip.
1920
1921 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
1922 rekurzivnih poziva.
1923
1924 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
1925 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
1926 pozivi.
1927
1928 \begin{lstlisting}
1929 MakeNull(S);
1930 REPEAT
1931   WHILE treba_rekurzija DO
1932     -prepisati sve od pocetka originalne
1933      procedure do prvog rekurzivnog poziva
1934     -staviti na stek potrebne
1935      lokalne promenljive, parametre procedure i
1936      adresu mesta poziva
1937     -podesiti vrednosti parametara da budu
1938      kao u rekurzivnom pozivu procedure
1939   END;
1940   trivijalan poziv
1941   umesto RETURN x pisati rez := x
1942   jos := TRUE;
1943   WHILE jos AND NOT Empty(S) DO
1944     Top(S, el, ok);
1945     Pop(S, ok);
1946     -restauriramo vrednosti sa steka
1947     -u zavisnosti od adrese poziva nastavimo
1948      prepisivanje originalne procedure sa
1949      tog mesta
1950     -ako se dodje do novog rek. poziva tada:
1951        -sacuvati na steku vrednosti
1952        -podesiti vrednosti parametara da budu
1953         kao u rekurzivnom pozivu procedure
1954        -ici na pocetak koda
1955         (ovo se postize sa jos := FALSE)
1956     -inace
1957        ako se naidje na RETURN x pisati rez := x
1958   END
1959 UNTIL Empty(S);
1960 \end{lstlisting}
1961
1962 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
1963
1964 \subsection*{ZADACI}
1965
1966 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
1967
1968 \subsection{Primer 1 -- faktorijel}
1969
1970
1971 \begin{lstlisting}[style=codeblock]
1972 MODULE Fakto;
1973 (* InfoTip = CARDINAL; *)
1974
1975 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
1976 FROM StekC IMPORT StekTip, MakeNull, Empty,
1977                   Top, Pop, Push;
1978 VAR
1979   n : CARDINAL;
1980 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
1981 BEGIN
1982   IF n <= 1 THEN
1983     RETURN 1
1984   ELSE
1985     RETURN n * RFakto(n-1)
1986   END
1987 END RFakto;
1988
1989
1990 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
1991 VAR
1992   s : StekTip;
1993   rez : CARDINAL;
1994   OK : BOOLEAN;
1995 BEGIN
1996   MakeNull(s);
1997   WHILE n > 1 DO
1998     Push(s,n,OK);
1999     DEC(n)
2000   END;
2001   rez := 1;
2002   WHILE NOT Empty(s) DO
2003     Top(s, n, OK);
2004     Pop(s, OK);
2005     rez := n * rez
2006   END;
2007   RETURN rez
2008 END SFakto;
2009
2010 BEGIN
2011   WrStr('n = ');
2012   n := RdCard();
2013   WrLn
2014   WrStr('n! = ');
2015   WrCard(RFakto(n), 1);
2016   WrStr(' = ');
2017   WrCard(SFakto(n), 1)
2018 END Fakto.
2019 \end{lstlisting}
2020
2021 \subsection{Primer 2 -- stepenovanje}
2022
2023 \begin{lstlisting}[style=codeblock]
2024 MODULE Step;
2025 (* InfoTip = RECORD
2026                 x : REAL;
2027                 n : CARDINAL;
2028                 adr : (par, nepar)
2029              END;
2030 *)
2031 FROM IO IMPORT WrStr, WrLn, WrReal,
2032         RdReal, RdCard;
2033 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2034              Top, Pop, Push, InfoTip, AdrTip;
2035 VAR
2036   n : CARDINAL;
2037   x : REAL;
2038
2039 PROCEDURE Sqr(y : REAL) : REAL;
2040 BEGIN
2041   RETURN y * y
2042 END Sqr;
2043
2044 PROCEDURE RStep(x : REAL;
2045                 n : CARDINAL) : REAL;
2046 BEGIN
2047   IF n = 0 THEN
2048     RETURN 1.
2049   ELSIF ODD(n) THEN
2050     RETURN x * Sqr( RStep(x, n DIV 2) )
2051   ELSE
2052     RETURN Sqr( RStep(x, n DIV 2) )
2053   END
2054 END RStep;
2055
2056 PROCEDURE SStep(x : REAL;
2057                 n : CARDINAL ) : REAL;
2058 VAR
2059   s : StekTip;
2060   OK : BOOLEAN;
2061   rez : REAL;
2062   el : InfoTip;
2063 BEGIN
2064   MakeNull(s);
2065   WHILE n > 0 DO
2066     el.x := x;
2067     el.n := n;
2068     IF ODD(n) THEN
2069       el.adr := nepar;
2070     ELSE
2071       el.adr := par
2072     END;
2073     Push(s,el,OK);
2074     n := n DIV 2
2075   END;
2076   rez := 1.;
2077   WHILE NOT Empty(s) DO
2078     Top(s, el, OK);
2079     Pop(s, OK);
2080     x := el.x;
2081     n := el.n;
2082     IF el.adr = nepar THEN
2083       rez := x * Sqr(rez)
2084     ELSE
2085       rez := Sqr(rez)
2086     END
2087   END;
2088   RETURN rez
2089 END SStep;
2090
2091 BEGIN
2092   WrStr('x =? ');
2093   x := RdReal();
2094   WrLn;
2095   WrStr('n =? ');
2096   n := RdCard();
2097   WrStr('x^n = ');
2098   WrReal(RStep(x, n), 10, 1);
2099   WrStr(' = ');
2100   WrReal(SStep(x, n), 10, 1)
2101 END Step.
2102 \end{lstlisting}
2103
2104 \subsection{Primer 3 -- Fibonači}
2105
2106 \begin{lstlisting}[style=codeblock]
2107 MODULE Fib;
2108 (* InfoTip = RECORD
2109                 n : CARDINAL;
2110                 PrviSab : CARDINAL;
2111                 adr : (prvi, drugi)
2112              END;
2113 *)
2114
2115 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2116 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2117        Top, Pop, Push, InfoTip, AdrTip;
2118 VAR
2119   n : CARDINAL;
2120
2121 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2122 BEGIN
2123   IF n <= 1 THEN
2124     RETURN n
2125   ELSE
2126     RETURN RFib(n-1) + RFib(n-2)
2127   END
2128 END RFib;
2129
2130 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2131 VAR
2132   s : StekTip;
2133   OK, jos : BOOLEAN;
2134   rez, PrviSab : CARDINAL;
2135   el : InfoTip;
2136 BEGIN
2137   MakeNull(s);
2138   REPEAT
2139     WHILE n > 1 DO
2140       el.n := n;
2141       el.adr := prvi;
2142       Push(s,el,OK);
2143       DEC(n)
2144     END;
2145     rez := (n);
2146     jos := TRUE;
2147     WHILE (NOT Empty(s)) AND jos DO
2148       Top(s, el, OK);
2149       Pop(s, OK);
2150       n := el.n;
2151       IF el.adr = prvi THEN
2152         PrviSab := rez;
2153         el.n := n;
2154         el.adr := drugi;
2155         el.PrviSab := PrviSab;
2156         Push(s, el, OK);
2157         DEC(n, 2);
2158         jos := FALSE
2159       ELSE
2160         PrviSab := el.PrviSab;
2161         rez := PrviSab + rez
2162       END
2163     END
2164   UNTIL Empty(s);
2165   RETURN rez
2166 END SFib;
2167
2168 BEGIN
2169   WrStr('n =? ');
2170   n := RdCard();
2171   WrStr('F(n) = ');
2172   WrCard(RFib(n), 1);
2173   WrStr(' = ');
2174   WrCard(SFib(n), 1)
2175 END Fib.
2176 \end{lstlisting}
2177
2178 \subsection{Primer 4 -- faktorijel 2}
2179
2180
2181 \begin{lstlisting}[style=codeblock]
2182 MODULE Faktor;
2183 (* InfoTip = CARDINAL; *)
2184 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2185 FROM StekC IMPORT StekTip, MakeNull, Empty,
2186                   Top, Pop, Push;
2187 VAR
2188   n,rez : CARDINAL;
2189
2190 PROCEDURE RFakto(n : CARDINAL;
2191                  VAR rez : CARDINAL);
2192 BEGIN
2193   IF n = 0 THEN
2194     rez := 1
2195   ELSE
2196     RFakto(n-1, rez);
2197     rez := n * rez
2198   END
2199 END RFakto;
2200
2201 PROCEDURE SFakto(n : CARDINAL;
2202                  VAR rez : CARDINAL);
2203 VAR
2204   s : StekTip;
2205   OK : BOOLEAN;
2206 BEGIN
2207   MakeNull(s);
2208   WHILE n > 0 DO
2209     Push(s,n,OK);
2210     DEC(n)
2211   END;
2212   rez := 1;
2213   WHILE NOT Empty(s) DO
2214     Top(s, n, OK);
2215     Pop(s, OK);
2216     rez := n * rez
2217   END
2218 END SFakto;
2219
2220 BEGIN
2221   WrStr('n =? ');
2222   n := RdCard();
2223   WrLn;
2224   WrStr('n! = ');
2225   RFakto(n, rez);
2226   WrCard(rez, 1);
2227   WrStr(' = ');
2228   SFakto(n, rez);
2229   WrCard(rez, 1)
2230 END Faktor.
2231 \end{lstlisting}
2232
2233 \subsection{Primer 5 (ispitni)}
2234
2235
2236 \begin{lstlisting}[style=codeblock]
2237 MODULE Rek1;
2238 (* InfoTip = RECORD
2239                 d, g, m1, m2 : INTEGER;
2240                 adr : (prvi, drugi)
2241              END;
2242 *)
2243 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2244          MakeNull, Empty, Top, Pop, Push;
2245 IMPORT IO;
2246 VAR
2247   X : ARRAY [1..20] OF INTEGER;
2248
2249 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2250 VAR
2251   m1, m2 : INTEGER;
2252 BEGIN
2253   IF d>g THEN
2254     RETURN MIN(INTEGER)
2255   ELSIF d=g THEN
2256     RETURN X[d]
2257   ELSE
2258     m1 := Max(d, (d+g) DIV 2);
2259     m2 := Max((d+g) DIV 2 +1, g);
2260     IF m1 > m2 THEN
2261       RETURN m1
2262     ELSE
2263       RETURN m2
2264     END
2265   END
2266 END Max;
2267
2268 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2269 VAR
2270   S : StekTip;
2271   el : InfoTip;
2272   ok, jos : BOOLEAN;
2273   m1, m2, rez : INTEGER;
2274 BEGIN
2275   MakeNull(S);
2276   REPEAT
2277     WHILE d<g DO
2278       el.d := d;
2279       el.g := g;
2280       el.adr := prvi;
2281       Push(S, el, ok);
2282       g := (d+g) DIV 2
2283     END;
2284     IF d>g THEN
2285       rez := MIN(INTEGER)
2286     ELSE (* d=g *)
2287       rez := X[d]
2288     END;
2289     jos := TRUE;
2290     WHILE jos AND NOT Empty(S) DO
2291       Top(S, el, ok);
2292       Pop(S, ok);
2293       d := el.d;
2294       g := el.g;
2295       m1 := el.m1;
2296       IF el.adr = prvi THEN
2297         m1 := rez;
2298         el.m1 := m1;
2299         el.adr := drugi;
2300         Push(S, el, ok);
2301         d := (d+g) DIV 2 + 1;
2302         jos := FALSE
2303       ELSE (*el.adr = drugi*)
2304         m2 := rez;
2305         IF m1 > m2 THEN
2306           rez := m1
2307         ELSE
2308           rez := m2
2309         END
2310       END
2311     END
2312   UNTIL Empty(S);
2313   RETURN rez
2314 END SMax;
2315
2316 BEGIN (* glavni program *)
2317   X[1] := 3;
2318   X[2] := 2;
2319   X[3] := 5;
2320   X[4] := -7;
2321   X[5] := 0;
2322   IO.WrCard(Max(1, 5), 3);
2323   IO.WrLn;
2324   IO.WrCard(SMax(1, 5), 3);
2325   IO.WrLn
2326 END Rek1.
2327 \end{lstlisting}
2328
2329 \subsection{Primer 6 (ispitni)}
2330
2331
2332 \begin{lstlisting}[style=codeblock]
2333 MODULE Rek2;
2334 (* InfoTip = RECORD
2335                 x, y, n : CARDINAL;
2336                 adr : (prvi, drugi, treci, cetvrti)
2337              END;
2338 *)
2339 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2340            MakeNull, Empty, Top, Pop, Push;
2341 IMPORT IO;
2342
2343 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2344             n : CARDINAL) : CARDINAL;
2345 BEGIN
2346   IF n < 3 THEN
2347     RETURN x + y
2348   ELSIF ODD(n) THEN
2349     RETURN g(g(x+1, y, n-2), y, n-3)
2350   ELSE
2351     RETURN g(x, g(x, y+1, n-2), n-3)
2352   END
2353 END g;
2354
2355 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2356              n : CARDINAL) : CARDINAL;
2357 VAR
2358   S : StekTip;
2359   el : InfoTip;
2360   ok, jos : BOOLEAN;
2361   rez : CARDINAL;
2362 BEGIN
2363   MakeNull(S);
2364   REPEAT
2365     WHILE n >= 3 DO
2366       IF ODD(n) THEN
2367         el.x := x;
2368         el.y := y;
2369         el.n := n;
2370         el.adr := prvi;
2371         Push(S, el, ok);
2372         INC(x);
2373         DEC(n, 2)
2374       ELSE
2375         el.x := x;
2376         el.y := y;
2377         el.n := n;
2378         el.adr := treci;
2379         Push(S, el, ok);
2380         INC(y);
2381         DEC(n, 2)
2382       END
2383     END;
2384     rez := x+y;
2385     jos := TRUE;
2386     WHILE jos AND NOT Empty(S) DO
2387       Top(S, el, ok);
2388       Pop(S, ok);
2389       x := el.x;
2390       y := el.y;
2391       n := el.n;
2392       IF el.adr = prvi THEN
2393         el.adr := drugi;
2394         Push(S, el, ok);
2395         x := rez;
2396         DEC(n, 3);
2397         jos := FALSE
2398       ELSIF el.adr = treci THEN
2399         el.adr := cetvrti;
2400         Push(S, el, ok);
2401         y := rez;
2402         DEC(n, 3);
2403         jos := FALSE
2404       END
2405     END
2406   UNTIL Empty(S);
2407   RETURN rez
2408 END Sg;
2409
2410 BEGIN (* glavni program *)
2411   IO.WrCard(g(2, 3, 10), 3);
2412   IO.WrCard(Sg(2, 3, 10), 3);
2413 END Rek2.
2414 \end{lstlisting}
2415
2416 %\columnbreak
2417
2418 \appendix
2419
2420 \sectionbreak
2421 \pagenumbering{Roman}
2422 \input{xds-uputstvo}
2423
2424 \mainend
2425
2426
2427
2428 %%% Local Variables:
2429 %%% mode: latex
2430 %%% TeX-master: "skripta-spa1-jk"
2431 %%% End: