From: Doni Pracner <quinnuendo@gmail.com>
Date: Mon, 21 Oct 2013 12:50:01 +0000 (+0200)
Subject: 02 - XDS verzije
X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-teorijske-vezbe.git;a=commitdiff_plain;h=bcfa13cb2167d46a110fe6aa3d8e4ef541b37a2e

02 - XDS verzije
---

diff --git a/02. Podslika/XDS/MALA.SLI b/02. Podslika/XDS/MALA.SLI
new file mode 100644
index 0000000..a05cae8
--- /dev/null
+++ b/02. Podslika/XDS/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/02. Podslika/XDS/PODSLIKA.MOD b/02. Podslika/XDS/PODSLIKA.MOD
new file mode 100644
index 0000000..5310154
--- /dev/null
+++ b/02. Podslika/XDS/PODSLIKA.MOD	
@@ -0,0 +1,168 @@
+MODULE Podslika;
+
+  FROM FIO IMPORT
+    File, Open, Close, RdCard, EOF, 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
+    
+    Slika = ARRAY [1 .. MaxDim], [1 .. MaxDim] OF CARDINAL;
+
+  VAR
+    Velika, Mala: Slika;
+    DimVel, DimMal, Vr, Ko: CARDINAL;
+    KljucMale, KljucSegmenta, Stepen: CARDINAL;
+    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): CARDINAL;
+    VAR
+      i, j: CARDINAL;
+      Kljuc, ZbirKolone, Temp: CARDINAL;
+  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 + (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: CARDINAL);
+    VAR
+      j: CARDINAL;
+      ZbirKolone, Temp: CARDINAL;
+  BEGIN
+
+    ZbirKolone:= 0;
+    FOR j:= Vr TO Vr + DimMal - 1 DO
+      ZbirKolone:= ZbirKolone + (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 + (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/02. Podslika/XDS/VELIKA.SLI b/02. Podslika/XDS/VELIKA.SLI
new file mode 100644
index 0000000..050166c
--- /dev/null
+++ b/02. Podslika/XDS/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