gitweb on Svarog

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