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