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.
1530
1531 \paragraph{PolinomL.DEF} \
1532
1533 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.DEF}
1534
1535 \paragraph{PolinomL.MOD} \
1536
1537 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.MOD}
1538
1539 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1540
1541 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1542
1543 \lstinputlisting[style=codeblock]{kodovi/polinomi/polinom.MOD}
1544
1545 \subsection{Zadatak: Suma k polinoma}
1546
1547 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1548 toga izracunava njihovu sumu
1549
1550 \lstinputlisting[style=codeblock]{kodovi/polinomi/PolSuma.MOD}
1551
1552 \sectionbreak
1553 \section{Stek i red opsluživanja}
1554
1555 \subsection{Primer: osnovno korišćenje steka i reda opsluživanja}
1556
1557 \lstinputlisting[style=codeblock]{kodovi/stek-redopsl/stekred.mod}
1558
1559 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
1560
1561 \begin{lstlisting}[style=codeblock]
1562 DEFINITION MODULE QueueInfo;
1563 CONST
1564   Maxqueue = 100;
1565 TYPE
1566   InfoTip = CHAR;
1567
1568 END QueueInfo.
1569
1570 IMPLEMENTATION MODULE QueueInfo;
1571 END QueueInfo.
1572
1573 DEFINITION MODULE RedOpsl1;
1574 FROM QueueInfo IMPORT InfoTip,Maxqueue;
1575 TYPE
1576   Niz = ARRAY[1..Maxqueue] OF InfoTip;
1577   RedOpslTip = RECORD
1578         Prvi, Zadnji : CARDINAL;
1579         Element : Niz
1580   END;
1581
1582 PROCEDURE MakeNull(VAR q : RedOpslTip);
1583 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1584 PROCEDURE First(VAR q : RedOpslTip;
1585                 VAR x : InfoTip;
1586                 VAR ok : BOOLEAN);
1587 PROCEDURE PopFirst(VAR q : RedOpslTip;
1588                    VAR ok : BOOLEAN);
1589 PROCEDURE AddRear(VAR q : RedOpslTip;
1590                   x : InfoTip;
1591                   VAR ok : BOOLEAN);
1592
1593 END RedOpsl1.
1594
1595 IMPLEMENTATION MODULE RedOpsl1;
1596 FROM QueueInfo IMPORT Maxqueue,InfoTip;
1597
1598 PROCEDURE MakeNull(VAR q : RedOpslTip);
1599 BEGIN
1600   WITH q DO
1601     Prvi := 0;
1602     Zadnji := 0
1603   END
1604 END MakeNull;
1605
1606 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1607 BEGIN
1608   RETURN q.Zadnji = 0
1609 END Empty;
1610
1611
1612 PROCEDURE First(VAR q : RedOpslTip;
1613                 VAR x : InfoTip;
1614                 VAR ok : BOOLEAN);
1615 BEGIN
1616   IF Empty(q) THEN
1617     ok := FALSE
1618   ELSE
1619     ok := TRUE;
1620     WITH q DO
1621       x := Element[Prvi]
1622     END
1623   END
1624 END First;
1625
1626 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
1627 BEGIN
1628   IF i = Maxqueue THEN
1629     RETURN 1
1630   ELSE
1631     RETURN i+1
1632   END
1633 END AddOne;
1634
1635 PROCEDURE PopFirst(VAR q : RedOpslTip;
1636                    VAR ok : BOOLEAN);
1637 BEGIN
1638   IF Empty(q) THEN
1639     ok := FALSE
1640   ELSE
1641     ok := TRUE;
1642     WITH q DO
1643       IF Prvi = Zadnji THEN
1644         MakeNull(q)
1645       ELSE
1646         Prvi := AddOne(Prvi)
1647       END
1648     END
1649   END
1650 END PopFirst;
1651
1652 PROCEDURE AddRear(VAR q : RedOpslTip;
1653                   x : InfoTip;
1654                   VAR ok : BOOLEAN);
1655 BEGIN
1656   WITH q DO
1657     IF AddOne(Zadnji) = Prvi THEN
1658       ok := FALSE
1659     ELSE
1660       ok := TRUE;
1661       IF Empty(q) THEN
1662         Prvi := 1;
1663         Zadnji := 1
1664       ELSE
1665         Zadnji := AddOne(Zadnji)
1666       END;
1667       Element[Zadnji] := x
1668     END
1669   END
1670 END AddRear;
1671
1672 END RedOpsl1.
1673
1674 MODULE Bafer;
1675 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
1676 FROM FIO IMPORT File,WrChar, Create, Close;
1677 IMPORT IO;
1678
1679 CONST
1680   ImeIzlaza = 'izlaz.txt';
1681
1682 VAR
1683   izlaz : File;
1684   znak : CHAR;
1685   buffer : RedOpslTip;
1686
1687 PROCEDURE IsprazniBafer(VAR dat : File;
1688                         VAR buf : RedOpslTip);
1689 VAR
1690   znak : CHAR;
1691   ok : BOOLEAN;
1692 BEGIN
1693   WHILE NOT Empty(buf) DO
1694     First(buf, znak, ok);
1695     PopFirst(buf, ok);
1696     WrChar(dat, znak)
1697   END
1698 END IsprazniBafer;
1699
1700 PROCEDURE BaferWrite(VAR dat : File;
1701                      VAR buf : RedOpslTip;
1702                      znak : CHAR);
1703 VAR
1704   ok : BOOLEAN;
1705 BEGIN
1706   AddRear(buf, znak, ok);
1707   IF NOT ok THEN
1708     IsprazniBafer(dat, buf);
1709     AddRear(buf, znak, ok)
1710   END
1711 END BaferWrite;
1712
1713 BEGIN
1714   izlaz := Create(ImeIzlaza);
1715   MakeNull(buffer);
1716   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
1717   IO.WrStr(ImeIzlaza);
1718   IO.WrChar('.');
1719   IO.WrLn;
1720   IO.WrStr('Unos zavrsite tackom.');
1721   IO.WrLn;
1722   znak := IO.RdChar();
1723   WHILE znak # '.' DO
1724     BaferWrite(izlaz, buffer, znak);
1725     znak := IO.RdChar();
1726   END;
1727   IsprazniBafer(izlaz, buffer);
1728   Close(izlaz)
1729 END Bafer.
1730 \end{lstlisting}
1731
1732 \subsection%
1733 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
1734
1735 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
1736 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
1737
1738 \begin{lstlisting}[style=codeblock]
1739 DEFINITION MODULE Stek;
1740 CONST
1741   Maxstack = 100;
1742 TYPE
1743   Niz = ARRAY [1..Maxstack] OF CHAR;
1744   StekTip = RECORD
1745             Top : CARDINAL;
1746             Element : Niz
1747           END;
1748 PROCEDURE MakeNull(VAR s : StekTip);
1749 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1750
1751 PROCEDURE Top(VAR s : StekTip;
1752               VAR x : CHAR;
1753               VAR ok : BOOLEAN);
1754 PROCEDURE Pop(VAR s : StekTip;
1755               VAR ok : BOOLEAN);
1756 PROCEDURE Push(VAR s : StekTip;
1757                x : CHAR;
1758                VAR ok : BOOLEAN);
1759 END Stek.
1760
1761
1762 IMPLEMENTATION MODULE Stek;
1763
1764 PROCEDURE MakeNull(VAR s : StekTip);
1765 BEGIN
1766   s.Top := 0
1767 END MakeNull;
1768
1769 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1770 BEGIN
1771   RETURN s.Top = 0
1772 END Empty;
1773
1774 PROCEDURE Top(VAR s : StekTip;
1775               VAR x : CHAR;
1776               VAR ok : BOOLEAN);
1777 BEGIN
1778   IF Empty(s) THEN
1779     ok := FALSE
1780   ELSE
1781     ok := TRUE;
1782     WITH s DO
1783       x := Element[Top]
1784     END
1785   END
1786 END Top;
1787 \end{lstlisting}
1788
1789 \begin{codeblock}
1790 PROCEDURE Pop(VAR s : StekTip;
1791               VAR ok : BOOLEAN);
1792 BEGIN
1793   IF Empty(s) THEN
1794     ok := FALSE
1795   ELSE
1796     ok := TRUE;
1797     DEC(s.Top)
1798   END
1799 END Pop;
1800
1801 PROCEDURE Push(VAR s : StekTip;
1802                x : CHAR;
1803                VAR ok : BOOLEAN);
1804 BEGIN
1805   WITH s DO
1806     IF Top = Maxstack THEN
1807       ok := FALSE
1808     ELSE
1809       ok := TRUE;
1810       INC(Top);
1811       Element[Top] := x
1812     END
1813   END
1814 END Push;
1815 END Stek.
1816
1817 MODULE wcw;
1818 (* Da li rec pripada gramatici wcw+. *)
1819 FROM Stek IMPORT StekTip, MakeNull, Empty,
1820                  Top, Pop, Push;
1821 FROM InOut IMPORT Read, Write, WriteString, EOL;
1822 TYPE
1823   slova = SET OF CHAR;
1824 VAR
1825   S : StekTip;
1826   Ch, C : CHAR;
1827   ok : BOOLEAN;
1828 BEGIN
1829   MakeNull(S);
1830   Read(Ch);
1831   ok := TRUE;
1832   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
1833     Push(S, Ch, ok);
1834     Read(Ch);
1835   END;
1836   IF NOT ok THEN
1837     WriteString('Greska - mali stek')
1838   ELSIF Ch # 'c' THEN
1839     WriteString('Pogresan string')
1840   ELSE
1841     Read(Ch);
1842     WHILE ok AND (Ch # EOL) DO
1843       Top(S, C, ok);
1844       ok := ok AND (C = Ch);
1845       IF ok THEN
1846         Pop(S, ok);
1847         Read(Ch);
1848       END
1849     END;
1850     IF NOT (ok AND Empty(S)) THEN
1851       WriteString('Pogresan string')
1852     ELSE
1853       WriteString('String pripada jeziku L')
1854     END
1855   END
1856 END wcw.
1857 \end{codeblock}
1858
1859 \manbreakJK
1860
1861 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
1862
1863
1864 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
1865 koji figurišu u izrazu su jednocifreni.
1866
1867 \begin{lstlisting}[style=codeblock]
1868 MODULE PostFix;
1869
1870 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
1871 FROM InOut IMPORT Read, Write, WriteInt, EOL;
1872 TYPE
1873   slova = SET OF CHAR;
1874 VAR
1875   S : StekTip;
1876   Ch : CHAR;
1877   Op1, Op2 : INTEGER;
1878   ok : BOOLEAN;
1879 PROCEDURE Conv(Ch : CHAR) : INTEGER;
1880 BEGIN
1881   RETURN  ORD(Ch) - ORD('0')
1882 END Conv;
1883
1884 BEGIN
1885   MakeNull(S);
1886   Read(Ch);
1887   WHILE Ch # EOL DO
1888     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
1889       Top(S, Op2, ok);
1890       Pop(S, ok);
1891       Top(S, Op1, ok);
1892       Pop(S, ok);
1893       CASE Ch OF
1894         '+' : Op1 := Op1 + Op2 |
1895         '-' : Op1 := Op1 - Op2 |
1896         '*' : Op1 := Op1 * Op2 |
1897         '/' : Op1 := Op1 DIV Op2 |
1898         '%' : Op1 := Op1 MOD Op2
1899       END;
1900       Push(S, Op1, ok)
1901     ELSE
1902       Push(S, Conv(Ch), ok)
1903     END;
1904     Read(Ch);
1905   END;
1906   Top(S, Op1, ok);
1907   Write('=');
1908   WriteInt(Op1,5)
1909 END PostFix.
1910 \end{lstlisting}
1911
1912 \sectionbreak
1913 \section{Simulacija rekurzije}
1914
1915
1916 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
1917 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
1918
1919 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
1920 mesta poziva, a u skladu sa tim se kreira InfoTip.
1921
1922 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
1923 rekurzivnih poziva.
1924
1925 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
1926 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
1927 pozivi.
1928
1929 \begin{lstlisting}
1930 MakeNull(S);
1931 REPEAT
1932   WHILE treba_rekurzija DO
1933     -prepisati sve od pocetka originalne
1934      procedure do prvog rekurzivnog poziva
1935     -staviti na stek potrebne
1936      lokalne promenljive, parametre procedure i
1937      adresu mesta poziva
1938     -podesiti vrednosti parametara da budu
1939      kao u rekurzivnom pozivu procedure
1940   END;
1941   trivijalan poziv
1942   umesto RETURN x pisati rez := x
1943   jos := TRUE;
1944   WHILE jos AND NOT Empty(S) DO
1945     Top(S, el, ok);
1946     Pop(S, ok);
1947     -restauriramo vrednosti sa steka
1948     -u zavisnosti od adrese poziva nastavimo
1949      prepisivanje originalne procedure sa
1950      tog mesta
1951     -ako se dodje do novog rek. poziva tada:
1952        -sacuvati na steku vrednosti
1953        -podesiti vrednosti parametara da budu
1954         kao u rekurzivnom pozivu procedure
1955        -ici na pocetak koda
1956         (ovo se postize sa jos := FALSE)
1957     -inace
1958        ako se naidje na RETURN x pisati rez := x
1959   END
1960 UNTIL Empty(S);
1961 \end{lstlisting}
1962
1963 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
1964
1965 \subsection*{ZADACI}
1966
1967 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
1968
1969 \subsection{Primer 1 -- faktorijel}
1970
1971
1972 \begin{lstlisting}[style=codeblock]
1973 MODULE Fakto;
1974 (* InfoTip = CARDINAL; *)
1975
1976 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
1977 FROM StekC IMPORT StekTip, MakeNull, Empty,
1978                   Top, Pop, Push;
1979 VAR
1980   n : CARDINAL;
1981 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
1982 BEGIN
1983   IF n <= 1 THEN
1984     RETURN 1
1985   ELSE
1986     RETURN n * RFakto(n-1)
1987   END
1988 END RFakto;
1989
1990
1991 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
1992 VAR
1993   s : StekTip;
1994   rez : CARDINAL;
1995   OK : BOOLEAN;
1996 BEGIN
1997   MakeNull(s);
1998   WHILE n > 1 DO
1999     Push(s,n,OK);
2000     DEC(n)
2001   END;
2002   rez := 1;
2003   WHILE NOT Empty(s) DO
2004     Top(s, n, OK);
2005     Pop(s, OK);
2006     rez := n * rez
2007   END;
2008   RETURN rez
2009 END SFakto;
2010
2011 BEGIN
2012   WrStr('n = ');
2013   n := RdCard();
2014   WrLn
2015   WrStr('n! = ');
2016   WrCard(RFakto(n), 1);
2017   WrStr(' = ');
2018   WrCard(SFakto(n), 1)
2019 END Fakto.
2020 \end{lstlisting}
2021
2022 \subsection{Primer 2 -- stepenovanje}
2023
2024 \begin{lstlisting}[style=codeblock]
2025 MODULE Step;
2026 (* InfoTip = RECORD
2027                 x : REAL;
2028                 n : CARDINAL;
2029                 adr : (par, nepar)
2030              END;
2031 *)
2032 FROM IO IMPORT WrStr, WrLn, WrReal,
2033         RdReal, RdCard;
2034 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2035              Top, Pop, Push, InfoTip, AdrTip;
2036 VAR
2037   n : CARDINAL;
2038   x : REAL;
2039
2040 PROCEDURE Sqr(y : REAL) : REAL;
2041 BEGIN
2042   RETURN y * y
2043 END Sqr;
2044
2045 PROCEDURE RStep(x : REAL;
2046                 n : CARDINAL) : REAL;
2047 BEGIN
2048   IF n = 0 THEN
2049     RETURN 1.
2050   ELSIF ODD(n) THEN
2051     RETURN x * Sqr( RStep(x, n DIV 2) )
2052   ELSE
2053     RETURN Sqr( RStep(x, n DIV 2) )
2054   END
2055 END RStep;
2056
2057 PROCEDURE SStep(x : REAL;
2058                 n : CARDINAL ) : REAL;
2059 VAR
2060   s : StekTip;
2061   OK : BOOLEAN;
2062   rez : REAL;
2063   el : InfoTip;
2064 BEGIN
2065   MakeNull(s);
2066   WHILE n > 0 DO
2067     el.x := x;
2068     el.n := n;
2069     IF ODD(n) THEN
2070       el.adr := nepar;
2071     ELSE
2072       el.adr := par
2073     END;
2074     Push(s,el,OK);
2075     n := n DIV 2
2076   END;
2077   rez := 1.;
2078   WHILE NOT Empty(s) DO
2079     Top(s, el, OK);
2080     Pop(s, OK);
2081     x := el.x;
2082     n := el.n;
2083     IF el.adr = nepar THEN
2084       rez := x * Sqr(rez)
2085     ELSE
2086       rez := Sqr(rez)
2087     END
2088   END;
2089   RETURN rez
2090 END SStep;
2091
2092 BEGIN
2093   WrStr('x =? ');
2094   x := RdReal();
2095   WrLn;
2096   WrStr('n =? ');
2097   n := RdCard();
2098   WrStr('x^n = ');
2099   WrReal(RStep(x, n), 10, 1);
2100   WrStr(' = ');
2101   WrReal(SStep(x, n), 10, 1)
2102 END Step.
2103 \end{lstlisting}
2104
2105 \subsection{Primer 3 -- Fibonači}
2106
2107 \begin{lstlisting}[style=codeblock]
2108 MODULE Fib;
2109 (* InfoTip = RECORD
2110                 n : CARDINAL;
2111                 PrviSab : CARDINAL;
2112                 adr : (prvi, drugi)
2113              END;
2114 *)
2115
2116 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2117 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2118        Top, Pop, Push, InfoTip, AdrTip;
2119 VAR
2120   n : CARDINAL;
2121
2122 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2123 BEGIN
2124   IF n <= 1 THEN
2125     RETURN n
2126   ELSE
2127     RETURN RFib(n-1) + RFib(n-2)
2128   END
2129 END RFib;
2130
2131 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2132 VAR
2133   s : StekTip;
2134   OK, jos : BOOLEAN;
2135   rez, PrviSab : CARDINAL;
2136   el : InfoTip;
2137 BEGIN
2138   MakeNull(s);
2139   REPEAT
2140     WHILE n > 1 DO
2141       el.n := n;
2142       el.adr := prvi;
2143       Push(s,el,OK);
2144       DEC(n)
2145     END;
2146     rez := (n);
2147     jos := TRUE;
2148     WHILE (NOT Empty(s)) AND jos DO
2149       Top(s, el, OK);
2150       Pop(s, OK);
2151       n := el.n;
2152       IF el.adr = prvi THEN
2153         PrviSab := rez;
2154         el.n := n;
2155         el.adr := drugi;
2156         el.PrviSab := PrviSab;
2157         Push(s, el, OK);
2158         DEC(n, 2);
2159         jos := FALSE
2160       ELSE
2161         PrviSab := el.PrviSab;
2162         rez := PrviSab + rez
2163       END
2164     END
2165   UNTIL Empty(s);
2166   RETURN rez
2167 END SFib;
2168
2169 BEGIN
2170   WrStr('n =? ');
2171   n := RdCard();
2172   WrStr('F(n) = ');
2173   WrCard(RFib(n), 1);
2174   WrStr(' = ');
2175   WrCard(SFib(n), 1)
2176 END Fib.
2177 \end{lstlisting}
2178
2179 \subsection{Primer 4 -- faktorijel 2}
2180
2181
2182 \begin{lstlisting}[style=codeblock]
2183 MODULE Faktor;
2184 (* InfoTip = CARDINAL; *)
2185 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2186 FROM StekC IMPORT StekTip, MakeNull, Empty,
2187                   Top, Pop, Push;
2188 VAR
2189   n,rez : CARDINAL;
2190
2191 PROCEDURE RFakto(n : CARDINAL;
2192                  VAR rez : CARDINAL);
2193 BEGIN
2194   IF n = 0 THEN
2195     rez := 1
2196   ELSE
2197     RFakto(n-1, rez);
2198     rez := n * rez
2199   END
2200 END RFakto;
2201
2202 PROCEDURE SFakto(n : CARDINAL;
2203                  VAR rez : CARDINAL);
2204 VAR
2205   s : StekTip;
2206   OK : BOOLEAN;
2207 BEGIN
2208   MakeNull(s);
2209   WHILE n > 0 DO
2210     Push(s,n,OK);
2211     DEC(n)
2212   END;
2213   rez := 1;
2214   WHILE NOT Empty(s) DO
2215     Top(s, n, OK);
2216     Pop(s, OK);
2217     rez := n * rez
2218   END
2219 END SFakto;
2220
2221 BEGIN
2222   WrStr('n =? ');
2223   n := RdCard();
2224   WrLn;
2225   WrStr('n! = ');
2226   RFakto(n, rez);
2227   WrCard(rez, 1);
2228   WrStr(' = ');
2229   SFakto(n, rez);
2230   WrCard(rez, 1)
2231 END Faktor.
2232 \end{lstlisting}
2233
2234 \subsection{Primer 5 (ispitni)}
2235
2236
2237 \begin{lstlisting}[style=codeblock]
2238 MODULE Rek1;
2239 (* InfoTip = RECORD
2240                 d, g, m1, m2 : INTEGER;
2241                 adr : (prvi, drugi)
2242              END;
2243 *)
2244 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2245          MakeNull, Empty, Top, Pop, Push;
2246 IMPORT IO;
2247 VAR
2248   X : ARRAY [1..20] OF INTEGER;
2249
2250 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2251 VAR
2252   m1, m2 : INTEGER;
2253 BEGIN
2254   IF d>g THEN
2255     RETURN MIN(INTEGER)
2256   ELSIF d=g THEN
2257     RETURN X[d]
2258   ELSE
2259     m1 := Max(d, (d+g) DIV 2);
2260     m2 := Max((d+g) DIV 2 +1, g);
2261     IF m1 > m2 THEN
2262       RETURN m1
2263     ELSE
2264       RETURN m2
2265     END
2266   END
2267 END Max;
2268
2269 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2270 VAR
2271   S : StekTip;
2272   el : InfoTip;
2273   ok, jos : BOOLEAN;
2274   m1, m2, rez : INTEGER;
2275 BEGIN
2276   MakeNull(S);
2277   REPEAT
2278     WHILE d<g DO
2279       el.d := d;
2280       el.g := g;
2281       el.adr := prvi;
2282       Push(S, el, ok);
2283       g := (d+g) DIV 2
2284     END;
2285     IF d>g THEN
2286       rez := MIN(INTEGER)
2287     ELSE (* d=g *)
2288       rez := X[d]
2289     END;
2290     jos := TRUE;
2291     WHILE jos AND NOT Empty(S) DO
2292       Top(S, el, ok);
2293       Pop(S, ok);
2294       d := el.d;
2295       g := el.g;
2296       m1 := el.m1;
2297       IF el.adr = prvi THEN
2298         m1 := rez;
2299         el.m1 := m1;
2300         el.adr := drugi;
2301         Push(S, el, ok);
2302         d := (d+g) DIV 2 + 1;
2303         jos := FALSE
2304       ELSE (*el.adr = drugi*)
2305         m2 := rez;
2306         IF m1 > m2 THEN
2307           rez := m1
2308         ELSE
2309           rez := m2
2310         END
2311       END
2312     END
2313   UNTIL Empty(S);
2314   RETURN rez
2315 END SMax;
2316
2317 BEGIN (* glavni program *)
2318   X[1] := 3;
2319   X[2] := 2;
2320   X[3] := 5;
2321   X[4] := -7;
2322   X[5] := 0;
2323   IO.WrCard(Max(1, 5), 3);
2324   IO.WrLn;
2325   IO.WrCard(SMax(1, 5), 3);
2326   IO.WrLn
2327 END Rek1.
2328 \end{lstlisting}
2329
2330 \subsection{Primer 6 (ispitni)}
2331
2332
2333 \begin{lstlisting}[style=codeblock]
2334 MODULE Rek2;
2335 (* InfoTip = RECORD
2336                 x, y, n : CARDINAL;
2337                 adr : (prvi, drugi, treci, cetvrti)
2338              END;
2339 *)
2340 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2341            MakeNull, Empty, Top, Pop, Push;
2342 IMPORT IO;
2343
2344 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2345             n : CARDINAL) : CARDINAL;
2346 BEGIN
2347   IF n < 3 THEN
2348     RETURN x + y
2349   ELSIF ODD(n) THEN
2350     RETURN g(g(x+1, y, n-2), y, n-3)
2351   ELSE
2352     RETURN g(x, g(x, y+1, n-2), n-3)
2353   END
2354 END g;
2355
2356 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2357              n : CARDINAL) : CARDINAL;
2358 VAR
2359   S : StekTip;
2360   el : InfoTip;
2361   ok, jos : BOOLEAN;
2362   rez : CARDINAL;
2363 BEGIN
2364   MakeNull(S);
2365   REPEAT
2366     WHILE n >= 3 DO
2367       IF ODD(n) THEN
2368         el.x := x;
2369         el.y := y;
2370         el.n := n;
2371         el.adr := prvi;
2372         Push(S, el, ok);
2373         INC(x);
2374         DEC(n, 2)
2375       ELSE
2376         el.x := x;
2377         el.y := y;
2378         el.n := n;
2379         el.adr := treci;
2380         Push(S, el, ok);
2381         INC(y);
2382         DEC(n, 2)
2383       END
2384     END;
2385     rez := x+y;
2386     jos := TRUE;
2387     WHILE jos AND NOT Empty(S) DO
2388       Top(S, el, ok);
2389       Pop(S, ok);
2390       x := el.x;
2391       y := el.y;
2392       n := el.n;
2393       IF el.adr = prvi THEN
2394         el.adr := drugi;
2395         Push(S, el, ok);
2396         x := rez;
2397         DEC(n, 3);
2398         jos := FALSE
2399       ELSIF el.adr = treci THEN
2400         el.adr := cetvrti;
2401         Push(S, el, ok);
2402         y := rez;
2403         DEC(n, 3);
2404         jos := FALSE
2405       END
2406     END
2407   UNTIL Empty(S);
2408   RETURN rez
2409 END Sg;
2410
2411 BEGIN (* glavni program *)
2412   IO.WrCard(g(2, 3, 10), 3);
2413   IO.WrCard(Sg(2, 3, 10), 3);
2414 END Rek2.
2415 \end{lstlisting}
2416
2417 %\columnbreak
2418
2419 \appendix
2420
2421 \sectionbreak
2422 \pagenumbering{Roman}
2423 \input{xds-uputstvo}
2424
2425 \mainend
2426
2427
2428
2429 %%% Local Variables:
2430 %%% mode: latex
2431 %%% TeX-master: "skripta-spa1-jk"
2432 %%% End: