skripta-spa1-sadrzaj.tex

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