From: Doni Pracner Date: Mon, 21 Oct 2013 12:42:25 +0000 (+0200) Subject: sve iz starih verzija X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-teorijske-vezbe.git;a=commitdiff_plain;h=cfda726ac9ecd0bd02935512ea0edaee2cd31b57 sve iz starih verzija --- diff --git a/Cas01/Prezentacija.ppt b/Cas01/Prezentacija.ppt new file mode 100644 index 0000000..6ff7ded Binary files /dev/null and b/Cas01/Prezentacija.ppt differ diff --git a/Cas01/RECNIKAT.DEF b/Cas01/RECNIKAT.DEF new file mode 100644 index 0000000..92a237a --- /dev/null +++ b/Cas01/RECNIKAT.DEF @@ -0,0 +1,42 @@ +DEFINITION MODULE RecnikATP; + + CONST + Broj = 11; (* Neki prost broj *) + MaxDuzRec = 50; + MaxTabela = Broj - 1; + + TYPE + String = ARRAY [1 .. MaxDuzRec] OF CHAR; + Lista = POINTER TO Element; + Element = RECORD + Veza, Prevod: Lista; + Rec: String; + END; + Indeksi = [0 .. MaxTabela]; + Tabela = ARRAY Indeksi OF Lista; + Recnik = RECORD + BrojReci: CARDINAL; + Domace, Strane: Tabela; + END; + + PROCEDURE Inicijalizuj(VAR R: Recnik); + PROCEDURE Unisti(VAR R: Recnik); + + PROCEDURE Ubaci(DomacaRec, StranaRec: String; + VAR R: Recnik; + VAR Duplikat: BOOLEAN); + + PROCEDURE Izbaci(Rec: String; + VAR R: Recnik; + Domaca: BOOLEAN; + VAR Ok: BOOLEAN); + + PROCEDURE Prevedi(StranaNaDomacu: BOOLEAN; + Rec: String; + VAR Prevod: String; + VAR R: Recnik; + VAR Ok: BOOLEAN); + + PROCEDURE Sadrzaj(VAR R: Recnik); + +END RecnikATP. diff --git a/Cas01/RECNIKAT.MOD b/Cas01/RECNIKAT.MOD new file mode 100644 index 0000000..1977893 --- /dev/null +++ b/Cas01/RECNIKAT.MOD @@ -0,0 +1,186 @@ +IMPLEMENTATION MODULE RecnikATP; + + FROM IO IMPORT + RdKey, WrStr, WrLn, WrCard; + FROM SYSTEM IMPORT + TSIZE; + FROM Str IMPORT + Compare; + FROM Storage IMPORT + ALLOCATE, DEALLOCATE; + + PROCEDURE Hash(Rec: String): Indeksi; + VAR + i, Zbir, Temp: CARDINAL; + BEGIN + Zbir:= 0; + i:= 1; + WHILE (i <= MaxDuzRec) AND (Rec[i] # CHR(0)) DO + Temp:= (ORD(Rec[i]) * ORD(Rec[i])) MOD Broj; + Zbir:= (Zbir + Temp) MOD Broj; + INC(i); + END; + RETURN Zbir; + END Hash; + + PROCEDURE Inicijalizuj(VAR R: Recnik); + VAR + i: Indeksi; + BEGIN + WITH R DO + BrojReci:= 0; + FOR i := 0 TO MaxTabela DO + NEW(Domace[i]); + Domace[i]^.Veza := Domace[i]; + NEW(Strane[i]); + Strane[i]^.Veza := Strane[i] + END; + END; + END Inicijalizuj; + + PROCEDURE Unisti(VAR R: Recnik); + VAR + i: Indeksi; + Tekuci: Lista; + BEGIN + FOR i:= 0 TO MaxTabela DO + WHILE R.Domace[i] # R.Domace[i]^.Veza DO + Tekuci:= R.Domace[i]^.Veza; + R.Domace[i]^.Veza:= Tekuci^.Veza; + DISPOSE(Tekuci); + END; + DISPOSE(R.Domace[i]); + WHILE R.Strane[i] # R.Strane[i]^.Veza DO + Tekuci:= R.Strane[i]^.Veza; + R.Strane[i]^.Veza:= Tekuci^.Veza; + DISPOSE(Tekuci); + END; + DISPOSE(R.Strane[i]); + END; + END Unisti; + + PROCEDURE Nadji(VAR Rec: String; + VAR Tab: Tabela; + VAR Prethodni: Lista; + VAR Nadjen: BOOLEAN); + VAR + Pozicija: Indeksi; + BEGIN + Pozicija:= Hash(Rec); + Prethodni:= Tab[Pozicija]; + Prethodni^.Rec:= Rec; + IF Prethodni^.Veza = Prethodni THEN + Nadjen:= FALSE; + ELSE + WHILE Compare(Prethodni^.Veza^.Rec, Rec) # 0 DO + Prethodni:= Prethodni^.Veza; + END; + Nadjen:= Prethodni^.Veza # Tab[Pozicija] + END; + END Nadji; + + PROCEDURE Ubaci(DomacaRec, StranaRec: String; + VAR R: Recnik; + VAR Duplikat: BOOLEAN); + VAR + NadjenDom, NadjenStr: BOOLEAN; + PrethodniDom, PrethodniStr, PomDom, PomStr: Lista; + BEGIN + + Nadji(DomacaRec, R.Domace, PrethodniDom, NadjenDom); + Nadji(StranaRec, R.Strane, PrethodniStr, NadjenStr); + + IF NadjenDom OR NadjenStr THEN + Duplikat:= TRUE; + ELSE + + Duplikat := FALSE; + + NEW(PomDom); + PomDom^.Rec:= DomacaRec; + PomDom^.Veza:= PrethodniDom^.Veza; + PrethodniDom^.Veza:= PomDom; + + NEW(PomStr); + PomStr^.Rec:= StranaRec; + PomStr^.Veza:= PrethodniStr^.Veza; + PrethodniStr^.Veza:= PomStr; + + PomDom^.Prevod:= PomStr; + PomStr^.Prevod:= PomDom; + + INC(R.BrojReci); + + END; + END Ubaci; + + PROCEDURE Izbaci(Rec: String; + VAR R: Recnik; + Domaca: BOOLEAN; + VAR Ok: BOOLEAN); + VAR + Prethodni, Prethodni2, Temp, Temp2: Lista; + BEGIN + + IF Domaca THEN + Nadji(Rec, R.Domace, Prethodni, Ok); + ELSE + Nadji(Rec, R.Strane, Prethodni, Ok); + END; + + IF Ok THEN + + Temp:= Prethodni^.Veza; + Prethodni^.Veza:= Temp^.Veza; + + Temp2:= Temp^.Prevod; + Prethodni2:= Temp2^.Veza; + WHILE Prethodni2^.Veza # Temp2 DO + Prethodni2:= Prethodni2^.Veza; + END; + Prethodni2^.Veza:= Temp2^.Veza; + + DISPOSE(Temp); + DISPOSE(Temp2); + + DEC(R.BrojReci); + END; + END Izbaci; + + PROCEDURE Prevedi(StranuNaDomacu: BOOLEAN; + Rec: String; + VAR Prevod: String; + VAR R: Recnik; + VAR Ok: BOOLEAN); + VAR + Prethodni: Lista; + BEGIN + IF StranuNaDomacu THEN + Nadji(Rec, R.Strane, Prethodni, Ok); + ELSE + Nadji(Rec, R.Domace, Prethodni, Ok); + END; + IF Ok THEN + Prevod:= Prethodni^.Veza^.Prevod^.Rec; + END + END Prevedi; + + PROCEDURE Sadrzaj(VAR R: Recnik); + VAR + i: Indeksi; + Tekuci: Lista; + BEGIN + WrStr('Sadrzaj recnika:'); + FOR i:= 0 TO MaxTabela DO + Tekuci:= R.Domace[i]^.Veza; + WHILE Tekuci# R.Domace[i] DO + WrLn; + WrStr(Tekuci^.Rec); + WrStr(' --------- '); + WrStr(Tekuci^.Prevod^.Rec); + Tekuci:= Tekuci^.Veza; + END; + END; + END Sadrzaj; + +END RecnikATP. diff --git a/Cas01/RECNIKTE.MOD b/Cas01/RECNIKTE.MOD new file mode 100644 index 0000000..5358707 --- /dev/null +++ b/Cas01/RECNIKTE.MOD @@ -0,0 +1,116 @@ +MODULE RecnikTest; + + FROM RecnikATP IMPORT + String, Recnik, Inicijalizuj, Ubaci, Izbaci, Sadrzaj, Prevedi, Unisti; + FROM IO IMPORT + WrLn, WrStr, RdStr, WrCard, RdKey, WrChar; + FROM Window IMPORT + Clear; + + VAR + R: Recnik; + Rec, Prevod: String; + Izbor, Izb: CHAR; + Ok, Duplikat, Domaca, StrNaDom: BOOLEAN; + + PROCEDURE Meni(VAR Izbor: CHAR); + TYPE + Slova = SET OF CHAR; + VAR + i: CARDINAL; + BEGIN + Clear; + FOR i:= 1 TO 8 DO + WrLn; + END; + WrStr(' P --- prevod reci'); WrLn; + WrStr(' B --- broj reci u recniku'); WrLn; + WrStr(' U --- ubacivanje nove reci i njenog prevoda u recnik'); WrLn; + WrStr(' I --- izbacivanje reci i njenog prevoda iz recnika'); WrLn; + WrStr(' S --- sekvencijalni prikaz recnika'); WrLn; + WrStr(' Q --- kraj rada'); + REPEAT + Izbor:= CAP(RdKey()); + UNTIL Izbor IN Slova {'P', 'B', 'U', 'I', 'S', 'Q'}; + Clear; + END Meni; + + PROCEDURE Pauza; + VAR + Ch: CHAR; + BEGIN + Ch:= RdKey(); + END Pauza; + +BEGIN + Inicijalizuj(R); + REPEAT + Meni(Izbor); + CASE Izbor OF + 'P': REPEAT + WrStr('1) prevod strane reci'); WrLn; + WrStr('2) prevod domace reci'); WrLn; + WrLn; + WrStr("Unesite '1' ili '2' --- "); + Izb:= RdKey(); + WrChar(Izb); WrLn; + UNTIL (Izb = '1') OR (Izb = '2'); + StrNaDom:= Izb = '1'; + IF StrNaDom THEN + WrStr('Unesite stranu rec ---- '); + RdStr(Rec); + Prevedi(StrNaDom, Rec, Prevod, R, Ok); + IF Ok THEN + WrStr('Prevod ---------------- '); + WrStr(Prevod); + ELSE + WrStr('Zadata rec se ne nalazi u recniku.'); + END; + ELSE + WrStr('Unesite domacu rec ---- '); + RdStr(Rec); + Prevedi(StrNaDom, Rec, Prevod, R, Ok); + IF Ok THEN + WrStr('Prevod ---------------- '); + WrStr(Prevod); + ELSE + WrStr('Zadata rec se ne nalazi u recniku.'); + END; + END; + Pauza; | + 'B': WrStr('Recnik raspolaze fondom od '); + WrCard(R.BrojReci, 1); + WrStr(' reci.'); + Pauza; | + 'U': WrStr('Unesite novu domacu rec ----- '); + RdStr(Rec); + WrStr('Unesite njen prevod -------- '); + RdStr(Prevod); + Ubaci(Rec, Prevod, R, Duplikat); + IF Duplikat THEN + WrStr('U recniku se vec nalazi data rec.'); + ELSE + WrStr('Upisano.'); + END; + Pauza; | + 'I': WrStr('Unesite rec --- '); + RdStr(Rec); + REPEAT + WrStr('Da li je uneta rec domaca ili strana? (d/s) '); + Izb:= RdKey(); + WrLn; + UNTIL (CAP(Izb) = 'D') OR (CAP(Izb) = 'S'); + Domaca:= CAP(Izb) = 'D'; + Izbaci(Rec, R, Domaca, Ok); + IF Ok THEN + WrStr('Izbrisano.') + ELSE + WrStr('Rec se nije ni nalazila u recniku.') + END; + Pauza; | + 'S': Sadrzaj(R); + Pauza; + END; + UNTIL Izbor = 'Q'; + Unisti(R); +END RecnikTest. diff --git a/Cas02/MALA.SLI b/Cas02/MALA.SLI new file mode 100644 index 0000000..a05cae8 --- /dev/null +++ b/Cas02/MALA.SLI @@ -0,0 +1,6 @@ +5 + 0 0 1 0 0 + 0 1 1 1 0 + 1 1 2 1 1 + 0 1 1 1 0 + 0 0 1 0 0 diff --git a/Cas02/PODSLIKA.MOD b/Cas02/PODSLIKA.MOD new file mode 100644 index 0000000..78dc19b --- /dev/null +++ b/Cas02/PODSLIKA.MOD @@ -0,0 +1,168 @@ +MODULE Podslika; + + FROM FIO IMPORT + File, Open, Close, RdCard, EOF, OK, Exists; + FROM IO IMPORT + WrLn, WrStr, WrCard; + + CONST + MaxDim = 100; + BrojBoja = 16; + Osnova = MaxDim * (BrojBoja - 1) + 1; + ProstBroj = 3001; + ImeVel = 'Velika.Sli'; + ImeMal = 'Mala.Sli'; + + TYPE + Boja = [0 .. BrojBoja - 1]; + Slika = ARRAY [1 .. MaxDim], [1 .. MaxDim] OF Boja; + + VAR + Velika, Mala: Slika; + DimVel, DimMal, Vr, Ko: CARDINAL; + KljucMale, KljucSegmenta, Stepen: LONGCARD; + Ok, Iste: BOOLEAN; + + PROCEDURE Citaj(VAR Slika: Slika; + Ime: ARRAY OF CHAR; + VAR Dim: CARDINAL; + VAR Ok: BOOLEAN); + VAR + F: File; + Vr, Ko: CARDINAL; + Jos: BOOLEAN; + BEGIN + Ok:= Ok AND Exists(Ime); + IF Ok THEN + F:= Open(Ime); + Dim:= RdCard(F); + Vr:= 1; + Jos:= TRUE; + WHILE Jos AND (Vr <= Dim) DO + Ko:= 1; + WHILE Jos AND (Ko <= Dim) DO + Slika[Vr, Ko]:= RdCard(F); + Ok:= Ok AND (Slika[Vr, Ko] < BrojBoja); + Jos:= Ok AND NOT EOF; + INC(Ko); + END; + INC(Vr); + END; + Close(F); + ELSE + Dim:= 0; + END; + END Citaj; + + PROCEDURE Proveri(VAR Velika, Mala: Slika; + DimMal, Vr, Ko: CARDINAL): BOOLEAN; + VAR + i, j: CARDINAL; + Iste: BOOLEAN; + BEGIN + Iste:= TRUE; + i:= 1; + WHILE Iste AND (i <= DimMal) DO + j:= 1; + WHILE Iste AND (j <= DimMal) DO + IF Mala[i, j] # Velika[Vr + i - 1, Ko + j - 1] THEN + Iste:= FALSE; + END; + INC(j); + END; + INC(i); + END; + RETURN Iste; + END Proveri; + + PROCEDURE Hash(S: Slika; DimMal, Vr: CARDINAL): LONGCARD; + VAR + i, j: CARDINAL; + Kljuc, ZbirKolone, Temp: LONGCARD; + BEGIN + + Stepen:= 1; + Kljuc:= 0; + + FOR i:= DimMal TO 1 BY -1 DO + + ZbirKolone:= 0; + FOR j:= Vr TO Vr + DimMal - 1 DO + ZbirKolone:= ZbirKolone + LONGCARD(S[j, i]); + END; + + Temp:= (ZbirKolone * Stepen) MOD ProstBroj; + Kljuc:= (Kljuc + Temp) MOD ProstBroj; + Stepen:= (Stepen * Osnova) MOD ProstBroj; + + END; + + Stepen:= Stepen DIV Osnova; + + RETURN Kljuc; + + END Hash; + + PROCEDURE DoterajHash(S: Slika; DimMal, Vr, Ko: CARDINAL; + VAR Kljuc: LONGCARD); + VAR + i, j: CARDINAL; + ZbirKolone, Temp: LONGCARD; + BEGIN + + ZbirKolone:= 0; + FOR j:= Vr TO Vr + DimMal - 1 DO + ZbirKolone:= ZbirKolone + LONGCARD(S[j, Ko - 1]); + END; + + Temp:= (ZbirKolone * Stepen) MOD ProstBroj; + + IF Kljuc >= Temp THEN + Kljuc:= Kljuc - Temp; + ELSE + Kljuc:= Kljuc + ProstBroj - Temp; + END; + + Kljuc:= (Kljuc * Osnova) MOD ProstBroj; + + ZbirKolone:= 0; + FOR j:= Vr TO Vr + DimMal - 1 DO + ZbirKolone:= ZbirKolone + LONGCARD(S[j, Ko + DimMal - 1]); + END; + + Kljuc:= (Kljuc + ZbirKolone) MOD ProstBroj; + + END DoterajHash; + +BEGIN + Ok:= TRUE; + Citaj(Velika, ImeVel, DimVel, Ok); + Citaj(Mala, ImeMal, DimMal, Ok); + IF Ok THEN + KljucMale:= Hash(Mala, DimMal, 1); + FOR Vr:= 1 TO (DimVel - DimMal + 1) DO + KljucSegmenta:= Hash(Velika, DimMal, Vr); + IF (KljucMale = KljucSegmenta) THEN + Iste:= Proveri(Velika, Mala, DimMal, Vr, 1); + IF Iste THEN + WrLn; + WrStr('Podslika je nadjena. Pocinje na poziciji ('); + WrCard(Vr, 1); WrStr(', '); WrCard(1, 1); WrStr(')'); + END; + END; + FOR Ko:= 2 TO (DimVel - DimMal + 1) DO + DoterajHash(Velika, DimMal, Vr, Ko, KljucSegmenta); + IF (KljucMale = KljucSegmenta) THEN + Iste:= Proveri(Velika, Mala, DimMal, Vr, Ko); + IF Iste THEN + WrLn; + WrStr('Podslika je nadjena. Pocinje na poziciji ('); + WrCard(Vr, 1); WrStr(', '); WrCard(Ko, 1); WrStr(')'); + END; + END; + END; + END; + ELSE + WrStr('Greska u citanju fajla.'); + END; +END Podslika. diff --git a/Cas02/Prezentacija.ppt b/Cas02/Prezentacija.ppt new file mode 100644 index 0000000..0c685f2 Binary files /dev/null and b/Cas02/Prezentacija.ppt differ diff --git a/Cas02/VELIKA.SLI b/Cas02/VELIKA.SLI new file mode 100644 index 0000000..050166c --- /dev/null +++ b/Cas02/VELIKA.SLI @@ -0,0 +1,13 @@ +12 + 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 1 0 0 0 0 0 0 0 0 + 0 0 1 1 1 0 0 0 0 0 0 0 + 0 1 1 2 1 1 0 0 0 0 0 0 + 0 0 1 1 1 0 5 5 5 0 0 0 + 0 0 0 1 0 0 0 0 0 0 0 0 + 0 0 0 0 0 5 0 0 1 0 0 0 + 0 0 0 0 5 0 0 1 2 1 0 0 + 0 0 0 5 0 0 1 2 15 2 1 0 + 0 0 5 0 0 0 0 1 2 1 0 0 + 0 0 0 0 0 0 0 0 1 0 0 0 diff --git a/Cas03/Prezentacija.ppt b/Cas03/Prezentacija.ppt new file mode 100644 index 0000000..d059c40 Binary files /dev/null and b/Cas03/Prezentacija.ppt differ diff --git a/Cas03/SHAKER.MOD b/Cas03/SHAKER.MOD new file mode 100644 index 0000000..5f1ef39 --- /dev/null +++ b/Cas03/SHAKER.MOD @@ -0,0 +1,80 @@ +MODULE Shaker; + + FROM IO IMPORT + WrCard, WrStr, RdCard, WrLn, OK; + + CONST + Max = 10; + + TYPE + Indeks = [1 .. Max]; + NizTip = ARRAY Indeks OF CARDINAL; + + VAR + Niz: NizTip; + + PROCEDURE Unos(VAR Niz: NizTip); + VAR + i: Indeks; + BEGIN + FOR i:= 1 TO Max DO + REPEAT + WrStr('Unesite '); + WrCard(i, 2); + WrStr('. clan niza: '); + Niz[i]:= RdCard(); + WrLn; + UNTIL OK; + END; + END Unos; + + PROCEDURE Ispis(VAR Niz: NizTip); + VAR + i: Indeks; + BEGIN + FOR i := 1 TO Max - 1 DO + WrCard(Niz[i], 1); + WrStr(', '); + END; + WrCard(Niz[Max], 1); + END Ispis; + + PROCEDURE ShakerSort(VAR Niz: NizTip); + VAR + Levi, Desni, i, ZadnjiMenjan: Indeks; + Temp: CARDINAL; + BEGIN + Levi:= 2; + Desni:= Max; + ZadnjiMenjan:= Max; + REPEAT + FOR i:= Desni TO Levi BY -1 DO + IF Niz[i - 1] > Niz[i] THEN + Temp:= Niz[i - 1]; + Niz[i - 1]:= Niz[i]; + Niz[i]:= Temp; + ZadnjiMenjan:= i; + END; + END; + Levi:= ZadnjiMenjan + 1; + FOR i:= Levi TO Desni DO + IF Niz[i - 1] > Niz[i] THEN + Temp:= Niz[i - 1]; + Niz[i - 1]:= Niz[i]; + Niz[i]:= Temp; + ZadnjiMenjan:= i; + END; + END; + Desni:= ZadnjiMenjan - 1; + UNTIL Levi > Desni; + END ShakerSort; + +BEGIN + Unos(Niz); + WrStr('Unesen niz: '); + Ispis(Niz); + WrLn; + WrStr('Sortiran niz: '); + ShakerSort(Niz); + Ispis(Niz); +END Shaker. diff --git a/Cas05/NBROJEVA.MOD b/Cas05/NBROJEVA.MOD new file mode 100644 index 0000000..9f15488 --- /dev/null +++ b/Cas05/NBROJEVA.MOD @@ -0,0 +1,112 @@ +MODULE NBrojeva; + + FROM IO IMPORT + WrLn, WrCard, RdCard, WrStr; + + CONST + MaxNiz = 50; + MaxSuma = 500; + + VAR + n, Suma, SumaPola: CARDINAL; + Broj: ARRAY [1 .. MaxNiz] OF CARDINAL; + Iskor: ARRAY[1 .. MaxNiz] OF BOOLEAN; + Mat: ARRAY[0 .. MaxSuma], [0 .. MaxNiz] OF CARDINAL; + (* Mat[i, j] je suma brojeva u resenju ako je maksimalna *) + (* dozvoljena suma brojeva u resenju jednaka 'i' i ako se *) + (* koristi samo prvih 'j' brojeva. *) + + PROCEDURE Unos; + VAR + i: CARDINAL; + BEGIN + WrStr('Unesite n: '); + n:= RdCard(); + Suma:= 0; + FOR i:= 1 TO n DO + WrStr('Unesite '); + WrCard(i, 1); + WrStr('. broj: '); + Broj[i]:= RdCard(); + Suma:= Suma + Broj[i]; + Iskor[i]:= FALSE; + END; + SumaPola:= Suma DIV 2; + END Unos; + + PROCEDURE Resi; + VAR + i, j, Pom: CARDINAL; + BEGIN + FOR i:= 0 TO SumaPola DO + Mat[i, 0]:= 0; (* Koristi se prvih 0 brojeva *) + END; + FOR j:= 1 TO n DO + Mat[0, j]:= 0; (* Maksimalna dozvoljena suma brojeva u resenju je 0 *) + END; + FOR i:= 1 TO SumaPola DO + (* Maks. dozvoljena suma brojeva u resenju je i *) + FOR j := 1 TO n DO + (* U resenju mogu ucestvovati prvih j brojeva *) + Mat[i, j]:= Mat[i, j - 1]; + IF Broj[j] <= i THEN + Pom:= Mat[i - Broj[j], j - 1] + Broj[j]; + IF Pom > Mat[i, j] THEN + Mat[i, j]:= Pom; + END; + END; + END; + END; + END Resi; + + PROCEDURE IspisiPrvu; + VAR + i, j: CARDINAL; + BEGIN + WrStr('Zbir prve grupe brojeva je '); + WrCard(Mat[SumaPola, n], 1); + WrLn; + WrStr('Prvu grupu brojeva cine brojevi:'); + WrLn; + i:= SumaPola; + j:= n; + REPEAT + WHILE (j > 0) AND (Mat[i, j] = Mat[i, j - 1]) DO + DEC(j); + END; + IF j > 0 THEN + WrCard(Broj[j], 8); + Iskor[j]:= TRUE; + i:= i - Broj[j]; + DEC(j); + END; + UNTIL j = 0; + END IspisiPrvu; + + PROCEDURE IspisiDrugu; + VAR + i, j: CARDINAL; + BEGIN + WrLn; + WrStr('Zbir druge grupe brojeva je '); + WrCard(Suma - Mat[SumaPola, n], 1); + WrLn; + WrStr('Drugu grupu brojeva cine brojevi:'); + WrLn; + FOR i := 1 TO n DO + IF NOT Iskor[i] THEN + WrCard(Broj[i], 8); + END; + END; + END IspisiDrugu; + +BEGIN + Unos; + IF SumaPola > MaxSuma THEN + WrStr('Ulazni podaci su suvise veliki.'); + ELSE + Resi; + IspisiPrvu; + IspisiDrugu; + END; +END NBrojeva. diff --git a/Cas05/Prezentacija.ppt b/Cas05/Prezentacija.ppt new file mode 100644 index 0000000..a1b04ab Binary files /dev/null and b/Cas05/Prezentacija.ppt differ diff --git a/Cas06/NIZDIN.MOD b/Cas06/NIZDIN.MOD new file mode 100644 index 0000000..6156e77 --- /dev/null +++ b/Cas06/NIZDIN.MOD @@ -0,0 +1,65 @@ +MODULE NizDin; + + FROM IO IMPORT + WrStr, RdInt, WrInt; + + CONST + MaxN = 1000; + + VAR + a, b: ARRAY [0 .. MaxN] OF INTEGER; + (* b[i] je suma elemenata u resenju za *) + (* deo niza 'a' do 'i'-tog elementa *) + n: INTEGER; + + PROCEDURE Unos; + VAR + i: CARDINAL; + BEGIN + WrStr('Unesite N: '); + n:= RdInt(); + FOR i:= 1 TO n DO + WrStr('A['); + WrInt(i, 1); + WrStr('] = '); + a[i]:= RdInt(); + END; + END Unos; + + PROCEDURE Resi; + VAR + i, j, Pom: CARDINAL; + BEGIN + b[0]:= 0; + IF a[1] > 0 THEN + b[1]:= a[1]; + ELSE + b[1]:= 0; + END; + FOR i:= 2 TO n DO + IF b[i - 2] + a[i] > b[i - 1] THEN + b[i]:= b[i - 2] + a[i]; + ELSE + b[i]:= b[i - 1]; + END + END; + END Resi; + + PROCEDURE Ispis(n: CARDINAL); + BEGIN + IF n > 0 THEN + IF b[n] = b[n - 1] THEN + Ispis(n - 1); + ELSE + Ispis(n - 2); + WrInt(a[n], 8); + END; + END; + END Ispis; + +BEGIN + Unos; + Resi; + WrStr('Podniz: '); + Ispis(n); +END NizDin. diff --git a/Cas06/Prezentacija.ppt b/Cas06/Prezentacija.ppt new file mode 100644 index 0000000..c0ab24e Binary files /dev/null and b/Cas06/Prezentacija.ppt differ diff --git a/Cas07/MAXZBIR.MOD b/Cas07/MAXZBIR.MOD new file mode 100644 index 0000000..85e8209 --- /dev/null +++ b/Cas07/MAXZBIR.MOD @@ -0,0 +1,100 @@ +MODULE MaxZbir; + + FROM IO IMPORT + WrStr, WrLn, WrCard, WrInt, RdCard, RdInt; + + CONST + Max = 100; + + VAR + A, B: ARRAY [1 .. Max], [1 .. Max] OF INTEGER; + m, n: CARDINAL; + (* B[vr, ko] je vrednost optimalnog resenja od (1, 1) do (vr, ko) *) + + PROCEDURE Unos; + VAR + i, j: CARDINAL; + BEGIN + WrStr('Unesite n: '); + n:= RdCard(); + WrStr('Unesite m: '); + m:= RdCard(); + IF (n < Max) AND (m < Max) THEN + FOR i:= 1 TO m DO + FOR j:= 1 TO n DO + WrStr('A['); + WrCard(i, 1); + WrStr(', '); + WrCard(j, 1); + WrStr('] = '); + A[i, j] := RdInt(); + END; + END; + END; + END Unos; + + PROCEDURE Resi; + VAR + i, j: CARDINAL; + BEGIN + B[1, 1]:= A[1, 1]; + FOR j:= 2 TO n DO + B[1, j]:= A[1, j] + B[1, j-1]; + END; + FOR i:= 2 TO m DO + B[i, 1]:= A[i, 1] + B[i-1, 1]; + END; + FOR i:= 2 TO m DO + FOR j:= 2 TO n DO + IF B[i, j - 1] < B[i - 1, j] THEN + B[i, j]:= A[i, j] + B[i - 1, j]; + ELSE + B[i, j]:= A[i, j] + B[i, j - 1]; + END; + END; + END; + END Resi; + + PROCEDURE Ispis(Vr, Ko: CARDINAL); + VAR + i: CARDINAL; + BEGIN + IF (Vr > 1) AND (Ko > 1) THEN + IF B[Vr - 1, Ko] > B[Vr, Ko - 1] THEN + Ispis(Vr - 1, Ko); + ELSE + Ispis(Vr, Ko - 1); + END; + WrStr('('); + WrCard(Vr, 1); + WrStr(', '); + WrCard(Ko, 1); + WrStr(')'); + ELSIF Vr = 1 THEN + FOR i:= 1 TO Ko DO + WrStr('(1, '); + WrCard(i, 1); + WrStr(')'); + END; + ELSE + FOR i:= 1 TO Vr DO + WrStr('('); + WrCard(i, 1); + WrStr(', 1)'); + END; + END; + END Ispis; + +BEGIN + Unos; + IF (n < Max) AND (m < Max) THEN + Resi; + WrStr('Maksimalni zbir je '); + WrInt(B[m, n], 1); + WrStr(' a postize se ovako:'); + WrLn; + Ispis(m, n) + ELSE + WrStr('Suvise velika matrica.') + END +END MaxZbir. diff --git a/Cas07/Prezentacija.ppt b/Cas07/Prezentacija.ppt new file mode 100644 index 0000000..3aab8ac Binary files /dev/null and b/Cas07/Prezentacija.ppt differ diff --git a/Cas08/BOJENJE.MOD b/Cas08/BOJENJE.MOD new file mode 100644 index 0000000..6986a33 --- /dev/null +++ b/Cas08/BOJENJE.MOD @@ -0,0 +1,128 @@ +MODULE Bojenje; + + FROM IO IMPORT + WrStr, WrLn, WrLngCard; + + CONST + MaxBrojZemalja = 30; + DuzinaImena = 18; + + TYPE + RangImena = [1 .. DuzinaImena]; + Zemlja = [1 .. MaxBrojZemalja]; + SkupZ = SET OF Zemlja; + Boja = (Crvena, Plava, Zelena, Zuta); + GraniceTip = ARRAY Zemlja OF SkupZ; + BojeZemalja = ARRAY Boja OF SkupZ; + ImenaZemalja = ARRAY Zemlja, RangImena OF CHAR; + + VAR + Granice: GraniceTip; + Obojeno: BojeZemalja; + Ime: ImenaZemalja; + BrZ: Zemlja; + RBr: LONGCARD; + + PROCEDURE Inicijalizacija; + VAR + i: Boja; + BEGIN + FOR i:= MIN(Boja) TO MAX(Boja) DO + Obojeno[i]:= SkupZ {}; + END; + Ime[ 1]:= 'Maroko'; + Ime[ 2]:= 'Zapadna Sahara'; + Ime[ 3]:= 'Alzir'; + Ime[ 4]:= 'Tunis'; + Ime[ 5]:= 'Mauritanija'; + Ime[ 6]:= 'Mali'; + Ime[ 7]:= 'Niger'; + Ime[ 8]:= 'Libija'; + Ime[ 9]:= 'Senegal'; + Ime[10]:= 'Gvineja'; + Ime[11]:= 'Obala Slonovace'; + Ime[12]:= 'Burkina Faso'; + Ime[13]:= 'Benin'; + Ime[14]:= 'Nigerija'; + Ime[15]:= 'Cad'; + Ime[16]:= 'Sudan'; + Ime[17]:= 'Egipat'; + Ime[18]:= 'Gambija'; + Ime[19]:= 'Gvineja Bisao'; + Ime[20]:= 'Siera Leone'; + Granice[ 1]:= SkupZ {3, 2}; + Granice[ 2]:= SkupZ {1, 3, 5}; + Granice[ 3]:= SkupZ {1, 2, 5, 6, 7, 8, 4}; + Granice[ 4]:= SkupZ {3, 8}; + Granice[ 5]:= SkupZ {2, 3, 6, 9}; + Granice[ 6]:= SkupZ {3, 5, 9, 10, 11, 12, 7}; + Granice[ 7]:= SkupZ {3, 6, 12, 13, 14, 15, 8}; + Granice[ 8]:= SkupZ {4, 3, 7, 15, 16, 17}; + Granice[ 9]:= SkupZ {18, 19, 10, 6, 5}; + Granice[10]:= SkupZ {19, 9, 6, 20, 11}; + Granice[11]:= SkupZ {10, 6, 12}; + Granice[12]:= SkupZ {6, 11, 13, 7}; + Granice[13]:= SkupZ {12, 7, 14}; + Granice[14]:= SkupZ {13, 7, 15}; + Granice[15]:= SkupZ {14, 7, 8, 16}; + Granice[16]:= SkupZ {17, 8, 15}; + Granice[17]:= SkupZ {8, 15, 16}; + Granice[18]:= SkupZ {9}; + Granice[19]:= SkupZ {9, 10}; + Granice[20]:= SkupZ {10}; + RBr:= 0; + BrZ:= 20 + END Inicijalizacija; + + PROCEDURE StampajSkup(VAR S: SkupZ); + VAR + z: Zemlja; + Prvi: BOOLEAN; + BEGIN + Prvi:= TRUE; + FOR z:= 1 TO MaxBrojZemalja DO + IF z IN S THEN + IF Prvi THEN + WrStr(Ime[z]); + Prvi:= FALSE; + ELSE + WrStr(', '); + WrStr(Ime[z]); + END; + END; + END; + END StampajSkup; + + + PROCEDURE Stampa(RBr: LONGCARD; VAR Obojeno: BojeZemalja); + BEGIN + WrLn; WrLn; WrLngCard(RBr, 1); + WrLn; WrStr('Crvena: '); StampajSkup(Obojeno[Crvena]); + WrLn; WrStr('Plava: '); StampajSkup(Obojeno[Plava]); + WrLn; WrStr('Zelena: '); StampajSkup(Obojeno[Zelena]); + WrLn; WrStr('Zuta: '); StampajSkup(Obojeno[Zuta]); + END Stampa; + + PROCEDURE Oboji(z: Zemlja); + VAR + i: Boja; + BEGIN + FOR i:= MIN(Boja) TO MAX(Boja) DO + IF Granice[z] * Obojeno[i] = SkupZ {} THEN + Obojeno[i]:= Obojeno[i] + SkupZ {z}; + IF z = BrZ THEN + INC(RBr); + Stampa(RBr, Obojeno); + ELSE + Oboji(z + 1); + END; + Obojeno[i]:= Obojeno[i] - SkupZ {z}; + END; + END; + END Oboji; + +BEGIN + Inicijalizacija; + Oboji(1); + (* Broj mogucih bojenja je 1 527 552 *) +END Bojenje. diff --git a/Cas08/Prezentacija.ppt b/Cas08/Prezentacija.ppt new file mode 100644 index 0000000..73a6b8b Binary files /dev/null and b/Cas08/Prezentacija.ppt differ diff --git a/Cas09/Prezentacija.ppt b/Cas09/Prezentacija.ppt new file mode 100644 index 0000000..2c77cf5 Binary files /dev/null and b/Cas09/Prezentacija.ppt differ diff --git a/Cas09/Put.MOD b/Cas09/Put.MOD new file mode 100644 index 0000000..2b93a80 --- /dev/null +++ b/Cas09/Put.MOD @@ -0,0 +1,143 @@ +MODULE Put; + + FROM IO IMPORT + WrLn, WrStr, RdCard, WrCard, OK; + + FROM Storage IMPORT + ALLOCATE; + + CONST + MaxBrGrad = 50; + + TYPE + Lista = POINTER TO Grad; + Grad = RECORD + Info: CARDINAL; + Veza: Lista; + END; + Mreza = ARRAY [1 .. MaxBrGrad] OF Lista; + Posecen = ARRAY [1 .. MaxBrGrad] OF BOOLEAN; + + VAR + m: Mreza; + BrojGr: CARDINAL; + GPoc, GKra: CARDINAL; + + PROCEDURE Ubaci(VAR L: Lista; G: CARDINAL); + VAR + Tek, Novi: Lista; + BEGIN + IF (L = NIL) OR (G < L^.Info) THEN + NEW(Novi); + Novi^.Info:= G; + Novi^.Veza:= L; + L:= Novi; + ELSE + Tek:= L; + WHILE (Tek^.Veza # NIL) AND (Tek^.Veza^.Info < G) DO + Tek:= Tek^.Veza; + END; + IF (Tek^.Veza = NIL) OR (Tek^.Veza^.Info > G) THEN + NEW(Novi); + Novi^.Info:= G; + Novi^.Veza:= Tek^.Veza; + Tek^.Veza:= Novi; + END; + END; + END Ubaci; + + PROCEDURE Povezi(G1, G2: CARDINAL); + BEGIN + Ubaci(m[G1], G2); + Ubaci(m[G2], G1); + END Povezi; + + PROCEDURE Unos(VAR G1, G2: CARDINAL); + VAR + G: CARDINAL; + BEGIN + REPEAT + WrStr('Unesite broj gradova (od 2 do '); + WrCard(MaxBrGrad, 1); + WrStr(') ---- '); + BrojGr:= RdCard(); + WrLn; + UNTIL OK AND (2 <= BrojGr) AND (BrojGr <= MaxBrGrad); + FOR G:= 1 TO BrojGr DO + m[G]:= NIL; + END; + REPEAT + WrStr('Unesite dva grada koji su povezani linijom.'); + REPEAT + WrLn; + WrStr('Unesite red. br. prvog grada (ili 0 za kraj unosa linija) -- '); + G1:= RdCard() + UNTIL OK AND (G1 <= BrojGr); + IF G1 > 0 THEN + REPEAT + WrStr('Unesite red. br. drugog grada ------------------------------ '); + G2:= RdCard(); + UNTIL OK AND (1 <= G2) AND (G2 <= BrojGr) AND (G1 # G2); + Povezi(G1, G2); + END; + WrLn; + UNTIL G1 = 0; + REPEAT + WrLn; + WrLn; + WrStr('Unesite red. br. pocetnog grada -- '); + G1:= RdCard(); + UNTIL OK AND (1 <= G1) AND (G1 <= BrojGr); + REPEAT + WrLn; + WrStr('Unesite red. br ciljnog grada -- '); + G2:= RdCard(); + UNTIL OK AND (1 <= G2) AND (G2 <= BrojGr) AND (G1 # G2); + END Unos; + + PROCEDURE NadjiPut(Od, Do, brojGr : CARDINAL); + VAR + Pos: Posecen; + Reseno: BOOLEAN; + i: CARDINAL; + Resenje: ARRAY [1 .. MaxBrGrad] OF CARDINAL; + + PROCEDURE Pokusaj(Od, Br: CARDINAL; VAR Reseno: BOOLEAN); + VAR + Pok: Lista; + BEGIN + Pos[Od]:= TRUE; + Resenje[Br]:= Od; + IF Od = Do THEN + Reseno:= TRUE; + WrLn; + WrStr('Put koji treba precji je sledeci:'); + WrLn; + FOR i:= 1 TO Br DO + WrCard(Resenje[i], 4); + END; + ELSE + Pok:= m[Od]; + WHILE (Pok # NIL) AND NOT Reseno DO + WHILE (Pok # NIL) AND Pos[Pok^.Info] DO + Pok:= Pok^.Veza; + END; + IF Pok # NIL THEN + Pokusaj(Pok^.Info, Br + 1, Reseno); + END; + END; + END; + END Pokusaj; + + BEGIN + Reseno:= FALSE; + FOR i:= 1 TO BrojGr DO + Pos[i]:= FALSE; + END; + Pokusaj(Od, 1, Reseno); + END NadjiPut; + +BEGIN + Unos(GPoc, GKra); + NadjiPut(GPoc, GKra, BrojGr); +END Put. diff --git a/Cas10/PERMP.MOD b/Cas10/PERMP.MOD new file mode 100644 index 0000000..b72c076 --- /dev/null +++ b/Cas10/PERMP.MOD @@ -0,0 +1,92 @@ +MODULE PermP; + +FROM IO IMPORT + WrStr, WrLn, WrCard, RdCard, WrChar, RdKey, OK; + +CONST + MaxDim = 50; + +TYPE + Niz = ARRAY [1 .. MaxDim] OF CHAR; + +VAR + A: Niz; + n: CARDINAL; + +PROCEDURE Unos(VAR n: CARDINAL; VAR A: Niz); +VAR + i: CARDINAL; +BEGIN + REPEAT + WrStr('Unesite n (1 <= n <= '); + WrCard(MaxDim, 1); + WrStr(') --- '); + n:= RdCard(); + WrLn; + UNTIL OK AND (1 <= n) AND (n <= MaxDim); + REPEAT + WrLn; + WrStr('Unesite '); + WrCard(n, 1); + WrStr(' slova koja treba permutovati (mogu se i ponavljati):'); + WrLn; + WrLn; + i:= 0; + REPEAT + INC(i); + A[i]:= RdKey(); + WrChar(A[i]) + UNTIL (i = n) OR ((CAP(A[i]) < 'A') AND (CAP(A[i]) > 'Z') + AND (A[i] < '0') AND (A[i] > '9')); + UNTIL NOT ((CAP(A[i]) < 'A') AND (CAP(A[i]) > 'Z') AND + (A[i] < '0') AND (A[i] > '9')); +END Unos; + +PROCEDURE Permutacije(n: CARDINAL; VAR A: Niz); + + PROCEDURE Nadji(k: CARDINAL); + VAR + i, j: CARDINAL; + Temp: CHAR; + BEGIN + IF k = 1 THEN + FOR i:= 1 TO n DO + WrChar(A[i]); + END; + WrLn; + ELSE + Nadji(k - 1); + FOR i:= 1 TO k - 1 DO + IF A[k] # A[i] THEN + (* Zamenimo elemente samo ako su razliciti *) + j:= 1; + WHILE (j < i) AND (A[j] # A[i]) DO + INC(j); + END; + IF j = i THEN + (* A[i] nema duplikata u skupu {a[1], ... , a[i-1] *) + Temp:= A[i]; + A[i]:= A[k]; + A[k]:= Temp; + Nadji(k - 1); + Temp:= A[i]; + A[i]:= A[k]; + A[k]:= Temp; + END; + END; + END; + END; + END Nadji; + +BEGIN + Nadji(n); +END Permutacije; + +BEGIN + Unos(n, A); + WrLn; + WrLn; + WrStr('Permutacije: '); + WrLn; + Permutacije(n, A); +END PermP. diff --git a/Cas10/Prezentacija.ppt b/Cas10/Prezentacija.ppt new file mode 100644 index 0000000..7097444 Binary files /dev/null and b/Cas10/Prezentacija.ppt differ diff --git a/Cas11/Prezentacija.ppt b/Cas11/Prezentacija.ppt new file mode 100644 index 0000000..e3b4ce5 Binary files /dev/null and b/Cas11/Prezentacija.ppt differ diff --git a/Cas11/QUEENS.MOD b/Cas11/QUEENS.MOD new file mode 100644 index 0000000..acae9e4 --- /dev/null +++ b/Cas11/QUEENS.MOD @@ -0,0 +1,315 @@ +MODULE Queens; + + FROM IO IMPORT + WrStr, WrLn, WrCard, RdCard, OK; + + FROM SYSTEM IMPORT + TSIZE; + + FROM Storage IMPORT + ALLOCATE, DEALLOCATE; + + IMPORT FIO; + + CONST + MaxDim = 50; + + TYPE + Indeks = [1 .. MaxDim]; + DomenCene = [0 .. MaxDim * MaxDim]; + DomenBrojaKraljica = [1 .. MaxDim * MaxDim]; + + PPolozaj = POINTER TO SPolozaj; + SPolozaj = RECORD + Ko, Vr: Indeks; + Cena: DomenCene; + Veza: PPolozaj; + END; + + PKraljica = POINTER TO SKraljica; + SKraljica = RECORD + Pre, Sled: PKraljica; + Kandidati: PPolozaj; + TekKo, TekVr: Indeks; + END; + + StanjeTip = RECORD + Cena: DomenCene; + PrvaKra, TekKra: PKraljica; + END; + StatusTip = (stZauzeto, stNapadnuto, stSlobodno); + ResenjeTip = RECORD + Cena: DomenCene; + Poz: ARRAY Indeks, Indeks OF StatusTip; + END; + VAR + BrojKol, BrojVrs: Indeks; + BrojKraljica: DomenBrojaKraljica; + + PROCEDURE Unos(); + BEGIN + REPEAT + WrLn; + WrStr('Unesite broj Kolona sahovske table (od 1 do '); + WrCard(MaxDim, 1); + WrStr(') ------- '); + BrojKol:= RdCard(); + UNTIL OK AND (1 <= BrojKol) AND (BrojKol <= MaxDim); + REPEAT + WrLn; + WrStr('Unesite broj Vrsta sahovske table (od 1 do '); + WrCard(MaxDim, 1); + WrStr(') ------- '); + BrojVrs:= RdCard(); + UNTIL OK AND (1 <= BrojVrs) AND (BrojVrs <= MaxDim); + REPEAT + WrLn; + WrStr('Unesite broj kraljica (od 1 do '); + WrCard(BrojKol * BrojVrs, 1); + WrStr(') ------- '); + BrojKraljica:= RdCard(); + UNTIL OK AND (1 <= BrojKraljica) AND (BrojKraljica <= BrojKol * BrojVrs); + END Unos; + + PROCEDURE Postavi(VAR Stanje: StanjeTip); + VAR + Temp: PPolozaj; + BEGIN + WITH Stanje DO + Temp:= TekKra^.Kandidati; + TekKra^.Kandidati:= Temp^.Veza; + TekKra^.TekKo:= Temp^.Ko; + TekKra^.TekVr:= Temp^.Vr; + Cena:= Temp^.Cena; + DISPOSE(Temp); + END; + END Postavi; + + PROCEDURE Inicijalizacija(VAR Stanje: StanjeTip; VAR Br: CARDINAL); + VAR + Tek, Pom: PKraljica; + i: DomenBrojaKraljica; + BEGIN + Br:= 0; + WITH Stanje DO + Cena:= 0; + NEW(PrvaKra); + TekKra:= PrvaKra; + Tek:= PrvaKra; + Tek^.Pre:= NIL; + FOR i:= 2 TO BrojKraljica DO + Pom:= Tek; + NEW(Tek^.Sled); + Tek:= Tek^.Sled; + Tek^.Pre:= Pom; + END; + Tek^.Sled:= NIL; + END; + END Inicijalizacija; + + PROCEDURE Ispitaj(Ko, Vr: Indeks; Granica: PKraljica; VAR Stanje: StanjeTip; VAR Status: StatusTip); + VAR + Tek: PKraljica; + Jos: BOOLEAN; + BEGIN + WITH Stanje DO + Tek:= PrvaKra; + Jos:= Tek # Granica; + Status:= stSlobodno; + WHILE Jos DO + IF (Tek^.TekKo = Ko) AND (Tek^.TekVr = Vr) THEN + Status:= stZauzeto; + Jos:= FALSE; + ELSE + IF (Tek^.TekKo = Ko) OR (Tek^.TekVr = Vr) OR (ABS(Tek^.TekKo - Ko) = ABS(Tek^.TekVr - Vr)) THEN + Status:= stNapadnuto; + END; + IF Tek^.Sled= Granica THEN + Jos:= FALSE; + ELSE + Tek:= Tek^.Sled; + END; + END; + END; + END; + END Ispitaj; + + PROCEDURE Stampa(VAR Resenje: ResenjeTip); + CONST + ImeFajla = "Resenje.txt"; + VAR + Ko, Vr: Indeks; + Izlaz: FIO.File; + BEGIN + IF FIO.Exists(ImeFajla) THEN + Izlaz:= FIO.Append(ImeFajla); + ELSE + Izlaz:= FIO.Create(ImeFajla); + END; + WrLn; + WrStr('-----------------------------------------------------------------'); + WrStr('---------------'); + WrLn; + FIO.WrLn(Izlaz); + WrStr('Kraljice treba staviti na sledeca polja:'); + FIO.WrStr(Izlaz, 'Kraljice treba staviti na sledeca polja:'); + WrLn; + FIO.WrLn(Izlaz); + FOR Vr:= BrojVrs TO 1 BY -1 DO + WrLn; + FIO.WrLn(Izlaz); + FOR Ko:= 1 TO BrojKol DO + CASE Resenje.Poz[Ko, Vr] OF + stZauzeto: WrStr(' Q'); + FIO.WrStr(Izlaz, ' Q'); | + stNapadnuto: WrStr(' x'); + FIO.WrStr(Izlaz, ' x'); + ELSE + WrStr(' .'); + FIO.WrStr(Izlaz, ' .'); + END; + END; + END; + WrLn; + FIO.WrLn(Izlaz); + WrLn; + FIO.WrLn(Izlaz); + WrStr('Broj slobodnih polja je: '); + FIO.WrStr(Izlaz, 'Broj slobodnih polja je: '); + WrCard(BrojKol * BrojVrs - Resenje.Cena, 1); + FIO.WrCard(Izlaz, BrojKol * BrojVrs - Resenje.Cena, 1); + FIO.Close(Izlaz); + END Stampa; + + PROCEDURE Dame(BrojKol, BrojVrs: Indeks; BrojKraljica: DomenBrojaKraljica); + VAR + Stanje: StanjeTip; + Resenje: ResenjeTip; + MinCena: DomenCene; + Br: CARDINAL; + + PROCEDURE NadjiKandidate(VAR Stanje: StanjeTip); + + PROCEDURE NadjiCenu(k, v: Indeks; VAR Cena: DomenCene; VAR Stanje: StanjeTip); + VAR + Ko, Vr: Indeks; + Status: StatusTip; + BEGIN + Cena:= 0; + FOR Ko:= 1 TO BrojKol DO + FOR Vr:= 1 TO BrojVrs DO + IF (Ko # k) AND (Vr # v) AND (ABS(Ko - k) # ABS(Vr - v)) THEN + Ispitaj(Ko, Vr, Stanje.TekKra, Stanje, Status); + IF Status # stSlobodno THEN + INC(Cena); + END; + ELSE + INC(Cena); + END; + END; + END; + END NadjiCenu; + + PROCEDURE Ubaci(VAR Prvi, Novi: PPolozaj); + VAR + Tek: PPolozaj; + BEGIN + IF (Prvi = NIL) OR (Novi^.Cena < Prvi^.Cena) THEN + Novi^.Veza:= Prvi; + Prvi:= Novi; + ELSE + Tek:= Prvi; + WHILE (Tek^.Veza # NIL) AND (Tek^.Veza^.Cena < Novi^.Cena) DO + Tek:= Tek^.Veza; + END; + Novi^.Veza:= Tek^.Veza; + Tek^.Veza:= Novi; + END; + END Ubaci; + + VAR + k, v: Indeks; + Temp, Prvi: PPolozaj; + NovaCena: DomenCene; + Status: StatusTip; + PocKol, PocVrs: CARDINAL; + + BEGIN + Prvi:= NIL; + IF Stanje.TekKra = Stanje.PrvaKra THEN + PocKol:= 1; + ELSE + PocKol:= Stanje.TekKra^.Pre^.TekKo; + END; + FOR k:= PocKol TO BrojKol DO + IF (k = PocKol) AND (Stanje.TekKra # Stanje.PrvaKra) THEN + PocVrs:= Stanje.TekKra^.Pre^.TekVr + 1; + ELSE + PocVrs:= 1; + END; + FOR v:= PocVrs TO BrojVrs DO + NadjiCenu(k, v, NovaCena, Stanje); + IF NovaCena < MinCena THEN + NEW(Temp); + WITH Temp^ DO + Veza:= NIL; + Ko:= k; + Vr:= v; + Cena:= NovaCena; + END; + Ubaci(Prvi, Temp); + END; + END; + END; + Stanje.TekKra^.Kandidati:= Prvi; + END NadjiKandidate; + + PROCEDURE ZapamtiResenje(VAR Stanje: StanjeTip; VAR Resenje: ResenjeTip); + VAR + Ko, Vr: Indeks; + Status: StatusTip; + BEGIN + Resenje.Cena:= Stanje.Cena; + FOR Ko:= 1 TO BrojKol DO + FOR Vr:= 1 TO BrojVrs DO + Ispitaj(Ko, Vr, NIL, Stanje, Status); + Resenje.Poz[Ko, Vr]:= Status; + END; + END; + END ZapamtiResenje; + + BEGIN + Inicijalizacija(Stanje, Br); + MinCena:= BrojKol * BrojVrs + 1; + NadjiKandidate(Stanje); + WITH Stanje DO + WHILE TekKra # NIL DO + WHILE TekKra^.Kandidati # NIL DO + IF TekKra = PrvaKra THEN + INC(Br); + WrCard(Br, 4); + END; + Postavi(Stanje); + IF TekKra^.Sled = NIL THEN + IF Cena < MinCena THEN + MinCena:= Cena; + ZapamtiResenje(Stanje, Resenje); + END; + ELSE + TekKra:= TekKra^.Sled; + NadjiKandidate(Stanje); + END; + END; + TekKra:= TekKra^.Pre; + END; + Stampa(Resenje); + END; + END Dame; + +BEGIN + Unos(); + WrLn; + WrStr('Sacekajte !!!'); + WrLn; + Dame(BrojKol, BrojVrs, BrojKraljica); +END Queens. diff --git a/Cas11/RESENJE.TXT b/Cas11/RESENJE.TXT new file mode 100644 index 0000000..3b1c517 --- /dev/null +++ b/Cas11/RESENJE.TXT @@ -0,0 +1,8 @@ + +Kraljice treba staviti na sledeca polja: + + Q Q x + x Q x + x x . + +Broj slobodnih polja je: 1 \ No newline at end of file