skripta-spa1.tex

   1 % skripta-spa1.tex
   2 % Skripta za predmet Strukture podataka i algoritmi 1, DMI, PMF, NS
   3
   4 \documentclass[a4paper,twoside]{article}
   5 \usepackage[T1]{fontenc}
   6 \usepackage[utf8]{inputenc}%definišemo da je ulaz utf-8 fajl
   7
   8 % osnovne informacije koje ce se prikazati na naslovnoj strani,
   9 % kao i u informacijama u generisanom pdfu
  10 \newcommand{\autor}{Vladimir Kurbalija, Milos Radovanovic, Doni Pracner}
  11 \newcommand{\naslov}{Skripta za vezbe iz predmeta "Strukture podataka
  12   i algoritmi 1"}
  13 \newcommand{\datum}{Februar 2013, Novi Sad}
  14 \newcommand{\verzija}{ver 13a-jk}
  15 %jk=jedna kolona, dk=dve kolone
  16
  17 \newcommand{\mainstart}{
  18 %\begin{multicols}{2}
  19 }
  20
  21 \newcommand{\mainend}{
  22 %\end{multicols}
  23 }
  24
  25 \newcommand{\manbreakJK}{
  26 \pagebreak
  27 }
  28
  29 \usepackage[serbian]{babel}
  30 \usepackage{fancyhdr}
  31 \pagestyle{fancy}
  32
  33 \title{\naslov -- \verzija}
  34 \author{\autor}
  35 \date{\datum}
  36
  37 %change the default font
  38 \usepackage{lmodern}
  39 \usepackage{beramono}
  40 \renewcommand{\familydefault}{\sfdefault}
  41
  42 \usepackage{pifont}
  43
  44 %podesavanja outputa za pdf verzije
  45 \usepackage[bookmarks,pdffitwindow=false,unicode=true,%
  46 pdftitle={\naslov -- \verzija},%
  47 pdfauthor={\autor}%
  48 ]{hyperref}
  49
  50 \usepackage{graphicx}
  51 \usepackage{listings}
  52 \usepackage{amsthm}
  53 \usepackage{amsmath}
  54 \usepackage{latexsym}
  55 \usepackage{multicol}
  56
  57 %margine
  58 %experiment
  59 %\usepackage[top=2.5cm, bottom=1.5cm, left=3cm, right=2cm]{geometry}
  60 %staro:
  61 \usepackage[top=1.5cm, bottom=1cm, left=2cm, right=1cm]{geometry}
  62
  63 \begin{document}
  64
  65 %customize the itemize environments
  66
  67 \let\olditemize=\itemize
  68 \def\itemize{
  69 \olditemize
  70   \setlength{\itemsep}{1pt}
  71   \setlength{\parskip}{0pt}
  72   \setlength{\parsep}{0pt}
  73   \setlength{\topsep}{-1cm}
  74   \setlength{\partopsep}{1pt}
  75 }
  76
  77 %% ovi redovi daju header i footer
  78
  79 \renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}}
  80 \fancyhf{} % delete current setting for header and footer
  81 %\fancyfoot[C]{\thepage}
  82 \fancyhead[LO]{\bfseries\rightmark}
  83 \fancyhead[RO]{\thepage}
  84 \fancyhead[RE]{Strukture podataka i algoritmi 1 -- skripta}
  85 \fancyhead[LE]{\thepage}
  86 \renewcommand{\headrulewidth}{0.5pt}
  87 \renewcommand{\headwidth}{\textwidth}
  88 %\renewcommand{\footrulewidth}{0.5pt}
  89 %\addtolength{\headheight}{0.5pt} % make space for the rule
  90 \fancypagestyle{plain}{%
  91 \fancyhead{} % get rid of headers on plain pages
  92 \fancyfoot{}
  93 \renewcommand{\headrulewidth}{0pt} % and the line
  94 \renewcommand{\footrulewidth}{0pt} % and the line
  95 }
  96 \renewcommand{\headheight}{15pt}
  97
  98 %promene u marginama:
  99 %\setlength{\marginparwidth}{32pt}
 100 %\setlength{\textwidth}{620pt}
 101 %\setlength{\textheight}{620pt}
 102
 103
 104 %% specijalni blokovi koji služe kao podsetnici u radu ili napomene
 105 \newcommand{\skica}[1]{
 106     \noindent \framebox{\parbox[c]{0.9\textwidth}{  {\small** \textit{#1}  }}
 107     \newline }
 108 }
 109
 110 \newcommand{\skicas}[1]{
 111     \framebox{* \textit{#1} *}
 112 }
 113
 114 %boldovane skice visokog prioriteta
 115 \newcommand{\skicab}[1]{
 116   \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small***
 117         \textbf{#1} }} \newline } }
 118
 119 \newcommand{\kod}[1]{{\small\texttt{#1}}}
 120
 121 % ako je sledeci red odkomentarisan nista od skica nece biti ispisano
 122 % u finalni dokument
 123
 124 % \renewcommand{\skica}[1]{}
 125
 126 % title u skladu sa uobičajenim na Departmanu
 127 \newcommand{\makemytitle}{
 128   \begin{center}
 129         \makebox{%
 130         \includegraphics[width=2cm]{grbPMF}
 131         \parbox[b]{65ex}{\centering
 132                 Univerzitet u Novom Sadu\\
 133                 Prirodno-matematički fakultet\\
 134                 Departman za matematiku i informatiku}
 135         \includegraphics[width=2cm]{grbUNS}
 136         }
 137         \vspace{10ex}
 138
 139         \parbox[b]{\textwidth}{{\Large {\bf
 140               Vladimir Kurbalija, \href{mailto:kurba@dmi.rs}{kurba@dmi.rs}\\
 141               Miloš Radovanović, \href{mailto:radacha@dmi.rs}{radacha@dmi.rs}\\
 142               Doni Pracner, \href{mailto:doni.pracner@dmi.rs}{doni.pracner@dmi.rs}}}}
 143         \vspace{5ex}
 144
 145         {\Large {\bf Skripta za vežbe iz predmeta }}
 146
 147         {\Huge {\bf
 148             \setlength{\baselineskip}{1.5\baselineskip}Strukture
 149               podataka i algoritmi 1}}
 150
 151         \vspace{5ex}
 152         %\vfill
 153
 154         \verzija \ -- \datum
 155
 156         \end{center}
 157         \thispagestyle{plain}
 158 %       \newpage
 159 }
 160
 161 \makemytitle
 162
 163 % theorems, definition etc.
 164 %''''''''''''''''''''''''''
 165
 166 \theoremstyle{definition}
 167 \newtheorem{def1}{Definicija}
 168 \theoremstyle{plain}
 169 \newtheorem{theo}{Teorema}
 170 \newtheorem{lema}{Lema}
 171
 172 \lstloadlanguages{Modula-2}
 173
 174 \lstset{
 175         basicstyle=\footnotesize\ttfamily,
 176         showstringspaces=false,
 177         breaklines=true
 178 }
 179
 180 \lstdefinestyle{codeblock}{
 181         basicstyle=\footnotesize\ttfamily,
 182         keywordstyle=\textbf,
 183         columns=[l]fixed,
 184         breakatwhitespace=true,
 185 %        prebreak=\P,
 186 %        postbreak=\ding{229}\space,
 187         language=Modula-2
 188 }
 189
 190 \lstdefinestyle{numcodeblock}{
 191   style=codeblock,
 192   numbers=left
 193 }
 194
 195 \lstnewenvironment{codeblock}{\lstset{style=codeblock}}{}
 196
 197
 198 % ----------------==================--------------------------------------
 199 %                 Pravi pocetak rada
 200
 201
 202 Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula
 203 2'. Za verzije pre 2.60 je neophodno dodatno instalirati i TSCP (Top
 204 Speed Compatibility Pack), pošto je potreban za neke od modula koji se
 205 ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi
 206 moduli uključeni u standardnu instalaciju.
 207
 208 Sav sadržaj se može koristiti u skladu sa {\ttfamily CC-BY-NC-SA} licencom. \url{http://creativecommons.org/licenses/by-nc-sa/3.0/}
 209
 210 \tableofcontents
 211
 212 %\newpage
 213
 214 \mainstart
 215
 216 \section{Ilustracija efikasnosti algoritma}
 217
 218 \subsection{Zadatak: Pronaći sve pitagorine
 219 trojke do zadate granice}
 220
 221 Pitagorina trojka su tri broja $a,b,c$ za koje važi $a^2 + b^2 = c^2\\$
 222
 223 \begin{lstlisting}[style=codeblock]
 224 MODULE Trojke1;
 225 (* Pitagorine trojke koriscenjem "Brute-force" *)
 226 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 227 CONST
 228   Gr = 100;
 229 VAR
 230   a, b, c : [1 .. Gr];
 231 BEGIN
 232   FOR a := 1 TO Gr DO
 233     FOR b := 1 TO Gr DO
 234       FOR c := 1 TO Gr DO
 235         IF a*a + b*b = c*c THEN
 236           WriteLn;
 237           WriteString('a = ');
 238           WriteCard(a,2);
 239           WriteString(', b = ');
 240           WriteCard(b,2);
 241           WriteString(', c = ');
 242           WriteCard(c,2)
 243         END
 244       END
 245     END
 246   END
 247 END Trojke1.
 248 \end{lstlisting}
 249
 250 \begin{codeblock}
 251 MODULE Trojke2;
 252 (*Pitagorine trojke koriscenjem zaokrugljivanja*)
 253 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 254 FROM MathLib0 IMPORT sqrt;
 255 CONST
 256   Gr = 100;
 257 VAR
 258   a, b, c : CARDINAL;
 259   creal : REAL;
 260 BEGIN
 261   FOR a := 1 TO Gr DO
 262     FOR b := 1 TO Gr DO
 263       creal := FLOAT(a*a) + FLOAT(b*b);
 264       creal := sqrt(creal);
 265       c := TRUNC(creal);
 266       IF creal = FLOAT(c) THEN
 267         WriteLn;
 268         WriteString(' a = ');
 269         WriteCard(a,2);
 270         WriteString(', b = ');
 271         WriteCard(b,2);
 272         WriteString(', c = ');
 273         WriteCard(c,2)
 274       END
 275     END
 276   END
 277 END Trojke2.
 278 \end{codeblock}
 279
 280 Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup.
 281 Ako uzmemo neka dva prirodna broja $m$ i $n$, tada se iz njih može
 282 izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove:
 283 \[
 284 \begin{array}{l}
 285 a = 2mn\\
 286 b = m^2 - n^2\\
 287 c = m^2 + n^2
 288 \end{array}
 289 \]
 290 Odnosno kad probamo da proverimo da li je ovo
 291 Pitagorina trojka dobijamo:
 292 \[
 293 \begin{array}{r@=l}
 294 a^2 + b^2 & c^2\\
 295 (2mn)^2 + (m^2 - n^2)^2 & (m^2 + n^2)^2
 296 \end{array}
 297 \]
 298
 299 \begin{codeblock}
 300 MODULE Trojke3;
 301 (* Pitagorine trojke koriscenjem teoreme *)
 302 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 303 CONST
 304   Gr = 10;
 305 VAR
 306   a, b, c, m, n : CARDINAL;
 307 BEGIN
 308   FOR m := 1 TO Gr DO
 309     FOR n := 1 TO m-1 DO
 310       a := 2*m*n;
 311       b := m*m - n*n;
 312       c := m*m + n*n;
 313       WriteLn;
 314       WriteString('a = ');
 315       WriteCard(a,2);
 316       WriteString(', b = ');
 317       WriteCard(b,2);
 318       WriteString(', c = ');
 319       WriteCard(c,2)
 320     END
 321   END
 322 END Trojke3.
 323 \end{codeblock}
 324
 325 Sledeća dva metoda traže trojke sa nekim specifičnim osobinama.
 326
 327 \begin{codeblock}
 328 MODULE Trojke4;
 329 (* Pitagorine trojke kod kojih je razlika
 330    izmedju katete i hipotenuze tacno 1 *)
 331 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 332 CONST
 333   Gr = 10;
 334 VAR
 335   a, b, c, m, n : CARDINAL;
 336 BEGIN
 337   FOR m := 2 TO Gr DO
 338     n := m - 1;
 339     a := 2*m*n;
 340     b := m*m - n*n;
 341     c := m*m + n*n;
 342     WriteLn;
 343     WriteString('a = ');
 344     WriteCard(a,2);
 345     WriteString(', b = ');
 346     WriteCard(b,2);
 347     WriteString(', c = ');
 348     WriteCard(c,2)
 349   END
 350 END Trojke4.
 351 \end{codeblock}
 352
 353 \begin{lstlisting}[style=codeblock]
 354 MODULE Trojke5;
 355 (* Pitagorine trojke kod kojih je razlika
 356    izmedju kateta jedan *)
 357 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 358 CONST
 359   Gr = 7;
 360 VAR
 361   a, b, c, m, n, w, i, temp : CARDINAL;
 362 BEGIN
 363   w := 1;
 364   n := 0;
 365   FOR i := 1 TO Gr DO
 366     m := n + w;
 367     a := 2*m*n;
 368     b := m*m - n*n;
 369     c := m*m + n*n;
 370     WriteLn;
 371     WriteString('a = ');
 372     WriteCard(a,2);
 373     WriteString(', b = ');
 374     WriteCard(b,2);
 375     WriteString(', c = ');
 376     WriteCard(c,2);
 377     temp := w;
 378     w := 3*w + 4*n;
 379     n := 2*temp + 3*n
 380   END
 381 END Trojke5.
 382 \end{lstlisting}
 383
 384 \manbreakJK
 385
 386 \subsection[Zadatak: Maksimalna suma susednih elemenata u
 387 nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u
 388   nizu celih brojeva}
 389
 390 \begin{lstlisting}[style=codeblock]
 391 MODULE MaxNiza1;
 392 (* Prvo resenje. Brute Force: O(n^3)  *)
 393 FROM InOut IMPORT WriteString,ReadInt,
 394            WriteInt,WriteCard,WriteLn;
 395 CONST
 396   N = 10;
 397 TYPE
 398   Interval = [1..N];
 399 VAR
 400   Max, Suma : INTEGER;
 401   d,g,i,Ood,Doo : Interval;
 402   X : ARRAY Interval OF INTEGER;
 403 BEGIN
 404   WriteString(' Unesite niz X ');
 405   WriteLn;
 406   FOR i := 1 TO N DO
 407     ReadInt(X[i]);
 408     WriteLn
 409   END;
 410   Max := 0;
 411   FOR d := 1 TO N DO
 412     FOR g := 1 TO N DO
 413       Suma := 0;
 414       FOR i := d TO g DO
 415         Suma := Suma + X[i]
 416       END;
 417       IF Suma > Max THEN
 418         Max := Suma;
 419         Ood := d;
 420         Doo := g
 421       END
 422     END
 423   END;
 424   WriteLn;
 425   WriteString(' Maksimum je ');
 426   WriteInt(Max,3);
 427   WriteString(' u intervalu od ');
 428   WriteCard(Ood,3);
 429   WriteString(' do ');
 430   WriteCard(Doo,3)
 431 END MaxNiza1.
 432
 433 MODULE MaxNiza2;
 434 (* Drugo resenje: O(n^2).
 435    Koristi se cinjenica da je suma X[d..g]
 436    izracunljiva iz X[d..g-1].  *)
 437 FROM InOut IMPORT WriteString,ReadInt,
 438            WriteInt,WriteCard,WriteLn;
 439 CONST
 440   N = 10;
 441 TYPE
 442   Interval = [1..N];
 443 VAR
 444   Max, Suma : INTEGER;
 445   d,g,i,Ood,Doo : Interval;
 446   X : ARRAY Interval OF INTEGER;
 447 BEGIN
 448   WriteString(' Unesite niz X ');
 449   WriteLn;
 450   FOR i := 1 TO N DO
 451     ReadInt(X[i]);
 452     WriteLn
 453   END;
 454   Max := 0;
 455   FOR d := 1 TO N DO
 456     Suma := 0;
 457     FOR g := d TO N DO
 458       Suma := Suma + X[g];
 459       IF Suma > Max THEN
 460         Max := Suma;
 461         Ood := d;
 462         Doo := g
 463       END
 464     END
 465   END;
 466   WriteLn;
 467   WriteString(' Maksimum je ');
 468   WriteInt(Max,3);
 469   WriteString(' u intervalu od ');
 470   WriteCard(Ood,3);
 471   WriteString(' do ');
 472   WriteCard(Doo,3)
 473 END MaxNiza2.
 474 \end{lstlisting}
 475
 476 \begin{codeblock}
 477 MODULE MaxNiza3;
 478 (* Trece resenje: O(n^2).
 479    Koristi pomocni niz u kome je na i-tom mestu
 480    suma podniza x[1..i] *)
 481 FROM InOut IMPORT WriteString,ReadInt,
 482            WriteInt,WriteCard,WriteLn;
 483 CONST
 484   N = 10;
 485 TYPE
 486   Interval = [1..N];
 487 VAR
 488   Max, Suma : INTEGER;
 489   d,g,i,Ood,Doo : Interval;
 490   X : ARRAY Interval OF INTEGER;
 491   Pom : ARRAY [0..N] OF INTEGER;
 492 BEGIN
 493   WriteString(' Unesite niz X ');
 494   WriteLn;
 495   FOR i := 1 TO N DO
 496     ReadInt(X[i]);
 497     WriteLn
 498   END;
 499   Pom[0] := 0;
 500   FOR i := 1 TO N DO
 501     Pom[i] := Pom[i-1] + X[i]
 502   END;
 503   Max := 0;
 504   FOR d := 1 TO N DO
 505     FOR g := d TO N DO
 506       Suma := Pom[g] - Pom[d-1];
 507       IF Suma > Max THEN
 508         Max := Suma;
 509         Ood := d;
 510         Doo := g
 511       END
 512     END
 513   END;
 514   WriteLn;
 515   WriteString(' Maksimum je ');
 516   WriteInt(Max,3);
 517   WriteString(' u intervalu od ');
 518   WriteCard(Ood,3);
 519   WriteString(' do ');
 520   WriteCard(Doo,3)
 521 END MaxNiza3.
 522 \end{codeblock}
 523
 524 \begin{codeblock}
 525 MODULE MaxNiza4;
 526 (* Cetvrto resenje. Najbolje moguce: O(n)  *)
 527 FROM InOut IMPORT WriteString,ReadInt,
 528            WriteInt,WriteCard,WriteLn;
 529 CONST
 530   N = 10;
 531 TYPE
 532   Interval = [1..N];
 533 VAR
 534   Max, MaxDovde : INTEGER;
 535   i,d,Ood,Doo : Interval;
 536   X : ARRAY Interval OF INTEGER;
 537 BEGIN
 538   WriteString(' Unesite niz X ');
 539   WriteLn;
 540   FOR i := 1 TO N DO
 541     ReadInt(X[i]);
 542     WriteLn
 543   END;
 544   Max := 0;
 545   MaxDovde := 0;
 546   FOR i := 1 TO N DO
 547     IF MaxDovde = 0 THEN
 548       d := i
 549     END;
 550     MaxDovde := MaxDovde + X[i];
 551     IF MaxDovde < 0 THEN
 552       MaxDovde := 0
 553     END;
 554     IF MaxDovde > Max THEN
 555       Ood := d;
 556       Doo := i;
 557       Max := MaxDovde
 558     END
 559   END;
 560   WriteLn;
 561   WriteString(' Maksimum je ');
 562   WriteInt(Max,3);
 563   WriteString(' u intervalu od ');
 564   WriteCard(Ood,3);
 565   WriteString(' do ');
 566   WriteCard(Doo,3)
 567 END MaxNiza4.
 568 \end{codeblock}
 569
 570 \section{Stringovi}
 571
 572
 573 Stringovi -- odnosno nizovi znakova -- ne postoje kao ugrađeni tip u
 574 jeziku Modula 2. Ovo daje slobodu da se niz znakova definiše na dužinu
 575 najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr:
 576 \begin{codeblock}
 577   TYPE
 578      String = ARRAY [1..30] OF CHAR;
 579 \end{codeblock}
 580
 581 Operacije nad stringovima se najčešće uvoze iz modula \kod{Str}. One
 582 sve prihvataju \emph{otvorene nizove znakova} (strukture definisane sa
 583 \kod{ARRAY OF CHAR}), tako da im se može proslediti niz proizvoljne
 584 dužine.
 585
 586 Određivanje stvarne dužine stringa (tj koliko od maksimalnog
 587 kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na
 588 sledeći način:
 589 \begin{codeblock}
 590      duzina := Length(str)
 591 \end{codeblock}
 592
 593 Leksikografsko poređenje dva stringa se ne može vršiti standardnim
 594 operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o
 595 nizovima, a delom i zato što se ne vidi direktno koji deo niza je
 596 popunjen stvarnim sadržajem. Za ovo se koristi komanda \kod{Compare},
 597 koja prihvata dva stringa kao parametre, a vraća broj koji predstavlja
 598 njihov odnos. Taj broj će biti 0 ako su stringovi jednaki, veći
 599 od nule ako je prvi string ``veći'', i manji od nule ako je prvi
 600 string ``manji''. Ovo se lako pamti kad primetimo da je odnos
 601 između \kod{Compare} i 0 isti kao i između prvog i drugog stringa.
 602
 603 \begin{codeblock}
 604   IF    Compare(str1, str2) > 0 THEN
 605      WriteString("Prvi string je veci");
 606   ELSIF Compare(str1, str2) < 0 THEN
 607      WriteString("Prvi string je manji");
 608   ELSE (* moraju biti jednaki *)
 609      WriteString("Jednaki su");
 610   END;
 611 \end{codeblock}
 612
 613 Postoji i modul \kod{Strings} koji ima nešto drugačije definisane
 614 procedure, no na njih se sada nećemo fokusirati.
 615
 616 \section{Rad sa fajlovima}
 617
 618 \subsection{Modul FIO}
 619
 620 U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
 621 sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
 622 kao što uvozimo i komande).
 623
 624 \begin{quote}U primerima se pretpostavlja da je ``f'' tipa \kod{File}, ``str'' niz
 625 znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa \kod{CARDINAL} i ``ch''
 626 tipa \kod{CHAR}. Dodatna promenljiva ``n'' tipa \kod{INTEGER} služi za
 627 formatiranje slično kao u modulu \kod{InOut}.
 628 \end{quote}
 629
 630 Promenljiva tipa \kod{File} se mora vezati za neki fajl
 631 jednom od sledećih komandi:
 632 \begin{itemize}
 633 \item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\
 634 \item \kod{f := Create(str);} -- kreira se fajl za pisanje\\
 635 \item \kod{f := Append(str);} -- otvara se postojeći fajl za
 636   dopisivanje na kraj
 637 \end{itemize}
 638
 639 Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo
 640 \kod{Close(f);}
 641
 642 Procedure za čitanje i pisanje su vrlo slične onima iz modula
 643 \kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
 644 fajl sa kojim se radi.
 645 \begin{itemize}
 646 \item \kod{RdStr(f,str)} -- učitava ceo red u string str\\
 647 \item   \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\
 648 \item   \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\
 649 \item   \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
 650 \end{itemize}
 651
 652 Analogne su i procedure za pisanje različitih tipova u fajl:
 653 \begin{itemize}
 654 \item \kod{WrStr(f,str); WrInt(f,i,n);}\ \kod{WrCard(f,c,n);}\
 655   \kod{WrChar(f,ch);}
 656 \end{itemize}
 657
 658
 659 Prelom reda se eksplicitno upisuje u fajl komandom \kod{WrLn(f);}.
 660
 661 Da bi odredili da li smo stigli do kraja fajla možemo koristiti
 662 \kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
 663 FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
 664 operacijom čitanja stigli do kraja fajla.  Ne menja joj se vrednost
 665 pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
 666 tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
 667 radu.
 668
 669 \subsection{Zadatak: ispis sadržaja fajla na ekran}
 670
 671 Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 672
 673 \begin{lstlisting}[style=codeblock]
 674 MODULE ispis;
 675 FROM FIO IMPORT File, Open, Close, EOF, RdStr;
 676 FROM InOut IMPORT WriteString, WriteLn, ReadString;
 677
 678 PROCEDURE ispisF(ime: ARRAY OF CHAR);
 679 VAR
 680   f:File;
 681   s : ARRAY[1..100] OF CHAR;
 682 BEGIN
 683   f:=Open(ime);
 684   EOF := FALSE;
 685   WHILE NOT EOF DO
 686       RdStr(f,s);
 687       WriteString(s);
 688       WriteLn;
 689   END;
 690   Close(f);
 691 END ispisF;
 692
 693 VAR
 694   ime: ARRAY[1..100] OF CHAR;
 695 BEGIN
 696   WriteString("unesite ime fajla:");
 697   ReadString(ime);
 698   ispisF(ime);
 699 END ispis.
 700 \end{lstlisting}
 701
 702 \subsection{Zadatak: spisak studenata}
 703
 704 Napraviti program koji iz fajla učitava podatke o studentima, dodaje
 705 novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
 706 podatak o jednom studentu, redom prezime, ime i godina rođenja,
 707 razdvojeni razmacima.
 708
 709 \begin{lstlisting}[style=codeblock]
 710 MODULE nizslog;
 711 FROM InOut IMPORT WriteString, WriteLn,
 712      WriteCard, ReadCard, ReadString;
 713 FROM FIO IMPORT File, Open, Create, Close, EOF,
 714     RdItem, RdCard, WrStr, WrCard, WrLn;
 715 FROM Str IMPORT Compare;
 716
 717 CONST
 718     MaxStud = 100;
 719 TYPE
 720     String = ARRAY[1..30] OF CHAR;
 721     Student = RECORD
 722         ime, prez: String;
 723         god: CARDINAL;
 724     END;
 725     Studenti = ARRAY[1..MaxStud] OF Student;
 726
 727 PROCEDURE UcitajF(fajl:String;
 728           VAR spisak: Studenti; VAR n:CARDINAL);
 729 VAR
 730     f:File;
 731 BEGIN
 732     n:=0;
 733     f:= Open(fajl);
 734     EOF := FALSE;
 735     WHILE NOT EOF DO
 736         INC(n);
 737         RdItem(f, spisak[n].prez);
 738         RdItem(f, spisak[n].ime);
 739         spisak[n].god := RdCard(f);
 740     END;
 741     Close(f);
 742 END UcitajF;
 743
 744 PROCEDURE Ispisi(spisak:Studenti; n:CARDINAL);
 745 VAR
 746     i: CARDINAL;
 747 BEGIN
 748     FOR i:=1 TO n DO
 749         WriteString(spisak[i].prez);
 750         WriteString(" ");
 751         WriteString(spisak[i].ime);
 752         WriteString(" ");
 753         WriteCard(spisak[i].god,1);
 754         WriteLn;
 755     END;
 756 END Ispisi;
 757
 758 PROCEDURE IspisiF(fajl:String;
 759           spisak:Studenti; n:CARDINAL);
 760 VAR
 761     f:File;
 762     i: CARDINAL;
 763 BEGIN
 764     IF (n>0) AND (n<=MaxStud) THEN
 765         f:=Create(fajl);
 766         (* pravimo takav fajl da ne
 767            postoji zadnji prazan red *)
 768         FOR i:=1 TO n-1 DO
 769             WrStr(f,spisak[i].prez);
 770             WrStr(f," ");
 771             WrStr(f,spisak[i].ime);
 772             WrStr(f," ");
 773             WrCard(f,spisak[i].god,1);
 774             WrLn(f);
 775         END;
 776         WrStr(f,spisak[n].prez);
 777         WrStr(f," ");
 778         WrStr(f,spisak[n].ime);
 779         WrStr(f," ");
 780         WrCard(f,spisak[n].god,1);
 781         Close(f);
 782     END;
 783 END IspisiF;
 784
 785 PROCEDURE NoviStudent(VAR spisak:Studenti;
 786                       VAR n:CARDINAL);
 787 VAR
 788     stud,temp:Student;
 789     i:CARDINAL;
 790     dodaj:BOOLEAN;
 791 BEGIN
 792     IF n<MaxStud THEN
 793         WriteString("Prezime novog studenta?");
 794         ReadString(stud.prez);
 795         WriteString("Ime novog studenta?");
 796         ReadString(stud.ime);
 797         WriteString("Godina rodjenja");
 798         WriteString("novog studenta?");
 799         ReadCard(stud.god);
 800         (* proverimo da li vec postoji *)
 801         i:=1;
 802         dodaj := TRUE;
 803         WHILE (i<=n) AND dodaj DO
 804             temp := spisak[i];
 805             IF (temp.god = stud.god) &
 806               (Compare(temp.prez,stud.prez)=0) &
 807               (Compare(temp.ime,stud.ime)=0) THEN
 808                 dodaj:=FALSE;
 809             END;
 810             INC(i);
 811         END;
 812         IF dodaj THEN
 813             INC(n);
 814             spisak[n]:=stud;
 815         ELSE
 816             WriteString("podaci vec postoje!");
 817         END;
 818     ELSE
 819         WriteString("popunjen kapacitet!");
 820     END;
 821 END NoviStudent;
 822
 823 VAR
 824     spisak : Studenti;
 825     fajl:String;
 826     n:CARDINAL;
 827 BEGIN
 828     fajl:="studenti.txt";
 829     UcitajF(fajl, spisak, n);
 830     Ispisi(spisak, n);
 831     NoviStudent(spisak,n);
 832     IspisiF(fajl, spisak, n);
 833 END nizslog.
 834 \end{lstlisting}
 835
 836 \section{Liste i pokazivači}
 837
 838 Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure
 839 \kod{ALLOCATE} i \kod{DEALLOCATE}. U kodu se tada mogu koristiti i njihovi
 840 skraćeni oblici \kod{NEW} i \kod{DISPOSE}.
 841
 842 \subsection{Zadatak: Formiranje, štampanje i brisanje listi}
 843
 844
 845 \begin{lstlisting}[style=codeblock]
 846 MODULE liste;
 847 FROM InOut IMPORT WriteString, WriteLn, WriteInt,
 848         ReadInt, ReadCard;
 849 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 850 TYPE
 851   brojevi = POINTER TO brojSlog;
 852   brojSlog = RECORD
 853       info:INTEGER;
 854       veza:brojevi;
 855   END;
 856 VAR
 857   n,i:CARDINAL;
 858   lista : brojevi;
 859   br:INTEGER;
 860
 861 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 862 (* dodaje broj br na pocetak liste *)
 863 VAR
 864   temp:brojevi;
 865 BEGIN
 866   NEW(temp);
 867   temp^.info := br;
 868   temp^.veza := lista;
 869   lista := temp;
 870 END DodajPoc;
 871
 872 PROCEDURE Stampaj(lista:brojevi);
 873 VAR
 874   temp:brojevi;
 875 BEGIN
 876   temp:=lista;
 877   WHILE temp # NIL DO
 878       WriteInt(temp^.info,0);
 879       WriteLn;
 880       temp := temp^.veza;
 881   END;
 882 END Stampaj;
 883
 884 PROCEDURE Unisti(VAR lista:brojevi);
 885 VAR
 886   temp:brojevi;
 887 BEGIN
 888   temp:=lista;
 889   WHILE temp # NIL DO
 890         lista:=lista^.veza;
 891         DISPOSE(temp);
 892         temp:=lista;
 893   END;
 894 END Unisti;
 895
 896 BEGIN
 897   lista := NIL;
 898   WriteString('unesite n (broj brojeva): ');
 899   ReadCard(n);
 900   WriteString('unesite brojeve: ');
 901   WriteLn;
 902   FOR i:= 1 TO n DO
 903       ReadInt(br);
 904       DodajPoc(lista,br);
 905   END;
 906   WriteString('sadrzaj liste:');
 907   WriteLn;
 908   Stampaj(lista);
 909   Unisti(lista);
 910   WriteString('memorija je oslobodjena');
 911   WriteLn;
 912 END liste.
 913 \end{lstlisting}
 914
 915 Alternativno je poziv \kod{DodajPoc} moguće zameniti pozivom jedne od
 916 sledeće dve procedure čime se dobija dodavanje elementa na kraj liste,
 917 ili kreiranje sortirane liste:
 918
 919 \begin{lstlisting}[style=codeblock]
 920 PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
 921 (* dodaje element na kraj liste *)
 922 VAR
 923   tekuci, temp :brojevi;
 924 BEGIN
 925   NEW(temp);
 926   temp^.info := br;
 927   temp^.veza := NIL;
 928   IF lista = NIL THEN
 929      (* prazna lista *)
 930      lista:=temp;
 931   ELSE
 932      tekuci := lista;
 933      WHILE tekuci^.veza#NIL DO
 934         tekuci:=tekuci^.veza;
 935      END;
 936      tekuci^.veza := temp;
 937   END;
 938 END DodajKraj;
 939
 940 PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
 941 (* dodaje broj tako da lista ostane sortirana
 942    (podrazumeva se da je vec sortirana) *)
 943 VAR
 944   temp, tekuci : brojevi;
 945 BEGIN
 946   NEW(temp);
 947   temp^.info:=br;
 948   temp^.veza:=NIL;
 949   IF (lista = NIL) OR (lista^.info>=br) THEN
 950   (*prazna lista ili na pocetak*)
 951     temp^.veza:=lista;
 952     lista := temp;
 953   ELSE
 954   (*negde u listi*)
 955     tekuci:= lista;
 956     WHILE (tekuci^.veza # NIL) AND
 957           (tekuci^.veza^.info<=br) DO
 958       tekuci:=tekuci^.veza;
 959     END;
 960     temp^.veza := tekuci^.veza;
 961     tekuci^.veza:=temp;
 962   END;
 963 END DodajSort;
 964 \end{lstlisting}
 965
 966 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 967
 968 \begin{lstlisting}[style=codeblock]
 969 MODULE liste2;
 970 FROM InOut IMPORT WriteString, WriteLn,
 971            WriteCard, ReadCard;
 972 FROM IO IMPORT RdKey;
 973 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 974 TYPE
 975   skupZn = SET OF CHAR;
 976   brojevi = POINTER TO brojSlog;
 977   brojSlog = RECORD
 978       info:CARDINAL;
 979       veza:brojevi;
 980   END;
 981 VAR
 982   lista : brojevi;
 983   menu,prazno:CHAR;
 984
 985 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 986 (* dodaje broj pom na pocetak liste *)
 987 VAR
 988   temp:brojevi;
 989 BEGIN
 990   (* kreiramo novi element *)
 991   NEW(temp);
 992   temp^.info := br;
 993   (* treba da pokazuje na ostatak liste *)
 994   temp^.veza := lista;
 995   (* pocetak liste je novi element *)
 996   lista := temp;
 997 END DodajPoc;
 998
 999 PROCEDURE Unos(VAR lista:brojevi);
1000 (* dodaje n brojeva u listu *)
1001 VAR
1002   n,i,br:CARDINAL;
1003 BEGIN
1004   WriteString('unesite n (broj brojeva): ');
1005   ReadCard(n);
1006   FOR i:= 1 TO n DO
1007       WriteString("unesite broj ");
1008       WriteCard(i,0);
1009       WriteString(": ");
1010       ReadCard(br);
1011       DodajPoc(lista,br);
1012   END;
1013 END Unos;
1014
1015 (* -- procedure za stampu -- *)
1016
1017 PROCEDURE Stampaj(lista:brojevi);
1018 (* stampa sadrzaj liste na ekran *)
1019 VAR
1020   temp:brojevi;
1021 BEGIN
1022   WriteLn;
1023   WriteString("Sadrzaj liste:");
1024   WriteLn;
1025   temp:=lista;
1026   WHILE temp # NIL DO
1027       WriteCard(temp^.info,0);
1028       WriteLn;
1029       temp := temp^.veza;
1030   END;
1031 END Stampaj;
1032
1033 PROCEDURE StampajK(VAR lista:brojevi);
1034 (* stampa k-ti element (k unosi korisnik) *)
1035 VAR
1036   temp:brojevi;
1037   k,brojac:CARDINAL;
1038 BEGIN
1039   WriteString("unesite redni broj elementa:");
1040   ReadCard(k);
1041   temp:=lista;
1042   brojac := 1;
1043   WHILE (temp# NIL) AND (k>brojac) DO
1044     temp:=temp^.veza;
1045     INC(brojac);
1046   END;
1047   IF (temp#NIL) THEN
1048     WriteCard(temp^.info,2);
1049   ELSE
1050     WriteString("greska! - ne postoji element");
1051     WriteString(" u listi sa rednim brojem ");
1052     WriteCard(k,2);
1053   END;
1054   WriteLn();
1055 END StampajK;
1056
1057 PROCEDURE StampajMinimum(VAR lista:brojevi);
1058 (* nalazi i stampa minimalni element liste *)
1059 VAR
1060   temp:brojevi;
1061   min:CARDINAL;
1062 BEGIN
1063   IF (lista=NIL) THEN
1064     WriteString("prazna lista!");
1065   ELSE
1066     min:=lista^.info;
1067     temp:=lista^.veza;
1068     WHILE temp # NIL DO
1069       IF temp^.info < min THEN
1070         min := temp^.info;
1071       END;
1072       temp := temp^.veza;
1073     END;
1074     WriteString("Minimalni element liste je ");
1075     WriteCard(min,0);
1076   END;
1077   WriteLn;
1078 END StampajMinimum;
1079
1080 (* -- pomocne procedure, bez ispisa  -- *)
1081
1082 PROCEDURE UListi(lista:brojevi;
1083                  br: CARDINAL):BOOLEAN;
1084 (* vraca da li se 'br' nalazi u listi 'lista' *)
1085 VAR
1086   temp:brojevi;
1087 BEGIN
1088   temp:=lista;
1089   WHILE (temp # NIL) AND (temp^.info # br) DO
1090     (* dok ne dodjemo do kraja liste
1091        ili ne nadjemo broj *)
1092       temp := temp^.veza;
1093   END;
1094   IF temp#NIL THEN
1095     (* znaci da nismo na kraju liste,
1096        tj da je nadjen broj *)
1097     RETURN TRUE;
1098   ELSE (* temp = NIL *)
1099     RETURN FALSE;
1100   END;
1101 END UListi;
1102
1103 PROCEDURE IzbaciIzListe(VAR lista:brojevi;
1104                         br: CARDINAL):BOOLEAN;
1105 (* izbacuje broj 'br' iz liste, naravno ako
1106    postoji i vraca da li je operacija uspesno
1107    obavljena *)
1108 VAR
1109   temp,prethodni:brojevi;
1110 BEGIN
1111   (* proverimo da li je prvi element *)
1112   IF (lista # NIL) AND (lista^.info = br) THEN
1113     temp:=lista;
1114     lista :=lista^.veza;
1115     DISPOSE(temp);
1116     RETURN TRUE;
1117   ELSE
1118   (* trazimo u ostatku liste *)
1119     temp:=lista;
1120     prethodni:=NIL;
1121     WHILE (temp # NIL) AND (temp^.info # br) DO
1122         (* dok ne dodjemo do kraja liste
1123            ili ne nadjemo broj *)
1124         prethodni:=temp;
1125         temp := temp^.veza;
1126     END;
1127     IF temp#NIL THEN
1128       (* znaci da nismo na kraju liste,
1129          odnosno da smo nasli broj *)
1130       (* prevezemo listu oko elementa *)
1131       prethodni^.veza:=temp^.veza;
1132       DISPOSE(temp);
1133       RETURN TRUE;
1134     ELSE
1135       RETURN FALSE;
1136     END;
1137   END;
1138 END IzbaciIzListe;
1139
1140 PROCEDURE IzbaciIzListeSve(VAR lista:brojevi;
1141                         br: CARDINAL):CARDINAL;
1142 (* izbacuje sve brojeve 'br' iz liste, naravno ako
1143    postoje i vraca koliko ih je bilo *)
1144 VAR
1145   temp,prethodni:brojevi;
1146   brojac : CARDINAL;
1147 BEGIN
1148   brojac := 0;
1149   (* uklanjamo sa pocetka koliko je potrebno *)
1150   WHILE (lista # NIL) AND (lista^.info = br) DO
1151     temp:=lista;
1152     lista :=lista^.veza;
1153     DISPOSE(temp);
1154     INC(brojac);
1155   END;
1156   (* trazimo u ostatku liste *)
1157   IF (lista # NIL) THEN
1158     temp:=lista;
1159     WHILE (temp^.veza # NIL)  DO
1160         (* idemo do poslednjeg elementa liste *)
1161         prethodni:=temp;
1162         temp := temp^.veza;
1163         IF temp^.info = br THEN
1164           (* prevezemo listu oko elementa *)
1165           prethodni^.veza:=temp^.veza;
1166           DISPOSE(temp);
1167           INC(brojac);
1168           (* vracamo se jedan korak da bi
1169           u novom krugu proverili i ovaj element *)
1170           temp := prethodni;
1171         END;
1172     END;
1173   END;
1174   RETURN brojac;
1175 END IzbaciIzListeSve;
1176
1177 (* - procedure sa interakcijom sa korisnikom - *)
1178
1179 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1180 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1181 VAR
1182   br:CARDINAL;
1183 BEGIN
1184   WriteString("unesite broj za izbacivanje: ");
1185   ReadCard(br);
1186   IF IzbaciIzListe(lista,br) THEN
1187     WriteString("broj je izbacen iz liste");
1188   ELSE
1189     WriteString("greska! - broj ne postoji");
1190   END;
1191   WriteLn;
1192 END IzbacivanjeEl;
1193
1194 PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
1195 (* izbacuje sve primeke unetog broj iz liste
1196    koristeci proceduru IzbaciIzListeSve *)
1197 VAR
1198   br, ukupno:CARDINAL;
1199 BEGIN
1200   WriteString("unesite broj za izbacivanje: ");
1201   ReadCard(br);
1202   ukupno := IzbaciIzListeSve(lista,br);
1203   WriteString("Iz liste je izbaceno ");
1204   WriteCard(ukupno,3);
1205   WriteString(" el.");
1206   WriteLn;
1207 END IzbacivanjeElSvi;
1208
1209 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1210 (* izbacuje k-ti element iz liste *)
1211 VAR
1212   temp,tekuci:brojevi;
1213   k,brojac:CARDINAL;
1214 BEGIN
1215   IF lista=NIL THEN
1216     WriteString("lista je prazna, nema ");
1217     WriteString("elemenata za izbacivanje");
1218   ELSE
1219     WriteString("unesite redni broj elementa");
1220     WriteString(" koji zelite izbaciti:");
1221     ReadCard(k);
1222     IF k=1 THEN (*izbacivanje prvog *)
1223       temp:=lista;
1224       lista := lista^.veza;
1225       DISPOSE(temp);
1226     ELSE
1227       tekuci := lista;
1228       brojac := 2; (*gledamo jedan unapred*)
1229       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1230         (* idemo kroz listu do k-tog el *)
1231         tekuci:=tekuci^.veza;
1232         INC(brojac);
1233       END;
1234       IF (tekuci^.veza#NIL) THEN
1235          (* pamtimo element za brisanje *)
1236          temp:=tekuci^.veza;
1237          (* prevezujemo listu oko njega*)
1238          tekuci^.veza:=tekuci^.veza^.veza;
1239          DISPOSE(temp);
1240       ELSE
1241         WriteString("greska! - ne postoji el ");
1242         WriteString("u listi sa rednim brojem ");
1243         WriteCard(k,2);
1244       END;
1245       WriteLn();
1246     END;
1247   END;
1248 END IzbacivanjeK;
1249
1250 PROCEDURE Pretraga(lista:brojevi);
1251 (* provera da li se uneti broj nalazi u listi *)
1252 VAR
1253   br:CARDINAL;
1254 BEGIN
1255   WriteString("unesite trazeni broj");
1256   ReadCard(br);
1257   IF UListi(lista,br) THEN
1258     WriteString("broj postoji u listi");
1259   ELSE
1260     WriteString("broj ne postoji u listi");
1261   END;
1262   WriteLn;
1263 END Pretraga;
1264
1265 (* -- oslobadjanje memorije -- *)
1266
1267 PROCEDURE Unisti(VAR lista:brojevi);
1268 VAR
1269   temp:brojevi;
1270 BEGIN
1271   temp:=lista;
1272   WHILE temp # NIL DO
1273         lista:=lista^.veza;
1274         DISPOSE(temp);
1275         temp:=lista;
1276   END;
1277 END Unisti;
1278
1279 BEGIN
1280   (* pocinjemo od prazne liste *)
1281   lista := NIL;
1282   REPEAT
1283      WriteLn;
1284      WriteString("Ilustracija rada sa");
1285      WriteString(" listama brojeva");
1286      WriteLn;
1287      WriteString("=============================");
1288      WriteLn;
1289      WriteString("s - Stampa");WriteLn;
1290      WriteString("u - Unos");WriteLn;
1291      WriteString("i - Izbacivanje br iz liste");
1292      WriteLn;
1293      WriteString("v - izbacivanje svih br iz liste");
1294      WriteLn;
1295      WriteString("e - izbacivanje k-tog El.");
1296      WriteLn;
1297      WriteString("k - stampanje k-tog elementa");
1298      WriteLn;
1299      WriteString("m - Minimalni broj u listi");
1300      WriteLn;
1301      WriteString("p - Pretraga el. u listi");
1302      WriteLn;
1303      WriteLn;
1304      WriteString("q - kraj rada (Quit)");WriteLn;
1305       REPEAT
1306         menu := CAP(RdKey());
1307       UNTIL menu IN skupZn{'S','U','E','I','V',
1308                            'M','K','P','Q'};
1309       IF menu#'Q' THEN
1310         CASE menu OF
1311          'S' : Stampaj(lista);|
1312          'U' : Unos(lista);|
1313          'I' : IzbacivanjeEl(lista);|
1314          'V' : IzbacivanjeElSvi(lista);|
1315          'E' : IzbacivanjeK(lista);|
1316          'K' : StampajK(lista); |
1317          'M' : StampajMinimum(lista); |
1318          'P' : Pretraga(lista);|
1319         END;
1320         WriteLn;
1321         WriteString("--- pritisnite bilo koji ");
1322         WriteString("taster za povratak u meni");
1323         prazno:=RdKey();
1324       ELSE
1325         WriteString("Kraj rada")
1326       END;
1327       WriteLn;
1328   UNTIL menu='Q';
1329   Unisti(lista);
1330 END liste2.
1331 \end{lstlisting}
1332
1333
1334 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1335
1336 \begin{lstlisting}[style=codeblock]
1337 MODULE Radnici;
1338
1339 FROM InOut IMPORT WriteString, ReadString,
1340            WriteLn, WriteCard, ReadCard, Done;
1341 FROM IO IMPORT RdKey;
1342 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1343
1344 TYPE
1345   skupZn = SET OF CHAR;
1346   str = ARRAY [1..20] OF CHAR;
1347   radnici = POINTER TO slog;
1348   slog = RECORD
1349            ime, prez : str;
1350            broj : CARDINAL;
1351            sled : radnici
1352          END;
1353 VAR
1354   meni, pom : CHAR;
1355   rad : radnici;
1356
1357   PROCEDURE Clear();
1358   VAR
1359     br: CARDINAL;
1360   BEGIN
1361     FOR br:=1 TO 100 DO
1362       WriteLn;
1363     END;
1364   END Clear;
1365
1366   PROCEDURE Spisak(rad : radnici);
1367   BEGIN
1368     WHILE rad # NIL DO
1369       WriteString(rad^.ime);
1370       WriteString(' ');
1371       WriteString(rad^.prez);
1372       WriteCard(rad^.broj, 8);
1373       WriteLn;
1374       rad := rad^.sled
1375     END
1376   END Spisak;
1377
1378   PROCEDURE Zaposli(VAR rad : radnici);
1379   VAR
1380     novi, tek : radnici;
1381     nadjen : BOOLEAN;
1382   BEGIN
1383     NEW(novi);
1384     REPEAT
1385       WriteString('Ime, prezime i jedinstveni');
1386       WriteString(' broj novog radnika: ');
1387       WriteLn;
1388       ReadString(novi^.ime);
1389       ReadString(novi^.prez);
1390       ReadCard(novi^.broj);
1391       nadjen := FALSE;
1392       tek := rad;
1393       WHILE NOT nadjen AND (tek # NIL) AND
1394             (tek^.broj <= novi^.broj) DO
1395         IF novi^.broj = tek^.broj THEN
1396           nadjen := TRUE
1397         ELSE
1398           tek := tek^.sled
1399         END
1400       END
1401     UNTIL Done AND NOT nadjen;
1402     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1403       novi^.sled := rad;
1404       rad := novi
1405     ELSE
1406       tek := rad;
1407       WHILE (tek^.sled # NIL) AND
1408             (tek^.sled^.broj < novi^.broj) DO
1409         tek := tek^.sled
1410       END;
1411       novi^.sled := tek^.sled;
1412       tek^.sled := novi
1413     END
1414   END Zaposli;
1415
1416   PROCEDURE Otpusti(VAR rad : radnici);
1417   VAR
1418     tek, pom : radnici;
1419     br : CARDINAL;
1420   BEGIN
1421     REPEAT
1422       WriteLn;
1423       WriteString('Unesite redni broj radnika:');
1424       ReadCard(br)
1425     UNTIL Done;
1426     WriteLn;
1427     IF rad = NIL THEN
1428       WriteString('Greska.')
1429     ELSIF br = rad^.broj THEN
1430       pom := rad;
1431       rad := rad^.sled;
1432       DISPOSE(pom)
1433     ELSE
1434       tek := rad;
1435       WHILE (tek^.sled # NIL) AND
1436             (tek^.sled^.broj < br) DO
1437         tek := tek^.sled
1438       END;
1439       IF (tek^.sled = NIL) OR
1440          (tek^.sled^.broj > br) THEN
1441         WriteString('Greska.')
1442       ELSE
1443         pom := tek^.sled;
1444         tek^.sled := tek^.sled^.sled;
1445         DISPOSE(pom)
1446       END
1447     END
1448   END Otpusti;
1449
1450   PROCEDURE Inform(rad : radnici);
1451   VAR
1452     br : CARDINAL;
1453   BEGIN
1454     REPEAT
1455       WriteLn;
1456       WriteString('Unesite redni broj radnika:');
1457       ReadCard(br)
1458     UNTIL Done;
1459     WriteLn;
1460     WHILE (rad # NIL) AND (rad^.broj < br) DO
1461       rad := rad^.sled
1462     END;
1463     IF (rad = NIL) OR (rad^.broj # br) THEN
1464       WriteString('Greska.')
1465     ELSE
1466       WriteString(rad^.ime);
1467       WriteString(' ');
1468       WriteString(rad^.prez)
1469     END
1470   END Inform;
1471
1472   PROCEDURE Bankrot(VAR rad : radnici);
1473   VAR
1474     pom : radnici;
1475   BEGIN
1476     WHILE rad # NIL DO
1477       pom := rad;
1478       rad := rad^.sled;
1479       DISPOSE(pom)
1480     END
1481   END Bankrot;
1482
1483 BEGIN
1484   rad := NIL;
1485   REPEAT
1486     Clear;
1487     WriteString('s - spisak svih zaposlenih');
1488     WriteLn;
1489     WriteString('z - zaposljavanje radnika');
1490     WriteLn;
1491     WriteString('o - otpustanje radnika');
1492     WriteLn;
1493     WriteString('i - informacije o radniku');
1494     WriteLn;
1495     WriteString('b - bankrot firme');
1496     WriteLn;
1497     WriteString('k - kraj rada');
1498     WriteLn;
1499     REPEAT
1500       meni := RdKey();
1501     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1502                               'I', 'B', 'K'};
1503     Clear;
1504     IF CAP(meni) # 'K' THEN
1505       CASE CAP(meni) OF
1506         'S' : Spisak(rad)|
1507         'Z' : Zaposli(rad)|
1508         'O' : Otpusti(rad)|
1509         'I' : Inform(rad)|
1510         'B' : Bankrot(rad)
1511       END;
1512       WriteLn;
1513       WriteString('-- pritisnite bilo koji ');
1514       WriteString('taster za nastavak --');
1515       pom := RdKey()
1516     END
1517   UNTIL CAP(meni) = 'K'
1518 END Radnici.
1519 \end{lstlisting}
1520
1521 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1522
1523 \begin{lstlisting}[style=codeblock]
1524   PROCEDURE Spisak(rad : radnici);
1525   BEGIN
1526     IF rad # NIL THEN
1527       WriteString(rad^.ime);
1528       WriteString(' ');
1529       WriteString(rad^.prez);
1530       WriteCard(rad^.broj, 8);
1531       WriteLn;
1532       Spisak(rad^.sled)
1533     END
1534   END Spisak;
1535 \end{lstlisting}
1536
1537 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1538   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1539   težini}
1540
1541 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1542 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1543 uređenje i po visini i po težini.
1544
1545 \begin{lstlisting}[style=codeblock]
1546 MODULE VisTez;
1547 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1548 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1549 FROM SYSTEM IMPORT TSIZE;
1550 TYPE
1551   pok = POINTER TO element;
1552   element = RECORD
1553               visina, tezina : CARDINAL;
1554               Vveza, Tveza : pok
1555             END;
1556 VAR
1557   pocV, pocT : pok;
1558   vis, tez : CARDINAL;
1559 PROCEDURE Ispisi(pocV, pocT : pok);
1560 VAR
1561   tek : pok;
1562 BEGIN
1563   tek := pocV;
1564   WrStr('Po visini:');
1565   WrLn;
1566   WHILE tek # NIL DO
1567     WrCard(tek^.visina, 6);
1568     tek := tek^.Vveza
1569   END;
1570   WrLn;
1571   tek := pocT;
1572   WrStr('Po tezini:');
1573   WrLn;
1574   WHILE tek # NIL DO
1575     WrCard(tek^.tezina,6);
1576     tek := tek^.Tveza
1577   END
1578 END Ispisi;
1579
1580 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1581                 vis, tez : CARDINAL);
1582 VAR
1583   novi, tek, iza : pok;
1584   nadjen : BOOLEAN;
1585 BEGIN
1586   IF pocV = NIL THEN
1587     ALLOCATE(pocV, TSIZE(element));
1588     pocV^.visina := vis;
1589     pocV^.tezina := tez;
1590     pocV^.Vveza := NIL;
1591     pocV^.Tveza := NIL;
1592     pocT := pocV
1593   ELSE
1594     ALLOCATE(novi, TSIZE(element));
1595     novi^.visina := vis;
1596     novi^.tezina := tez;
1597     tek := pocV;
1598     nadjen := FALSE;
1599     WHILE (tek # NIL) AND NOT nadjen DO
1600       nadjen := vis <= tek^.visina;
1601       IF NOT nadjen THEN
1602         iza := tek;
1603         tek := tek^.Vveza
1604       END
1605     END;
1606     novi^.Vveza := tek;
1607     IF tek = pocV THEN
1608       pocV := novi
1609     ELSE
1610       iza^.Vveza := novi
1611     END;
1612     tek := pocT;
1613     nadjen := FALSE;
1614     WHILE (tek # NIL) AND NOT nadjen DO
1615       nadjen := tez <= tek^.tezina;
1616       IF NOT nadjen THEN
1617         iza := tek;
1618         tek := tek^.Tveza
1619       END
1620     END;
1621     novi^.Tveza := tek;
1622     IF tek = pocT THEN
1623       pocT := novi
1624     ELSE
1625       iza^.Tveza := novi
1626     END
1627   END
1628 END Ubaci;
1629
1630 BEGIN
1631   pocV := NIL;
1632   pocT := NIL;
1633   WrStr('Unesite visinu ---- ');
1634   vis := RdCard();
1635   WHILE vis > 0 DO
1636     WrStr('Unesite tezinu ---- ');
1637     tez := RdCard();
1638     Ubaci(pocV, pocT, vis, tez);
1639     WrLn;
1640     WrStr('Unesite visinu ---- ');
1641     vis := RdCard()
1642   END;
1643   WrLn;
1644   Ispisi(pocV, pocT)
1645 END VisTez.
1646 \end{lstlisting}
1647
1648 \section{Polinomi preko listi}
1649
1650 \subsection{Moduli}
1651
1652 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1653 \kod{Polinom} je definisan u globalnom modulu.
1654
1655 \paragraph{PolinomL.DEF} \
1656
1657 \begin{lstlisting}[style=codeblock]
1658 DEFINITION MODULE PolinomL;
1659 TYPE
1660   Polinom = POINTER TO Monom;
1661   Monom = RECORD
1662             k : REAL;
1663             st : CARDINAL;
1664             veza : Polinom
1665           END;
1666
1667 PROCEDURE Anuliraj(VAR p: Polinom);
1668 PROCEDURE Unos(VAR p: Polinom);
1669 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1670 PROCEDURE Kopiraj(p: Polinom;
1671                   VAR kopija: Polinom);
1672 PROCEDURE UbaciMonom(mon:Polinom;
1673                      VAR p: Polinom);
1674 PROCEDURE PromeniZnak(VAR p: Polinom);
1675 PROCEDURE Saberi(p1, p2: Polinom;
1676                  VAR zbir: Polinom);
1677 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1678 PROCEDURE Oduzmi(p1,p2: Polinom;
1679                  VAR razlika: Polinom);
1680 PROCEDURE MonomPuta(p, mon: Polinom;
1681                     VAR mp : Polinom);
1682 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1683 PROCEDURE Kolicnik(p1, p2: Polinom;
1684                    VAR kol, ost: Polinom;
1685                    VAR ok : BOOLEAN);
1686 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1687                      VAR rez: Polinom);
1688 PROCEDURE DisposePolinom(VAR p: Polinom);
1689
1690 END PolinomL.
1691 \end{lstlisting}
1692
1693 \paragraph{PolinomL.MOD} \
1694
1695 \begin{codeblock}
1696 (* Modul za rad sa polinomima preko listi
1697    verzija 2012, rev 1 *)
1698 IMPLEMENTATION MODULE PolinomL;
1699 FROM InOut IMPORT Write, WriteString, WriteLn,
1700            WriteCard, ReadCard, Done;
1701 FROM RealInOut IMPORT WriteReal, ReadReal;
1702 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1703
1704 PROCEDURE Anuliraj(VAR p: Polinom);
1705 BEGIN
1706   p := NIL;
1707 END Anuliraj;
1708
1709 PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
1710 VAR
1711   pomocni: Polinom;
1712 BEGIN
1713   IF p = NIL THEN
1714     kopija := NIL
1715   ELSE
1716     NEW(kopija);
1717     kopija^ := p^;
1718     p := p^.veza;
1719     pomocni := kopija;
1720     WHILE p <> NIL DO
1721       NEW(pomocni^.veza);
1722       pomocni := pomocni^.veza;
1723       pomocni^ := p^;
1724       p := p^.veza
1725     END
1726   END
1727 END Kopiraj;
1728
1729 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1730
1731   PROCEDURE StampajMonom(m : Polinom);
1732   BEGIN
1733     WITH m^ DO
1734       IF st <> 0 THEN
1735         IF ABS(k) <> 1.0 THEN
1736           WriteReal(ABS(k), d)
1737         END;
1738         Write('x');
1739         IF st <> 1 THEN
1740           Write('^');
1741           WriteCard(st, 1)
1742         END
1743       ELSE
1744         WriteReal(ABS(k), d)
1745       END
1746     END
1747   END StampajMonom;
1748
1749 BEGIN
1750   IF p = NIL THEN
1751     WriteReal(0., d)
1752   ELSE
1753     IF p^.k < 0.0 THEN
1754       WriteString(' - ')
1755     END;
1756     StampajMonom(p);
1757     p := p^.veza;
1758     WHILE p <> NIL DO
1759       IF p^.k > 0.0 THEN
1760         WriteString(' + ')
1761       ELSE
1762         WriteString(' - ')
1763       END;
1764       StampajMonom(p);
1765       p := p^.veza
1766     END
1767   END
1768 END Stampaj;
1769
1770 PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
1771 VAR
1772   stari, tekuci, kopija: Polinom;
1773 BEGIN
1774   IF mon # NIL THEN
1775     NEW(kopija);
1776     kopija^ := mon^;
1777     tekuci := p;
1778         stari := NIL;
1779     WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO
1780       stari := tekuci;
1781       tekuci := tekuci^.veza
1782     END;
1783     kopija^.veza := tekuci;
1784     IF tekuci = p THEN
1785       p := kopija
1786     ELSE
1787       stari^.veza := kopija
1788     END;
1789     IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
1790       kopija^.k := kopija^.k + tekuci^.k;
1791       kopija^.veza := tekuci^.veza;
1792       DISPOSE(tekuci);
1793       IF kopija^.k = 0.0 THEN
1794         IF p = kopija THEN
1795           p := kopija^.veza
1796         ELSE
1797           stari^.veza := kopija^.veza
1798         END;
1799         DISPOSE(kopija)
1800       END
1801     END
1802   END
1803 END UbaciMonom;
1804
1805 PROCEDURE Unos(VAR p : Polinom);
1806 VAR
1807   i, n: CARDINAL;
1808   novi: Polinom;
1809 BEGIN
1810   Anuliraj(p);
1811   REPEAT
1812     WriteLn;
1813     WriteString('Unesite broj monoma n (n>=0) ');
1814     ReadCard(n);
1815   UNTIL Done;
1816   WriteLn;
1817   FOR i := 1 TO n DO
1818     NEW(novi);
1819     WITH novi^ DO
1820       REPEAT
1821         WriteString('Unesite koeficijent monoma br.');
1822         WriteCard(i, 1);
1823         WriteString(' (<> 0) ');
1824         ReadReal(k);
1825         WriteLn
1826       UNTIL k <> 0.0;
1827       REPEAT
1828         WriteLn;
1829         WriteString('Unesite eksponent monoma br.');
1830         WriteCard(i, 1);
1831         WriteString(' (>=0) ');
1832         ReadCard(st);
1833       UNTIL Done;
1834       WriteLn;
1835     END;
1836     UbaciMonom(novi, p);
1837     DISPOSE(novi);
1838   END
1839 END Unos;
1840
1841 PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
1842 BEGIN
1843   Kopiraj(p1, zbir);
1844   WHILE p2 <> NIL DO
1845     UbaciMonom(p2, zbir);
1846     p2 := p2^.veza
1847   END
1848 END Saberi;
1849
1850 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1851 BEGIN
1852   WHILE p <> NIL DO
1853     UbaciMonom(p,rez);
1854     p := p^.veza;
1855   END;
1856 END SaberiNa;
1857
1858 PROCEDURE PromeniZnak(VAR p: Polinom);
1859 VAR
1860   t: Polinom;
1861 BEGIN
1862   t := p;
1863   WHILE t <> NIL DO
1864     t^.k := - t^.k;
1865     t := t^.veza
1866   END
1867 END PromeniZnak;
1868
1869 PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
1870 BEGIN
1871   Kopiraj(p2, razlika);
1872   PromeniZnak(razlika);
1873   WHILE p1 <> NIL DO
1874     UbaciMonom(p1, razlika);
1875     p1 := p1^.veza
1876   END
1877 END Oduzmi;
1878
1879 PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
1880 VAR
1881   tekuci: Polinom;
1882 BEGIN
1883   Anuliraj(mp);
1884   IF (mon <> NIL) AND (p <> NIL) THEN
1885     NEW(mp);
1886     mp^.k := p^.k * mon^.k;
1887     mp^.st := p^.st + mon^.st;
1888     p := p^.veza;
1889     tekuci := mp;
1890     WHILE p <> NIL DO
1891       NEW(tekuci^.veza);
1892       tekuci := tekuci^.veza;
1893       tekuci^.k := p^.k * mon^.k;
1894       tekuci^.st := p^.st + mon^.st;
1895       p := p^.veza
1896     END;
1897     tekuci^.veza := NIL
1898   END
1899 END MonomPuta;
1900
1901 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1902 VAR
1903   pomocni: Polinom;
1904 BEGIN
1905   Anuliraj(pr);
1906   IF (p1 <> NIL) AND (p2 <> NIL) THEN
1907     MonomPuta(p1, p2, pr);
1908     p2 := p2^.veza;
1909     WHILE p2 <> NIL DO
1910       MonomPuta(p1, p2, pomocni);
1911       REPEAT
1912         UbaciMonom(pomocni, pr);
1913         pomocni := pomocni^.veza
1914       UNTIL pomocni = NIL;
1915       p2 := p2^.veza
1916     END
1917   END
1918 END Puta;
1919
1920 PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);
1921
1922   PROCEDURE Deli(VAR kol, ost: Polinom);
1923   VAR
1924     novi, pomocni: Polinom;
1925   BEGIN
1926     IF ost <> NIL THEN
1927       IF ost^.st >= p2^.st THEN
1928         NEW(novi);
1929         novi^.k := - ost^.k / p2^.k;
1930         novi^.st := ost^.st - p2^.st;
1931         MonomPuta(p2, novi, pomocni);
1932         Saberi(ost, pomocni, ost);
1933         novi^.k := - novi^.k;
1934         UbaciMonom(novi, kol);
1935         DISPOSE(novi);
1936         Deli(kol, ost)
1937       END
1938     END
1939   END Deli;
1940
1941 BEGIN (* Kolicnik *)
1942   ok := TRUE;
1943   Anuliraj(kol);
1944   IF p2 = NIL THEN
1945     ok := FALSE
1946   ELSE
1947     Kopiraj(p1, ost);
1948     Deli(kol, ost)
1949   END
1950 END Kolicnik;
1951
1952 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1953                      VAR rez: Polinom);
1954 VAR
1955   i: CARDINAL;
1956 BEGIN
1957   IF n = 0 THEN
1958     NEW(rez);
1959     rez^.k := 1.0;
1960     rez^.st := 0;
1961     rez^.veza := NIL;
1962   ELSIF n = 1 THEN
1963         Kopiraj( p, rez );
1964   ELSE
1965     rez := p;
1966     FOR i := 2 TO n DO
1967       Puta(rez, p, rez)
1968     END
1969   END;
1970 END PolinomNaN;
1971
1972 PROCEDURE DisposePolinom(VAR p: Polinom);
1973 VAR
1974   pomocni: Polinom;
1975 BEGIN
1976   pomocni := p;
1977   WHILE pomocni # NIL DO
1978     p := p^.veza;
1979     DISPOSE(pomocni);
1980     pomocni := p
1981   END
1982 END DisposePolinom;
1983
1984 END PolinomL.
1985 \end{codeblock}
1986
1987
1988 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1989
1990 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1991
1992 \begin{lstlisting}[style=codeblock]
1993 MODULE polinom;
1994 FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj, DisposePolinom, UbaciMonom, Unos, Saberi;
1995 FROM InOut IMPORT WriteString, WriteLn;
1996 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1997
1998 VAR
1999   p,q,rez,pom : Polinom;
2000
2001 BEGIN
2002   (* korisnik unosi prvi polinom *)
2003   WriteString("Unesite polinom:");
2004   WriteLn;
2005   Unos(p);
2006   (* drugi polinom kreiramo mi,
2007      monom po monom *)
2008   Anuliraj(q); (* isto sto i q:=NIL; *)
2009   (* formiramo monom x^5 *)
2010   NEW(pom);
2011   pom^.st:=5;
2012   pom^.k:=1.0;
2013   (* dodajemo ga u polinom *)
2014   UbaciMonom(pom,q);
2015   DISPOSE(pom);
2016   (* -3 x^4 *)
2017   NEW(pom);
2018   pom^.st := 4;
2019   pom^.k := -3.0;
2020   UbaciMonom(pom,q);
2021   DISPOSE(pom);
2022   (* 4 x *)
2023   NEW(pom);
2024   pom^.st := 1;
2025   pom^.k := 4.0;
2026   UbaciMonom(pom,q);
2027   DISPOSE(pom);
2028   (* 7 (x^0) *)
2029   NEW(pom);
2030   pom^.st := 0;
2031   pom^.k := 7.0;
2032   UbaciMonom(pom,q);
2033   DISPOSE(pom);
2034   (* saberemo polinome *)
2035   Saberi(p, q, rez);
2036   (* odstampamo rezultat *)
2037   Stampaj(rez,0);
2038   WriteLn;
2039   (* oslobadjanje zauzete memorije *)
2040   DisposePolinom(p);
2041   DisposePolinom(q);
2042   DisposePolinom(rez);
2043 END polinom.
2044 \end{lstlisting}
2045
2046 \subsection{Zadatak: Suma k polinoma}
2047
2048 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
2049 toga izracunava njihovu sumu
2050
2051 \begin{lstlisting}[style=codeblock]
2052 MODULE PolSuma;
2053
2054 FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom, Unos, Stampaj, SaberiNa;
2055 FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard;
2056 CONST
2057   maxk = 50;
2058 TYPE
2059   nizPol = ARRAY [1..maxk] OF Polinom;
2060 VAR
2061   i, k: CARDINAL;
2062   suma : Polinom;
2063   p : nizPol;
2064 BEGIN
2065   REPEAT
2066     WriteString('Unesite broj k (1 <= k <= ');
2067     WriteCard(maxk, 1);
2068     WriteString(') ');
2069     ReadCard(k);
2070     WriteLn;
2071   UNTIL (1 <= k) AND (k <= maxk);
2072   FOR i := 1 TO k DO
2073     WriteLn;
2074     WriteString('Unos ');
2075     WriteCard(i, 1);
2076     WriteString('. polinoma.');
2077     WriteLn;
2078     Unos(p[i])
2079   END;
2080   Anuliraj(suma);
2081   FOR i := 1 TO k DO
2082     SaberiNa(suma, p[i])
2083   END;
2084   WriteLn;
2085   WriteString('Njihova suma je:');
2086   WriteLn;
2087   Stampaj(suma, 4);
2088   DisposePolinom(suma);
2089   FOR i := 1 TO k DO
2090     DisposePolinom(p[i]);
2091   END;
2092 END PolSuma.
2093 \end{lstlisting}
2094
2095 \section{Stek i red opsluživanja}
2096
2097 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
2098
2099 \begin{lstlisting}[style=codeblock]
2100 DEFINITION MODULE QueueInfo;
2101 CONST
2102   Maxqueue = 100;
2103 TYPE
2104   InfoTip = CHAR;
2105
2106 END QueueInfo.
2107
2108 IMPLEMENTATION MODULE QueueInfo;
2109 END QueueInfo.
2110
2111 DEFINITION MODULE RedOpsl1;
2112 FROM QueueInfo IMPORT InfoTip,Maxqueue;
2113 TYPE
2114   Niz = ARRAY[1..Maxqueue] OF InfoTip;
2115   RedOpslTip = RECORD
2116         Prvi, Zadnji : CARDINAL;
2117         Element : Niz
2118   END;
2119
2120 PROCEDURE MakeNull(VAR q : RedOpslTip);
2121 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2122 PROCEDURE First(VAR q : RedOpslTip;
2123                 VAR x : InfoTip;
2124                 VAR ok : BOOLEAN);
2125 PROCEDURE PopFirst(VAR q : RedOpslTip;
2126                    VAR ok : BOOLEAN);
2127 PROCEDURE AddRear(VAR q : RedOpslTip;
2128                   x : InfoTip;
2129                   VAR ok : BOOLEAN);
2130
2131 END RedOpsl1.
2132
2133 IMPLEMENTATION MODULE RedOpsl1;
2134 FROM QueueInfo IMPORT Maxqueue,InfoTip;
2135
2136 PROCEDURE MakeNull(VAR q : RedOpslTip);
2137 BEGIN
2138   WITH q DO
2139     Prvi := 0;
2140     Zadnji := 0
2141   END
2142 END MakeNull;
2143
2144 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2145 BEGIN
2146   RETURN q.Zadnji = 0
2147 END Empty;
2148
2149
2150 PROCEDURE First(VAR q : RedOpslTip;
2151                 VAR x : InfoTip;
2152                 VAR ok : BOOLEAN);
2153 BEGIN
2154   IF Empty(q) THEN
2155     ok := FALSE
2156   ELSE
2157     ok := TRUE;
2158     WITH q DO
2159       x := Element[Prvi]
2160     END
2161   END
2162 END First;
2163
2164 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
2165 BEGIN
2166   IF i = Maxqueue THEN
2167     RETURN 1
2168   ELSE
2169     RETURN i+1
2170   END
2171 END AddOne;
2172
2173 PROCEDURE PopFirst(VAR q : RedOpslTip;
2174                    VAR ok : BOOLEAN);
2175 BEGIN
2176   IF Empty(q) THEN
2177     ok := FALSE
2178   ELSE
2179     ok := TRUE;
2180     WITH q DO
2181       IF Prvi = Zadnji THEN
2182         MakeNull(q)
2183       ELSE
2184         Prvi := AddOne(Prvi)
2185       END
2186     END
2187   END
2188 END PopFirst;
2189
2190 PROCEDURE AddRear(VAR q : RedOpslTip;
2191                   x : InfoTip;
2192                   VAR ok : BOOLEAN);
2193 BEGIN
2194   WITH q DO
2195     IF AddOne(Zadnji) = Prvi THEN
2196       ok := FALSE
2197     ELSE
2198       ok := TRUE;
2199       IF Empty(q) THEN
2200         Prvi := 1;
2201         Zadnji := 1
2202       ELSE
2203         Zadnji := AddOne(Zadnji)
2204       END;
2205       Element[Zadnji] := x
2206     END
2207   END
2208 END AddRear;
2209
2210 END RedOpsl1.
2211
2212 MODULE Bafer;
2213 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
2214 FROM FIO IMPORT File,WrChar, Create, Close;
2215 IMPORT IO;
2216
2217 CONST
2218   ImeIzlaza = 'izlaz.txt';
2219
2220 VAR
2221   izlaz : File;
2222   znak : CHAR;
2223   buffer : RedOpslTip;
2224
2225 PROCEDURE IsprazniBafer(VAR dat : File;
2226                         VAR buf : RedOpslTip);
2227 VAR
2228   znak : CHAR;
2229   ok : BOOLEAN;
2230 BEGIN
2231   WHILE NOT Empty(buf) DO
2232     First(buf, znak, ok);
2233     PopFirst(buf, ok);
2234     WrChar(dat, znak)
2235   END
2236 END IsprazniBafer;
2237
2238 PROCEDURE BaferWrite(VAR dat : File;
2239                      VAR buf : RedOpslTip;
2240                      znak : CHAR);
2241 VAR
2242   ok : BOOLEAN;
2243 BEGIN
2244   AddRear(buf, znak, ok);
2245   IF NOT ok THEN
2246     IsprazniBafer(dat, buf);
2247     AddRear(buf, znak, ok)
2248   END
2249 END BaferWrite;
2250
2251 BEGIN
2252   izlaz := Create(ImeIzlaza);
2253   MakeNull(buffer);
2254   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
2255   IO.WrStr(ImeIzlaza);
2256   IO.WrChar('.');
2257   IO.WrLn;
2258   IO.WrStr('Unos zavrsite tackom.');
2259   IO.WrLn;
2260   znak := IO.RdChar();
2261   WHILE znak # '.' DO
2262     BaferWrite(izlaz, buffer, znak);
2263     znak := IO.RdChar();
2264   END;
2265   IsprazniBafer(izlaz, buffer);
2266   Close(izlaz)
2267 END Bafer.
2268 \end{lstlisting}
2269
2270 \subsection%
2271 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
2272
2273 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
2274 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
2275
2276 \begin{lstlisting}[style=codeblock]
2277 DEFINITION MODULE Stek;
2278 CONST
2279   Maxstack = 100;
2280 TYPE
2281   Niz = ARRAY [1..Maxstack] OF CHAR;
2282   StekTip = RECORD
2283             Top : CARDINAL;
2284             Element : Niz
2285           END;
2286 PROCEDURE MakeNull(VAR s : StekTip);
2287 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2288
2289 PROCEDURE Top(VAR s : StekTip;
2290               VAR x : CHAR;
2291               VAR ok : BOOLEAN);
2292 PROCEDURE Pop(VAR s : StekTip;
2293               VAR ok : BOOLEAN);
2294 PROCEDURE Push(VAR s : StekTip;
2295                x : CHAR;
2296                VAR ok : BOOLEAN);
2297 END Stek.
2298
2299
2300 IMPLEMENTATION MODULE Stek;
2301
2302 PROCEDURE MakeNull(VAR s : StekTip);
2303 BEGIN
2304   s.Top := 0
2305 END MakeNull;
2306
2307 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2308 BEGIN
2309   RETURN s.Top = 0
2310 END Empty;
2311
2312 PROCEDURE Top(VAR s : StekTip;
2313               VAR x : CHAR;
2314               VAR ok : BOOLEAN);
2315 BEGIN
2316   IF Empty(s) THEN
2317     ok := FALSE
2318   ELSE
2319     ok := TRUE;
2320     WITH s DO
2321       x := Element[Top]
2322     END
2323   END
2324 END Top;
2325
2326 PROCEDURE Pop(VAR s : StekTip;
2327               VAR ok : BOOLEAN);
2328 BEGIN
2329   IF Empty(s) THEN
2330     ok := FALSE
2331   ELSE
2332     ok := TRUE;
2333     DEC(s.Top)
2334   END
2335 END Pop;
2336
2337 PROCEDURE Push(VAR s : StekTip;
2338                x : CHAR;
2339                VAR ok : BOOLEAN);
2340 BEGIN
2341   WITH s DO
2342     IF Top = Maxstack THEN
2343       ok := FALSE
2344     ELSE
2345       ok := TRUE;
2346       INC(Top);
2347       Element[Top] := x
2348     END
2349   END
2350 END Push;
2351 END Stek.
2352
2353 MODULE wcw;
2354 (* Da li rec pripada gramatici wcw+. *)
2355 FROM Stek IMPORT StekTip, MakeNull, Empty,
2356                  Top, Pop, Push;
2357 FROM InOut IMPORT Read, Write, WriteString, EOL;
2358 TYPE
2359   slova = SET OF CHAR;
2360 VAR
2361   S : StekTip;
2362   Ch, C : CHAR;
2363   ok : BOOLEAN;
2364 BEGIN
2365   MakeNull(S);
2366   Read(Ch);
2367   ok := TRUE;
2368   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
2369     Push(S, Ch, ok);
2370     Read(Ch);
2371   END;
2372   IF NOT ok THEN
2373     WriteString('Greska - mali stek')
2374   ELSIF Ch # 'c' THEN
2375     WriteString('Pogresan string')
2376   ELSE
2377     Read(Ch);
2378     WHILE ok AND (Ch # EOL) DO
2379       Top(S, C, ok);
2380       ok := ok AND (C = Ch);
2381       IF ok THEN
2382         Pop(S, ok);
2383         Read(Ch);
2384       END
2385     END;
2386     IF NOT (ok AND Empty(S)) THEN
2387       WriteString('Pogresan string')
2388     ELSE
2389       WriteString('String pripada jeziku L')
2390     END
2391   END
2392 END wcw.
2393 \end{lstlisting}
2394
2395 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
2396
2397
2398 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
2399 koji figurišu u izrazu su jednocifreni.
2400
2401 \begin{lstlisting}[style=codeblock]
2402 MODULE PostFix;
2403
2404 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
2405 FROM InOut IMPORT Read, Write, WriteInt, EOL;
2406 TYPE
2407   slova = SET OF CHAR;
2408 VAR
2409   S : StekTip;
2410   Ch : CHAR;
2411   Op1, Op2 : INTEGER;
2412   ok : BOOLEAN;
2413 PROCEDURE Conv(Ch : CHAR) : INTEGER;
2414 BEGIN
2415   RETURN  ORD(Ch) - ORD('0')
2416 END Conv;
2417
2418 BEGIN
2419   MakeNull(S);
2420   Read(Ch);
2421   WHILE Ch # EOL DO
2422     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
2423       Top(S, Op2, ok);
2424       Pop(S, ok);
2425       Top(S, Op1, ok);
2426       Pop(S, ok);
2427       CASE Ch OF
2428         '+' : Op1 := Op1 + Op2 |
2429         '-' : Op1 := Op1 - Op2 |
2430         '*' : Op1 := Op1 * Op2 |
2431         '/' : Op1 := Op1 DIV Op2 |
2432         '%' : Op1 := Op1 MOD Op2
2433       END;
2434       Push(S, Op1, ok)
2435     ELSE
2436       Push(S, Conv(Ch), ok)
2437     END;
2438     Read(Ch);
2439   END;
2440   Top(S, Op1, ok);
2441   Write('=');
2442   WriteInt(Op1,5)
2443 END PostFix.
2444 \end{lstlisting}
2445
2446
2447 \section{Simulacija rekurzije}
2448
2449
2450 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
2451 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
2452
2453 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
2454 mesta poziva, a u skladu sa tim se kreira InfoTip.
2455
2456 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
2457 rekurzivnih poziva.
2458
2459 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
2460 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
2461 pozivi.
2462
2463 \begin{lstlisting}
2464 MakeNull(S);
2465 REPEAT
2466   WHILE treba_rekurzija DO
2467     -prepisati sve od pocetka originalne
2468      procedure do prvog rekurzivnog poziva
2469     -staviti na stek potrebne
2470      lokalne promenljive, parametre procedure i
2471      adresu mesta poziva
2472     -podesiti vrednosti parametara da budu
2473      kao u rekurzivnom pozivu procedure
2474   END;
2475   trivijalan poziv
2476   umesto RETURN x pisati rez := x
2477   jos := TRUE;
2478   WHILE jos AND NOT Empty(S) DO
2479     Top(S, el, ok);
2480     Pop(S, ok);
2481     -restauriramo vrednosti sa steka
2482     -u zavisnosti od adrese poziva nastavimo
2483      prepisivanje originalne procedure sa
2484      tog mesta
2485     -ako se dodje do novog rek. poziva tada:
2486        -sacuvati na steku vrednosti
2487        -podesiti vrednosti parametara da budu
2488         kao u rekurzivnom pozivu procedure
2489        -ici na pocetak koda
2490         (ovo se postize sa jos := FALSE)
2491     -inace
2492        ako se naidje na RETURN x pisati rez := x
2493   END
2494 UNTIL Empty(S);
2495 \end{lstlisting}
2496
2497 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
2498
2499 \subsection*{ZADACI}
2500
2501 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
2502
2503 \subsection{Primer 1 -- faktorijel}
2504
2505
2506 \begin{lstlisting}[style=codeblock]
2507 MODULE Fakto;
2508 (* InfoTip = CARDINAL; *)
2509
2510 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2511 FROM StekC IMPORT StekTip, MakeNull, Empty,
2512                   Top, Pop, Push;
2513 VAR
2514   n : CARDINAL;
2515 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
2516 BEGIN
2517   IF n <= 1 THEN
2518     RETURN 1
2519   ELSE
2520     RETURN n * RFakto(n-1)
2521   END
2522 END RFakto;
2523
2524
2525 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
2526 VAR
2527   s : StekTip;
2528   rez : CARDINAL;
2529   OK : BOOLEAN;
2530 BEGIN
2531   MakeNull(s);
2532   WHILE n > 1 DO
2533     Push(s,n,OK);
2534     DEC(n)
2535   END;
2536   rez := 1;
2537   WHILE NOT Empty(s) DO
2538     Top(s, n, OK);
2539     Pop(s, OK);
2540     rez := n * rez
2541   END;
2542   RETURN rez
2543 END SFakto;
2544
2545 BEGIN
2546   WrStr('n = ');
2547   n := RdCard();
2548   WrLn
2549   WrStr('n! = ');
2550   WrCard(RFakto(n), 1);
2551   WrStr(' = ');
2552   WrCard(SFakto(n), 1)
2553 END Fakto.
2554 \end{lstlisting}
2555
2556 \manbreakJK
2557
2558 \subsection{Primer 2 -- stepenovanje}
2559
2560 \begin{lstlisting}[style=codeblock]
2561 MODULE Step;
2562 (* InfoTip = RECORD
2563                 x : REAL;
2564                 n : CARDINAL;
2565                 adr : (par, nepar)
2566              END;
2567 *)
2568 FROM IO IMPORT WrStr, WrLn, WrReal,
2569         RdReal, RdCard;
2570 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2571              Top, Pop, Push, InfoTip, AdrTip;
2572 VAR
2573   n : CARDINAL;
2574   x : REAL;
2575
2576 PROCEDURE Sqr(y : REAL) : REAL;
2577 BEGIN
2578   RETURN y * y
2579 END Sqr;
2580
2581 PROCEDURE RStep(x : REAL;
2582                 n : CARDINAL) : REAL;
2583 BEGIN
2584   IF n = 0 THEN
2585     RETURN 1.
2586   ELSIF ODD(n) THEN
2587     RETURN x * Sqr( RStep(x, n DIV 2) )
2588   ELSE
2589     RETURN Sqr( RStep(x, n DIV 2) )
2590   END
2591 END RStep;
2592
2593 PROCEDURE SStep(x : REAL;
2594                 n : CARDINAL ) : REAL;
2595 VAR
2596   s : StekTip;
2597   OK : BOOLEAN;
2598   rez : REAL;
2599   el : InfoTip;
2600 BEGIN
2601   MakeNull(s);
2602   WHILE n > 0 DO
2603     el.x := x;
2604     el.n := n;
2605     IF ODD(n) THEN
2606       el.adr := nepar;
2607     ELSE
2608       el.adr := par
2609     END;
2610     Push(s,el,OK);
2611     n := n DIV 2
2612   END;
2613   rez := 1.;
2614   WHILE NOT Empty(s) DO
2615     Top(s, el, OK);
2616     Pop(s, OK);
2617     x := el.x;
2618     n := el.n;
2619     IF el.adr = nepar THEN
2620       rez := x * Sqr(rez)
2621     ELSE
2622       rez := Sqr(rez)
2623     END
2624   END;
2625   RETURN rez
2626 END SStep;
2627
2628 BEGIN
2629   WrStr('x =? ');
2630   x := RdReal();
2631   WrLn;
2632   WrStr('n =? ');
2633   n := RdCard();
2634   WrStr('x^n = ');
2635   WrReal(RStep(x, n), 10, 1);
2636   WrStr(' = ');
2637   WrReal(SStep(x, n), 10, 1)
2638 END Step.
2639 \end{lstlisting}
2640
2641 \subsection{Primer 3 -- Fibonači}
2642
2643 \begin{lstlisting}[style=codeblock]
2644 MODULE Fib;
2645 (* InfoTip = RECORD
2646                 n : CARDINAL;
2647                 PrviSab : CARDINAL;
2648                 adr : (prvi, drugi)
2649              END;
2650 *)
2651
2652 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2653 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2654        Top, Pop, Push, InfoTip, AdrTip;
2655 VAR
2656   n : CARDINAL;
2657
2658 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2659 BEGIN
2660   IF n <= 1 THEN
2661     RETURN n
2662   ELSE
2663     RETURN RFib(n-1) + RFib(n-2)
2664   END
2665 END RFib;
2666
2667 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2668 VAR
2669   s : StekTip;
2670   OK, jos : BOOLEAN;
2671   rez, PrviSab : CARDINAL;
2672   el : InfoTip;
2673 BEGIN
2674   MakeNull(s);
2675   REPEAT
2676     WHILE n > 1 DO
2677       el.n := n;
2678       el.adr := prvi;
2679       Push(s,el,OK);
2680       DEC(n)
2681     END;
2682     rez := (n);
2683     jos := TRUE;
2684     WHILE (NOT Empty(s)) AND jos DO
2685       Top(s, el, OK);
2686       Pop(s, OK);
2687       n := el.n;
2688       IF el.adr = prvi THEN
2689         PrviSab := rez;
2690         el.n := n;
2691         el.adr := drugi;
2692         el.PrviSab := PrviSab;
2693         Push(s, el, OK);
2694         DEC(n, 2);
2695         jos := FALSE
2696       ELSE
2697         PrviSab := el.PrviSab;
2698         rez := PrviSab + rez
2699       END
2700     END
2701   UNTIL Empty(s);
2702   RETURN rez
2703 END SFib;
2704
2705 BEGIN
2706   WrStr('n =? ');
2707   n := RdCard();
2708   WrStr('F(n) = ');
2709   WrCard(RFib(n), 1);
2710   WrStr(' = ');
2711   WrCard(SFib(n), 1)
2712 END Fib.
2713 \end{lstlisting}
2714
2715 \subsection{Primer 4 -- faktorijel 2}
2716
2717
2718 \begin{lstlisting}[style=codeblock]
2719 MODULE Faktor;
2720 (* InfoTip = CARDINAL; *)
2721 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2722 FROM StekC IMPORT StekTip, MakeNull, Empty,
2723                   Top, Pop, Push;
2724 VAR
2725   n,rez : CARDINAL;
2726
2727 PROCEDURE RFakto(n : CARDINAL;
2728                  VAR rez : CARDINAL);
2729 BEGIN
2730   IF n = 0 THEN
2731     rez := 1
2732   ELSE
2733     RFakto(n-1, rez);
2734     rez := n * rez
2735   END
2736 END RFakto;
2737
2738 PROCEDURE SFakto(n : CARDINAL;
2739                  VAR rez : CARDINAL);
2740 VAR
2741   s : StekTip;
2742   OK : BOOLEAN;
2743 BEGIN
2744   MakeNull(s);
2745   WHILE n > 0 DO
2746     Push(s,n,OK);
2747     DEC(n)
2748   END;
2749   rez := 1;
2750   WHILE NOT Empty(s) DO
2751     Top(s, n, OK);
2752     Pop(s, OK);
2753     rez := n * rez
2754   END
2755 END SFakto;
2756
2757 BEGIN
2758   WrStr('n =? ');
2759   n := RdCard();
2760   WrLn;
2761   WrStr('n! = ');
2762   RFakto(n, rez);
2763   WrCard(rez, 1);
2764   WrStr(' = ');
2765   SFakto(n, rez);
2766   WrCard(rez, 1)
2767 END Faktor.
2768 \end{lstlisting}
2769
2770 \subsection{Primer 5 (ispitni)}
2771
2772
2773 \begin{lstlisting}[style=codeblock]
2774 MODULE Rek1;
2775 (* InfoTip = RECORD
2776                 d, g, m1, m2 : INTEGER;
2777                 adr : (prvi, drugi)
2778              END;
2779 *)
2780 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2781          MakeNull, Empty, Top, Pop, Push;
2782 IMPORT IO;
2783 VAR
2784   X : ARRAY [1..20] OF INTEGER;
2785
2786 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2787 VAR
2788   m1, m2 : INTEGER;
2789 BEGIN
2790   IF d>g THEN
2791     RETURN MIN(INTEGER)
2792   ELSIF d=g THEN
2793     RETURN X[d]
2794   ELSE
2795     m1 := Max(d, (d+g) DIV 2);
2796     m2 := Max((d+g) DIV 2 +1, g);
2797     IF m1 > m2 THEN
2798       RETURN m1
2799     ELSE
2800       RETURN m2
2801     END
2802   END
2803 END Max;
2804
2805 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2806 VAR
2807   S : StekTip;
2808   el : InfoTip;
2809   ok, jos : BOOLEAN;
2810   m1, m2, rez : INTEGER;
2811 BEGIN
2812   MakeNull(S);
2813   REPEAT
2814     WHILE d<g DO
2815       el.d := d;
2816       el.g := g;
2817       el.adr := prvi;
2818       Push(S, el, ok);
2819       g := (d+g) DIV 2
2820     END;
2821     IF d>g THEN
2822       rez := MIN(INTEGER)
2823     ELSE (* d=g *)
2824       rez := X[d]
2825     END;
2826     jos := TRUE;
2827     WHILE jos AND NOT Empty(S) DO
2828       Top(S, el, ok);
2829       Pop(S, ok);
2830       d := el.d;
2831       g := el.g;
2832       m1 := el.m1;
2833       IF el.adr = prvi THEN
2834         m1 := rez;
2835         el.m1 := m1;
2836         el.adr := drugi;
2837         Push(S, el, ok);
2838         d := (d+g) DIV 2 + 1;
2839         jos := FALSE
2840       ELSE (*el.adr = drugi*)
2841         m2 := rez;
2842         IF m1 > m2 THEN
2843           rez := m1
2844         ELSE
2845           rez := m2
2846         END
2847       END
2848     END
2849   UNTIL Empty(S);
2850   RETURN rez
2851 END SMax;
2852
2853 BEGIN (* glavni program *)
2854   X[1] := 3;
2855   X[2] := 2;
2856   X[3] := 5;
2857   X[4] := -7;
2858   X[5] := 0;
2859   IO.WrCard(Max(1, 5), 3);
2860   IO.WrLn;
2861   IO.WrCard(SMax(1, 5), 3);
2862   IO.WrLn
2863 END Rek1.
2864 \end{lstlisting}
2865
2866 \subsection{Primer 6 (ispitni)}
2867
2868
2869 \begin{lstlisting}[style=codeblock]
2870 MODULE Rek2;
2871 (* InfoTip = RECORD
2872                 x, y, n : CARDINAL;
2873                 adr : (prvi, drugi, treci, cetvrti)
2874              END;
2875 *)
2876 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2877            MakeNull, Empty, Top, Pop, Push;
2878 IMPORT IO;
2879
2880 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2881             n : CARDINAL) : CARDINAL;
2882 BEGIN
2883   IF n < 3 THEN
2884     RETURN x + y
2885   ELSIF ODD(n) THEN
2886     RETURN g(g(x+1, y, n-2), y, n-3)
2887   ELSE
2888     RETURN g(x, g(x, y+1, n-2), n-3)
2889   END
2890 END g;
2891
2892 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2893              n : CARDINAL) : CARDINAL;
2894 VAR
2895   S : StekTip;
2896   el : InfoTip;
2897   ok, jos : BOOLEAN;
2898   rez : CARDINAL;
2899 BEGIN
2900   MakeNull(S);
2901   REPEAT
2902     WHILE n >= 3 DO
2903       IF ODD(n) THEN
2904         el.x := x;
2905         el.y := y;
2906         el.n := n;
2907         el.adr := prvi;
2908         Push(S, el, ok);
2909         INC(x);
2910         DEC(n, 2)
2911       ELSE
2912         el.x := x;
2913         el.y := y;
2914         el.n := n;
2915         el.adr := treci;
2916         Push(S, el, ok);
2917         INC(y);
2918         DEC(n, 2)
2919       END
2920     END;
2921     rez := x+y;
2922     jos := TRUE;
2923     WHILE jos AND NOT Empty(S) DO
2924       Top(S, el, ok);
2925       Pop(S, ok);
2926       x := el.x;
2927       y := el.y;
2928       n := el.n;
2929       IF el.adr = prvi THEN
2930         el.adr := drugi;
2931         Push(S, el, ok);
2932         x := rez;
2933         DEC(n, 3);
2934         jos := FALSE
2935       ELSIF el.adr = treci THEN
2936         el.adr := cetvrti;
2937         Push(S, el, ok);
2938         y := rez;
2939         DEC(n, 3);
2940         jos := FALSE
2941       END
2942     END
2943   UNTIL Empty(S);
2944   RETURN rez
2945 END Sg;
2946
2947 BEGIN (* glavni program *)
2948   IO.WrCard(g(2, 3, 10), 3);
2949   IO.WrCard(Sg(2, 3, 10), 3);
2950 END Rek2.
2951 \end{lstlisting}
2952
2953 %\columnbreak
2954
2955 \appendix
2956
2957 \section{Native XDS Modula 2 -- kratko uputstvo}
2958
2959
2960 Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows
2961 sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program.
2962
2963 \subsection*{Dobavljanje instalacije}
2964
2965
2966 Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača,
2967 \url{http://www.excelsior-usa.com/}, tačnije na adresi:
2968
2969 \url{http://www.excelsior-usa.com/xdsdl.html}
2970
2971 Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste
2972 razumeli i da ćete ga se pridržavati.
2973
2974 Na stranici koja se potom otvara je potrebno odabrati ``XDS 2.6 beta 2
2975 for Windows'' i snimiti je na računar.
2976
2977 \subsection*{Instalacija okruženja}
2978
2979 Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute
2980  instalacione arhive.
2981
2982 \emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione
2983   pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim
2984   klikom miša.}
2985
2986 Pretpostavićemo u daljem tekstu da je program instaliran u
2987 \kod{C:/XDS/}
2988
2989 \subsection*{Pokretanje okruženja}
2990
2991 Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao
2992 i grupa sa programom u start meniju.
2993
2994 Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice,
2995 okruženje se može pokrenuti uz pomoć izvršnog fajla
2996 \kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj
2997 lokaciji).
2998
2999 \subsection*{Prvi projekat}
3000
3001 Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo
3002 napraviti projekat za njega, što se radi na sledeći način:
3003
3004 \begin{itemize}
3005
3006 \item
3007  Iz menija se odabere Project->New.
3008 \item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde
3009   će se kreirati projekat i ukuca se ime novog projekta.
3010
3011 \item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko
3012   postoji neki tekst, obrisati ga.
3013
3014 \item Kliknuti na ``OK''
3015
3016 \item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje,
3017   kliknuti na ``OK'' da se on napravi.
3018
3019 \item Pojavljuje se forma za kucanje programa, ukucati (na primer):
3020
3021 \begin{minipage}{\columnwidth}
3022 \begin{lstlisting}[style=codeblock]
3023   MODULE Hello;
3024   FROM InOut IMPORT WriteString,WriteLn;
3025   BEGIN
3026     WriteString("Hello World");
3027     WriteLn;
3028   END Hello.
3029 \end{lstlisting}
3030 \end{minipage}
3031
3032 \item Program se može pokrenuti na različite načine, pri čemu se
3033   automatski prevodi:
3034
3035   \begin{itemize}
3036
3037   \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči)
3038
3039   \item Meni Debug->Run
3040
3041   \item Prečica Ctrl+F9 na tastaturi
3042
3043   \end{itemize}
3044
3045 \item Ako je sve u redu sa programom, treba da se pojavi novi terminal
3046   u kome se ispisuje rezultat izvršavanja programa, u našem slučaju
3047   jednostavna pozdravna poruka.
3048 \end{itemize}
3049
3050 Naravno moguće je i samo prevesti (kompajlirati) program, tako da se
3051 samo prikažu greške (ako ih ima) i bez pokretanja programa:
3052 \begin{itemize}
3053 \item Klik na ``Compile'' ikonicu u toolbaru
3054 \item Meni Tools->Compile
3055 \item Prečica F9 na tastaturi
3056 \end{itemize}
3057
3058 Ukoliko u programu postoje greške, on neće biti pokrenut, već će se
3059 dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S''
3060 u četvrtom redu i probamo da pokrenemo program, taj red će biti
3061 označen svetlo plavom bojom i dobićemo poruku:
3062
3063 \kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"}
3064
3065 Što znači da u četvrtom redu, kod petog karatkera postoji problem, da
3066 identifikator nije deklarisan, što najčešće znači da ga nismo uvezli,
3067 ili, kao u našem slučaju, da smo napravili grešku u kucanju.
3068
3069 Stvar na koju isto treba obratiti pažnju je da se nekad greška
3070 prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer,
3071 ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo
3072 program, peti red će biti označen svetlo plavom bojom i dobićemo
3073 poruku:
3074
3075 \kod{- Error in pro1.mod [5:5]: Expected symbol ";" }
3076
3077 Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će
3078 kompajler probati da je traži i dalje, pa će tek na početku petog reda
3079 prijaviti grešku.
3080
3081 U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se
3082 uvezena komanda WriteString ne koristi nigde u programu. Često se
3083 upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na
3084 greške, odnosno poruke koje počinju sa ``Error''.
3085
3086 Takođe se često dešava da su druge prijavljene greške posledica prve,
3087 te je poželjno ponovo kompajlirati (ili pokretati) program posle svake
3088 ispravljene greške.
3089
3090 \paragraph{Napomena o template-ovima pri kreiranju projekta:}
3091 Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template''
3092  uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
3093  ``Configure'', a potom isprazniti polje ``default template''.
3094
3095 \subsection{Mogući problemi}
3096
3097 \subsubsection*{Nedostajući sistemski moduli}
3098
3099 Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se
3100 koriste u okviru kursa, i bilo je neophodno da se dodatno instalira i
3101 ``Top Speed Compatibility Pack'' (tscp-x86...). Bez njega je kompajler
3102 prijavljivao da ne postoje neki moduli - najčešće je problem bio da
3103 nedostaje \kod{FIO} modul.
3104
3105 \subsubsection*{Problemi u pokretanju - nemoguće naći exe}
3106
3107 Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi
3108 da ne može da nađe exe i pri tome prijavljuje kraću putanju od one
3109 koja je stvarno u pitanju, obično se radi o tome da je postojao razmak
3110 u okviru putanje do modula. Npr ``C:\textbackslash Moj prvi program''
3111 će prouzrokovati probleme, a kompajler će prijaviti da ne može da nađe
3112 ``C:\textbackslash Moj''.
3113
3114 Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj
3115 verziji ne može se zaobići, tako da je jedino rešenje premestiti
3116 fajlove, odnosno ako je moguće preimenovati problematične foldere.
3117
3118 \mainend
3119
3120 \end{document}