From: Doni Pracner Date: Thu, 21 Feb 2013 19:04:23 +0000 (+0100) Subject: dve varijante skripte - tri fajla X-Git-Tag: v13a~2 X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa1skripta-public.git;a=commitdiff_plain;h=3a61709b99b7f56048e0cdf6422ad84882f42b1e dve varijante skripte - tri fajla --- diff --git a/skripta-spa1-dk.tex b/skripta-spa1-dk.tex new file mode 100644 index 0000000..d795337 --- /dev/null +++ b/skripta-spa1-dk.tex @@ -0,0 +1,62 @@ +\documentclass[a4paper,twoside]{article} + +\usepackage[T1]{fontenc} +\usepackage[utf8]{inputenc}%definišemo da je ulaz utf-8 fajl + +\usepackage[serbian]{babel} + +\newcommand{\varijacija}{dk} +%jk=jedna kolona, dk=dve kolone + +\newcommand{\mainstart}{ +\begin{multicols}{2} +} + +\newcommand{\mainend}{ +\end{multicols} +} + +\newcommand{\manbreakJK}{ +%\pagebreak +} + +%margine +%experiment +%\usepackage[top=2.5cm, bottom=1.5cm, left=3cm, right=2cm]{geometry} +%staro: +\usepackage[top=1.5cm, bottom=1cm, left=2cm, right=1cm]{geometry} + +\usepackage{fancyhdr} +\pagestyle{fancy} + +%% ovi redovi daju header i footer +\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}} +\fancyhf{} % delete current setting for header and footer +% \fancyfoot[C]{\thepage} +\fancyhead[LO]{\bfseries\rightmark} +\fancyhead[RO]{\thepage} + +\fancyhead[RE]{Strukture podataka i algoritmi 1 -- skripta} +\fancyhead[LE]{\thepage} + +\renewcommand{\headrulewidth}{0.5pt} +\renewcommand{\headwidth}{\textwidth} +% \renewcommand{\footrulewidth}{0.5pt} +% \addtolength{\headheight}{0.5pt} % make space for the rule + +\fancypagestyle{plain}{% + \fancyhead{} % get rid of headers on plain pages + \fancyfoot{} + \renewcommand{\headrulewidth}{0pt} % and the line + \renewcommand{\footrulewidth}{0pt} % and the line +} +\setlength{\headheight}{15pt} + +%promene u marginama: +%\setlength{\marginparwidth}{32pt} +%\setlength{\textwidth}{620pt} +%\setlength{\textheight}{620pt} + +\include{skripta-spa1-sadrzaj} + +\end{document} \ No newline at end of file diff --git a/skripta-spa1-jk.tex b/skripta-spa1-jk.tex new file mode 100644 index 0000000..9f8089d --- /dev/null +++ b/skripta-spa1-jk.tex @@ -0,0 +1,62 @@ +\documentclass[a4paper,twoside]{article} + +\usepackage[T1]{fontenc} +\usepackage[utf8]{inputenc}%definišemo da je ulaz utf-8 fajl + +\usepackage[serbian]{babel} + +\newcommand{\varijacija}{jk} +%jk=jedna kolona, dk=dve kolone + +\newcommand{\mainstart}{ +%\begin{multicols}{2} +} + +\newcommand{\mainend}{ +%\end{multicols} +} + +\newcommand{\manbreakJK}{ +\pagebreak +} + +%margine +%experiment +%\usepackage[top=2.5cm, bottom=1.5cm, left=3cm, right=2cm]{geometry} +%staro: +\usepackage[top=1.5cm, bottom=1cm, left=2cm, right=1cm]{geometry} + +\usepackage{fancyhdr} +\pagestyle{fancy} + +%% ovi redovi daju header i footer +\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}} +\fancyhf{} % delete current setting for header and footer +% \fancyfoot[C]{\thepage} +\fancyhead[LO]{\bfseries\rightmark} +\fancyhead[RO]{\thepage} + +\fancyhead[RE]{Strukture podataka i algoritmi 1 -- skripta} +\fancyhead[LE]{\thepage} + +\renewcommand{\headrulewidth}{0.5pt} +\renewcommand{\headwidth}{\textwidth} +% \renewcommand{\footrulewidth}{0.5pt} +% \addtolength{\headheight}{0.5pt} % make space for the rule + +\fancypagestyle{plain}{% + \fancyhead{} % get rid of headers on plain pages + \fancyfoot{} + \renewcommand{\headrulewidth}{0pt} % and the line + \renewcommand{\footrulewidth}{0pt} % and the line +} +\setlength{\headheight}{15pt} + +%promene u marginama: +%\setlength{\marginparwidth}{32pt} +%\setlength{\textwidth}{620pt} +%\setlength{\textheight}{620pt} + +\include{skripta-spa1-sadrzaj} + +\end{document} \ No newline at end of file diff --git a/skripta-spa1-sadrzaj.tex b/skripta-spa1-sadrzaj.tex new file mode 100644 index 0000000..68dacce --- /dev/null +++ b/skripta-spa1-sadrzaj.tex @@ -0,0 +1,3070 @@ +% skripta-spa1-sadrzaj.tex +% Skripta za predmet Strukture podataka i algoritmi 1, DMI, PMF, NS +% ovaj fajl sadrzi glavni sadrzaj skripte koji se ukljucuje u jedan +% od pomocnih fajlova koji ce primeniti adekvatna formatiranja, +% npr za jednu ili dve kolone + +% osnovne informacije koje ce se prikazati na naslovnoj strani, +% kao i u informacijama u generisanom pdfu +\newcommand{\autor}{Vladimir Kurbalija, Milos Radovanovic, Doni Pracner} +\newcommand{\naslov}{Skripta za vezbe iz predmeta "Strukture podataka + i algoritmi 1"} +\newcommand{\datum}{Februar 2013, Novi Sad} +\newcommand{\verzija}{ver 13a-\varijacija} +%varijacija je definisana u fajlu koji ukljucuje ovaj + +\title{\naslov -- \verzija} +\author{\autor} +\date{\datum} + +%change the default font +\usepackage{lmodern} +\usepackage{beramono} +\renewcommand{\familydefault}{\sfdefault} + +\usepackage{pifont} + +%podesavanja outputa za pdf verzije +\usepackage[bookmarks,pdffitwindow=false,unicode=true,% +pdftitle={\naslov -- \verzija},% +pdfauthor={\autor}% +]{hyperref} + +\usepackage{graphicx} +\usepackage{listings} +\usepackage{amsthm} +\usepackage{amsmath} +\usepackage{latexsym} +\usepackage{multicol} + +\begin{document} + +%customize the itemize environments + +\let\olditemize=\itemize +\def\itemize{ +\olditemize + \setlength{\itemsep}{1pt} + \setlength{\parskip}{0pt} + \setlength{\parsep}{0pt} + \setlength{\topsep}{-1cm} + \setlength{\partopsep}{1pt} +} + +%% specijalni blokovi koji služe kao podsetnici u radu ili napomene +\newcommand{\skica}[1]{ + \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small** \textit{#1} }} + \newline } +} + +\newcommand{\skicas}[1]{ + \framebox{* \textit{#1} *} +} + +%boldovane skice visokog prioriteta +\newcommand{\skicab}[1]{ + \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small*** + \textbf{#1} }} \newline } } + +\newcommand{\kod}[1]{{\small\texttt{#1}}} + +% ako je sledeci red odkomentarisan nista od skica nece biti ispisano +% u finalni dokument + +% \renewcommand{\skica}[1]{} + +% title u skladu sa uobičajenim na Departmanu +\newcommand{\makemytitle}{ + \begin{center} + \makebox{% + \includegraphics[width=2cm]{grbPMF} + \parbox[b]{65ex}{\centering + Univerzitet u Novom Sadu\\ + Prirodno-matematički fakultet\\ + Departman za matematiku i informatiku} + \includegraphics[width=2cm]{grbUNS} + } + \vspace{10ex} + + \parbox[b]{\textwidth}{{\Large {\bf + Vladimir Kurbalija, \href{mailto:kurba@dmi.rs}{kurba@dmi.rs}\\ + Miloš Radovanović, \href{mailto:radacha@dmi.rs}{radacha@dmi.rs}\\ + Doni Pracner, \href{mailto:doni.pracner@dmi.rs}{doni.pracner@dmi.rs}}}} + \vspace{5ex} + + {\Large {\bf Skripta za vežbe iz predmeta }} + + {\Huge {\bf + \setlength{\baselineskip}{1.5\baselineskip}Strukture + podataka i algoritmi 1}} + + \vspace{5ex} + %\vfill + + \verzija \ -- \datum + + \end{center} + \thispagestyle{plain} +% \newpage +} + +\makemytitle + +% theorems, definition etc. +%'''''''''''''''''''''''''' + +\theoremstyle{definition} +\newtheorem{def1}{Definicija} +\theoremstyle{plain} +\newtheorem{theo}{Teorema} +\newtheorem{lema}{Lema} + +\lstloadlanguages{Modula-2} + +\lstset{ + basicstyle=\footnotesize\ttfamily, + showstringspaces=false, + breaklines=true +} + +\lstdefinestyle{codeblock}{ + basicstyle=\footnotesize\ttfamily, + keywordstyle=\textbf, + columns=[l]fixed, + breakatwhitespace=true, +% prebreak=\P, +% postbreak=\ding{229}\space, + language=Modula-2 +} + +\lstdefinestyle{numcodeblock}{ + style=codeblock, + numbers=left +} + +\lstnewenvironment{codeblock}{\lstset{style=codeblock}}{} + + +% ----------------==================-------------------------------------- +% Pravi pocetak rada + + +Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula +2'. Za verzije pre 2.60 je neophodno dodatno instalirati i TSCP (Top +Speed Compatibility Pack), pošto je potreban za neke od modula koji se +ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi +moduli uključeni u standardnu instalaciju. + +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/} + +\tableofcontents + +%\newpage + +\mainstart + +\section{Ilustracija efikasnosti algoritma} + +\subsection{Zadatak: Pronaći sve pitagorine +trojke do zadate granice} + +Pitagorina trojka su tri broja $a,b,c$ za koje važi $a^2 + b^2 = c^2\\$ + +\begin{lstlisting}[style=codeblock] +MODULE Trojke1; +(* Pitagorine trojke koriscenjem "Brute-force" *) +FROM InOut IMPORT WriteString, WriteLn, WriteCard; +CONST + Gr = 100; +VAR + a, b, c : [1 .. Gr]; +BEGIN + FOR a := 1 TO Gr DO + FOR b := 1 TO Gr DO + FOR c := 1 TO Gr DO + IF a*a + b*b = c*c THEN + WriteLn; + WriteString('a = '); + WriteCard(a,2); + WriteString(', b = '); + WriteCard(b,2); + WriteString(', c = '); + WriteCard(c,2) + END + END + END + END +END Trojke1. +\end{lstlisting} + +\begin{codeblock} +MODULE Trojke2; +(*Pitagorine trojke koriscenjem zaokrugljivanja*) +FROM InOut IMPORT WriteString, WriteLn, WriteCard; +FROM MathLib0 IMPORT sqrt; +CONST + Gr = 100; +VAR + a, b, c : CARDINAL; + creal : REAL; +BEGIN + FOR a := 1 TO Gr DO + FOR b := 1 TO Gr DO + creal := FLOAT(a*a) + FLOAT(b*b); + creal := sqrt(creal); + c := TRUNC(creal); + IF creal = FLOAT(c) THEN + WriteLn; + WriteString(' a = '); + WriteCard(a,2); + WriteString(', b = '); + WriteCard(b,2); + WriteString(', c = '); + WriteCard(c,2) + END + END + END +END Trojke2. +\end{codeblock} + +Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup. +Ako uzmemo neka dva prirodna broja $m$ i $n$, tada se iz njih može +izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove: +\[ +\begin{array}{l} +a = 2mn\\ +b = m^2 - n^2\\ +c = m^2 + n^2 +\end{array} +\] +Odnosno kad probamo da proverimo da li je ovo +Pitagorina trojka dobijamo: +\[ +\begin{array}{r@=l} +a^2 + b^2 & c^2\\ +(2mn)^2 + (m^2 - n^2)^2 & (m^2 + n^2)^2 +\end{array} +\] + +\begin{codeblock} +MODULE Trojke3; +(* Pitagorine trojke koriscenjem teoreme *) +FROM InOut IMPORT WriteString, WriteLn, WriteCard; +CONST + Gr = 10; +VAR + a, b, c, m, n : CARDINAL; +BEGIN + FOR m := 1 TO Gr DO + FOR n := 1 TO m-1 DO + a := 2*m*n; + b := m*m - n*n; + c := m*m + n*n; + WriteLn; + WriteString('a = '); + WriteCard(a,2); + WriteString(', b = '); + WriteCard(b,2); + WriteString(', c = '); + WriteCard(c,2) + END + END +END Trojke3. +\end{codeblock} + +Sledeća dva metoda traže trojke sa nekim specifičnim osobinama. + +\begin{codeblock} +MODULE Trojke4; +(* Pitagorine trojke kod kojih je razlika + izmedju katete i hipotenuze tacno 1 *) +FROM InOut IMPORT WriteString, WriteLn, WriteCard; +CONST + Gr = 10; +VAR + a, b, c, m, n : CARDINAL; +BEGIN + FOR m := 2 TO Gr DO + n := m - 1; + a := 2*m*n; + b := m*m - n*n; + c := m*m + n*n; + WriteLn; + WriteString('a = '); + WriteCard(a,2); + WriteString(', b = '); + WriteCard(b,2); + WriteString(', c = '); + WriteCard(c,2) + END +END Trojke4. +\end{codeblock} + +\begin{lstlisting}[style=codeblock] +MODULE Trojke5; +(* Pitagorine trojke kod kojih je razlika + izmedju kateta jedan *) +FROM InOut IMPORT WriteString, WriteLn, WriteCard; +CONST + Gr = 7; +VAR + a, b, c, m, n, w, i, temp : CARDINAL; +BEGIN + w := 1; + n := 0; + FOR i := 1 TO Gr DO + m := n + w; + a := 2*m*n; + b := m*m - n*n; + c := m*m + n*n; + WriteLn; + WriteString('a = '); + WriteCard(a,2); + WriteString(', b = '); + WriteCard(b,2); + WriteString(', c = '); + WriteCard(c,2); + temp := w; + w := 3*w + 4*n; + n := 2*temp + 3*n + END +END Trojke5. +\end{lstlisting} + +\manbreakJK + +\subsection[Zadatak: Maksimalna suma susednih elemenata u +nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u + nizu celih brojeva} + +\begin{lstlisting}[style=codeblock] +MODULE MaxNiza1; +(* Prvo resenje. Brute Force: O(n^3) *) +FROM InOut IMPORT WriteString,ReadInt, + WriteInt,WriteCard,WriteLn; +CONST + N = 10; +TYPE + Interval = [1..N]; +VAR + Max, Suma : INTEGER; + d,g,i,Ood,Doo : Interval; + X : ARRAY Interval OF INTEGER; +BEGIN + WriteString(' Unesite niz X '); + WriteLn; + FOR i := 1 TO N DO + ReadInt(X[i]); + WriteLn + END; + Max := 0; + FOR d := 1 TO N DO + FOR g := 1 TO N DO + Suma := 0; + FOR i := d TO g DO + Suma := Suma + X[i] + END; + IF Suma > Max THEN + Max := Suma; + Ood := d; + Doo := g + END + END + END; + WriteLn; + WriteString(' Maksimum je '); + WriteInt(Max,3); + WriteString(' u intervalu od '); + WriteCard(Ood,3); + WriteString(' do '); + WriteCard(Doo,3) +END MaxNiza1. + +MODULE MaxNiza2; +(* Drugo resenje: O(n^2). + Koristi se cinjenica da je suma X[d..g] + izracunljiva iz X[d..g-1]. *) +FROM InOut IMPORT WriteString,ReadInt, + WriteInt,WriteCard,WriteLn; +CONST + N = 10; +TYPE + Interval = [1..N]; +VAR + Max, Suma : INTEGER; + d,g,i,Ood,Doo : Interval; + X : ARRAY Interval OF INTEGER; +BEGIN + WriteString(' Unesite niz X '); + WriteLn; + FOR i := 1 TO N DO + ReadInt(X[i]); + WriteLn + END; + Max := 0; + FOR d := 1 TO N DO + Suma := 0; + FOR g := d TO N DO + Suma := Suma + X[g]; + IF Suma > Max THEN + Max := Suma; + Ood := d; + Doo := g + END + END + END; + WriteLn; + WriteString(' Maksimum je '); + WriteInt(Max,3); + WriteString(' u intervalu od '); + WriteCard(Ood,3); + WriteString(' do '); + WriteCard(Doo,3) +END MaxNiza2. +\end{lstlisting} + +\begin{codeblock} +MODULE MaxNiza3; +(* Trece resenje: O(n^2). + Koristi pomocni niz u kome je na i-tom mestu + suma podniza x[1..i] *) +FROM InOut IMPORT WriteString,ReadInt, + WriteInt,WriteCard,WriteLn; +CONST + N = 10; +TYPE + Interval = [1..N]; +VAR + Max, Suma : INTEGER; + d,g,i,Ood,Doo : Interval; + X : ARRAY Interval OF INTEGER; + Pom : ARRAY [0..N] OF INTEGER; +BEGIN + WriteString(' Unesite niz X '); + WriteLn; + FOR i := 1 TO N DO + ReadInt(X[i]); + WriteLn + END; + Pom[0] := 0; + FOR i := 1 TO N DO + Pom[i] := Pom[i-1] + X[i] + END; + Max := 0; + FOR d := 1 TO N DO + FOR g := d TO N DO + Suma := Pom[g] - Pom[d-1]; + IF Suma > Max THEN + Max := Suma; + Ood := d; + Doo := g + END + END + END; + WriteLn; + WriteString(' Maksimum je '); + WriteInt(Max,3); + WriteString(' u intervalu od '); + WriteCard(Ood,3); + WriteString(' do '); + WriteCard(Doo,3) +END MaxNiza3. +\end{codeblock} + +\begin{codeblock} +MODULE MaxNiza4; +(* Cetvrto resenje. Najbolje moguce: O(n) *) +FROM InOut IMPORT WriteString,ReadInt, + WriteInt,WriteCard,WriteLn; +CONST + N = 10; +TYPE + Interval = [1..N]; +VAR + Max, MaxDovde : INTEGER; + i,d,Ood,Doo : Interval; + X : ARRAY Interval OF INTEGER; +BEGIN + WriteString(' Unesite niz X '); + WriteLn; + FOR i := 1 TO N DO + ReadInt(X[i]); + WriteLn + END; + Max := 0; + MaxDovde := 0; + FOR i := 1 TO N DO + IF MaxDovde = 0 THEN + d := i + END; + MaxDovde := MaxDovde + X[i]; + IF MaxDovde < 0 THEN + MaxDovde := 0 + END; + IF MaxDovde > Max THEN + Ood := d; + Doo := i; + Max := MaxDovde + END + END; + WriteLn; + WriteString(' Maksimum je '); + WriteInt(Max,3); + WriteString(' u intervalu od '); + WriteCard(Ood,3); + WriteString(' do '); + WriteCard(Doo,3) +END MaxNiza4. +\end{codeblock} + +\section{Stringovi} + + +Stringovi -- odnosno nizovi znakova -- ne postoje kao ugrađeni tip u +jeziku Modula 2. Ovo daje slobodu da se niz znakova definiše na dužinu +najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr: +\begin{codeblock} + TYPE + String = ARRAY [1..30] OF CHAR; +\end{codeblock} + +Operacije nad stringovima se najčešće uvoze iz modula \kod{Str}. One +sve prihvataju \emph{otvorene nizove znakova} (strukture definisane sa +\kod{ARRAY OF CHAR}), tako da im se može proslediti niz proizvoljne +dužine. + +Određivanje stvarne dužine stringa (tj koliko od maksimalnog +kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na +sledeći način: +\begin{codeblock} + duzina := Length(str) +\end{codeblock} + +Leksikografsko poređenje dva stringa se ne može vršiti standardnim +operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o +nizovima, a delom i zato što se ne vidi direktno koji deo niza je +popunjen stvarnim sadržajem. Za ovo se koristi komanda \kod{Compare}, +koja prihvata dva stringa kao parametre, a vraća broj koji predstavlja +njihov odnos. Taj broj će biti 0 ako su stringovi jednaki, veći +od nule ako je prvi string ``veći'', i manji od nule ako je prvi +string ``manji''. Ovo se lako pamti kad primetimo da je odnos +između \kod{Compare} i 0 isti kao i između prvog i drugog stringa. + +\begin{codeblock} + IF Compare(str1, str2) > 0 THEN + WriteString("Prvi string je veci"); + ELSIF Compare(str1, str2) < 0 THEN + WriteString("Prvi string je manji"); + ELSE (* moraju biti jednaki *) + WriteString("Jednaki su"); + END; +\end{codeblock} + +Postoji i modul \kod{Strings} koji ima nešto drugačije definisane +procedure, no na njih se sada nećemo fokusirati. + +\section{Rad sa fajlovima} + +\subsection{Modul FIO} + +U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl +sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto +kao što uvozimo i komande). + +\begin{quote}U primerima se pretpostavlja da je ``f'' tipa \kod{File}, ``str'' niz +znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa \kod{CARDINAL} i ``ch'' +tipa \kod{CHAR}. Dodatna promenljiva ``n'' tipa \kod{INTEGER} služi za +formatiranje slično kao u modulu \kod{InOut}. +\end{quote} + +Promenljiva tipa \kod{File} se mora vezati za neki fajl +jednom od sledećih komandi: +\begin{itemize} +\item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\ +\item \kod{f := Create(str);} -- kreira se fajl za pisanje\\ +\item \kod{f := Append(str);} -- otvara se postojeći fajl za + dopisivanje na kraj +\end{itemize} + +Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo +\kod{Close(f);} + +Procedure za čitanje i pisanje su vrlo slične onima iz modula +\kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava +fajl sa kojim se radi. +\begin{itemize} +\item \kod{RdStr(f,str)} -- učitava ceo red u string str\\ +\item \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\ +\item \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\ +\item \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla +\end{itemize} + +Analogne su i procedure za pisanje različitih tipova u fajl: +\begin{itemize} +\item \kod{WrStr(f,str); WrInt(f,i,n);}\ \kod{WrCard(f,c,n);}\ + \kod{WrChar(f,ch);} +\end{itemize} + + +Prelom reda se eksplicitno upisuje u fajl komandom \kod{WrLn(f);}. + +Da bi odredili da li smo stigli do kraja fajla možemo koristiti +\kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula +FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom +operacijom čitanja stigli do kraja fajla. Ne menja joj se vrednost +pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri +tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri +radu. + +\subsection{Zadatak: ispis sadržaja fajla na ekran} + +Potrebno je sve redove iz fajla učitati i ispisati ih na ekran. + +\begin{lstlisting}[style=codeblock] +MODULE ispis; +FROM FIO IMPORT File, Open, Close, EOF, RdStr; +FROM InOut IMPORT WriteString, WriteLn, ReadString; + +PROCEDURE ispisF(ime: ARRAY OF CHAR); +VAR + f:File; + s : ARRAY[1..100] OF CHAR; +BEGIN + f:=Open(ime); + EOF := FALSE; + WHILE NOT EOF DO + RdStr(f,s); + WriteString(s); + WriteLn; + END; + Close(f); +END ispisF; + +VAR + ime: ARRAY[1..100] OF CHAR; +BEGIN + WriteString("unesite ime fajla:"); + ReadString(ime); + ispisF(ime); +END ispis. +\end{lstlisting} + +\subsection{Zadatak: spisak studenata} + +Napraviti program koji iz fajla učitava podatke o studentima, dodaje +novog studenta u spisak i snima fajl. U fajlu se u svakom redu nalazi +podatak o jednom studentu, redom prezime, ime i godina rođenja, +razdvojeni razmacima. + +\begin{lstlisting}[style=codeblock] +MODULE nizslog; +FROM InOut IMPORT WriteString, WriteLn, + WriteCard, ReadCard, ReadString; +FROM FIO IMPORT File, Open, Create, Close, EOF, + RdItem, RdCard, WrStr, WrCard, WrLn; +FROM Str IMPORT Compare; + +CONST + MaxStud = 100; +TYPE + String = ARRAY[1..30] OF CHAR; + Student = RECORD + ime, prez: String; + god: CARDINAL; + END; + Studenti = ARRAY[1..MaxStud] OF Student; + +PROCEDURE UcitajF(fajl:String; + VAR spisak: Studenti; VAR n:CARDINAL); +VAR + f:File; +BEGIN + n:=0; + f:= Open(fajl); + EOF := FALSE; + WHILE NOT EOF DO + INC(n); + RdItem(f, spisak[n].prez); + RdItem(f, spisak[n].ime); + spisak[n].god := RdCard(f); + END; + Close(f); +END UcitajF; + +PROCEDURE Ispisi(spisak:Studenti; n:CARDINAL); +VAR + i: CARDINAL; +BEGIN + FOR i:=1 TO n DO + WriteString(spisak[i].prez); + WriteString(" "); + WriteString(spisak[i].ime); + WriteString(" "); + WriteCard(spisak[i].god,1); + WriteLn; + END; +END Ispisi; + +PROCEDURE IspisiF(fajl:String; + spisak:Studenti; n:CARDINAL); +VAR + f:File; + i: CARDINAL; +BEGIN + IF (n>0) AND (n<=MaxStud) THEN + f:=Create(fajl); + (* pravimo takav fajl da ne + postoji zadnji prazan red *) + FOR i:=1 TO n-1 DO + WrStr(f,spisak[i].prez); + WrStr(f," "); + WrStr(f,spisak[i].ime); + WrStr(f," "); + WrCard(f,spisak[i].god,1); + WrLn(f); + END; + WrStr(f,spisak[n].prez); + WrStr(f," "); + WrStr(f,spisak[n].ime); + WrStr(f," "); + WrCard(f,spisak[n].god,1); + Close(f); + END; +END IspisiF; + +PROCEDURE NoviStudent(VAR spisak:Studenti; + VAR n:CARDINAL); +VAR + stud,temp:Student; + i:CARDINAL; + dodaj:BOOLEAN; +BEGIN + IF n=br) THEN + (*prazna lista ili na pocetak*) + temp^.veza:=lista; + lista := temp; + ELSE + (*negde u listi*) + tekuci:= lista; + WHILE (tekuci^.veza # NIL) AND + (tekuci^.veza^.info<=br) DO + tekuci:=tekuci^.veza; + END; + temp^.veza := tekuci^.veza; + tekuci^.veza:=temp; + END; +END DodajSort; +\end{lstlisting} + +\subsection{Zadatak: Prikaz osnovih operacija nad listama} + +\begin{lstlisting}[style=codeblock] +MODULE liste2; +FROM InOut IMPORT WriteString, WriteLn, + WriteCard, ReadCard; +FROM IO IMPORT RdKey; +FROM Storage IMPORT ALLOCATE, DEALLOCATE; +TYPE + skupZn = SET OF CHAR; + brojevi = POINTER TO brojSlog; + brojSlog = RECORD + info:CARDINAL; + veza:brojevi; + END; +VAR + lista : brojevi; + menu,prazno:CHAR; + +PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER); +(* dodaje broj pom na pocetak liste *) +VAR + temp:brojevi; +BEGIN + (* kreiramo novi element *) + NEW(temp); + temp^.info := br; + (* treba da pokazuje na ostatak liste *) + temp^.veza := lista; + (* pocetak liste je novi element *) + lista := temp; +END DodajPoc; + +PROCEDURE Unos(VAR lista:brojevi); +(* dodaje n brojeva u listu *) +VAR + n,i,br:CARDINAL; +BEGIN + WriteString('unesite n (broj brojeva): '); + ReadCard(n); + FOR i:= 1 TO n DO + WriteString("unesite broj "); + WriteCard(i,0); + WriteString(": "); + ReadCard(br); + DodajPoc(lista,br); + END; +END Unos; + +(* -- procedure za stampu -- *) + +PROCEDURE Stampaj(lista:brojevi); +(* stampa sadrzaj liste na ekran *) +VAR + temp:brojevi; +BEGIN + WriteLn; + WriteString("Sadrzaj liste:"); + WriteLn; + temp:=lista; + WHILE temp # NIL DO + WriteCard(temp^.info,0); + WriteLn; + temp := temp^.veza; + END; +END Stampaj; + +PROCEDURE StampajK(VAR lista:brojevi); +(* stampa k-ti element (k unosi korisnik) *) +VAR + temp:brojevi; + k,brojac:CARDINAL; +BEGIN + WriteString("unesite redni broj elementa:"); + ReadCard(k); + temp:=lista; + brojac := 1; + WHILE (temp# NIL) AND (k>brojac) DO + temp:=temp^.veza; + INC(brojac); + END; + IF (temp#NIL) THEN + WriteCard(temp^.info,2); + ELSE + WriteString("greska! - ne postoji element"); + WriteString(" u listi sa rednim brojem "); + WriteCard(k,2); + END; + WriteLn(); +END StampajK; + +PROCEDURE StampajMinimum(VAR lista:brojevi); +(* nalazi i stampa minimalni element liste *) +VAR + temp:brojevi; + min:CARDINAL; +BEGIN + IF (lista=NIL) THEN + WriteString("prazna lista!"); + ELSE + min:=lista^.info; + temp:=lista^.veza; + WHILE temp # NIL DO + IF temp^.info < min THEN + min := temp^.info; + END; + temp := temp^.veza; + END; + WriteString("Minimalni element liste je "); + WriteCard(min,0); + END; + WriteLn; +END StampajMinimum; + +(* -- pomocne procedure, bez ispisa -- *) + +PROCEDURE UListi(lista:brojevi; + br: CARDINAL):BOOLEAN; +(* vraca da li se 'br' nalazi u listi 'lista' *) +VAR + temp:brojevi; +BEGIN + temp:=lista; + WHILE (temp # NIL) AND (temp^.info # br) DO + (* dok ne dodjemo do kraja liste + ili ne nadjemo broj *) + temp := temp^.veza; + END; + IF temp#NIL THEN + (* znaci da nismo na kraju liste, + tj da je nadjen broj *) + RETURN TRUE; + ELSE (* temp = NIL *) + RETURN FALSE; + END; +END UListi; + +PROCEDURE IzbaciIzListe(VAR lista:brojevi; + br: CARDINAL):BOOLEAN; +(* izbacuje broj 'br' iz liste, naravno ako + postoji i vraca da li je operacija uspesno + obavljena *) +VAR + temp,prethodni:brojevi; +BEGIN + (* proverimo da li je prvi element *) + IF (lista # NIL) AND (lista^.info = br) THEN + temp:=lista; + lista :=lista^.veza; + DISPOSE(temp); + RETURN TRUE; + ELSE + (* trazimo u ostatku liste *) + temp:=lista; + prethodni:=NIL; + WHILE (temp # NIL) AND (temp^.info # br) DO + (* dok ne dodjemo do kraja liste + ili ne nadjemo broj *) + prethodni:=temp; + temp := temp^.veza; + END; + IF temp#NIL THEN + (* znaci da nismo na kraju liste, + odnosno da smo nasli broj *) + (* prevezemo listu oko elementa *) + prethodni^.veza:=temp^.veza; + DISPOSE(temp); + RETURN TRUE; + ELSE + RETURN FALSE; + END; + END; +END IzbaciIzListe; + +PROCEDURE IzbaciIzListeSve(VAR lista:brojevi; + br: CARDINAL):CARDINAL; +(* izbacuje sve brojeve 'br' iz liste, naravno ako + postoje i vraca koliko ih je bilo *) +VAR + temp,prethodni:brojevi; + brojac : CARDINAL; +BEGIN + brojac := 0; + (* uklanjamo sa pocetka koliko je potrebno *) + WHILE (lista # NIL) AND (lista^.info = br) DO + temp:=lista; + lista :=lista^.veza; + DISPOSE(temp); + INC(brojac); + END; + (* trazimo u ostatku liste *) + IF (lista # NIL) THEN + temp:=lista; + WHILE (temp^.veza # NIL) DO + (* idemo do poslednjeg elementa liste *) + prethodni:=temp; + temp := temp^.veza; + IF temp^.info = br THEN + (* prevezemo listu oko elementa *) + prethodni^.veza:=temp^.veza; + DISPOSE(temp); + INC(brojac); + (* vracamo se jedan korak da bi + u novom krugu proverili i ovaj element *) + temp := prethodni; + END; + END; + END; + RETURN brojac; +END IzbaciIzListeSve; + +(* - procedure sa interakcijom sa korisnikom - *) + +PROCEDURE IzbacivanjeEl(VAR lista:brojevi); +(* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *) +VAR + br:CARDINAL; +BEGIN + WriteString("unesite broj za izbacivanje: "); + ReadCard(br); + IF IzbaciIzListe(lista,br) THEN + WriteString("broj je izbacen iz liste"); + ELSE + WriteString("greska! - broj ne postoji"); + END; + WriteLn; +END IzbacivanjeEl; + +PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi); +(* izbacuje sve primeke unetog broj iz liste + koristeci proceduru IzbaciIzListeSve *) +VAR + br, ukupno:CARDINAL; +BEGIN + WriteString("unesite broj za izbacivanje: "); + ReadCard(br); + ukupno := IzbaciIzListeSve(lista,br); + WriteString("Iz liste je izbaceno "); + WriteCard(ukupno,3); + WriteString(" el."); + WriteLn; +END IzbacivanjeElSvi; + +PROCEDURE IzbacivanjeK(VAR lista:brojevi); +(* izbacuje k-ti element iz liste *) +VAR + temp,tekuci:brojevi; + k,brojac:CARDINAL; +BEGIN + IF lista=NIL THEN + WriteString("lista je prazna, nema "); + WriteString("elemenata za izbacivanje"); + ELSE + WriteString("unesite redni broj elementa"); + WriteString(" koji zelite izbaciti:"); + ReadCard(k); + IF k=1 THEN (*izbacivanje prvog *) + temp:=lista; + lista := lista^.veza; + DISPOSE(temp); + ELSE + tekuci := lista; + brojac := 2; (*gledamo jedan unapred*) + WHILE (tekuci^.veza# NIL) AND (k>brojac) DO + (* idemo kroz listu do k-tog el *) + tekuci:=tekuci^.veza; + INC(brojac); + END; + IF (tekuci^.veza#NIL) THEN + (* pamtimo element za brisanje *) + temp:=tekuci^.veza; + (* prevezujemo listu oko njega*) + tekuci^.veza:=tekuci^.veza^.veza; + DISPOSE(temp); + ELSE + WriteString("greska! - ne postoji el "); + WriteString("u listi sa rednim brojem "); + WriteCard(k,2); + END; + WriteLn(); + END; + END; +END IzbacivanjeK; + +PROCEDURE Pretraga(lista:brojevi); +(* provera da li se uneti broj nalazi u listi *) +VAR + br:CARDINAL; +BEGIN + WriteString("unesite trazeni broj"); + ReadCard(br); + IF UListi(lista,br) THEN + WriteString("broj postoji u listi"); + ELSE + WriteString("broj ne postoji u listi"); + END; + WriteLn; +END Pretraga; + +(* -- oslobadjanje memorije -- *) + +PROCEDURE Unisti(VAR lista:brojevi); +VAR + temp:brojevi; +BEGIN + temp:=lista; + WHILE temp # NIL DO + lista:=lista^.veza; + DISPOSE(temp); + temp:=lista; + END; +END Unisti; + +BEGIN + (* pocinjemo od prazne liste *) + lista := NIL; + REPEAT + WriteLn; + WriteString("Ilustracija rada sa"); + WriteString(" listama brojeva"); + WriteLn; + WriteString("============================="); + WriteLn; + WriteString("s - Stampa");WriteLn; + WriteString("u - Unos");WriteLn; + WriteString("i - Izbacivanje br iz liste"); + WriteLn; + WriteString("v - izbacivanje svih br iz liste"); + WriteLn; + WriteString("e - izbacivanje k-tog El."); + WriteLn; + WriteString("k - stampanje k-tog elementa"); + WriteLn; + WriteString("m - Minimalni broj u listi"); + WriteLn; + WriteString("p - Pretraga el. u listi"); + WriteLn; + WriteLn; + WriteString("q - kraj rada (Quit)");WriteLn; + REPEAT + menu := CAP(RdKey()); + UNTIL menu IN skupZn{'S','U','E','I','V', + 'M','K','P','Q'}; + IF menu#'Q' THEN + CASE menu OF + 'S' : Stampaj(lista);| + 'U' : Unos(lista);| + 'I' : IzbacivanjeEl(lista);| + 'V' : IzbacivanjeElSvi(lista);| + 'E' : IzbacivanjeK(lista);| + 'K' : StampajK(lista); | + 'M' : StampajMinimum(lista); | + 'P' : Pretraga(lista);| + END; + WriteLn; + WriteString("--- pritisnite bilo koji "); + WriteString("taster za povratak u meni"); + prazno:=RdKey(); + ELSE + WriteString("Kraj rada") + END; + WriteLn; + UNTIL menu='Q'; + Unisti(lista); +END liste2. +\end{lstlisting} + + +\subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem} + +\begin{lstlisting}[style=codeblock] +MODULE Radnici; + +FROM InOut IMPORT WriteString, ReadString, + WriteLn, WriteCard, ReadCard, Done; +FROM IO IMPORT RdKey; +FROM Storage IMPORT ALLOCATE, DEALLOCATE; + +TYPE + skupZn = SET OF CHAR; + str = ARRAY [1..20] OF CHAR; + radnici = POINTER TO slog; + slog = RECORD + ime, prez : str; + broj : CARDINAL; + sled : radnici + END; +VAR + meni, pom : CHAR; + rad : radnici; + + PROCEDURE Clear(); + VAR + br: CARDINAL; + BEGIN + FOR br:=1 TO 100 DO + WriteLn; + END; + END Clear; + + PROCEDURE Spisak(rad : radnici); + BEGIN + WHILE rad # NIL DO + WriteString(rad^.ime); + WriteString(' '); + WriteString(rad^.prez); + WriteCard(rad^.broj, 8); + WriteLn; + rad := rad^.sled + END + END Spisak; + + PROCEDURE Zaposli(VAR rad : radnici); + VAR + novi, tek : radnici; + nadjen : BOOLEAN; + BEGIN + NEW(novi); + REPEAT + WriteString('Ime, prezime i jedinstveni'); + WriteString(' broj novog radnika: '); + WriteLn; + ReadString(novi^.ime); + ReadString(novi^.prez); + ReadCard(novi^.broj); + nadjen := FALSE; + tek := rad; + WHILE NOT nadjen AND (tek # NIL) AND + (tek^.broj <= novi^.broj) DO + IF novi^.broj = tek^.broj THEN + nadjen := TRUE + ELSE + tek := tek^.sled + END + END + UNTIL Done AND NOT nadjen; + IF (rad = NIL) OR (novi^.broj br) THEN + WriteString('Greska.') + ELSE + pom := tek^.sled; + tek^.sled := tek^.sled^.sled; + DISPOSE(pom) + END + END + END Otpusti; + + PROCEDURE Inform(rad : radnici); + VAR + br : CARDINAL; + BEGIN + REPEAT + WriteLn; + WriteString('Unesite redni broj radnika:'); + ReadCard(br) + UNTIL Done; + WriteLn; + WHILE (rad # NIL) AND (rad^.broj < br) DO + rad := rad^.sled + END; + IF (rad = NIL) OR (rad^.broj # br) THEN + WriteString('Greska.') + ELSE + WriteString(rad^.ime); + WriteString(' '); + WriteString(rad^.prez) + END + END Inform; + + PROCEDURE Bankrot(VAR rad : radnici); + VAR + pom : radnici; + BEGIN + WHILE rad # NIL DO + pom := rad; + rad := rad^.sled; + DISPOSE(pom) + END + END Bankrot; + +BEGIN + rad := NIL; + REPEAT + Clear; + WriteString('s - spisak svih zaposlenih'); + WriteLn; + WriteString('z - zaposljavanje radnika'); + WriteLn; + WriteString('o - otpustanje radnika'); + WriteLn; + WriteString('i - informacije o radniku'); + WriteLn; + WriteString('b - bankrot firme'); + WriteLn; + WriteString('k - kraj rada'); + WriteLn; + REPEAT + meni := RdKey(); + UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O', + 'I', 'B', 'K'}; + Clear; + IF CAP(meni) # 'K' THEN + CASE CAP(meni) OF + 'S' : Spisak(rad)| + 'Z' : Zaposli(rad)| + 'O' : Otpusti(rad)| + 'I' : Inform(rad)| + 'B' : Bankrot(rad) + END; + WriteLn; + WriteString('-- pritisnite bilo koji '); + WriteString('taster za nastavak --'); + pom := RdKey() + END + UNTIL CAP(meni) = 'K' +END Radnici. +\end{lstlisting} + +Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji: + +\begin{lstlisting}[style=codeblock] + PROCEDURE Spisak(rad : radnici); + BEGIN + IF rad # NIL THEN + WriteString(rad^.ime); + WriteString(' '); + WriteString(rad^.prez); + WriteCard(rad^.broj, 8); + WriteLn; + Spisak(rad^.sled) + END + END Spisak; +\end{lstlisting} + +\subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve + liste osoba koje dele sadržaj, jedna sortirana po visini, druga po + težini} + +Sa tastature učitavati po dva broja koji opisuju osobu (visina i +težina) i smeštati ih u povezane listu, tako da postoji neopadajuće +uređenje i po visini i po težini. + +\begin{lstlisting}[style=codeblock] +MODULE VisTez; +FROM Storage IMPORT ALLOCATE, DEALLOCATE; +FROM IO IMPORT WrLn, WrStr, RdCard, WrCard; +FROM SYSTEM IMPORT TSIZE; +TYPE + pok = POINTER TO element; + element = RECORD + visina, tezina : CARDINAL; + Vveza, Tveza : pok + END; +VAR + pocV, pocT : pok; + vis, tez : CARDINAL; +PROCEDURE Ispisi(pocV, pocT : pok); +VAR + tek : pok; +BEGIN + tek := pocV; + WrStr('Po visini:'); + WrLn; + WHILE tek # NIL DO + WrCard(tek^.visina, 6); + tek := tek^.Vveza + END; + WrLn; + tek := pocT; + WrStr('Po tezini:'); + WrLn; + WHILE tek # NIL DO + WrCard(tek^.tezina,6); + tek := tek^.Tveza + END +END Ispisi; + +PROCEDURE Ubaci(VAR pocV, pocT : pok; + vis, tez : CARDINAL); +VAR + novi, tek, iza : pok; + nadjen : BOOLEAN; +BEGIN + IF pocV = NIL THEN + ALLOCATE(pocV, TSIZE(element)); + pocV^.visina := vis; + pocV^.tezina := tez; + pocV^.Vveza := NIL; + pocV^.Tveza := NIL; + pocT := pocV + ELSE + ALLOCATE(novi, TSIZE(element)); + novi^.visina := vis; + novi^.tezina := tez; + tek := pocV; + nadjen := FALSE; + WHILE (tek # NIL) AND NOT nadjen DO + nadjen := vis <= tek^.visina; + IF NOT nadjen THEN + iza := tek; + tek := tek^.Vveza + END + END; + novi^.Vveza := tek; + IF tek = pocV THEN + pocV := novi + ELSE + iza^.Vveza := novi + END; + tek := pocT; + nadjen := FALSE; + WHILE (tek # NIL) AND NOT nadjen DO + nadjen := tez <= tek^.tezina; + IF NOT nadjen THEN + iza := tek; + tek := tek^.Tveza + END + END; + novi^.Tveza := tek; + IF tek = pocT THEN + pocT := novi + ELSE + iza^.Tveza := novi + END + END +END Ubaci; + +BEGIN + pocV := NIL; + pocT := NIL; + WrStr('Unesite visinu ---- '); + vis := RdCard(); + WHILE vis > 0 DO + WrStr('Unesite tezinu ---- '); + tez := RdCard(); + Ubaci(pocV, pocT, vis, tez); + WrLn; + WrStr('Unesite visinu ---- '); + vis := RdCard() + END; + WrLn; + Ispisi(pocV, pocT) +END VisTez. +\end{lstlisting} + +\section{Polinomi preko listi} + +\subsection{Moduli} + +Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka +\kod{Polinom} je definisan u globalnom modulu. + +\paragraph{PolinomL.DEF} \ + +\begin{lstlisting}[style=codeblock] +DEFINITION MODULE PolinomL; +TYPE + Polinom = POINTER TO Monom; + Monom = RECORD + k : REAL; + st : CARDINAL; + veza : Polinom + END; + +PROCEDURE Anuliraj(VAR p: Polinom); +PROCEDURE Unos(VAR p: Polinom); +PROCEDURE Stampaj(p: Polinom; d: CARDINAL); +PROCEDURE Kopiraj(p: Polinom; + VAR kopija: Polinom); +PROCEDURE UbaciMonom(mon:Polinom; + VAR p: Polinom); +PROCEDURE PromeniZnak(VAR p: Polinom); +PROCEDURE Saberi(p1, p2: Polinom; + VAR zbir: Polinom); +PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom); +PROCEDURE Oduzmi(p1,p2: Polinom; + VAR razlika: Polinom); +PROCEDURE MonomPuta(p, mon: Polinom; + VAR mp : Polinom); +PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom); +PROCEDURE Kolicnik(p1, p2: Polinom; + VAR kol, ost: Polinom; + VAR ok : BOOLEAN); +PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL; + VAR rez: Polinom); +PROCEDURE DisposePolinom(VAR p: Polinom); + +END PolinomL. +\end{lstlisting} + +\paragraph{PolinomL.MOD} \ + +\begin{codeblock} +(* Modul za rad sa polinomima preko listi + verzija 2012, rev 1 *) +IMPLEMENTATION MODULE PolinomL; +FROM InOut IMPORT Write, WriteString, WriteLn, + WriteCard, ReadCard, Done; +FROM RealInOut IMPORT WriteReal, ReadReal; +FROM Storage IMPORT ALLOCATE, DEALLOCATE; + +PROCEDURE Anuliraj(VAR p: Polinom); +BEGIN + p := NIL; +END Anuliraj; + +PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom); +VAR + pomocni: Polinom; +BEGIN + IF p = NIL THEN + kopija := NIL + ELSE + NEW(kopija); + kopija^ := p^; + p := p^.veza; + pomocni := kopija; + WHILE p <> NIL DO + NEW(pomocni^.veza); + pomocni := pomocni^.veza; + pomocni^ := p^; + p := p^.veza + END + END +END Kopiraj; + +PROCEDURE Stampaj(p: Polinom; d: CARDINAL); + + PROCEDURE StampajMonom(m : Polinom); + BEGIN + WITH m^ DO + IF st <> 0 THEN + IF ABS(k) <> 1.0 THEN + WriteReal(ABS(k), d) + END; + Write('x'); + IF st <> 1 THEN + Write('^'); + WriteCard(st, 1) + END + ELSE + WriteReal(ABS(k), d) + END + END + END StampajMonom; + +BEGIN + IF p = NIL THEN + WriteReal(0., d) + ELSE + IF p^.k < 0.0 THEN + WriteString(' - ') + END; + StampajMonom(p); + p := p^.veza; + WHILE p <> NIL DO + IF p^.k > 0.0 THEN + WriteString(' + ') + ELSE + WriteString(' - ') + END; + StampajMonom(p); + p := p^.veza + END + END +END Stampaj; + +PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom); +VAR + stari, tekuci, kopija: Polinom; +BEGIN + IF mon # NIL THEN + NEW(kopija); + kopija^ := mon^; + tekuci := p; + stari := NIL; + WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO + stari := tekuci; + tekuci := tekuci^.veza + END; + kopija^.veza := tekuci; + IF tekuci = p THEN + p := kopija + ELSE + stari^.veza := kopija + END; + IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN + kopija^.k := kopija^.k + tekuci^.k; + kopija^.veza := tekuci^.veza; + DISPOSE(tekuci); + IF kopija^.k = 0.0 THEN + IF p = kopija THEN + p := kopija^.veza + ELSE + stari^.veza := kopija^.veza + END; + DISPOSE(kopija) + END + END + END +END UbaciMonom; + +PROCEDURE Unos(VAR p : Polinom); +VAR + i, n: CARDINAL; + novi: Polinom; +BEGIN + Anuliraj(p); + REPEAT + WriteLn; + WriteString('Unesite broj monoma n (n>=0) '); + ReadCard(n); + UNTIL Done; + WriteLn; + FOR i := 1 TO n DO + NEW(novi); + WITH novi^ DO + REPEAT + WriteString('Unesite koeficijent monoma br.'); + WriteCard(i, 1); + WriteString(' (<> 0) '); + ReadReal(k); + WriteLn + UNTIL k <> 0.0; + REPEAT + WriteLn; + WriteString('Unesite eksponent monoma br.'); + WriteCard(i, 1); + WriteString(' (>=0) '); + ReadCard(st); + UNTIL Done; + WriteLn; + END; + UbaciMonom(novi, p); + DISPOSE(novi); + END +END Unos; + +PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom); +BEGIN + Kopiraj(p1, zbir); + WHILE p2 <> NIL DO + UbaciMonom(p2, zbir); + p2 := p2^.veza + END +END Saberi; + +PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom); +BEGIN + WHILE p <> NIL DO + UbaciMonom(p,rez); + p := p^.veza; + END; +END SaberiNa; + +PROCEDURE PromeniZnak(VAR p: Polinom); +VAR + t: Polinom; +BEGIN + t := p; + WHILE t <> NIL DO + t^.k := - t^.k; + t := t^.veza + END +END PromeniZnak; + +PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom); +BEGIN + Kopiraj(p2, razlika); + PromeniZnak(razlika); + WHILE p1 <> NIL DO + UbaciMonom(p1, razlika); + p1 := p1^.veza + END +END Oduzmi; + +PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom); +VAR + tekuci: Polinom; +BEGIN + Anuliraj(mp); + IF (mon <> NIL) AND (p <> NIL) THEN + NEW(mp); + mp^.k := p^.k * mon^.k; + mp^.st := p^.st + mon^.st; + p := p^.veza; + tekuci := mp; + WHILE p <> NIL DO + NEW(tekuci^.veza); + tekuci := tekuci^.veza; + tekuci^.k := p^.k * mon^.k; + tekuci^.st := p^.st + mon^.st; + p := p^.veza + END; + tekuci^.veza := NIL + END +END MonomPuta; + +PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom); +VAR + pomocni: Polinom; +BEGIN + Anuliraj(pr); + IF (p1 <> NIL) AND (p2 <> NIL) THEN + MonomPuta(p1, p2, pr); + p2 := p2^.veza; + WHILE p2 <> NIL DO + MonomPuta(p1, p2, pomocni); + REPEAT + UbaciMonom(pomocni, pr); + pomocni := pomocni^.veza + UNTIL pomocni = NIL; + p2 := p2^.veza + END + END +END Puta; + +PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN); + + PROCEDURE Deli(VAR kol, ost: Polinom); + VAR + novi, pomocni: Polinom; + BEGIN + IF ost <> NIL THEN + IF ost^.st >= p2^.st THEN + NEW(novi); + novi^.k := - ost^.k / p2^.k; + novi^.st := ost^.st - p2^.st; + MonomPuta(p2, novi, pomocni); + Saberi(ost, pomocni, ost); + novi^.k := - novi^.k; + UbaciMonom(novi, kol); + DISPOSE(novi); + Deli(kol, ost) + END + END + END Deli; + +BEGIN (* Kolicnik *) + ok := TRUE; + Anuliraj(kol); + IF p2 = NIL THEN + ok := FALSE + ELSE + Kopiraj(p1, ost); + Deli(kol, ost) + END +END Kolicnik; + +PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL; + VAR rez: Polinom); +VAR + i: CARDINAL; +BEGIN + IF n = 0 THEN + NEW(rez); + rez^.k := 1.0; + rez^.st := 0; + rez^.veza := NIL; + ELSIF n = 1 THEN + Kopiraj( p, rez ); + ELSE + rez := p; + FOR i := 2 TO n DO + Puta(rez, p, rez) + END + END; +END PolinomNaN; + +PROCEDURE DisposePolinom(VAR p: Polinom); +VAR + pomocni: Polinom; +BEGIN + pomocni := p; + WHILE pomocni # NIL DO + p := p^.veza; + DISPOSE(pomocni); + pomocni := p + END +END DisposePolinom; + +END PolinomL. +\end{codeblock} + + +\subsection{Zadatak: Sabiranje sa unapred određenim polinomom} + +Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$. + +\begin{lstlisting}[style=codeblock] +MODULE polinom; +FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj, DisposePolinom, UbaciMonom, Unos, Saberi; +FROM InOut IMPORT WriteString, WriteLn; +FROM Storage IMPORT ALLOCATE, DEALLOCATE; + +VAR + p,q,rez,pom : Polinom; + +BEGIN + (* korisnik unosi prvi polinom *) + WriteString("Unesite polinom:"); + WriteLn; + Unos(p); + (* drugi polinom kreiramo mi, + monom po monom *) + Anuliraj(q); (* isto sto i q:=NIL; *) + (* formiramo monom x^5 *) + NEW(pom); + pom^.st:=5; + pom^.k:=1.0; + (* dodajemo ga u polinom *) + UbaciMonom(pom,q); + DISPOSE(pom); + (* -3 x^4 *) + NEW(pom); + pom^.st := 4; + pom^.k := -3.0; + UbaciMonom(pom,q); + DISPOSE(pom); + (* 4 x *) + NEW(pom); + pom^.st := 1; + pom^.k := 4.0; + UbaciMonom(pom,q); + DISPOSE(pom); + (* 7 (x^0) *) + NEW(pom); + pom^.st := 0; + pom^.k := 7.0; + UbaciMonom(pom,q); + DISPOSE(pom); + (* saberemo polinome *) + Saberi(p, q, rez); + (* odstampamo rezultat *) + Stampaj(rez,0); + WriteLn; + (* oslobadjanje zauzete memorije *) + DisposePolinom(p); + DisposePolinom(q); + DisposePolinom(rez); +END polinom. +\end{lstlisting} + +\subsection{Zadatak: Suma k polinoma} + +Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon +toga izracunava njihovu sumu + +\begin{lstlisting}[style=codeblock] +MODULE PolSuma; + +FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom, Unos, Stampaj, SaberiNa; +FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard; +CONST + maxk = 50; +TYPE + nizPol = ARRAY [1..maxk] OF Polinom; +VAR + i, k: CARDINAL; + suma : Polinom; + p : nizPol; +BEGIN + REPEAT + WriteString('Unesite broj k (1 <= k <= '); + WriteCard(maxk, 1); + WriteString(') '); + ReadCard(k); + WriteLn; + UNTIL (1 <= k) AND (k <= maxk); + FOR i := 1 TO k DO + WriteLn; + WriteString('Unos '); + WriteCard(i, 1); + WriteString('. polinoma.'); + WriteLn; + Unos(p[i]) + END; + Anuliraj(suma); + FOR i := 1 TO k DO + SaberiNa(suma, p[i]) + END; + WriteLn; + WriteString('Njihova suma je:'); + WriteLn; + Stampaj(suma, 4); + DisposePolinom(suma); + FOR i := 1 TO k DO + DisposePolinom(p[i]); + END; +END PolSuma. +\end{lstlisting} + +\section{Stek i red opsluživanja} + +\subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera} + +\begin{lstlisting}[style=codeblock] +DEFINITION MODULE QueueInfo; +CONST + Maxqueue = 100; +TYPE + InfoTip = CHAR; + +END QueueInfo. + +IMPLEMENTATION MODULE QueueInfo; +END QueueInfo. + +DEFINITION MODULE RedOpsl1; +FROM QueueInfo IMPORT InfoTip,Maxqueue; +TYPE + Niz = ARRAY[1..Maxqueue] OF InfoTip; + RedOpslTip = RECORD + Prvi, Zadnji : CARDINAL; + Element : Niz + END; + +PROCEDURE MakeNull(VAR q : RedOpslTip); +PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN; +PROCEDURE First(VAR q : RedOpslTip; + VAR x : InfoTip; + VAR ok : BOOLEAN); +PROCEDURE PopFirst(VAR q : RedOpslTip; + VAR ok : BOOLEAN); +PROCEDURE AddRear(VAR q : RedOpslTip; + x : InfoTip; + VAR ok : BOOLEAN); + +END RedOpsl1. + +IMPLEMENTATION MODULE RedOpsl1; +FROM QueueInfo IMPORT Maxqueue,InfoTip; + +PROCEDURE MakeNull(VAR q : RedOpslTip); +BEGIN + WITH q DO + Prvi := 0; + Zadnji := 0 + END +END MakeNull; + +PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN; +BEGIN + RETURN q.Zadnji = 0 +END Empty; + + +PROCEDURE First(VAR q : RedOpslTip; + VAR x : InfoTip; + VAR ok : BOOLEAN); +BEGIN + IF Empty(q) THEN + ok := FALSE + ELSE + ok := TRUE; + WITH q DO + x := Element[Prvi] + END + END +END First; + +PROCEDURE AddOne(i : CARDINAL) : CARDINAL; +BEGIN + IF i = Maxqueue THEN + RETURN 1 + ELSE + RETURN i+1 + END +END AddOne; + +PROCEDURE PopFirst(VAR q : RedOpslTip; + VAR ok : BOOLEAN); +BEGIN + IF Empty(q) THEN + ok := FALSE + ELSE + ok := TRUE; + WITH q DO + IF Prvi = Zadnji THEN + MakeNull(q) + ELSE + Prvi := AddOne(Prvi) + END + END + END +END PopFirst; + +PROCEDURE AddRear(VAR q : RedOpslTip; + x : InfoTip; + VAR ok : BOOLEAN); +BEGIN + WITH q DO + IF AddOne(Zadnji) = Prvi THEN + ok := FALSE + ELSE + ok := TRUE; + IF Empty(q) THEN + Prvi := 1; + Zadnji := 1 + ELSE + Zadnji := AddOne(Zadnji) + END; + Element[Zadnji] := x + END + END +END AddRear; + +END RedOpsl1. + +MODULE Bafer; +FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear; +FROM FIO IMPORT File,WrChar, Create, Close; +IMPORT IO; + +CONST + ImeIzlaza = 'izlaz.txt'; + +VAR + izlaz : File; + znak : CHAR; + buffer : RedOpslTip; + +PROCEDURE IsprazniBafer(VAR dat : File; + VAR buf : RedOpslTip); +VAR + znak : CHAR; + ok : BOOLEAN; +BEGIN + WHILE NOT Empty(buf) DO + First(buf, znak, ok); + PopFirst(buf, ok); + WrChar(dat, znak) + END +END IsprazniBafer; + +PROCEDURE BaferWrite(VAR dat : File; + VAR buf : RedOpslTip; + znak : CHAR); +VAR + ok : BOOLEAN; +BEGIN + AddRear(buf, znak, ok); + IF NOT ok THEN + IsprazniBafer(dat, buf); + AddRear(buf, znak, ok) + END +END BaferWrite; + +BEGIN + izlaz := Create(ImeIzlaza); + MakeNull(buffer); + IO.WrStr('Unesite tekst, koji treba da se unese u datoteku '); + IO.WrStr(ImeIzlaza); + IO.WrChar('.'); + IO.WrLn; + IO.WrStr('Unos zavrsite tackom.'); + IO.WrLn; + znak := IO.RdChar(); + WHILE znak # '.' DO + BaferWrite(izlaz, buffer, znak); + znak := IO.RdChar(); + END; + IsprazniBafer(izlaz, buffer); + Close(izlaz) +END Bafer. +\end{lstlisting} + +\subsection% +{Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$} + +Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od +slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w. + +\begin{lstlisting}[style=codeblock] +DEFINITION MODULE Stek; +CONST + Maxstack = 100; +TYPE + Niz = ARRAY [1..Maxstack] OF CHAR; + StekTip = RECORD + Top : CARDINAL; + Element : Niz + END; +PROCEDURE MakeNull(VAR s : StekTip); +PROCEDURE Empty(VAR s : StekTip) : BOOLEAN; + +PROCEDURE Top(VAR s : StekTip; + VAR x : CHAR; + VAR ok : BOOLEAN); +PROCEDURE Pop(VAR s : StekTip; + VAR ok : BOOLEAN); +PROCEDURE Push(VAR s : StekTip; + x : CHAR; + VAR ok : BOOLEAN); +END Stek. + + +IMPLEMENTATION MODULE Stek; + +PROCEDURE MakeNull(VAR s : StekTip); +BEGIN + s.Top := 0 +END MakeNull; + +PROCEDURE Empty(VAR s : StekTip) : BOOLEAN; +BEGIN + RETURN s.Top = 0 +END Empty; + +PROCEDURE Top(VAR s : StekTip; + VAR x : CHAR; + VAR ok : BOOLEAN); +BEGIN + IF Empty(s) THEN + ok := FALSE + ELSE + ok := TRUE; + WITH s DO + x := Element[Top] + END + END +END Top; + +PROCEDURE Pop(VAR s : StekTip; + VAR ok : BOOLEAN); +BEGIN + IF Empty(s) THEN + ok := FALSE + ELSE + ok := TRUE; + DEC(s.Top) + END +END Pop; + +PROCEDURE Push(VAR s : StekTip; + x : CHAR; + VAR ok : BOOLEAN); +BEGIN + WITH s DO + IF Top = Maxstack THEN + ok := FALSE + ELSE + ok := TRUE; + INC(Top); + Element[Top] := x + END + END +END Push; +END Stek. + +MODULE wcw; +(* Da li rec pripada gramatici wcw+. *) +FROM Stek IMPORT StekTip, MakeNull, Empty, + Top, Pop, Push; +FROM InOut IMPORT Read, Write, WriteString, EOL; +TYPE + slova = SET OF CHAR; +VAR + S : StekTip; + Ch, C : CHAR; + ok : BOOLEAN; +BEGIN + MakeNull(S); + Read(Ch); + ok := TRUE; + WHILE ok AND (Ch IN slova{'a', 'b'}) DO + Push(S, Ch, ok); + Read(Ch); + END; + IF NOT ok THEN + WriteString('Greska - mali stek') + ELSIF Ch # 'c' THEN + WriteString('Pogresan string') + ELSE + Read(Ch); + WHILE ok AND (Ch # EOL) DO + Top(S, C, ok); + ok := ok AND (C = Ch); + IF ok THEN + Pop(S, ok); + Read(Ch); + END + END; + IF NOT (ok AND Empty(S)) THEN + WriteString('Pogresan string') + ELSE + WriteString('String pripada jeziku L') + END + END +END wcw. +\end{lstlisting} + +\subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza} + + +Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi +koji figurišu u izrazu su jednocifreni. + +\begin{lstlisting}[style=codeblock] +MODULE PostFix; + +FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push; +FROM InOut IMPORT Read, Write, WriteInt, EOL; +TYPE + slova = SET OF CHAR; +VAR + S : StekTip; + Ch : CHAR; + Op1, Op2 : INTEGER; + ok : BOOLEAN; +PROCEDURE Conv(Ch : CHAR) : INTEGER; +BEGIN + RETURN ORD(Ch) - ORD('0') +END Conv; + +BEGIN + MakeNull(S); + Read(Ch); + WHILE Ch # EOL DO + IF Ch IN slova{'+', '-', '/', '*', '%'} THEN + Top(S, Op2, ok); + Pop(S, ok); + Top(S, Op1, ok); + Pop(S, ok); + CASE Ch OF + '+' : Op1 := Op1 + Op2 | + '-' : Op1 := Op1 - Op2 | + '*' : Op1 := Op1 * Op2 | + '/' : Op1 := Op1 DIV Op2 | + '%' : Op1 := Op1 MOD Op2 + END; + Push(S, Op1, ok) + ELSE + Push(S, Conv(Ch), ok) + END; + Read(Ch); + END; + Top(S, Op1, ok); + Write('='); + WriteInt(Op1,5) +END PostFix. +\end{lstlisting} + + +\section{Simulacija rekurzije} + + +Na početku označiti sve rekurzivne pozive u originalnoj proceduri +adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka). + +Na steku se čuvaju lokalne promenljive, parametri procedure i adresa +mesta poziva, a u skladu sa tim se kreira InfoTip. + +Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih +rekurzivnih poziva. + +U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan, +odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni +pozivi. + +\begin{lstlisting} +MakeNull(S); +REPEAT + WHILE treba_rekurzija DO + -prepisati sve od pocetka originalne + procedure do prvog rekurzivnog poziva + -staviti na stek potrebne + lokalne promenljive, parametre procedure i + adresu mesta poziva + -podesiti vrednosti parametara da budu + kao u rekurzivnom pozivu procedure + END; + trivijalan poziv + umesto RETURN x pisati rez := x + jos := TRUE; + WHILE jos AND NOT Empty(S) DO + Top(S, el, ok); + Pop(S, ok); + -restauriramo vrednosti sa steka + -u zavisnosti od adrese poziva nastavimo + prepisivanje originalne procedure sa + tog mesta + -ako se dodje do novog rek. poziva tada: + -sacuvati na steku vrednosti + -podesiti vrednosti parametara da budu + kao u rekurzivnom pozivu procedure + -ici na pocetak koda + (ovo se postize sa jos := FALSE) + -inace + ako se naidje na RETURN x pisati rez := x + END +UNTIL Empty(S); +\end{lstlisting} + +Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}. + +\subsection*{ZADACI} + +Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka: + +\subsection{Primer 1 -- faktorijel} + + +\begin{lstlisting}[style=codeblock] +MODULE Fakto; +(* InfoTip = CARDINAL; *) + +FROM IO IMPORT WrStr, WrLn, WrCard, RdCard; +FROM StekC IMPORT StekTip, MakeNull, Empty, + Top, Pop, Push; +VAR + n : CARDINAL; +PROCEDURE RFakto(n : CARDINAL) : CARDINAL; +BEGIN + IF n <= 1 THEN + RETURN 1 + ELSE + RETURN n * RFakto(n-1) + END +END RFakto; + + +PROCEDURE SFakto(n : CARDINAL) : CARDINAL; +VAR + s : StekTip; + rez : CARDINAL; + OK : BOOLEAN; +BEGIN + MakeNull(s); + WHILE n > 1 DO + Push(s,n,OK); + DEC(n) + END; + rez := 1; + WHILE NOT Empty(s) DO + Top(s, n, OK); + Pop(s, OK); + rez := n * rez + END; + RETURN rez +END SFakto; + +BEGIN + WrStr('n = '); + n := RdCard(); + WrLn + WrStr('n! = '); + WrCard(RFakto(n), 1); + WrStr(' = '); + WrCard(SFakto(n), 1) +END Fakto. +\end{lstlisting} + +\manbreakJK + +\subsection{Primer 2 -- stepenovanje} + +\begin{lstlisting}[style=codeblock] +MODULE Step; +(* InfoTip = RECORD + x : REAL; + n : CARDINAL; + adr : (par, nepar) + END; +*) +FROM IO IMPORT WrStr, WrLn, WrReal, + RdReal, RdCard; +FROM StekStep IMPORT StekTip, MakeNull, Empty, + Top, Pop, Push, InfoTip, AdrTip; +VAR + n : CARDINAL; + x : REAL; + +PROCEDURE Sqr(y : REAL) : REAL; +BEGIN + RETURN y * y +END Sqr; + +PROCEDURE RStep(x : REAL; + n : CARDINAL) : REAL; +BEGIN + IF n = 0 THEN + RETURN 1. + ELSIF ODD(n) THEN + RETURN x * Sqr( RStep(x, n DIV 2) ) + ELSE + RETURN Sqr( RStep(x, n DIV 2) ) + END +END RStep; + +PROCEDURE SStep(x : REAL; + n : CARDINAL ) : REAL; +VAR + s : StekTip; + OK : BOOLEAN; + rez : REAL; + el : InfoTip; +BEGIN + MakeNull(s); + WHILE n > 0 DO + el.x := x; + el.n := n; + IF ODD(n) THEN + el.adr := nepar; + ELSE + el.adr := par + END; + Push(s,el,OK); + n := n DIV 2 + END; + rez := 1.; + WHILE NOT Empty(s) DO + Top(s, el, OK); + Pop(s, OK); + x := el.x; + n := el.n; + IF el.adr = nepar THEN + rez := x * Sqr(rez) + ELSE + rez := Sqr(rez) + END + END; + RETURN rez +END SStep; + +BEGIN + WrStr('x =? '); + x := RdReal(); + WrLn; + WrStr('n =? '); + n := RdCard(); + WrStr('x^n = '); + WrReal(RStep(x, n), 10, 1); + WrStr(' = '); + WrReal(SStep(x, n), 10, 1) +END Step. +\end{lstlisting} + +\subsection{Primer 3 -- Fibonači} + +\begin{lstlisting}[style=codeblock] +MODULE Fib; +(* InfoTip = RECORD + n : CARDINAL; + PrviSab : CARDINAL; + adr : (prvi, drugi) + END; +*) + +FROM IO IMPORT WrStr, WrLn, WrCard, RdCard; +FROM StekFib IMPORT StekTip, MakeNull, Empty, + Top, Pop, Push, InfoTip, AdrTip; +VAR + n : CARDINAL; + +PROCEDURE RFib(n : CARDINAL) : CARDINAL; +BEGIN + IF n <= 1 THEN + RETURN n + ELSE + RETURN RFib(n-1) + RFib(n-2) + END +END RFib; + +PROCEDURE SFib(n : CARDINAL ) : CARDINAL; +VAR + s : StekTip; + OK, jos : BOOLEAN; + rez, PrviSab : CARDINAL; + el : InfoTip; +BEGIN + MakeNull(s); + REPEAT + WHILE n > 1 DO + el.n := n; + el.adr := prvi; + Push(s,el,OK); + DEC(n) + END; + rez := (n); + jos := TRUE; + WHILE (NOT Empty(s)) AND jos DO + Top(s, el, OK); + Pop(s, OK); + n := el.n; + IF el.adr = prvi THEN + PrviSab := rez; + el.n := n; + el.adr := drugi; + el.PrviSab := PrviSab; + Push(s, el, OK); + DEC(n, 2); + jos := FALSE + ELSE + PrviSab := el.PrviSab; + rez := PrviSab + rez + END + END + UNTIL Empty(s); + RETURN rez +END SFib; + +BEGIN + WrStr('n =? '); + n := RdCard(); + WrStr('F(n) = '); + WrCard(RFib(n), 1); + WrStr(' = '); + WrCard(SFib(n), 1) +END Fib. +\end{lstlisting} + +\subsection{Primer 4 -- faktorijel 2} + + +\begin{lstlisting}[style=codeblock] +MODULE Faktor; +(* InfoTip = CARDINAL; *) +FROM IO IMPORT WrStr, WrLn, WrCard, RdCard; +FROM StekC IMPORT StekTip, MakeNull, Empty, + Top, Pop, Push; +VAR + n,rez : CARDINAL; + +PROCEDURE RFakto(n : CARDINAL; + VAR rez : CARDINAL); +BEGIN + IF n = 0 THEN + rez := 1 + ELSE + RFakto(n-1, rez); + rez := n * rez + END +END RFakto; + +PROCEDURE SFakto(n : CARDINAL; + VAR rez : CARDINAL); +VAR + s : StekTip; + OK : BOOLEAN; +BEGIN + MakeNull(s); + WHILE n > 0 DO + Push(s,n,OK); + DEC(n) + END; + rez := 1; + WHILE NOT Empty(s) DO + Top(s, n, OK); + Pop(s, OK); + rez := n * rez + END +END SFakto; + +BEGIN + WrStr('n =? '); + n := RdCard(); + WrLn; + WrStr('n! = '); + RFakto(n, rez); + WrCard(rez, 1); + WrStr(' = '); + SFakto(n, rez); + WrCard(rez, 1) +END Faktor. +\end{lstlisting} + +\subsection{Primer 5 (ispitni)} + + +\begin{lstlisting}[style=codeblock] +MODULE Rek1; +(* InfoTip = RECORD + d, g, m1, m2 : INTEGER; + adr : (prvi, drugi) + END; +*) +FROM Stek1 IMPORT StekTip, adresa, InfoTip, + MakeNull, Empty, Top, Pop, Push; +IMPORT IO; +VAR + X : ARRAY [1..20] OF INTEGER; + +PROCEDURE Max(d, g: INTEGER) : INTEGER; +VAR + m1, m2 : INTEGER; +BEGIN + IF d>g THEN + RETURN MIN(INTEGER) + ELSIF d=g THEN + RETURN X[d] + ELSE + m1 := Max(d, (d+g) DIV 2); + m2 := Max((d+g) DIV 2 +1, g); + IF m1 > m2 THEN + RETURN m1 + ELSE + RETURN m2 + END + END +END Max; + +PROCEDURE SMax(d, g: INTEGER) : INTEGER; +VAR + S : StekTip; + el : InfoTip; + ok, jos : BOOLEAN; + m1, m2, rez : INTEGER; +BEGIN + MakeNull(S); + REPEAT + WHILE dg THEN + rez := MIN(INTEGER) + ELSE (* d=g *) + rez := X[d] + END; + jos := TRUE; + WHILE jos AND NOT Empty(S) DO + Top(S, el, ok); + Pop(S, ok); + d := el.d; + g := el.g; + m1 := el.m1; + IF el.adr = prvi THEN + m1 := rez; + el.m1 := m1; + el.adr := drugi; + Push(S, el, ok); + d := (d+g) DIV 2 + 1; + jos := FALSE + ELSE (*el.adr = drugi*) + m2 := rez; + IF m1 > m2 THEN + rez := m1 + ELSE + rez := m2 + END + END + END + UNTIL Empty(S); + RETURN rez +END SMax; + +BEGIN (* glavni program *) + X[1] := 3; + X[2] := 2; + X[3] := 5; + X[4] := -7; + X[5] := 0; + IO.WrCard(Max(1, 5), 3); + IO.WrLn; + IO.WrCard(SMax(1, 5), 3); + IO.WrLn +END Rek1. +\end{lstlisting} + +\subsection{Primer 6 (ispitni)} + + +\begin{lstlisting}[style=codeblock] +MODULE Rek2; +(* InfoTip = RECORD + x, y, n : CARDINAL; + adr : (prvi, drugi, treci, cetvrti) + END; +*) +FROM Stek2 IMPORT StekTip, adresa, InfoTip, + MakeNull, Empty, Top, Pop, Push; +IMPORT IO; + +PROCEDURE g(x : CARDINAL; y : CARDINAL; + n : CARDINAL) : CARDINAL; +BEGIN + IF n < 3 THEN + RETURN x + y + ELSIF ODD(n) THEN + RETURN g(g(x+1, y, n-2), y, n-3) + ELSE + RETURN g(x, g(x, y+1, n-2), n-3) + END +END g; + +PROCEDURE Sg(x : CARDINAL; y : CARDINAL; + n : CARDINAL) : CARDINAL; +VAR + S : StekTip; + el : InfoTip; + ok, jos : BOOLEAN; + rez : CARDINAL; +BEGIN + MakeNull(S); + REPEAT + WHILE n >= 3 DO + IF ODD(n) THEN + el.x := x; + el.y := y; + el.n := n; + el.adr := prvi; + Push(S, el, ok); + INC(x); + DEC(n, 2) + ELSE + el.x := x; + el.y := y; + el.n := n; + el.adr := treci; + Push(S, el, ok); + INC(y); + DEC(n, 2) + END + END; + rez := x+y; + jos := TRUE; + WHILE jos AND NOT Empty(S) DO + Top(S, el, ok); + Pop(S, ok); + x := el.x; + y := el.y; + n := el.n; + IF el.adr = prvi THEN + el.adr := drugi; + Push(S, el, ok); + x := rez; + DEC(n, 3); + jos := FALSE + ELSIF el.adr = treci THEN + el.adr := cetvrti; + Push(S, el, ok); + y := rez; + DEC(n, 3); + jos := FALSE + END + END + UNTIL Empty(S); + RETURN rez +END Sg; + +BEGIN (* glavni program *) + IO.WrCard(g(2, 3, 10), 3); + IO.WrCard(Sg(2, 3, 10), 3); +END Rek2. +\end{lstlisting} + +%\columnbreak + +\appendix + +\section{Native XDS Modula 2 -- kratko uputstvo} + + +Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows +sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program. + +\subsection*{Dobavljanje instalacije} + + +Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača, +\url{http://www.excelsior-usa.com/}, tačnije na adresi: + +\url{http://www.excelsior-usa.com/xdsdl.html} + +Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste +razumeli i da ćete ga se pridržavati. + +Na stranici koja se potom otvara je potrebno odabrati ``XDS 2.6 beta 2 +for Windows'' i snimiti je na računar. + +\subsection*{Instalacija okruženja} + +Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute + instalacione arhive. + +\emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione + pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim + klikom miša.} + +Pretpostavićemo u daljem tekstu da je program instaliran u +\kod{C:/XDS/} + +\subsection*{Pokretanje okruženja} + +Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao +i grupa sa programom u start meniju. + +Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice, +okruženje se može pokrenuti uz pomoć izvršnog fajla +\kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj +lokaciji). + +\subsection*{Prvi projekat} + +Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo +napraviti projekat za njega, što se radi na sledeći način: + +\begin{itemize} + +\item + Iz menija se odabere Project->New. +\item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde + će se kreirati projekat i ukuca se ime novog projekta. + +\item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko + postoji neki tekst, obrisati ga. + +\item Kliknuti na ``OK'' + +\item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje, + kliknuti na ``OK'' da se on napravi. + +\item Pojavljuje se forma za kucanje programa, ukucati (na primer): + +\begin{minipage}{\columnwidth} +\begin{lstlisting}[style=codeblock] + MODULE Hello; + FROM InOut IMPORT WriteString,WriteLn; + BEGIN + WriteString("Hello World"); + WriteLn; + END Hello. +\end{lstlisting} +\end{minipage} + +\item Program se može pokrenuti na različite načine, pri čemu se + automatski prevodi: + + \begin{itemize} + + \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči) + + \item Meni Debug->Run + + \item Prečica Ctrl+F9 na tastaturi + + \end{itemize} + +\item Ako je sve u redu sa programom, treba da se pojavi novi terminal + u kome se ispisuje rezultat izvršavanja programa, u našem slučaju + jednostavna pozdravna poruka. +\end{itemize} + +Naravno moguće je i samo prevesti (kompajlirati) program, tako da se +samo prikažu greške (ako ih ima) i bez pokretanja programa: +\begin{itemize} +\item Klik na ``Compile'' ikonicu u toolbaru +\item Meni Tools->Compile +\item Prečica F9 na tastaturi +\end{itemize} + +Ukoliko u programu postoje greške, on neće biti pokrenut, već će se +dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S'' +u četvrtom redu i probamo da pokrenemo program, taj red će biti +označen svetlo plavom bojom i dobićemo poruku: + +\kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"} + +Što znači da u četvrtom redu, kod petog karatkera postoji problem, da +identifikator nije deklarisan, što najčešće znači da ga nismo uvezli, +ili, kao u našem slučaju, da smo napravili grešku u kucanju. + +Stvar na koju isto treba obratiti pažnju je da se nekad greška +prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer, +ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo +program, peti red će biti označen svetlo plavom bojom i dobićemo +poruku: + +\kod{- Error in pro1.mod [5:5]: Expected symbol ";" } + +Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će +kompajler probati da je traži i dalje, pa će tek na početku petog reda +prijaviti grešku. + +U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se +uvezena komanda WriteString ne koristi nigde u programu. Često se +upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na +greške, odnosno poruke koje počinju sa ``Error''. + +Takođe se često dešava da su druge prijavljene greške posledica prve, +te je poželjno ponovo kompajlirati (ili pokretati) program posle svake +ispravljene greške. + +\paragraph{Napomena o template-ovima pri kreiranju projekta:} +Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template'' + uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na + ``Configure'', a potom isprazniti polje ``default template''. + +\subsection{Mogući problemi} + +\subsubsection*{Nedostajući sistemski moduli} + +Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se +koriste u okviru kursa, i bilo je neophodno da se dodatno instalira i +``Top Speed Compatibility Pack'' (tscp-x86...). Bez njega je kompajler +prijavljivao da ne postoje neki moduli - najčešće je problem bio da +nedostaje \kod{FIO} modul. + +\subsubsection*{Problemi u pokretanju - nemoguće naći exe} + +Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi +da ne može da nađe exe i pri tome prijavljuje kraću putanju od one +koja je stvarno u pitanju, obično se radi o tome da je postojao razmak +u okviru putanje do modula. Npr ``C:\textbackslash Moj prvi program'' +će prouzrokovati probleme, a kompajler će prijaviti da ne može da nađe +``C:\textbackslash Moj''. + +Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj +verziji ne može se zaobići, tako da je jedino rešenje premestiti +fajlove, odnosno ako je moguće preimenovati problematične foldere. + +\mainend + + diff --git a/skripta-spa1.tex b/skripta-spa1.tex deleted file mode 100644 index b19c92f..0000000 --- a/skripta-spa1.tex +++ /dev/null @@ -1,3120 +0,0 @@ -% skripta-spa1.tex -% Skripta za predmet Strukture podataka i algoritmi 1, DMI, PMF, NS - -\documentclass[a4paper,twoside]{article} -\usepackage[T1]{fontenc} -\usepackage[utf8]{inputenc}%definišemo da je ulaz utf-8 fajl - -% osnovne informacije koje ce se prikazati na naslovnoj strani, -% kao i u informacijama u generisanom pdfu -\newcommand{\autor}{Vladimir Kurbalija, Milos Radovanovic, Doni Pracner} -\newcommand{\naslov}{Skripta za vezbe iz predmeta "Strukture podataka - i algoritmi 1"} -\newcommand{\datum}{Februar 2013, Novi Sad} -\newcommand{\verzija}{ver 13a-jk} -%jk=jedna kolona, dk=dve kolone - -\newcommand{\mainstart}{ -%\begin{multicols}{2} -} - -\newcommand{\mainend}{ -%\end{multicols} -} - -\newcommand{\manbreakJK}{ -\pagebreak -} - -\usepackage[serbian]{babel} -\usepackage{fancyhdr} -\pagestyle{fancy} - -\title{\naslov -- \verzija} -\author{\autor} -\date{\datum} - -%change the default font -\usepackage{lmodern} -\usepackage{beramono} -\renewcommand{\familydefault}{\sfdefault} - -\usepackage{pifont} - -%podesavanja outputa za pdf verzije -\usepackage[bookmarks,pdffitwindow=false,unicode=true,% -pdftitle={\naslov -- \verzija},% -pdfauthor={\autor}% -]{hyperref} - -\usepackage{graphicx} -\usepackage{listings} -\usepackage{amsthm} -\usepackage{amsmath} -\usepackage{latexsym} -\usepackage{multicol} - -%margine -%experiment -%\usepackage[top=2.5cm, bottom=1.5cm, left=3cm, right=2cm]{geometry} -%staro: -\usepackage[top=1.5cm, bottom=1cm, left=2cm, right=1cm]{geometry} - -\begin{document} - -%customize the itemize environments - -\let\olditemize=\itemize -\def\itemize{ -\olditemize - \setlength{\itemsep}{1pt} - \setlength{\parskip}{0pt} - \setlength{\parsep}{0pt} - \setlength{\topsep}{-1cm} - \setlength{\partopsep}{1pt} -} - -%% ovi redovi daju header i footer - -\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}} -\fancyhf{} % delete current setting for header and footer -%\fancyfoot[C]{\thepage} -\fancyhead[LO]{\bfseries\rightmark} -\fancyhead[RO]{\thepage} -\fancyhead[RE]{Strukture podataka i algoritmi 1 -- skripta} -\fancyhead[LE]{\thepage} -\renewcommand{\headrulewidth}{0.5pt} -\renewcommand{\headwidth}{\textwidth} -%\renewcommand{\footrulewidth}{0.5pt} -%\addtolength{\headheight}{0.5pt} % make space for the rule -\fancypagestyle{plain}{% -\fancyhead{} % get rid of headers on plain pages -\fancyfoot{} -\renewcommand{\headrulewidth}{0pt} % and the line -\renewcommand{\footrulewidth}{0pt} % and the line -} -\renewcommand{\headheight}{15pt} - -%promene u marginama: -%\setlength{\marginparwidth}{32pt} -%\setlength{\textwidth}{620pt} -%\setlength{\textheight}{620pt} - - -%% specijalni blokovi koji služe kao podsetnici u radu ili napomene -\newcommand{\skica}[1]{ - \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small** \textit{#1} }} - \newline } -} - -\newcommand{\skicas}[1]{ - \framebox{* \textit{#1} *} -} - -%boldovane skice visokog prioriteta -\newcommand{\skicab}[1]{ - \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small*** - \textbf{#1} }} \newline } } - -\newcommand{\kod}[1]{{\small\texttt{#1}}} - -% ako je sledeci red odkomentarisan nista od skica nece biti ispisano -% u finalni dokument - -% \renewcommand{\skica}[1]{} - -% title u skladu sa uobičajenim na Departmanu -\newcommand{\makemytitle}{ - \begin{center} - \makebox{% - \includegraphics[width=2cm]{grbPMF} - \parbox[b]{65ex}{\centering - Univerzitet u Novom Sadu\\ - Prirodno-matematički fakultet\\ - Departman za matematiku i informatiku} - \includegraphics[width=2cm]{grbUNS} - } - \vspace{10ex} - - \parbox[b]{\textwidth}{{\Large {\bf - Vladimir Kurbalija, \href{mailto:kurba@dmi.rs}{kurba@dmi.rs}\\ - Miloš Radovanović, \href{mailto:radacha@dmi.rs}{radacha@dmi.rs}\\ - Doni Pracner, \href{mailto:doni.pracner@dmi.rs}{doni.pracner@dmi.rs}}}} - \vspace{5ex} - - {\Large {\bf Skripta za vežbe iz predmeta }} - - {\Huge {\bf - \setlength{\baselineskip}{1.5\baselineskip}Strukture - podataka i algoritmi 1}} - - \vspace{5ex} - %\vfill - - \verzija \ -- \datum - - \end{center} - \thispagestyle{plain} -% \newpage -} - -\makemytitle - -% theorems, definition etc. -%'''''''''''''''''''''''''' - -\theoremstyle{definition} -\newtheorem{def1}{Definicija} -\theoremstyle{plain} -\newtheorem{theo}{Teorema} -\newtheorem{lema}{Lema} - -\lstloadlanguages{Modula-2} - -\lstset{ - basicstyle=\footnotesize\ttfamily, - showstringspaces=false, - breaklines=true -} - -\lstdefinestyle{codeblock}{ - basicstyle=\footnotesize\ttfamily, - keywordstyle=\textbf, - columns=[l]fixed, - breakatwhitespace=true, -% prebreak=\P, -% postbreak=\ding{229}\space, - language=Modula-2 -} - -\lstdefinestyle{numcodeblock}{ - style=codeblock, - numbers=left -} - -\lstnewenvironment{codeblock}{\lstset{style=codeblock}}{} - - -% ----------------==================-------------------------------------- -% Pravi pocetak rada - - -Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula -2'. Za verzije pre 2.60 je neophodno dodatno instalirati i TSCP (Top -Speed Compatibility Pack), pošto je potreban za neke od modula koji se -ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi -moduli uključeni u standardnu instalaciju. - -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/} - -\tableofcontents - -%\newpage - -\mainstart - -\section{Ilustracija efikasnosti algoritma} - -\subsection{Zadatak: Pronaći sve pitagorine -trojke do zadate granice} - -Pitagorina trojka su tri broja $a,b,c$ za koje važi $a^2 + b^2 = c^2\\$ - -\begin{lstlisting}[style=codeblock] -MODULE Trojke1; -(* Pitagorine trojke koriscenjem "Brute-force" *) -FROM InOut IMPORT WriteString, WriteLn, WriteCard; -CONST - Gr = 100; -VAR - a, b, c : [1 .. Gr]; -BEGIN - FOR a := 1 TO Gr DO - FOR b := 1 TO Gr DO - FOR c := 1 TO Gr DO - IF a*a + b*b = c*c THEN - WriteLn; - WriteString('a = '); - WriteCard(a,2); - WriteString(', b = '); - WriteCard(b,2); - WriteString(', c = '); - WriteCard(c,2) - END - END - END - END -END Trojke1. -\end{lstlisting} - -\begin{codeblock} -MODULE Trojke2; -(*Pitagorine trojke koriscenjem zaokrugljivanja*) -FROM InOut IMPORT WriteString, WriteLn, WriteCard; -FROM MathLib0 IMPORT sqrt; -CONST - Gr = 100; -VAR - a, b, c : CARDINAL; - creal : REAL; -BEGIN - FOR a := 1 TO Gr DO - FOR b := 1 TO Gr DO - creal := FLOAT(a*a) + FLOAT(b*b); - creal := sqrt(creal); - c := TRUNC(creal); - IF creal = FLOAT(c) THEN - WriteLn; - WriteString(' a = '); - WriteCard(a,2); - WriteString(', b = '); - WriteCard(b,2); - WriteString(', c = '); - WriteCard(c,2) - END - END - END -END Trojke2. -\end{codeblock} - -Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup. -Ako uzmemo neka dva prirodna broja $m$ i $n$, tada se iz njih može -izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove: -\[ -\begin{array}{l} -a = 2mn\\ -b = m^2 - n^2\\ -c = m^2 + n^2 -\end{array} -\] -Odnosno kad probamo da proverimo da li je ovo -Pitagorina trojka dobijamo: -\[ -\begin{array}{r@=l} -a^2 + b^2 & c^2\\ -(2mn)^2 + (m^2 - n^2)^2 & (m^2 + n^2)^2 -\end{array} -\] - -\begin{codeblock} -MODULE Trojke3; -(* Pitagorine trojke koriscenjem teoreme *) -FROM InOut IMPORT WriteString, WriteLn, WriteCard; -CONST - Gr = 10; -VAR - a, b, c, m, n : CARDINAL; -BEGIN - FOR m := 1 TO Gr DO - FOR n := 1 TO m-1 DO - a := 2*m*n; - b := m*m - n*n; - c := m*m + n*n; - WriteLn; - WriteString('a = '); - WriteCard(a,2); - WriteString(', b = '); - WriteCard(b,2); - WriteString(', c = '); - WriteCard(c,2) - END - END -END Trojke3. -\end{codeblock} - -Sledeća dva metoda traže trojke sa nekim specifičnim osobinama. - -\begin{codeblock} -MODULE Trojke4; -(* Pitagorine trojke kod kojih je razlika - izmedju katete i hipotenuze tacno 1 *) -FROM InOut IMPORT WriteString, WriteLn, WriteCard; -CONST - Gr = 10; -VAR - a, b, c, m, n : CARDINAL; -BEGIN - FOR m := 2 TO Gr DO - n := m - 1; - a := 2*m*n; - b := m*m - n*n; - c := m*m + n*n; - WriteLn; - WriteString('a = '); - WriteCard(a,2); - WriteString(', b = '); - WriteCard(b,2); - WriteString(', c = '); - WriteCard(c,2) - END -END Trojke4. -\end{codeblock} - -\begin{lstlisting}[style=codeblock] -MODULE Trojke5; -(* Pitagorine trojke kod kojih je razlika - izmedju kateta jedan *) -FROM InOut IMPORT WriteString, WriteLn, WriteCard; -CONST - Gr = 7; -VAR - a, b, c, m, n, w, i, temp : CARDINAL; -BEGIN - w := 1; - n := 0; - FOR i := 1 TO Gr DO - m := n + w; - a := 2*m*n; - b := m*m - n*n; - c := m*m + n*n; - WriteLn; - WriteString('a = '); - WriteCard(a,2); - WriteString(', b = '); - WriteCard(b,2); - WriteString(', c = '); - WriteCard(c,2); - temp := w; - w := 3*w + 4*n; - n := 2*temp + 3*n - END -END Trojke5. -\end{lstlisting} - -\manbreakJK - -\subsection[Zadatak: Maksimalna suma susednih elemenata u -nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u - nizu celih brojeva} - -\begin{lstlisting}[style=codeblock] -MODULE MaxNiza1; -(* Prvo resenje. Brute Force: O(n^3) *) -FROM InOut IMPORT WriteString,ReadInt, - WriteInt,WriteCard,WriteLn; -CONST - N = 10; -TYPE - Interval = [1..N]; -VAR - Max, Suma : INTEGER; - d,g,i,Ood,Doo : Interval; - X : ARRAY Interval OF INTEGER; -BEGIN - WriteString(' Unesite niz X '); - WriteLn; - FOR i := 1 TO N DO - ReadInt(X[i]); - WriteLn - END; - Max := 0; - FOR d := 1 TO N DO - FOR g := 1 TO N DO - Suma := 0; - FOR i := d TO g DO - Suma := Suma + X[i] - END; - IF Suma > Max THEN - Max := Suma; - Ood := d; - Doo := g - END - END - END; - WriteLn; - WriteString(' Maksimum je '); - WriteInt(Max,3); - WriteString(' u intervalu od '); - WriteCard(Ood,3); - WriteString(' do '); - WriteCard(Doo,3) -END MaxNiza1. - -MODULE MaxNiza2; -(* Drugo resenje: O(n^2). - Koristi se cinjenica da je suma X[d..g] - izracunljiva iz X[d..g-1]. *) -FROM InOut IMPORT WriteString,ReadInt, - WriteInt,WriteCard,WriteLn; -CONST - N = 10; -TYPE - Interval = [1..N]; -VAR - Max, Suma : INTEGER; - d,g,i,Ood,Doo : Interval; - X : ARRAY Interval OF INTEGER; -BEGIN - WriteString(' Unesite niz X '); - WriteLn; - FOR i := 1 TO N DO - ReadInt(X[i]); - WriteLn - END; - Max := 0; - FOR d := 1 TO N DO - Suma := 0; - FOR g := d TO N DO - Suma := Suma + X[g]; - IF Suma > Max THEN - Max := Suma; - Ood := d; - Doo := g - END - END - END; - WriteLn; - WriteString(' Maksimum je '); - WriteInt(Max,3); - WriteString(' u intervalu od '); - WriteCard(Ood,3); - WriteString(' do '); - WriteCard(Doo,3) -END MaxNiza2. -\end{lstlisting} - -\begin{codeblock} -MODULE MaxNiza3; -(* Trece resenje: O(n^2). - Koristi pomocni niz u kome je na i-tom mestu - suma podniza x[1..i] *) -FROM InOut IMPORT WriteString,ReadInt, - WriteInt,WriteCard,WriteLn; -CONST - N = 10; -TYPE - Interval = [1..N]; -VAR - Max, Suma : INTEGER; - d,g,i,Ood,Doo : Interval; - X : ARRAY Interval OF INTEGER; - Pom : ARRAY [0..N] OF INTEGER; -BEGIN - WriteString(' Unesite niz X '); - WriteLn; - FOR i := 1 TO N DO - ReadInt(X[i]); - WriteLn - END; - Pom[0] := 0; - FOR i := 1 TO N DO - Pom[i] := Pom[i-1] + X[i] - END; - Max := 0; - FOR d := 1 TO N DO - FOR g := d TO N DO - Suma := Pom[g] - Pom[d-1]; - IF Suma > Max THEN - Max := Suma; - Ood := d; - Doo := g - END - END - END; - WriteLn; - WriteString(' Maksimum je '); - WriteInt(Max,3); - WriteString(' u intervalu od '); - WriteCard(Ood,3); - WriteString(' do '); - WriteCard(Doo,3) -END MaxNiza3. -\end{codeblock} - -\begin{codeblock} -MODULE MaxNiza4; -(* Cetvrto resenje. Najbolje moguce: O(n) *) -FROM InOut IMPORT WriteString,ReadInt, - WriteInt,WriteCard,WriteLn; -CONST - N = 10; -TYPE - Interval = [1..N]; -VAR - Max, MaxDovde : INTEGER; - i,d,Ood,Doo : Interval; - X : ARRAY Interval OF INTEGER; -BEGIN - WriteString(' Unesite niz X '); - WriteLn; - FOR i := 1 TO N DO - ReadInt(X[i]); - WriteLn - END; - Max := 0; - MaxDovde := 0; - FOR i := 1 TO N DO - IF MaxDovde = 0 THEN - d := i - END; - MaxDovde := MaxDovde + X[i]; - IF MaxDovde < 0 THEN - MaxDovde := 0 - END; - IF MaxDovde > Max THEN - Ood := d; - Doo := i; - Max := MaxDovde - END - END; - WriteLn; - WriteString(' Maksimum je '); - WriteInt(Max,3); - WriteString(' u intervalu od '); - WriteCard(Ood,3); - WriteString(' do '); - WriteCard(Doo,3) -END MaxNiza4. -\end{codeblock} - -\section{Stringovi} - - -Stringovi -- odnosno nizovi znakova -- ne postoje kao ugrađeni tip u -jeziku Modula 2. Ovo daje slobodu da se niz znakova definiše na dužinu -najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr: -\begin{codeblock} - TYPE - String = ARRAY [1..30] OF CHAR; -\end{codeblock} - -Operacije nad stringovima se najčešće uvoze iz modula \kod{Str}. One -sve prihvataju \emph{otvorene nizove znakova} (strukture definisane sa -\kod{ARRAY OF CHAR}), tako da im se može proslediti niz proizvoljne -dužine. - -Određivanje stvarne dužine stringa (tj koliko od maksimalnog -kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na -sledeći način: -\begin{codeblock} - duzina := Length(str) -\end{codeblock} - -Leksikografsko poređenje dva stringa se ne može vršiti standardnim -operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o -nizovima, a delom i zato što se ne vidi direktno koji deo niza je -popunjen stvarnim sadržajem. Za ovo se koristi komanda \kod{Compare}, -koja prihvata dva stringa kao parametre, a vraća broj koji predstavlja -njihov odnos. Taj broj će biti 0 ako su stringovi jednaki, veći -od nule ako je prvi string ``veći'', i manji od nule ako je prvi -string ``manji''. Ovo se lako pamti kad primetimo da je odnos -između \kod{Compare} i 0 isti kao i između prvog i drugog stringa. - -\begin{codeblock} - IF Compare(str1, str2) > 0 THEN - WriteString("Prvi string je veci"); - ELSIF Compare(str1, str2) < 0 THEN - WriteString("Prvi string je manji"); - ELSE (* moraju biti jednaki *) - WriteString("Jednaki su"); - END; -\end{codeblock} - -Postoji i modul \kod{Strings} koji ima nešto drugačije definisane -procedure, no na njih se sada nećemo fokusirati. - -\section{Rad sa fajlovima} - -\subsection{Modul FIO} - -U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl -sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto -kao što uvozimo i komande). - -\begin{quote}U primerima se pretpostavlja da je ``f'' tipa \kod{File}, ``str'' niz -znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa \kod{CARDINAL} i ``ch'' -tipa \kod{CHAR}. Dodatna promenljiva ``n'' tipa \kod{INTEGER} služi za -formatiranje slično kao u modulu \kod{InOut}. -\end{quote} - -Promenljiva tipa \kod{File} se mora vezati za neki fajl -jednom od sledećih komandi: -\begin{itemize} -\item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\ -\item \kod{f := Create(str);} -- kreira se fajl za pisanje\\ -\item \kod{f := Append(str);} -- otvara se postojeći fajl za - dopisivanje na kraj -\end{itemize} - -Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo -\kod{Close(f);} - -Procedure za čitanje i pisanje su vrlo slične onima iz modula -\kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava -fajl sa kojim se radi. -\begin{itemize} -\item \kod{RdStr(f,str)} -- učitava ceo red u string str\\ -\item \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\ -\item \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\ -\item \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla -\end{itemize} - -Analogne su i procedure za pisanje različitih tipova u fajl: -\begin{itemize} -\item \kod{WrStr(f,str); WrInt(f,i,n);}\ \kod{WrCard(f,c,n);}\ - \kod{WrChar(f,ch);} -\end{itemize} - - -Prelom reda se eksplicitno upisuje u fajl komandom \kod{WrLn(f);}. - -Da bi odredili da li smo stigli do kraja fajla možemo koristiti -\kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula -FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom -operacijom čitanja stigli do kraja fajla. Ne menja joj se vrednost -pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri -tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri -radu. - -\subsection{Zadatak: ispis sadržaja fajla na ekran} - -Potrebno je sve redove iz fajla učitati i ispisati ih na ekran. - -\begin{lstlisting}[style=codeblock] -MODULE ispis; -FROM FIO IMPORT File, Open, Close, EOF, RdStr; -FROM InOut IMPORT WriteString, WriteLn, ReadString; - -PROCEDURE ispisF(ime: ARRAY OF CHAR); -VAR - f:File; - s : ARRAY[1..100] OF CHAR; -BEGIN - f:=Open(ime); - EOF := FALSE; - WHILE NOT EOF DO - RdStr(f,s); - WriteString(s); - WriteLn; - END; - Close(f); -END ispisF; - -VAR - ime: ARRAY[1..100] OF CHAR; -BEGIN - WriteString("unesite ime fajla:"); - ReadString(ime); - ispisF(ime); -END ispis. -\end{lstlisting} - -\subsection{Zadatak: spisak studenata} - -Napraviti program koji iz fajla učitava podatke o studentima, dodaje -novog studenta u spisak i snima fajl. U fajlu se u svakom redu nalazi -podatak o jednom studentu, redom prezime, ime i godina rođenja, -razdvojeni razmacima. - -\begin{lstlisting}[style=codeblock] -MODULE nizslog; -FROM InOut IMPORT WriteString, WriteLn, - WriteCard, ReadCard, ReadString; -FROM FIO IMPORT File, Open, Create, Close, EOF, - RdItem, RdCard, WrStr, WrCard, WrLn; -FROM Str IMPORT Compare; - -CONST - MaxStud = 100; -TYPE - String = ARRAY[1..30] OF CHAR; - Student = RECORD - ime, prez: String; - god: CARDINAL; - END; - Studenti = ARRAY[1..MaxStud] OF Student; - -PROCEDURE UcitajF(fajl:String; - VAR spisak: Studenti; VAR n:CARDINAL); -VAR - f:File; -BEGIN - n:=0; - f:= Open(fajl); - EOF := FALSE; - WHILE NOT EOF DO - INC(n); - RdItem(f, spisak[n].prez); - RdItem(f, spisak[n].ime); - spisak[n].god := RdCard(f); - END; - Close(f); -END UcitajF; - -PROCEDURE Ispisi(spisak:Studenti; n:CARDINAL); -VAR - i: CARDINAL; -BEGIN - FOR i:=1 TO n DO - WriteString(spisak[i].prez); - WriteString(" "); - WriteString(spisak[i].ime); - WriteString(" "); - WriteCard(spisak[i].god,1); - WriteLn; - END; -END Ispisi; - -PROCEDURE IspisiF(fajl:String; - spisak:Studenti; n:CARDINAL); -VAR - f:File; - i: CARDINAL; -BEGIN - IF (n>0) AND (n<=MaxStud) THEN - f:=Create(fajl); - (* pravimo takav fajl da ne - postoji zadnji prazan red *) - FOR i:=1 TO n-1 DO - WrStr(f,spisak[i].prez); - WrStr(f," "); - WrStr(f,spisak[i].ime); - WrStr(f," "); - WrCard(f,spisak[i].god,1); - WrLn(f); - END; - WrStr(f,spisak[n].prez); - WrStr(f," "); - WrStr(f,spisak[n].ime); - WrStr(f," "); - WrCard(f,spisak[n].god,1); - Close(f); - END; -END IspisiF; - -PROCEDURE NoviStudent(VAR spisak:Studenti; - VAR n:CARDINAL); -VAR - stud,temp:Student; - i:CARDINAL; - dodaj:BOOLEAN; -BEGIN - IF n=br) THEN - (*prazna lista ili na pocetak*) - temp^.veza:=lista; - lista := temp; - ELSE - (*negde u listi*) - tekuci:= lista; - WHILE (tekuci^.veza # NIL) AND - (tekuci^.veza^.info<=br) DO - tekuci:=tekuci^.veza; - END; - temp^.veza := tekuci^.veza; - tekuci^.veza:=temp; - END; -END DodajSort; -\end{lstlisting} - -\subsection{Zadatak: Prikaz osnovih operacija nad listama} - -\begin{lstlisting}[style=codeblock] -MODULE liste2; -FROM InOut IMPORT WriteString, WriteLn, - WriteCard, ReadCard; -FROM IO IMPORT RdKey; -FROM Storage IMPORT ALLOCATE, DEALLOCATE; -TYPE - skupZn = SET OF CHAR; - brojevi = POINTER TO brojSlog; - brojSlog = RECORD - info:CARDINAL; - veza:brojevi; - END; -VAR - lista : brojevi; - menu,prazno:CHAR; - -PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER); -(* dodaje broj pom na pocetak liste *) -VAR - temp:brojevi; -BEGIN - (* kreiramo novi element *) - NEW(temp); - temp^.info := br; - (* treba da pokazuje na ostatak liste *) - temp^.veza := lista; - (* pocetak liste je novi element *) - lista := temp; -END DodajPoc; - -PROCEDURE Unos(VAR lista:brojevi); -(* dodaje n brojeva u listu *) -VAR - n,i,br:CARDINAL; -BEGIN - WriteString('unesite n (broj brojeva): '); - ReadCard(n); - FOR i:= 1 TO n DO - WriteString("unesite broj "); - WriteCard(i,0); - WriteString(": "); - ReadCard(br); - DodajPoc(lista,br); - END; -END Unos; - -(* -- procedure za stampu -- *) - -PROCEDURE Stampaj(lista:brojevi); -(* stampa sadrzaj liste na ekran *) -VAR - temp:brojevi; -BEGIN - WriteLn; - WriteString("Sadrzaj liste:"); - WriteLn; - temp:=lista; - WHILE temp # NIL DO - WriteCard(temp^.info,0); - WriteLn; - temp := temp^.veza; - END; -END Stampaj; - -PROCEDURE StampajK(VAR lista:brojevi); -(* stampa k-ti element (k unosi korisnik) *) -VAR - temp:brojevi; - k,brojac:CARDINAL; -BEGIN - WriteString("unesite redni broj elementa:"); - ReadCard(k); - temp:=lista; - brojac := 1; - WHILE (temp# NIL) AND (k>brojac) DO - temp:=temp^.veza; - INC(brojac); - END; - IF (temp#NIL) THEN - WriteCard(temp^.info,2); - ELSE - WriteString("greska! - ne postoji element"); - WriteString(" u listi sa rednim brojem "); - WriteCard(k,2); - END; - WriteLn(); -END StampajK; - -PROCEDURE StampajMinimum(VAR lista:brojevi); -(* nalazi i stampa minimalni element liste *) -VAR - temp:brojevi; - min:CARDINAL; -BEGIN - IF (lista=NIL) THEN - WriteString("prazna lista!"); - ELSE - min:=lista^.info; - temp:=lista^.veza; - WHILE temp # NIL DO - IF temp^.info < min THEN - min := temp^.info; - END; - temp := temp^.veza; - END; - WriteString("Minimalni element liste je "); - WriteCard(min,0); - END; - WriteLn; -END StampajMinimum; - -(* -- pomocne procedure, bez ispisa -- *) - -PROCEDURE UListi(lista:brojevi; - br: CARDINAL):BOOLEAN; -(* vraca da li se 'br' nalazi u listi 'lista' *) -VAR - temp:brojevi; -BEGIN - temp:=lista; - WHILE (temp # NIL) AND (temp^.info # br) DO - (* dok ne dodjemo do kraja liste - ili ne nadjemo broj *) - temp := temp^.veza; - END; - IF temp#NIL THEN - (* znaci da nismo na kraju liste, - tj da je nadjen broj *) - RETURN TRUE; - ELSE (* temp = NIL *) - RETURN FALSE; - END; -END UListi; - -PROCEDURE IzbaciIzListe(VAR lista:brojevi; - br: CARDINAL):BOOLEAN; -(* izbacuje broj 'br' iz liste, naravno ako - postoji i vraca da li je operacija uspesno - obavljena *) -VAR - temp,prethodni:brojevi; -BEGIN - (* proverimo da li je prvi element *) - IF (lista # NIL) AND (lista^.info = br) THEN - temp:=lista; - lista :=lista^.veza; - DISPOSE(temp); - RETURN TRUE; - ELSE - (* trazimo u ostatku liste *) - temp:=lista; - prethodni:=NIL; - WHILE (temp # NIL) AND (temp^.info # br) DO - (* dok ne dodjemo do kraja liste - ili ne nadjemo broj *) - prethodni:=temp; - temp := temp^.veza; - END; - IF temp#NIL THEN - (* znaci da nismo na kraju liste, - odnosno da smo nasli broj *) - (* prevezemo listu oko elementa *) - prethodni^.veza:=temp^.veza; - DISPOSE(temp); - RETURN TRUE; - ELSE - RETURN FALSE; - END; - END; -END IzbaciIzListe; - -PROCEDURE IzbaciIzListeSve(VAR lista:brojevi; - br: CARDINAL):CARDINAL; -(* izbacuje sve brojeve 'br' iz liste, naravno ako - postoje i vraca koliko ih je bilo *) -VAR - temp,prethodni:brojevi; - brojac : CARDINAL; -BEGIN - brojac := 0; - (* uklanjamo sa pocetka koliko je potrebno *) - WHILE (lista # NIL) AND (lista^.info = br) DO - temp:=lista; - lista :=lista^.veza; - DISPOSE(temp); - INC(brojac); - END; - (* trazimo u ostatku liste *) - IF (lista # NIL) THEN - temp:=lista; - WHILE (temp^.veza # NIL) DO - (* idemo do poslednjeg elementa liste *) - prethodni:=temp; - temp := temp^.veza; - IF temp^.info = br THEN - (* prevezemo listu oko elementa *) - prethodni^.veza:=temp^.veza; - DISPOSE(temp); - INC(brojac); - (* vracamo se jedan korak da bi - u novom krugu proverili i ovaj element *) - temp := prethodni; - END; - END; - END; - RETURN brojac; -END IzbaciIzListeSve; - -(* - procedure sa interakcijom sa korisnikom - *) - -PROCEDURE IzbacivanjeEl(VAR lista:brojevi); -(* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *) -VAR - br:CARDINAL; -BEGIN - WriteString("unesite broj za izbacivanje: "); - ReadCard(br); - IF IzbaciIzListe(lista,br) THEN - WriteString("broj je izbacen iz liste"); - ELSE - WriteString("greska! - broj ne postoji"); - END; - WriteLn; -END IzbacivanjeEl; - -PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi); -(* izbacuje sve primeke unetog broj iz liste - koristeci proceduru IzbaciIzListeSve *) -VAR - br, ukupno:CARDINAL; -BEGIN - WriteString("unesite broj za izbacivanje: "); - ReadCard(br); - ukupno := IzbaciIzListeSve(lista,br); - WriteString("Iz liste je izbaceno "); - WriteCard(ukupno,3); - WriteString(" el."); - WriteLn; -END IzbacivanjeElSvi; - -PROCEDURE IzbacivanjeK(VAR lista:brojevi); -(* izbacuje k-ti element iz liste *) -VAR - temp,tekuci:brojevi; - k,brojac:CARDINAL; -BEGIN - IF lista=NIL THEN - WriteString("lista je prazna, nema "); - WriteString("elemenata za izbacivanje"); - ELSE - WriteString("unesite redni broj elementa"); - WriteString(" koji zelite izbaciti:"); - ReadCard(k); - IF k=1 THEN (*izbacivanje prvog *) - temp:=lista; - lista := lista^.veza; - DISPOSE(temp); - ELSE - tekuci := lista; - brojac := 2; (*gledamo jedan unapred*) - WHILE (tekuci^.veza# NIL) AND (k>brojac) DO - (* idemo kroz listu do k-tog el *) - tekuci:=tekuci^.veza; - INC(brojac); - END; - IF (tekuci^.veza#NIL) THEN - (* pamtimo element za brisanje *) - temp:=tekuci^.veza; - (* prevezujemo listu oko njega*) - tekuci^.veza:=tekuci^.veza^.veza; - DISPOSE(temp); - ELSE - WriteString("greska! - ne postoji el "); - WriteString("u listi sa rednim brojem "); - WriteCard(k,2); - END; - WriteLn(); - END; - END; -END IzbacivanjeK; - -PROCEDURE Pretraga(lista:brojevi); -(* provera da li se uneti broj nalazi u listi *) -VAR - br:CARDINAL; -BEGIN - WriteString("unesite trazeni broj"); - ReadCard(br); - IF UListi(lista,br) THEN - WriteString("broj postoji u listi"); - ELSE - WriteString("broj ne postoji u listi"); - END; - WriteLn; -END Pretraga; - -(* -- oslobadjanje memorije -- *) - -PROCEDURE Unisti(VAR lista:brojevi); -VAR - temp:brojevi; -BEGIN - temp:=lista; - WHILE temp # NIL DO - lista:=lista^.veza; - DISPOSE(temp); - temp:=lista; - END; -END Unisti; - -BEGIN - (* pocinjemo od prazne liste *) - lista := NIL; - REPEAT - WriteLn; - WriteString("Ilustracija rada sa"); - WriteString(" listama brojeva"); - WriteLn; - WriteString("============================="); - WriteLn; - WriteString("s - Stampa");WriteLn; - WriteString("u - Unos");WriteLn; - WriteString("i - Izbacivanje br iz liste"); - WriteLn; - WriteString("v - izbacivanje svih br iz liste"); - WriteLn; - WriteString("e - izbacivanje k-tog El."); - WriteLn; - WriteString("k - stampanje k-tog elementa"); - WriteLn; - WriteString("m - Minimalni broj u listi"); - WriteLn; - WriteString("p - Pretraga el. u listi"); - WriteLn; - WriteLn; - WriteString("q - kraj rada (Quit)");WriteLn; - REPEAT - menu := CAP(RdKey()); - UNTIL menu IN skupZn{'S','U','E','I','V', - 'M','K','P','Q'}; - IF menu#'Q' THEN - CASE menu OF - 'S' : Stampaj(lista);| - 'U' : Unos(lista);| - 'I' : IzbacivanjeEl(lista);| - 'V' : IzbacivanjeElSvi(lista);| - 'E' : IzbacivanjeK(lista);| - 'K' : StampajK(lista); | - 'M' : StampajMinimum(lista); | - 'P' : Pretraga(lista);| - END; - WriteLn; - WriteString("--- pritisnite bilo koji "); - WriteString("taster za povratak u meni"); - prazno:=RdKey(); - ELSE - WriteString("Kraj rada") - END; - WriteLn; - UNTIL menu='Q'; - Unisti(lista); -END liste2. -\end{lstlisting} - - -\subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem} - -\begin{lstlisting}[style=codeblock] -MODULE Radnici; - -FROM InOut IMPORT WriteString, ReadString, - WriteLn, WriteCard, ReadCard, Done; -FROM IO IMPORT RdKey; -FROM Storage IMPORT ALLOCATE, DEALLOCATE; - -TYPE - skupZn = SET OF CHAR; - str = ARRAY [1..20] OF CHAR; - radnici = POINTER TO slog; - slog = RECORD - ime, prez : str; - broj : CARDINAL; - sled : radnici - END; -VAR - meni, pom : CHAR; - rad : radnici; - - PROCEDURE Clear(); - VAR - br: CARDINAL; - BEGIN - FOR br:=1 TO 100 DO - WriteLn; - END; - END Clear; - - PROCEDURE Spisak(rad : radnici); - BEGIN - WHILE rad # NIL DO - WriteString(rad^.ime); - WriteString(' '); - WriteString(rad^.prez); - WriteCard(rad^.broj, 8); - WriteLn; - rad := rad^.sled - END - END Spisak; - - PROCEDURE Zaposli(VAR rad : radnici); - VAR - novi, tek : radnici; - nadjen : BOOLEAN; - BEGIN - NEW(novi); - REPEAT - WriteString('Ime, prezime i jedinstveni'); - WriteString(' broj novog radnika: '); - WriteLn; - ReadString(novi^.ime); - ReadString(novi^.prez); - ReadCard(novi^.broj); - nadjen := FALSE; - tek := rad; - WHILE NOT nadjen AND (tek # NIL) AND - (tek^.broj <= novi^.broj) DO - IF novi^.broj = tek^.broj THEN - nadjen := TRUE - ELSE - tek := tek^.sled - END - END - UNTIL Done AND NOT nadjen; - IF (rad = NIL) OR (novi^.broj br) THEN - WriteString('Greska.') - ELSE - pom := tek^.sled; - tek^.sled := tek^.sled^.sled; - DISPOSE(pom) - END - END - END Otpusti; - - PROCEDURE Inform(rad : radnici); - VAR - br : CARDINAL; - BEGIN - REPEAT - WriteLn; - WriteString('Unesite redni broj radnika:'); - ReadCard(br) - UNTIL Done; - WriteLn; - WHILE (rad # NIL) AND (rad^.broj < br) DO - rad := rad^.sled - END; - IF (rad = NIL) OR (rad^.broj # br) THEN - WriteString('Greska.') - ELSE - WriteString(rad^.ime); - WriteString(' '); - WriteString(rad^.prez) - END - END Inform; - - PROCEDURE Bankrot(VAR rad : radnici); - VAR - pom : radnici; - BEGIN - WHILE rad # NIL DO - pom := rad; - rad := rad^.sled; - DISPOSE(pom) - END - END Bankrot; - -BEGIN - rad := NIL; - REPEAT - Clear; - WriteString('s - spisak svih zaposlenih'); - WriteLn; - WriteString('z - zaposljavanje radnika'); - WriteLn; - WriteString('o - otpustanje radnika'); - WriteLn; - WriteString('i - informacije o radniku'); - WriteLn; - WriteString('b - bankrot firme'); - WriteLn; - WriteString('k - kraj rada'); - WriteLn; - REPEAT - meni := RdKey(); - UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O', - 'I', 'B', 'K'}; - Clear; - IF CAP(meni) # 'K' THEN - CASE CAP(meni) OF - 'S' : Spisak(rad)| - 'Z' : Zaposli(rad)| - 'O' : Otpusti(rad)| - 'I' : Inform(rad)| - 'B' : Bankrot(rad) - END; - WriteLn; - WriteString('-- pritisnite bilo koji '); - WriteString('taster za nastavak --'); - pom := RdKey() - END - UNTIL CAP(meni) = 'K' -END Radnici. -\end{lstlisting} - -Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji: - -\begin{lstlisting}[style=codeblock] - PROCEDURE Spisak(rad : radnici); - BEGIN - IF rad # NIL THEN - WriteString(rad^.ime); - WriteString(' '); - WriteString(rad^.prez); - WriteCard(rad^.broj, 8); - WriteLn; - Spisak(rad^.sled) - END - END Spisak; -\end{lstlisting} - -\subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve - liste osoba koje dele sadržaj, jedna sortirana po visini, druga po - težini} - -Sa tastature učitavati po dva broja koji opisuju osobu (visina i -težina) i smeštati ih u povezane listu, tako da postoji neopadajuće -uređenje i po visini i po težini. - -\begin{lstlisting}[style=codeblock] -MODULE VisTez; -FROM Storage IMPORT ALLOCATE, DEALLOCATE; -FROM IO IMPORT WrLn, WrStr, RdCard, WrCard; -FROM SYSTEM IMPORT TSIZE; -TYPE - pok = POINTER TO element; - element = RECORD - visina, tezina : CARDINAL; - Vveza, Tveza : pok - END; -VAR - pocV, pocT : pok; - vis, tez : CARDINAL; -PROCEDURE Ispisi(pocV, pocT : pok); -VAR - tek : pok; -BEGIN - tek := pocV; - WrStr('Po visini:'); - WrLn; - WHILE tek # NIL DO - WrCard(tek^.visina, 6); - tek := tek^.Vveza - END; - WrLn; - tek := pocT; - WrStr('Po tezini:'); - WrLn; - WHILE tek # NIL DO - WrCard(tek^.tezina,6); - tek := tek^.Tveza - END -END Ispisi; - -PROCEDURE Ubaci(VAR pocV, pocT : pok; - vis, tez : CARDINAL); -VAR - novi, tek, iza : pok; - nadjen : BOOLEAN; -BEGIN - IF pocV = NIL THEN - ALLOCATE(pocV, TSIZE(element)); - pocV^.visina := vis; - pocV^.tezina := tez; - pocV^.Vveza := NIL; - pocV^.Tveza := NIL; - pocT := pocV - ELSE - ALLOCATE(novi, TSIZE(element)); - novi^.visina := vis; - novi^.tezina := tez; - tek := pocV; - nadjen := FALSE; - WHILE (tek # NIL) AND NOT nadjen DO - nadjen := vis <= tek^.visina; - IF NOT nadjen THEN - iza := tek; - tek := tek^.Vveza - END - END; - novi^.Vveza := tek; - IF tek = pocV THEN - pocV := novi - ELSE - iza^.Vveza := novi - END; - tek := pocT; - nadjen := FALSE; - WHILE (tek # NIL) AND NOT nadjen DO - nadjen := tez <= tek^.tezina; - IF NOT nadjen THEN - iza := tek; - tek := tek^.Tveza - END - END; - novi^.Tveza := tek; - IF tek = pocT THEN - pocT := novi - ELSE - iza^.Tveza := novi - END - END -END Ubaci; - -BEGIN - pocV := NIL; - pocT := NIL; - WrStr('Unesite visinu ---- '); - vis := RdCard(); - WHILE vis > 0 DO - WrStr('Unesite tezinu ---- '); - tez := RdCard(); - Ubaci(pocV, pocT, vis, tez); - WrLn; - WrStr('Unesite visinu ---- '); - vis := RdCard() - END; - WrLn; - Ispisi(pocV, pocT) -END VisTez. -\end{lstlisting} - -\section{Polinomi preko listi} - -\subsection{Moduli} - -Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka -\kod{Polinom} je definisan u globalnom modulu. - -\paragraph{PolinomL.DEF} \ - -\begin{lstlisting}[style=codeblock] -DEFINITION MODULE PolinomL; -TYPE - Polinom = POINTER TO Monom; - Monom = RECORD - k : REAL; - st : CARDINAL; - veza : Polinom - END; - -PROCEDURE Anuliraj(VAR p: Polinom); -PROCEDURE Unos(VAR p: Polinom); -PROCEDURE Stampaj(p: Polinom; d: CARDINAL); -PROCEDURE Kopiraj(p: Polinom; - VAR kopija: Polinom); -PROCEDURE UbaciMonom(mon:Polinom; - VAR p: Polinom); -PROCEDURE PromeniZnak(VAR p: Polinom); -PROCEDURE Saberi(p1, p2: Polinom; - VAR zbir: Polinom); -PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom); -PROCEDURE Oduzmi(p1,p2: Polinom; - VAR razlika: Polinom); -PROCEDURE MonomPuta(p, mon: Polinom; - VAR mp : Polinom); -PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom); -PROCEDURE Kolicnik(p1, p2: Polinom; - VAR kol, ost: Polinom; - VAR ok : BOOLEAN); -PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL; - VAR rez: Polinom); -PROCEDURE DisposePolinom(VAR p: Polinom); - -END PolinomL. -\end{lstlisting} - -\paragraph{PolinomL.MOD} \ - -\begin{codeblock} -(* Modul za rad sa polinomima preko listi - verzija 2012, rev 1 *) -IMPLEMENTATION MODULE PolinomL; -FROM InOut IMPORT Write, WriteString, WriteLn, - WriteCard, ReadCard, Done; -FROM RealInOut IMPORT WriteReal, ReadReal; -FROM Storage IMPORT ALLOCATE, DEALLOCATE; - -PROCEDURE Anuliraj(VAR p: Polinom); -BEGIN - p := NIL; -END Anuliraj; - -PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom); -VAR - pomocni: Polinom; -BEGIN - IF p = NIL THEN - kopija := NIL - ELSE - NEW(kopija); - kopija^ := p^; - p := p^.veza; - pomocni := kopija; - WHILE p <> NIL DO - NEW(pomocni^.veza); - pomocni := pomocni^.veza; - pomocni^ := p^; - p := p^.veza - END - END -END Kopiraj; - -PROCEDURE Stampaj(p: Polinom; d: CARDINAL); - - PROCEDURE StampajMonom(m : Polinom); - BEGIN - WITH m^ DO - IF st <> 0 THEN - IF ABS(k) <> 1.0 THEN - WriteReal(ABS(k), d) - END; - Write('x'); - IF st <> 1 THEN - Write('^'); - WriteCard(st, 1) - END - ELSE - WriteReal(ABS(k), d) - END - END - END StampajMonom; - -BEGIN - IF p = NIL THEN - WriteReal(0., d) - ELSE - IF p^.k < 0.0 THEN - WriteString(' - ') - END; - StampajMonom(p); - p := p^.veza; - WHILE p <> NIL DO - IF p^.k > 0.0 THEN - WriteString(' + ') - ELSE - WriteString(' - ') - END; - StampajMonom(p); - p := p^.veza - END - END -END Stampaj; - -PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom); -VAR - stari, tekuci, kopija: Polinom; -BEGIN - IF mon # NIL THEN - NEW(kopija); - kopija^ := mon^; - tekuci := p; - stari := NIL; - WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO - stari := tekuci; - tekuci := tekuci^.veza - END; - kopija^.veza := tekuci; - IF tekuci = p THEN - p := kopija - ELSE - stari^.veza := kopija - END; - IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN - kopija^.k := kopija^.k + tekuci^.k; - kopija^.veza := tekuci^.veza; - DISPOSE(tekuci); - IF kopija^.k = 0.0 THEN - IF p = kopija THEN - p := kopija^.veza - ELSE - stari^.veza := kopija^.veza - END; - DISPOSE(kopija) - END - END - END -END UbaciMonom; - -PROCEDURE Unos(VAR p : Polinom); -VAR - i, n: CARDINAL; - novi: Polinom; -BEGIN - Anuliraj(p); - REPEAT - WriteLn; - WriteString('Unesite broj monoma n (n>=0) '); - ReadCard(n); - UNTIL Done; - WriteLn; - FOR i := 1 TO n DO - NEW(novi); - WITH novi^ DO - REPEAT - WriteString('Unesite koeficijent monoma br.'); - WriteCard(i, 1); - WriteString(' (<> 0) '); - ReadReal(k); - WriteLn - UNTIL k <> 0.0; - REPEAT - WriteLn; - WriteString('Unesite eksponent monoma br.'); - WriteCard(i, 1); - WriteString(' (>=0) '); - ReadCard(st); - UNTIL Done; - WriteLn; - END; - UbaciMonom(novi, p); - DISPOSE(novi); - END -END Unos; - -PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom); -BEGIN - Kopiraj(p1, zbir); - WHILE p2 <> NIL DO - UbaciMonom(p2, zbir); - p2 := p2^.veza - END -END Saberi; - -PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom); -BEGIN - WHILE p <> NIL DO - UbaciMonom(p,rez); - p := p^.veza; - END; -END SaberiNa; - -PROCEDURE PromeniZnak(VAR p: Polinom); -VAR - t: Polinom; -BEGIN - t := p; - WHILE t <> NIL DO - t^.k := - t^.k; - t := t^.veza - END -END PromeniZnak; - -PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom); -BEGIN - Kopiraj(p2, razlika); - PromeniZnak(razlika); - WHILE p1 <> NIL DO - UbaciMonom(p1, razlika); - p1 := p1^.veza - END -END Oduzmi; - -PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom); -VAR - tekuci: Polinom; -BEGIN - Anuliraj(mp); - IF (mon <> NIL) AND (p <> NIL) THEN - NEW(mp); - mp^.k := p^.k * mon^.k; - mp^.st := p^.st + mon^.st; - p := p^.veza; - tekuci := mp; - WHILE p <> NIL DO - NEW(tekuci^.veza); - tekuci := tekuci^.veza; - tekuci^.k := p^.k * mon^.k; - tekuci^.st := p^.st + mon^.st; - p := p^.veza - END; - tekuci^.veza := NIL - END -END MonomPuta; - -PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom); -VAR - pomocni: Polinom; -BEGIN - Anuliraj(pr); - IF (p1 <> NIL) AND (p2 <> NIL) THEN - MonomPuta(p1, p2, pr); - p2 := p2^.veza; - WHILE p2 <> NIL DO - MonomPuta(p1, p2, pomocni); - REPEAT - UbaciMonom(pomocni, pr); - pomocni := pomocni^.veza - UNTIL pomocni = NIL; - p2 := p2^.veza - END - END -END Puta; - -PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN); - - PROCEDURE Deli(VAR kol, ost: Polinom); - VAR - novi, pomocni: Polinom; - BEGIN - IF ost <> NIL THEN - IF ost^.st >= p2^.st THEN - NEW(novi); - novi^.k := - ost^.k / p2^.k; - novi^.st := ost^.st - p2^.st; - MonomPuta(p2, novi, pomocni); - Saberi(ost, pomocni, ost); - novi^.k := - novi^.k; - UbaciMonom(novi, kol); - DISPOSE(novi); - Deli(kol, ost) - END - END - END Deli; - -BEGIN (* Kolicnik *) - ok := TRUE; - Anuliraj(kol); - IF p2 = NIL THEN - ok := FALSE - ELSE - Kopiraj(p1, ost); - Deli(kol, ost) - END -END Kolicnik; - -PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL; - VAR rez: Polinom); -VAR - i: CARDINAL; -BEGIN - IF n = 0 THEN - NEW(rez); - rez^.k := 1.0; - rez^.st := 0; - rez^.veza := NIL; - ELSIF n = 1 THEN - Kopiraj( p, rez ); - ELSE - rez := p; - FOR i := 2 TO n DO - Puta(rez, p, rez) - END - END; -END PolinomNaN; - -PROCEDURE DisposePolinom(VAR p: Polinom); -VAR - pomocni: Polinom; -BEGIN - pomocni := p; - WHILE pomocni # NIL DO - p := p^.veza; - DISPOSE(pomocni); - pomocni := p - END -END DisposePolinom; - -END PolinomL. -\end{codeblock} - - -\subsection{Zadatak: Sabiranje sa unapred određenim polinomom} - -Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$. - -\begin{lstlisting}[style=codeblock] -MODULE polinom; -FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj, DisposePolinom, UbaciMonom, Unos, Saberi; -FROM InOut IMPORT WriteString, WriteLn; -FROM Storage IMPORT ALLOCATE, DEALLOCATE; - -VAR - p,q,rez,pom : Polinom; - -BEGIN - (* korisnik unosi prvi polinom *) - WriteString("Unesite polinom:"); - WriteLn; - Unos(p); - (* drugi polinom kreiramo mi, - monom po monom *) - Anuliraj(q); (* isto sto i q:=NIL; *) - (* formiramo monom x^5 *) - NEW(pom); - pom^.st:=5; - pom^.k:=1.0; - (* dodajemo ga u polinom *) - UbaciMonom(pom,q); - DISPOSE(pom); - (* -3 x^4 *) - NEW(pom); - pom^.st := 4; - pom^.k := -3.0; - UbaciMonom(pom,q); - DISPOSE(pom); - (* 4 x *) - NEW(pom); - pom^.st := 1; - pom^.k := 4.0; - UbaciMonom(pom,q); - DISPOSE(pom); - (* 7 (x^0) *) - NEW(pom); - pom^.st := 0; - pom^.k := 7.0; - UbaciMonom(pom,q); - DISPOSE(pom); - (* saberemo polinome *) - Saberi(p, q, rez); - (* odstampamo rezultat *) - Stampaj(rez,0); - WriteLn; - (* oslobadjanje zauzete memorije *) - DisposePolinom(p); - DisposePolinom(q); - DisposePolinom(rez); -END polinom. -\end{lstlisting} - -\subsection{Zadatak: Suma k polinoma} - -Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon -toga izracunava njihovu sumu - -\begin{lstlisting}[style=codeblock] -MODULE PolSuma; - -FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom, Unos, Stampaj, SaberiNa; -FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard; -CONST - maxk = 50; -TYPE - nizPol = ARRAY [1..maxk] OF Polinom; -VAR - i, k: CARDINAL; - suma : Polinom; - p : nizPol; -BEGIN - REPEAT - WriteString('Unesite broj k (1 <= k <= '); - WriteCard(maxk, 1); - WriteString(') '); - ReadCard(k); - WriteLn; - UNTIL (1 <= k) AND (k <= maxk); - FOR i := 1 TO k DO - WriteLn; - WriteString('Unos '); - WriteCard(i, 1); - WriteString('. polinoma.'); - WriteLn; - Unos(p[i]) - END; - Anuliraj(suma); - FOR i := 1 TO k DO - SaberiNa(suma, p[i]) - END; - WriteLn; - WriteString('Njihova suma je:'); - WriteLn; - Stampaj(suma, 4); - DisposePolinom(suma); - FOR i := 1 TO k DO - DisposePolinom(p[i]); - END; -END PolSuma. -\end{lstlisting} - -\section{Stek i red opsluživanja} - -\subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera} - -\begin{lstlisting}[style=codeblock] -DEFINITION MODULE QueueInfo; -CONST - Maxqueue = 100; -TYPE - InfoTip = CHAR; - -END QueueInfo. - -IMPLEMENTATION MODULE QueueInfo; -END QueueInfo. - -DEFINITION MODULE RedOpsl1; -FROM QueueInfo IMPORT InfoTip,Maxqueue; -TYPE - Niz = ARRAY[1..Maxqueue] OF InfoTip; - RedOpslTip = RECORD - Prvi, Zadnji : CARDINAL; - Element : Niz - END; - -PROCEDURE MakeNull(VAR q : RedOpslTip); -PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN; -PROCEDURE First(VAR q : RedOpslTip; - VAR x : InfoTip; - VAR ok : BOOLEAN); -PROCEDURE PopFirst(VAR q : RedOpslTip; - VAR ok : BOOLEAN); -PROCEDURE AddRear(VAR q : RedOpslTip; - x : InfoTip; - VAR ok : BOOLEAN); - -END RedOpsl1. - -IMPLEMENTATION MODULE RedOpsl1; -FROM QueueInfo IMPORT Maxqueue,InfoTip; - -PROCEDURE MakeNull(VAR q : RedOpslTip); -BEGIN - WITH q DO - Prvi := 0; - Zadnji := 0 - END -END MakeNull; - -PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN; -BEGIN - RETURN q.Zadnji = 0 -END Empty; - - -PROCEDURE First(VAR q : RedOpslTip; - VAR x : InfoTip; - VAR ok : BOOLEAN); -BEGIN - IF Empty(q) THEN - ok := FALSE - ELSE - ok := TRUE; - WITH q DO - x := Element[Prvi] - END - END -END First; - -PROCEDURE AddOne(i : CARDINAL) : CARDINAL; -BEGIN - IF i = Maxqueue THEN - RETURN 1 - ELSE - RETURN i+1 - END -END AddOne; - -PROCEDURE PopFirst(VAR q : RedOpslTip; - VAR ok : BOOLEAN); -BEGIN - IF Empty(q) THEN - ok := FALSE - ELSE - ok := TRUE; - WITH q DO - IF Prvi = Zadnji THEN - MakeNull(q) - ELSE - Prvi := AddOne(Prvi) - END - END - END -END PopFirst; - -PROCEDURE AddRear(VAR q : RedOpslTip; - x : InfoTip; - VAR ok : BOOLEAN); -BEGIN - WITH q DO - IF AddOne(Zadnji) = Prvi THEN - ok := FALSE - ELSE - ok := TRUE; - IF Empty(q) THEN - Prvi := 1; - Zadnji := 1 - ELSE - Zadnji := AddOne(Zadnji) - END; - Element[Zadnji] := x - END - END -END AddRear; - -END RedOpsl1. - -MODULE Bafer; -FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear; -FROM FIO IMPORT File,WrChar, Create, Close; -IMPORT IO; - -CONST - ImeIzlaza = 'izlaz.txt'; - -VAR - izlaz : File; - znak : CHAR; - buffer : RedOpslTip; - -PROCEDURE IsprazniBafer(VAR dat : File; - VAR buf : RedOpslTip); -VAR - znak : CHAR; - ok : BOOLEAN; -BEGIN - WHILE NOT Empty(buf) DO - First(buf, znak, ok); - PopFirst(buf, ok); - WrChar(dat, znak) - END -END IsprazniBafer; - -PROCEDURE BaferWrite(VAR dat : File; - VAR buf : RedOpslTip; - znak : CHAR); -VAR - ok : BOOLEAN; -BEGIN - AddRear(buf, znak, ok); - IF NOT ok THEN - IsprazniBafer(dat, buf); - AddRear(buf, znak, ok) - END -END BaferWrite; - -BEGIN - izlaz := Create(ImeIzlaza); - MakeNull(buffer); - IO.WrStr('Unesite tekst, koji treba da se unese u datoteku '); - IO.WrStr(ImeIzlaza); - IO.WrChar('.'); - IO.WrLn; - IO.WrStr('Unos zavrsite tackom.'); - IO.WrLn; - znak := IO.RdChar(); - WHILE znak # '.' DO - BaferWrite(izlaz, buffer, znak); - znak := IO.RdChar(); - END; - IsprazniBafer(izlaz, buffer); - Close(izlaz) -END Bafer. -\end{lstlisting} - -\subsection% -{Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$} - -Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od -slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w. - -\begin{lstlisting}[style=codeblock] -DEFINITION MODULE Stek; -CONST - Maxstack = 100; -TYPE - Niz = ARRAY [1..Maxstack] OF CHAR; - StekTip = RECORD - Top : CARDINAL; - Element : Niz - END; -PROCEDURE MakeNull(VAR s : StekTip); -PROCEDURE Empty(VAR s : StekTip) : BOOLEAN; - -PROCEDURE Top(VAR s : StekTip; - VAR x : CHAR; - VAR ok : BOOLEAN); -PROCEDURE Pop(VAR s : StekTip; - VAR ok : BOOLEAN); -PROCEDURE Push(VAR s : StekTip; - x : CHAR; - VAR ok : BOOLEAN); -END Stek. - - -IMPLEMENTATION MODULE Stek; - -PROCEDURE MakeNull(VAR s : StekTip); -BEGIN - s.Top := 0 -END MakeNull; - -PROCEDURE Empty(VAR s : StekTip) : BOOLEAN; -BEGIN - RETURN s.Top = 0 -END Empty; - -PROCEDURE Top(VAR s : StekTip; - VAR x : CHAR; - VAR ok : BOOLEAN); -BEGIN - IF Empty(s) THEN - ok := FALSE - ELSE - ok := TRUE; - WITH s DO - x := Element[Top] - END - END -END Top; - -PROCEDURE Pop(VAR s : StekTip; - VAR ok : BOOLEAN); -BEGIN - IF Empty(s) THEN - ok := FALSE - ELSE - ok := TRUE; - DEC(s.Top) - END -END Pop; - -PROCEDURE Push(VAR s : StekTip; - x : CHAR; - VAR ok : BOOLEAN); -BEGIN - WITH s DO - IF Top = Maxstack THEN - ok := FALSE - ELSE - ok := TRUE; - INC(Top); - Element[Top] := x - END - END -END Push; -END Stek. - -MODULE wcw; -(* Da li rec pripada gramatici wcw+. *) -FROM Stek IMPORT StekTip, MakeNull, Empty, - Top, Pop, Push; -FROM InOut IMPORT Read, Write, WriteString, EOL; -TYPE - slova = SET OF CHAR; -VAR - S : StekTip; - Ch, C : CHAR; - ok : BOOLEAN; -BEGIN - MakeNull(S); - Read(Ch); - ok := TRUE; - WHILE ok AND (Ch IN slova{'a', 'b'}) DO - Push(S, Ch, ok); - Read(Ch); - END; - IF NOT ok THEN - WriteString('Greska - mali stek') - ELSIF Ch # 'c' THEN - WriteString('Pogresan string') - ELSE - Read(Ch); - WHILE ok AND (Ch # EOL) DO - Top(S, C, ok); - ok := ok AND (C = Ch); - IF ok THEN - Pop(S, ok); - Read(Ch); - END - END; - IF NOT (ok AND Empty(S)) THEN - WriteString('Pogresan string') - ELSE - WriteString('String pripada jeziku L') - END - END -END wcw. -\end{lstlisting} - -\subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza} - - -Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi -koji figurišu u izrazu su jednocifreni. - -\begin{lstlisting}[style=codeblock] -MODULE PostFix; - -FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push; -FROM InOut IMPORT Read, Write, WriteInt, EOL; -TYPE - slova = SET OF CHAR; -VAR - S : StekTip; - Ch : CHAR; - Op1, Op2 : INTEGER; - ok : BOOLEAN; -PROCEDURE Conv(Ch : CHAR) : INTEGER; -BEGIN - RETURN ORD(Ch) - ORD('0') -END Conv; - -BEGIN - MakeNull(S); - Read(Ch); - WHILE Ch # EOL DO - IF Ch IN slova{'+', '-', '/', '*', '%'} THEN - Top(S, Op2, ok); - Pop(S, ok); - Top(S, Op1, ok); - Pop(S, ok); - CASE Ch OF - '+' : Op1 := Op1 + Op2 | - '-' : Op1 := Op1 - Op2 | - '*' : Op1 := Op1 * Op2 | - '/' : Op1 := Op1 DIV Op2 | - '%' : Op1 := Op1 MOD Op2 - END; - Push(S, Op1, ok) - ELSE - Push(S, Conv(Ch), ok) - END; - Read(Ch); - END; - Top(S, Op1, ok); - Write('='); - WriteInt(Op1,5) -END PostFix. -\end{lstlisting} - - -\section{Simulacija rekurzije} - - -Na početku označiti sve rekurzivne pozive u originalnoj proceduri -adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka). - -Na steku se čuvaju lokalne promenljive, parametri procedure i adresa -mesta poziva, a u skladu sa tim se kreira InfoTip. - -Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih -rekurzivnih poziva. - -U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan, -odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni -pozivi. - -\begin{lstlisting} -MakeNull(S); -REPEAT - WHILE treba_rekurzija DO - -prepisati sve od pocetka originalne - procedure do prvog rekurzivnog poziva - -staviti na stek potrebne - lokalne promenljive, parametre procedure i - adresu mesta poziva - -podesiti vrednosti parametara da budu - kao u rekurzivnom pozivu procedure - END; - trivijalan poziv - umesto RETURN x pisati rez := x - jos := TRUE; - WHILE jos AND NOT Empty(S) DO - Top(S, el, ok); - Pop(S, ok); - -restauriramo vrednosti sa steka - -u zavisnosti od adrese poziva nastavimo - prepisivanje originalne procedure sa - tog mesta - -ako se dodje do novog rek. poziva tada: - -sacuvati na steku vrednosti - -podesiti vrednosti parametara da budu - kao u rekurzivnom pozivu procedure - -ici na pocetak koda - (ovo se postize sa jos := FALSE) - -inace - ako se naidje na RETURN x pisati rez := x - END -UNTIL Empty(S); -\end{lstlisting} - -Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}. - -\subsection*{ZADACI} - -Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka: - -\subsection{Primer 1 -- faktorijel} - - -\begin{lstlisting}[style=codeblock] -MODULE Fakto; -(* InfoTip = CARDINAL; *) - -FROM IO IMPORT WrStr, WrLn, WrCard, RdCard; -FROM StekC IMPORT StekTip, MakeNull, Empty, - Top, Pop, Push; -VAR - n : CARDINAL; -PROCEDURE RFakto(n : CARDINAL) : CARDINAL; -BEGIN - IF n <= 1 THEN - RETURN 1 - ELSE - RETURN n * RFakto(n-1) - END -END RFakto; - - -PROCEDURE SFakto(n : CARDINAL) : CARDINAL; -VAR - s : StekTip; - rez : CARDINAL; - OK : BOOLEAN; -BEGIN - MakeNull(s); - WHILE n > 1 DO - Push(s,n,OK); - DEC(n) - END; - rez := 1; - WHILE NOT Empty(s) DO - Top(s, n, OK); - Pop(s, OK); - rez := n * rez - END; - RETURN rez -END SFakto; - -BEGIN - WrStr('n = '); - n := RdCard(); - WrLn - WrStr('n! = '); - WrCard(RFakto(n), 1); - WrStr(' = '); - WrCard(SFakto(n), 1) -END Fakto. -\end{lstlisting} - -\manbreakJK - -\subsection{Primer 2 -- stepenovanje} - -\begin{lstlisting}[style=codeblock] -MODULE Step; -(* InfoTip = RECORD - x : REAL; - n : CARDINAL; - adr : (par, nepar) - END; -*) -FROM IO IMPORT WrStr, WrLn, WrReal, - RdReal, RdCard; -FROM StekStep IMPORT StekTip, MakeNull, Empty, - Top, Pop, Push, InfoTip, AdrTip; -VAR - n : CARDINAL; - x : REAL; - -PROCEDURE Sqr(y : REAL) : REAL; -BEGIN - RETURN y * y -END Sqr; - -PROCEDURE RStep(x : REAL; - n : CARDINAL) : REAL; -BEGIN - IF n = 0 THEN - RETURN 1. - ELSIF ODD(n) THEN - RETURN x * Sqr( RStep(x, n DIV 2) ) - ELSE - RETURN Sqr( RStep(x, n DIV 2) ) - END -END RStep; - -PROCEDURE SStep(x : REAL; - n : CARDINAL ) : REAL; -VAR - s : StekTip; - OK : BOOLEAN; - rez : REAL; - el : InfoTip; -BEGIN - MakeNull(s); - WHILE n > 0 DO - el.x := x; - el.n := n; - IF ODD(n) THEN - el.adr := nepar; - ELSE - el.adr := par - END; - Push(s,el,OK); - n := n DIV 2 - END; - rez := 1.; - WHILE NOT Empty(s) DO - Top(s, el, OK); - Pop(s, OK); - x := el.x; - n := el.n; - IF el.adr = nepar THEN - rez := x * Sqr(rez) - ELSE - rez := Sqr(rez) - END - END; - RETURN rez -END SStep; - -BEGIN - WrStr('x =? '); - x := RdReal(); - WrLn; - WrStr('n =? '); - n := RdCard(); - WrStr('x^n = '); - WrReal(RStep(x, n), 10, 1); - WrStr(' = '); - WrReal(SStep(x, n), 10, 1) -END Step. -\end{lstlisting} - -\subsection{Primer 3 -- Fibonači} - -\begin{lstlisting}[style=codeblock] -MODULE Fib; -(* InfoTip = RECORD - n : CARDINAL; - PrviSab : CARDINAL; - adr : (prvi, drugi) - END; -*) - -FROM IO IMPORT WrStr, WrLn, WrCard, RdCard; -FROM StekFib IMPORT StekTip, MakeNull, Empty, - Top, Pop, Push, InfoTip, AdrTip; -VAR - n : CARDINAL; - -PROCEDURE RFib(n : CARDINAL) : CARDINAL; -BEGIN - IF n <= 1 THEN - RETURN n - ELSE - RETURN RFib(n-1) + RFib(n-2) - END -END RFib; - -PROCEDURE SFib(n : CARDINAL ) : CARDINAL; -VAR - s : StekTip; - OK, jos : BOOLEAN; - rez, PrviSab : CARDINAL; - el : InfoTip; -BEGIN - MakeNull(s); - REPEAT - WHILE n > 1 DO - el.n := n; - el.adr := prvi; - Push(s,el,OK); - DEC(n) - END; - rez := (n); - jos := TRUE; - WHILE (NOT Empty(s)) AND jos DO - Top(s, el, OK); - Pop(s, OK); - n := el.n; - IF el.adr = prvi THEN - PrviSab := rez; - el.n := n; - el.adr := drugi; - el.PrviSab := PrviSab; - Push(s, el, OK); - DEC(n, 2); - jos := FALSE - ELSE - PrviSab := el.PrviSab; - rez := PrviSab + rez - END - END - UNTIL Empty(s); - RETURN rez -END SFib; - -BEGIN - WrStr('n =? '); - n := RdCard(); - WrStr('F(n) = '); - WrCard(RFib(n), 1); - WrStr(' = '); - WrCard(SFib(n), 1) -END Fib. -\end{lstlisting} - -\subsection{Primer 4 -- faktorijel 2} - - -\begin{lstlisting}[style=codeblock] -MODULE Faktor; -(* InfoTip = CARDINAL; *) -FROM IO IMPORT WrStr, WrLn, WrCard, RdCard; -FROM StekC IMPORT StekTip, MakeNull, Empty, - Top, Pop, Push; -VAR - n,rez : CARDINAL; - -PROCEDURE RFakto(n : CARDINAL; - VAR rez : CARDINAL); -BEGIN - IF n = 0 THEN - rez := 1 - ELSE - RFakto(n-1, rez); - rez := n * rez - END -END RFakto; - -PROCEDURE SFakto(n : CARDINAL; - VAR rez : CARDINAL); -VAR - s : StekTip; - OK : BOOLEAN; -BEGIN - MakeNull(s); - WHILE n > 0 DO - Push(s,n,OK); - DEC(n) - END; - rez := 1; - WHILE NOT Empty(s) DO - Top(s, n, OK); - Pop(s, OK); - rez := n * rez - END -END SFakto; - -BEGIN - WrStr('n =? '); - n := RdCard(); - WrLn; - WrStr('n! = '); - RFakto(n, rez); - WrCard(rez, 1); - WrStr(' = '); - SFakto(n, rez); - WrCard(rez, 1) -END Faktor. -\end{lstlisting} - -\subsection{Primer 5 (ispitni)} - - -\begin{lstlisting}[style=codeblock] -MODULE Rek1; -(* InfoTip = RECORD - d, g, m1, m2 : INTEGER; - adr : (prvi, drugi) - END; -*) -FROM Stek1 IMPORT StekTip, adresa, InfoTip, - MakeNull, Empty, Top, Pop, Push; -IMPORT IO; -VAR - X : ARRAY [1..20] OF INTEGER; - -PROCEDURE Max(d, g: INTEGER) : INTEGER; -VAR - m1, m2 : INTEGER; -BEGIN - IF d>g THEN - RETURN MIN(INTEGER) - ELSIF d=g THEN - RETURN X[d] - ELSE - m1 := Max(d, (d+g) DIV 2); - m2 := Max((d+g) DIV 2 +1, g); - IF m1 > m2 THEN - RETURN m1 - ELSE - RETURN m2 - END - END -END Max; - -PROCEDURE SMax(d, g: INTEGER) : INTEGER; -VAR - S : StekTip; - el : InfoTip; - ok, jos : BOOLEAN; - m1, m2, rez : INTEGER; -BEGIN - MakeNull(S); - REPEAT - WHILE dg THEN - rez := MIN(INTEGER) - ELSE (* d=g *) - rez := X[d] - END; - jos := TRUE; - WHILE jos AND NOT Empty(S) DO - Top(S, el, ok); - Pop(S, ok); - d := el.d; - g := el.g; - m1 := el.m1; - IF el.adr = prvi THEN - m1 := rez; - el.m1 := m1; - el.adr := drugi; - Push(S, el, ok); - d := (d+g) DIV 2 + 1; - jos := FALSE - ELSE (*el.adr = drugi*) - m2 := rez; - IF m1 > m2 THEN - rez := m1 - ELSE - rez := m2 - END - END - END - UNTIL Empty(S); - RETURN rez -END SMax; - -BEGIN (* glavni program *) - X[1] := 3; - X[2] := 2; - X[3] := 5; - X[4] := -7; - X[5] := 0; - IO.WrCard(Max(1, 5), 3); - IO.WrLn; - IO.WrCard(SMax(1, 5), 3); - IO.WrLn -END Rek1. -\end{lstlisting} - -\subsection{Primer 6 (ispitni)} - - -\begin{lstlisting}[style=codeblock] -MODULE Rek2; -(* InfoTip = RECORD - x, y, n : CARDINAL; - adr : (prvi, drugi, treci, cetvrti) - END; -*) -FROM Stek2 IMPORT StekTip, adresa, InfoTip, - MakeNull, Empty, Top, Pop, Push; -IMPORT IO; - -PROCEDURE g(x : CARDINAL; y : CARDINAL; - n : CARDINAL) : CARDINAL; -BEGIN - IF n < 3 THEN - RETURN x + y - ELSIF ODD(n) THEN - RETURN g(g(x+1, y, n-2), y, n-3) - ELSE - RETURN g(x, g(x, y+1, n-2), n-3) - END -END g; - -PROCEDURE Sg(x : CARDINAL; y : CARDINAL; - n : CARDINAL) : CARDINAL; -VAR - S : StekTip; - el : InfoTip; - ok, jos : BOOLEAN; - rez : CARDINAL; -BEGIN - MakeNull(S); - REPEAT - WHILE n >= 3 DO - IF ODD(n) THEN - el.x := x; - el.y := y; - el.n := n; - el.adr := prvi; - Push(S, el, ok); - INC(x); - DEC(n, 2) - ELSE - el.x := x; - el.y := y; - el.n := n; - el.adr := treci; - Push(S, el, ok); - INC(y); - DEC(n, 2) - END - END; - rez := x+y; - jos := TRUE; - WHILE jos AND NOT Empty(S) DO - Top(S, el, ok); - Pop(S, ok); - x := el.x; - y := el.y; - n := el.n; - IF el.adr = prvi THEN - el.adr := drugi; - Push(S, el, ok); - x := rez; - DEC(n, 3); - jos := FALSE - ELSIF el.adr = treci THEN - el.adr := cetvrti; - Push(S, el, ok); - y := rez; - DEC(n, 3); - jos := FALSE - END - END - UNTIL Empty(S); - RETURN rez -END Sg; - -BEGIN (* glavni program *) - IO.WrCard(g(2, 3, 10), 3); - IO.WrCard(Sg(2, 3, 10), 3); -END Rek2. -\end{lstlisting} - -%\columnbreak - -\appendix - -\section{Native XDS Modula 2 -- kratko uputstvo} - - -Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows -sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program. - -\subsection*{Dobavljanje instalacije} - - -Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača, -\url{http://www.excelsior-usa.com/}, tačnije na adresi: - -\url{http://www.excelsior-usa.com/xdsdl.html} - -Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste -razumeli i da ćete ga se pridržavati. - -Na stranici koja se potom otvara je potrebno odabrati ``XDS 2.6 beta 2 -for Windows'' i snimiti je na računar. - -\subsection*{Instalacija okruženja} - -Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute - instalacione arhive. - -\emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione - pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim - klikom miša.} - -Pretpostavićemo u daljem tekstu da je program instaliran u -\kod{C:/XDS/} - -\subsection*{Pokretanje okruženja} - -Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao -i grupa sa programom u start meniju. - -Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice, -okruženje se može pokrenuti uz pomoć izvršnog fajla -\kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj -lokaciji). - -\subsection*{Prvi projekat} - -Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo -napraviti projekat za njega, što se radi na sledeći način: - -\begin{itemize} - -\item - Iz menija se odabere Project->New. -\item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde - će se kreirati projekat i ukuca se ime novog projekta. - -\item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko - postoji neki tekst, obrisati ga. - -\item Kliknuti na ``OK'' - -\item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje, - kliknuti na ``OK'' da se on napravi. - -\item Pojavljuje se forma za kucanje programa, ukucati (na primer): - -\begin{minipage}{\columnwidth} -\begin{lstlisting}[style=codeblock] - MODULE Hello; - FROM InOut IMPORT WriteString,WriteLn; - BEGIN - WriteString("Hello World"); - WriteLn; - END Hello. -\end{lstlisting} -\end{minipage} - -\item Program se može pokrenuti na različite načine, pri čemu se - automatski prevodi: - - \begin{itemize} - - \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči) - - \item Meni Debug->Run - - \item Prečica Ctrl+F9 na tastaturi - - \end{itemize} - -\item Ako je sve u redu sa programom, treba da se pojavi novi terminal - u kome se ispisuje rezultat izvršavanja programa, u našem slučaju - jednostavna pozdravna poruka. -\end{itemize} - -Naravno moguće je i samo prevesti (kompajlirati) program, tako da se -samo prikažu greške (ako ih ima) i bez pokretanja programa: -\begin{itemize} -\item Klik na ``Compile'' ikonicu u toolbaru -\item Meni Tools->Compile -\item Prečica F9 na tastaturi -\end{itemize} - -Ukoliko u programu postoje greške, on neće biti pokrenut, već će se -dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S'' -u četvrtom redu i probamo da pokrenemo program, taj red će biti -označen svetlo plavom bojom i dobićemo poruku: - -\kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"} - -Što znači da u četvrtom redu, kod petog karatkera postoji problem, da -identifikator nije deklarisan, što najčešće znači da ga nismo uvezli, -ili, kao u našem slučaju, da smo napravili grešku u kucanju. - -Stvar na koju isto treba obratiti pažnju je da se nekad greška -prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer, -ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo -program, peti red će biti označen svetlo plavom bojom i dobićemo -poruku: - -\kod{- Error in pro1.mod [5:5]: Expected symbol ";" } - -Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će -kompajler probati da je traži i dalje, pa će tek na početku petog reda -prijaviti grešku. - -U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se -uvezena komanda WriteString ne koristi nigde u programu. Često se -upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na -greške, odnosno poruke koje počinju sa ``Error''. - -Takođe se često dešava da su druge prijavljene greške posledica prve, -te je poželjno ponovo kompajlirati (ili pokretati) program posle svake -ispravljene greške. - -\paragraph{Napomena o template-ovima pri kreiranju projekta:} -Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template'' - uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na - ``Configure'', a potom isprazniti polje ``default template''. - -\subsection{Mogući problemi} - -\subsubsection*{Nedostajući sistemski moduli} - -Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se -koriste u okviru kursa, i bilo je neophodno da se dodatno instalira i -``Top Speed Compatibility Pack'' (tscp-x86...). Bez njega je kompajler -prijavljivao da ne postoje neki moduli - najčešće je problem bio da -nedostaje \kod{FIO} modul. - -\subsubsection*{Problemi u pokretanju - nemoguće naći exe} - -Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi -da ne može da nađe exe i pri tome prijavljuje kraću putanju od one -koja je stvarno u pitanju, obično se radi o tome da je postojao razmak -u okviru putanje do modula. Npr ``C:\textbackslash Moj prvi program'' -će prouzrokovati probleme, a kompajler će prijaviti da ne može da nađe -``C:\textbackslash Moj''. - -Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj -verziji ne može se zaobići, tako da je jedino rešenje premestiti -fajlove, odnosno ako je moguće preimenovati problematične foldere. - -\mainend - -\end{document}