gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
summary | shortlog | log | commit | commitdiff | tree
raw | patch | inline | side by side (from parent 1: 2f27107)
raw | patch | inline | side by side (from parent 1: 2f27107)
| author | Doni Pracner <quinnuendo@gmail.com> | |
| Mon, 4 Dec 2017 15:58:10 +0000 (16:58 +0100) | ||
| committer | Doni Pracner <quinnuendo@gmail.com> | |
| Mon, 4 Dec 2017 15:58:10 +0000 (16:58 +0100) |
Klasa Resenje se sada zove Put, sto je tacnije za tumacenje
zadatka - ne mora uvek biti resenje, a uvek je put.
Klasa Polje je integrisana u Put.
Put je pojednostavljen, uklonjene su nebitne stvari koje
su samo uopstavale klasu za upotrebu van ovog programa.
Klasa Lavirint je ujedinjena sa NajboljiPut, tj main metod je sada zajedno
sa svim ostalima.
Skladistenje matrice i svih ostalih stanja je prebaceno u klasu NajboljiPut,
i vise ne postoji odvojena klasa Mapa koja je isto bila uopstenje koje se
moglo koristiti i van ovog programa, a nije bilo neophodno.
zadatka - ne mora uvek biti resenje, a uvek je put.
Klasa Polje je integrisana u Put.
Put je pojednostavljen, uklonjene su nebitne stvari koje
su samo uopstavale klasu za upotrebu van ovog programa.
Klasa Lavirint je ujedinjena sa NajboljiPut, tj main metod je sada zajedno
sa svim ostalima.
Skladistenje matrice i svih ostalih stanja je prebaceno u klasu NajboljiPut,
i vise ne postoji odvojena klasa Mapa koja je isto bila uopstenje koje se
moglo koristiti i van ovog programa, a nije bilo neophodno.
| PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java | [deleted file] | patch | blob | history |
| PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java | [deleted file] | patch | blob | history |
| PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java | patch | blob | history | |
| PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Polje.java | [deleted file] | patch | blob | history |
| PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Put.java | [new file with mode: 0644] | patch | blob |
| PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java | [deleted file] | patch | blob | history |
diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java
+++ /dev/null
@@ -1,88 +0,0 @@
-/**\r
- * Klasa Lavirint sadrzi nekoliko metoda za trazenje puteva.\r
- * \r
- * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore\r
- * koji se korste pri trazenju najkraceg i najvrednijeg puta.\r
- */\r
-\r
-import java.util.Comparator;\r
-\r
-public class Lavirint {\r
-\r
- // Polje m sadrzi kompletnu mapu\r
- private Mapa m;\r
- // Polje optResenje sluzi za pamcenje optimalnog resenja\r
- private Resenje optResenje;\r
-\r
- // Ucitava mapu iz datog fajla i stampa je na ekran\r
- Lavirint(String imeFajla) {\r
- m = Mapa.ucitajIzFajla(imeFajla);\r
- m.stampaj();\r
- }\r
-\r
- // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja\r
- // koristi komparator po duzini resenja, tj. trazi se najkrace resenje\r
- // Samo resenje kreira se u metodi optPut\r
- public Resenje najkraciPut(int x, int y) {\r
- Resenje r = new Resenje();\r
- optPut(x, y, r, new KomparatorPoDuzini());\r
- return optResenje;\r
- }\r
-\r
- // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja\r
- // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje\r
- // Samo resenje kreira se u metodi optPut\r
- public Resenje najvrednijiPut(int x, int y) {\r
- Resenje r = new Resenje();\r
- optPut(x, y, r, new KomparatorPoVredosti());\r
- return optResenje;\r
- }\r
-\r
- // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem\r
- // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u\r
- // optResenje\r
- // Optimalnost resenja se proverava komparatorom\r
- private void optPut(int x, int y, Resenje r, Comparator<Resenje> c) {\r
- if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {\r
- return;\r
- }\r
- if (m.getPos(x, y)) {\r
- return;\r
- }\r
- if (m.getMat(x, y) == Mapa.ZID) {\r
- return;\r
- }\r
- if (m.getMat(x, y) == Mapa.IZLAZ) {\r
- r.dodaj(x, y, 0);\r
- if (optResenje == null || c.compare(r, optResenje) < 0) {\r
- optResenje = r.kopija();\r
- }\r
- r.izbaciKraj();\r
- return;\r
- }\r
- \r
- // pokusavamo da trazimo dalje put\r
- m.setPos(x, y, true);\r
- r.dodaj(x, y, m.getMat(x, y));\r
- optPut(x + 1, y, r, c);\r
- optPut(x, y + 1, r, c);\r
- optPut(x, y - 1, r, c);\r
- optPut(x - 1, y, r, c);\r
- m.setPos(x, y, false);\r
- r.izbaciKraj();\r
- }\r
-}\r
-\r
-// Komparator za resenja po duzini resenja\r
-class KomparatorPoDuzini implements Comparator<Resenje> {\r
- public int compare(Resenje r1, Resenje r2) {\r
- return r1.getLength() - r2.getLength();\r
- }\r
-}\r
-\r
-// Komparator za resenja po vrednosti resenja\r
-class KomparatorPoVredosti implements Comparator<Resenje> {\r
- public int compare(Resenje r1, Resenje r2) {\r
- return r2.getVrednost() - r1.getVrednost();\r
- }\r
-}
\ No newline at end of file
diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java
+++ /dev/null
@@ -1,89 +0,0 @@
-public class Mapa {\r
- public final static int IZLAZ = -99;\r
- public final static int ZID = -11;\r
- public final static int ERROR = Integer.MIN_VALUE;\r
-\r
- private int visina, sirina;\r
- private int[][] mat;\r
- private boolean[][] pos;\r
-\r
- public int getSirina() {\r
- return sirina;\r
- }\r
-\r
- public int getVisina() {\r
- return visina;\r
- }\r
-\r
- public void setPos(int x, int y, boolean b) {\r
- if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
- pos[x][y] = b;\r
- }\r
- }\r
-\r
- public boolean getPos(int x, int y) {\r
- if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
- return pos[x][y];\r
- } else {\r
- return true;\r
- }\r
- }\r
-\r
- public int getMat(int x, int y) {\r
- if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
- return mat[x][y];\r
- } else {\r
- return ERROR;\r
- }\r
- }\r
-\r
- public Mapa(int sirina, int visina) {\r
- this.sirina = sirina;\r
- this.visina = visina;\r
- mat = new int[sirina][visina];\r
- pos = new boolean[sirina][visina];\r
- }\r
-\r
- public Mapa(String imeFajla) {\r
- if (!Svetovid.testIn(imeFajla)) {\r
- throw new RuntimeException("Fajl za kreiranje mape ("\r
- + imeFajla + ") nije prisupacan");\r
- }\r
-\r
- sirina = Svetovid.in(imeFajla).readInt();\r
- visina = Svetovid.in(imeFajla).readInt();\r
- mat = new int[sirina][visina];\r
- pos = new boolean[sirina][visina];\r
- for (int j = 0; j < visina; j++) {\r
- for (int i = 0; i < sirina; i++) {\r
- mat[i][j] = Svetovid.in(imeFajla).readInt();\r
- }\r
- }\r
- Svetovid.closeIn(imeFajla);\r
- }\r
-\r
- public static Mapa ucitajIzFajla(String imeFajla) {\r
- if (!Svetovid.testIn(imeFajla)) {\r
- return null;\r
- }\r
- \r
- return new Mapa(imeFajla);\r
-\r
- }\r
-\r
- public void stampaj() {\r
- if (visina != 0 && sirina != 0) {\r
- System.out.println(visina + " " + sirina);\r
- for (int j = 0; j < visina; j++) {\r
- for (int i = 0; i < sirina; i++) {\r
- System.out.print(mat[i][j] + "\t");\r
- }\r
- System.out.println();\r
- }\r
- }\r
- }\r
- \r
- public String toString() {\r
- return "Mapa velicine " + sirina + " x " + visina;\r
- }\r
-}\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java
+\r
/**\r
- * Program za nalazenje puta u lavirintu.\r
+ * Klasa NajboljiPut sadrzi nekoliko metoda za trazenje puteva.\r
* \r
- * Date su dva varijante problema optimalnog puta, najkraci\r
- * put i najvredniji put.\r
+ * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore\r
+ * koji se korste pri trazenju najkraceg i najvrednijeg puta.\r
*/\r
\r
+import java.util.Comparator;\r
+\r
public class NajboljiPut {\r
\r
+ // Konstante za polja u mapi\r
+ public final static int IZLAZ = -99;\r
+ public final static int ZID = -11;\r
+\r
+ // interno predstavljanje mape\r
+ private int visina, sirina;\r
+ private int[][] mat;\r
+ // matrica posecenih polja\r
+ private boolean[][] pos;\r
+\r
+ // Polje optResenje sluzi za pamcenje optimalnog resenja\r
+ private Put optResenje;\r
+\r
+ // Ucitava mapu iz datog fajla i stampa je na ekran\r
+ NajboljiPut(String imeFajla) {\r
+ if (!Svetovid.testIn(imeFajla)) {\r
+ throw new RuntimeException("Fajl za kreiranje mape (" + imeFajla + ") nije prisupacan");\r
+ }\r
+\r
+ sirina = Svetovid.in(imeFajla).readInt();\r
+ visina = Svetovid.in(imeFajla).readInt();\r
+ mat = new int[sirina][visina];\r
+ pos = new boolean[sirina][visina];\r
+ for (int j = 0; j < visina; j++) {\r
+ for (int i = 0; i < sirina; i++) {\r
+ mat[i][j] = Svetovid.in(imeFajla).readInt();\r
+ }\r
+ }\r
+ Svetovid.closeIn(imeFajla);\r
+\r
+ stampajMapu();\r
+ }\r
+\r
+ private void stampajMapu() {\r
+ if (visina > 0 && sirina > 0) {\r
+ System.out.println(visina + " " + sirina);\r
+ for (int j = 0; j < visina; j++) {\r
+ for (int i = 0; i < sirina; i++) {\r
+ System.out.print(mat[i][j] + "\t");\r
+ }\r
+ System.out.println();\r
+ }\r
+ }\r
+ }\r
+\r
+ // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja\r
+ // koristi komparator po duzini resenja, tj. trazi se najkrace resenje\r
+ // Samo resenje kreira se u metodi optPut\r
+ public Put najkraciPut(int x, int y) {\r
+ Put r = new Put();\r
+ optPut(x, y, r, new KomparatorPoDuzini());\r
+ return optResenje;\r
+ }\r
+\r
+ // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja\r
+ // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje\r
+ // Samo resenje kreira se u metodi optPut\r
+ public Put najvrednijiPut(int x, int y) {\r
+ Put r = new Put();\r
+ optPut(x, y, r, new KomparatorPoVredosti());\r
+ return optResenje;\r
+ }\r
+\r
+ // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem\r
+ // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u\r
+ // optResenje\r
+ // Optimalnost resenja se proverava komparatorom\r
+ private void optPut(int x, int y, Put r, Comparator<Put> c) {\r
+ if (x < 0 || x >= sirina || y < 0 || y >= visina) {\r
+ return;\r
+ }\r
+ if (pos[x][y]) {\r
+ return;\r
+ }\r
+ if (mat[x][y] == ZID) {\r
+ return;\r
+ }\r
+ if (mat[x][y] == IZLAZ) {\r
+ r.dodaj(x, y, 0);\r
+ if (optResenje == null || c.compare(r, optResenje) < 0) {\r
+ optResenje = r.kopija();\r
+ }\r
+ r.izbaciKraj();\r
+ return;\r
+ }\r
+\r
+ // pokusavamo da trazimo dalje put\r
+ pos[x][y] = true;\r
+ r.dodaj(x, y, mat[x][y]);\r
+ optPut(x + 1, y, r, c);\r
+ optPut(x, y + 1, r, c);\r
+ optPut(x, y - 1, r, c);\r
+ optPut(x - 1, y, r, c);\r
+ pos[x][y] = false;\r
+ r.izbaciKraj();\r
+ }\r
+\r
public static void main(String[] args) {\r
Svetovid.out.println("Unesite ime fajla: ");\r
String fajl = Svetovid.in.readLine();\r
return;\r
}\r
\r
- Lavirint l = new Lavirint(fajl);\r
- Resenje r;\r
+ NajboljiPut l = new NajboljiPut(fajl);\r
+ Put r;\r
\r
System.out.println("Unesite koordinate za pocetak:");\r
System.out.println("x?");\r
System.out.println("Nema resenja");\r
}\r
}\r
+}\r
+\r
+// Komparator za resenja po duzini resenja\r
+class KomparatorPoDuzini implements Comparator<Put> {\r
+ public int compare(Put r1, Put r2) {\r
+ return r1.getLength() - r2.getLength();\r
+ }\r
+}\r
+\r
+// Komparator za resenja po vrednosti resenja\r
+class KomparatorPoVredosti implements Comparator<Put> {\r
+ public int compare(Put r1, Put r2) {\r
+ return r2.getVrednost() - r1.getVrednost();\r
+ }\r
}
\ No newline at end of file
diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Polje.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Polje.java
+++ /dev/null
@@ -1,30 +0,0 @@
-/**\r
- * Klasa Polje se koristi za pamcenje x i y koordinata nekog polja, kao i\r
- * vrednosti na toj poziciji u mapi\r
- */\r
-\r
-public class Polje {\r
- private int x, y, v;\r
-\r
- Polje(int x, int y, int v) {\r
- this.x = x;\r
- this.y = y;\r
- this.v = v;\r
- }\r
-\r
- public int getX() {\r
- return x;\r
- }\r
-\r
- public int getY() {\r
- return y;\r
- }\r
-\r
- public int getV() {\r
- return v;\r
- }\r
-\r
- public String toString() {\r
- return x + " " + y + " " + v;\r
- }\r
-}
\ No newline at end of file
diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Put.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Put.java
--- /dev/null
@@ -0,0 +1,113 @@
+\r
+/**\r
+ * Klasa Put koristi se za pamcenje pronadjenog puta.\r
+ * \r
+ * Polje Polja se koristi za pamcenje svih polja na putu.\r
+ * \r
+ */\r
+import java.util.ArrayList;\r
+\r
+public class Put {\r
+ private ArrayList<Polje> polja;\r
+\r
+ public Put() {\r
+ polja = new ArrayList<Polje>();\r
+ }\r
+\r
+ /**\r
+ * Pravi novo resenje sa istim sadrzajem kao original\r
+ */\r
+ public Put(Put original) {\r
+ // pozovemo "podrazumevani" konstruktor\r
+ this();\r
+ // iskopiramo sva polja iz originala\r
+ for (Polje p : original.polja) {\r
+ dodaj(p.getX(), p.getY(), p.getV());\r
+ }\r
+ }\r
+\r
+ // Dodaje pulje u resenje\r
+ public void dodaj(int x, int y, int v) {\r
+ polja.add(new Polje(x, y, v));\r
+ }\r
+\r
+ // Izbacuje polje iz resenja\r
+ public void izbaciKraj() {\r
+ if (getLength() > 0) {\r
+ polja.remove(getLength() - 1);\r
+ } else {\r
+ System.err.println("greska: resenje je vec prazno");\r
+ }\r
+ }\r
+\r
+ // Stampa resenje\r
+ public void stampaj() {\r
+ System.out.println(getLength());\r
+ for (int i = 0; i < getLength(); i++)\r
+ System.out.println(polja.get(i));\r
+ }\r
+\r
+ public String toString() {\r
+ StringBuilder sb = new StringBuilder();\r
+ sb.append("Resenje: [ ");\r
+ if (getLength() > 0) {\r
+ sb.append(polja.get(0));\r
+ for (int i = 1; i < getLength(); i++) {\r
+ sb.append(", " + polja.get(i));\r
+ }\r
+ }\r
+ sb.append(" ]");\r
+\r
+ return sb.toString();\r
+ }\r
+\r
+ // Vraca duzinu resenja\r
+ public int getLength() {\r
+ return polja.size();\r
+ }\r
+\r
+ // Kreira nezavisnu kopiju ovog resenja\r
+ public Put kopija() {\r
+ Put rez = new Put();\r
+ for (Polje p : polja) {\r
+ rez.dodaj(p.getX(), p.getY(), p.getV());\r
+ }\r
+ return rez;\r
+ }\r
+\r
+ // Vraca vrednost puta\r
+ // Vrednost se definise kao zbir svih vrednosti polja na putu\r
+ public int getVrednost() {\r
+ int rez = 0;\r
+ for (Polje p : polja) {\r
+ rez = rez + p.getV();\r
+ }\r
+ return rez;\r
+ }\r
+\r
+ public class Polje {\r
+ private int x, y, v;\r
+\r
+ Polje(int x, int y, int v) {\r
+ this.x = x;\r
+ this.y = y;\r
+ this.v = v;\r
+ }\r
+\r
+ public int getX() {\r
+ return x;\r
+ }\r
+\r
+ public int getY() {\r
+ return y;\r
+ }\r
+\r
+ public int getV() {\r
+ return v;\r
+ }\r
+\r
+ public String toString() {\r
+ return x + " " + y + " " + v;\r
+ }\r
+ }\r
+}\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java
+++ /dev/null
@@ -1,105 +0,0 @@
-/**\r
- * Klasa Resenje koristi se za pamcenje pronadjenog puta.\r
- * \r
- * Polje Polja se koristi za pamcenje svih polja na putu.\r
- * \r
- * Polje nepromenljivaListaPolja je dodata da se omoguci\r
- * pristup poljima resenja "spolja" (za proveru kvaliteta puta na primer), \r
- * ali tako da ne moze da se utice na sam sadrzaj te liste.\r
- */\r
-import java.util.ArrayList;\r
-import java.util.List;\r
-import java.util.Collections;\r
-\r
-public class Resenje {\r
- private ArrayList<Polje> polja;\r
- private List<Polje> nepromenljivaListaPolja;\r
-\r
- public Resenje() {\r
- polja = new ArrayList<Polje>();\r
- nepromenljivaListaPolja = Collections.unmodifiableList(polja);\r
- }\r
- \r
- /**\r
- Pravi novo resenje sa istim sadrzajem kao original\r
- */\r
- public Resenje(Resenje original) {\r
- // pozovemo "podrazumevani" konstruktor\r
- this();\r
- // iskopiramo sva polja iz originala\r
- for (Polje p : original.getPolja()) {\r
- dodaj(p.getX(), p.getY(), p.getV());\r
- }\r
- }\r
-\r
- // Dodaje pulje u resenje\r
- public void dodaj(int x, int y, int v) {\r
- polja.add(new Polje(x, y, v));\r
- }\r
-\r
- // Izbacuje polje iz resenja\r
- public void izbaciKraj() {\r
- if (getLength() > 0) {\r
- polja.remove(getLength() - 1);\r
- } else {\r
- System.err.println("greska: resenje je vec prazno");\r
- }\r
- }\r
-\r
- // Stampa resenje\r
- public void stampaj() {\r
- System.out.println(getLength());\r
- for (int i = 0; i < getLength(); i++)\r
- System.out.println(polja.get(i));\r
- }\r
- \r
- public String toString() {\r
- StringBuilder sb = new StringBuilder();\r
- sb.append("Resenje: [ ");\r
- if (getLength()>0) {\r
- sb.append(polja.get(0));\r
- for (int i = 1; i < getLength(); i++) {\r
- sb.append(", " + polja.get(i));\r
- }\r
- }\r
- sb.append(" ]");\r
- \r
- return sb.toString();\r
- }\r
-\r
- // Vraca duzinu resenja\r
- public int getLength() {\r
- return polja.size();\r
- }\r
-\r
- // Vraca i-to polje na putu. Ne koristi se u ovoj verziji zadatka.\r
- // Moze se koristiti za proveru kvaliteta resenja\r
- public Polje getPolje(int i) {\r
- return polja.get(i);\r
- }\r
-\r
- // Vraca sva polja na putu. Ne koristi se u ovoj verziji zadatka.\r
- // Moze se koristiti za proveru kvaliteta resenja\r
- public List<Polje> getPolja() {\r
- return nepromenljivaListaPolja;\r
- }\r
-\r
- // Kreira nezavisnu kopiju ovog resenja\r
- public Resenje kopija() {\r
- Resenje rez = new Resenje();\r
- for (Polje p : polja) {\r
- rez.dodaj(p.getX(), p.getY(), p.getV());\r
- }\r
- return rez;\r
- }\r
-\r
- // Vraca vrednost puta\r
- // Vrednost se definise kao zbir svih vrednosti polja na putu\r
- public int getVrednost() {\r
- int rez = 0;\r
- for (Polje p : polja) {\r
- rez = rez + p.getV();\r
- }\r
- return rez;\r
- }\r
-}\r