gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control systemdiff --git a/skripta-spa1.tex b/skripta-spa1.tex
--- a/skripta-spa1.tex
+++ b/skripta-spa1.tex
% 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}{April 2012, Novi Sad}
-\newcommand{\verzija}{ver 12b}
-%sc=single-column
+\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}
+}
+
\usepackage[serbian]{babel}
\usepackage{fancyhdr}
\pagestyle{fancy}
%change the default font
\usepackage{lmodern}
+\usepackage{beramono}
\renewcommand{\familydefault}{\sfdefault}
\usepackage{pifont}
}
\lstdefinestyle{codeblock}{
- basicstyle=\footnotesize,
+ basicstyle=\footnotesize\ttfamily,
keywordstyle=\textbf,
columns=[l]fixed,
breakatwhitespace=true,
\lstnewenvironment{codeblock}{\lstset{style=codeblock}}{}
+
% ----------------==================--------------------------------------
% Pravi pocetak rada
Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula
-2' sa instaliranim dodatnim paketom TSCP (Top Speed Compatibility
-Pack), potrebnim za neke od modula koji se ne nalaze u ISO standardu
-Module 2.
+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
-\begin{multicols}{2}
+\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;
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 *)
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
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.
+sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
+kao što uvozimo i komande).
-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
+\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:\\
-\kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\
-\kod{f := Create(str);} -- kreira se fajl za pisanje\\
-\kod{f := Append(str);} -- otvara se postojeći za dopisivanje na kraj
+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}
-\kod{Close(f);} -- po završetku rada fajl se mora zatvoriti
+Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo
+\kod{Close(f);}
-Procedure za čitanje i pisanje imaju parametar „\kod{f}“ koji označava
- fajl sa kojim se radi.\\
-\kod{RdStr(f,str)} -- učitava ceo red u string str\\
-\kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\
-\kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\
-\kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
+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}
-Procedure za pisanje različitih tipova u fajl:
-\kod{WrStr(f,str); WrInt(f,i,n); WrCard(f,c,n);WrChar(f,ch);}
-\kod{WrLn(f);} -- upisuje prelom reda u fajl
+Prelom reda se eksplicitno upisuje u fajl komandom \kod{WrLn(f);}.
-\kod{EOF} -- logička promenljiva, označava da li smo poslednjom
+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}.
-
+tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
+radu.
\subsection{Zadatak: ispis sadržaja fajla na ekran}
\section{Liste i pokazivači}
-Za rad sa pokazivačima je potrebno iz modula Storage uvesti procedure
+Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure
\kod{ALLOCATE} i \kod{DEALLOCATE}. U kodu se tada mogu koristiti i njihovi
skraćeni oblici \kod{NEW} i \kod{DISPOSE}.
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);
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
WriteLn;
WriteString("=============================");
WriteLn;
- WriteString("s - stampa");WriteLn;
- WriteString("u - unos");WriteLn;
- WriteString("i - izbacivanje br iz liste");
+ 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.");
+ WriteString("e - izbacivanje k-tog El.");
WriteLn;
WriteString("k - stampanje k-tog elementa");
WriteLn;
- WriteString("m - minimalni broj u listi");
+ WriteString("m - Minimalni broj u listi");
WriteLn;
- WriteString("p - pretraga el. u listi");
+ WriteString("p - Pretraga el. u listi");
WriteLn;
WriteLn;
- WriteString("q - kraj rada (quit)");WriteLn;
+ WriteString("q - kraj rada (Quit)");WriteLn;
REPEAT
menu := CAP(RdKey());
- UNTIL menu IN skupZn{'S','U','E','I',
+ 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); |
liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
težini}
-Sa tastature ucitavati po dva broja koji opisiuju osobu (visina i
-tezina) i smestati ih u povezane listu, tako da postoji neopadajuce
-uredjenje i po visini i po tezini.
+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;
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
PROCEDURE DisposePolinom(VAR p: Polinom);
END PolinomL.
-(* --- kraj definicionog modula --- *)
+\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;
PROCEDURE Anuliraj(VAR p: Polinom);
BEGIN
- IF p # NIL THEN
- DisposePolinom(p);
- END;
+ p := NIL;
END Anuliraj;
-PROCEDURE Kopiraj(p: Polinom;
- VAR kopija: Polinom);
+PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
VAR
pomocni: Polinom;
BEGIN
END
END Stampaj;
-PROCEDURE UbaciMonom(mon :Polinom;
- VAR p: Polinom);
+PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
VAR
stari, tekuci, kopija: Polinom;
BEGIN
ELSE
stari^.veza := kopija
END;
- IF (tekuci#NIL) AND
- (kopija^.st = tekuci^.st) THEN
+ IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
kopija^.k := kopija^.k + tekuci^.k;
kopija^.veza := tekuci^.veza;
DISPOSE(tekuci);
NEW(novi);
WITH novi^ DO
REPEAT
- WriteString('koeficijent monoma br.');
+ WriteString('Unesite koeficijent monoma br.');
WriteCard(i, 1);
- WriteString(' (<> 0):');
+ WriteString(' (<> 0) ');
ReadReal(k);
WriteLn
UNTIL k <> 0.0;
REPEAT
WriteLn;
- WriteString('eksponent monoma br.');
+ WriteString('Unesite eksponent monoma br.');
WriteCard(i, 1);
- WriteString(' (>= 0): ');
+ WriteString(' (>=0) ');
ReadCard(st);
UNTIL Done;
WriteLn;
END
END Unos;
-PROCEDURE Saberi(p1, p2: Polinom;
- VAR zbir: Polinom);
+PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
BEGIN
Kopiraj(p1, zbir);
WHILE p2 <> NIL DO
END
END Saberi;
-PROCEDURE SaberiNa(p: Polinom;
- VAR rez: Polinom);
+PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
BEGIN
WHILE p <> NIL DO
UbaciMonom(p,rez);
END
END PromeniZnak;
-PROCEDURE Oduzmi(p1,p2: Polinom;
- VAR razlika: Polinom);
+PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
BEGIN
Kopiraj(p2, razlika);
PromeniZnak(razlika);
END
END Oduzmi;
-PROCEDURE MonomPuta(p, mon: Polinom;
- VAR mp: Polinom);
+PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
VAR
tekuci: Polinom;
BEGIN
END
END Puta;
-PROCEDURE Kolicnik(p1, p2: Polinom;
- VAR kol, ost: Polinom;
- VAR ok: BOOLEAN);
+PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);
PROCEDURE Deli(VAR kol, ost: Polinom);
VAR
rez^.st := 0;
rez^.veza := NIL;
ELSIF n = 1 THEN
- Kopiraj( rez, p );
+ Kopiraj( p, rez );
ELSE
rez := p;
FOR i := 2 TO n DO
END DisposePolinom;
END PolinomL.
-\end{lstlisting}
+\end{codeblock}
\subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
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 sledeće pakete za
-download:
-
-* Native XDS-x86 2.51 for Windows (6.5MB)
-\url{http://www.excelsior-usa.com/download/xds25x/xds-x86-251-enduser-win32.exe}
-
-* TSCP add-on (2.4MB)
-\url{http://www.excelsior-usa.com/download/xds25x/tscp-x86-251-enduser-win32.exe}
+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}
-Prvo treba instalirati osnovno okruženje (xds-x86...), a potom i Top
-Speed Compatibility Pack (tscp-x86...), koji je potreban za neke
-module koji se koriste.
+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
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''.
-\end{multicols}
+
+\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}