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 (parent: 06b67cc)
raw | patch | inline | side by side (parent: 06b67cc)
| author | Doni Pracner <quinnuendo@gmail.com> | |
| Sat, 30 May 2015 11:01:49 +0000 (13:01 +0200) | ||
| committer | Doni Pracner <quinnuendo@gmail.com> | |
| Sat, 30 May 2015 11:01:49 +0000 (13:01 +0200) |
| kodovi/simulacija-rekurzije/Rek1.java | [new file with mode: 0644] | patch | blob |
| kodovi/simulacija-rekurzije/Rek2.java | [new file with mode: 0644] | patch | blob |
diff --git a/kodovi/simulacija-rekurzije/Rek1.java b/kodovi/simulacija-rekurzije/Rek1.java
--- /dev/null
@@ -0,0 +1,106 @@
+/**\r
+ * Kompleksniji primer sa sukcesivnim pozivima.\r
+ * \r
+ * Sama funkcija nalazi maksimum niza polovljenjem intervala, medjutim\r
+ * nije neophodno razumeti funkciju da bi se ona simulirala.\r
+ * \r
+ * Funkcija je simulirana detaljno u skladu sa datim algoritmom, a naznacene\r
+ * su neke komande koje nisu bile neophodne da se navode posto nemaju efekta,\r
+ * no nije greska navesti ih.\r
+ * \r
+ * Pazljivom analizom funkcionisanja originalne funkcije mozemo videti\r
+ * da polje m2 nema svrhe pamtiti na steku, posto se vrednost postavlja\r
+ * tek nakon poslednjeg poziva. Medjutim ni ovo nije greska da se navede\r
+ * u simuliranoj verziji jer ne utice na ispravnost programa.\r
+ */\r
+public class Rek1 {\r
+\r
+ static int[] niz;\r
+\r
+ static int max(int d, int g) {\r
+ System.out.println(String.format("%d %d",d,g));\r
+ if (d > g) {\r
+ return Integer.MIN_VALUE;\r
+ }\r
+ if (d == g) {\r
+ return niz[d];\r
+ }\r
+ int m1 = max(d, (d + g) / 2);\r
+ int m2 = max((d + g) / 2 + 1, g);\r
+ if (m1 > m2) {\r
+ return m1;\r
+ } else {\r
+ return m2;\r
+ }\r
+ }\r
+\r
+ private static class InfoTip {\r
+ int d, g, m1, m2, adr;\r
+ }\r
+\r
+ static int maxS(int d, int g) {\r
+ int rez;\r
+ int m1,m2;\r
+ InfoTip el;\r
+ Stek<InfoTip> s = new Stek<InfoTip>();\r
+ \r
+ do {\r
+ // rekurzivni spust\r
+ while (d < g) {\r
+ el = new InfoTip();\r
+ el.d = d;\r
+ el.g = g;\r
+ el.m1 = 0;//nije postavljeno jos\r
+ el.m2 = 0;//nije postavljeno jos\r
+ el.adr = 1;\r
+ s.stavi(el);\r
+ g = (d + g) / 2;\r
+ }\r
+\r
+ // trivijalni slucaj\r
+ if (d > g) {\r
+ rez = Integer.MIN_VALUE;\r
+ } else { // d == g\r
+ rez = niz[d];\r
+ }\r
+\r
+ // povratak iz rekurzije\r
+ boolean nemaPoziva = true;\r
+ while (!s.jePrazan() && nemaPoziva) {\r
+ el = s.skiniVrh();\r
+ d = el.d;\r
+ g = el.g;\r
+ m1 = el.m1;\r
+ m2 = el.m2;\r
+ if (el.adr == 1) {\r
+ m1 = rez;\r
+ el.m1 = m1;\r
+ el.adr = 2;\r
+ el.m2 = 0;//nije potrebno zapravo\r
+ el.d = d;//nije potrebno zapravo\r
+ el.g = g;//nije potrebno zapravo\r
+ s.stavi(el);\r
+ d = (d + g) / 2 + 1;\r
+ nemaPoziva = false;\r
+ } else { // adr je 2\r
+ m2 = rez;\r
+ if (m1 > m2) {\r
+ rez = m1;\r
+ } else {\r
+ rez = m2;\r
+ }\r
+ }\r
+ }\r
+ } while (!s.jePrazan());\r
+ \r
+ return rez;\r
+ }\r
+\r
+ public static void main(String[] args) {\r
+ niz = new int[] { 300, 2, 5, -7, 20, 66, 128 };\r
+\r
+ System.out.print(max(0, niz.length - 1));\r
+ System.out.print(" = ");\r
+ System.out.println(maxS(0, niz.length - 1));\r
+ }\r
+}\r
diff --git a/kodovi/simulacija-rekurzije/Rek2.java b/kodovi/simulacija-rekurzije/Rek2.java
--- /dev/null
@@ -0,0 +1,106 @@
+/**\r
+ * Kompleksniji primer u kome simuliramo funkciju cije funkcionisanje\r
+ * i rezultat nisu nuzno jasni.\r
+ * \r
+ * U funkciji postoje ugnjezdjeni pozivi na koje treba obratiti paznju.\r
+ * \r
+ * Ova verzija resenja takodje sadrzi i ispise parametara na 'ulazu' u\r
+ * funkciju, i iste takve kod simulirane verzije da se jasno vidi da se\r
+ * svi pozivi desavaju u istom redosledu, pri cemu su dodatno naznacene\r
+ * adrese poziva u simuliranoj verziji. Ovakav dodatak nije potreban inace\r
+ * za resavanje, ali moze pomoci u razumevanju i proveri da li je\r
+ * sve ispravno uradjeno.\r
+ */\r
+public class Rek2 {\r
+\r
+ static int g(int x, int y, int n) {\r
+ System.out.printf("0 %d %d %d\n",x,y,n);\r
+ if (n < 3) {\r
+ return x + y;\r
+ }\r
+\r
+ if (n % 2 == 1) {\r
+ return g(g(x + 1, y, n - 2), y, n - 3);\r
+ } else {\r
+ return g(x, g(x, y + 1, n - 2), n - 3);\r
+ }\r
+ }\r
+\r
+ private static class InfoTip {\r
+ int x, y, n, adr;\r
+ }\r
+\r
+ static int gS(int x, int y, int n) {\r
+ int rez;\r
+ InfoTip el;\r
+ Stek<InfoTip> s = new Stek<InfoTip>();\r
+ System.out.printf("%d %d %d %d\n",0,x,y,n);\r
+\r
+ do {\r
+ // rekurzivni spust\r
+ while (n >= 3) {\r
+ if (n % 2 == 1) {\r
+ el = new InfoTip();\r
+ el.x = x;\r
+ el.y = y;\r
+ el.n = n;\r
+ el.adr = 1;\r
+ s.stavi(el);\r
+ x = x + 1;\r
+ n = n - 2;\r
+ System.out.printf("%d %d %d %d\n",el.adr,x,y,n);\r
+ } else {\r
+ el = new InfoTip();\r
+ el.x = x;\r
+ el.y = y;\r
+ el.n = n;\r
+ el.adr = 3;\r
+ s.stavi(el);\r
+ y = y + 1;\r
+ n = n - 2;\r
+ System.out.printf("%d %d %d %d\n",el.adr,x,y,n);\r
+ }\r
+ }\r
+\r
+ // trivijalni slucaj\r
+ rez = x + y;\r
+\r
+ // povratak iz rekurzije\r
+ boolean nemaPoziva = true;\r
+ while (!s.jePrazan() && nemaPoziva) {\r
+ el = s.skiniVrh();\r
+ x = el.x;\r
+ y = el.y;\r
+ n = el.n;\r
+ if (el.adr == 1) {\r
+ el.x = x; // nije potrebno zapravo\r
+ el.y = y; // nije potrebno zapravo\r
+ el.n = n; // nije potrebno zapravo\r
+ el.adr = 2;\r
+ s.stavi(el);\r
+ x = rez;\r
+ n = n - 3;\r
+ System.out.printf("%d %d %d %d\n",el.adr,x,y,n);\r
+ nemaPoziva = false;\r
+ } else if (el.adr == 3) {\r
+ el.x = x; // nije potrebno zapravo\r
+ el.y = y; // nije potrebno zapravo\r
+ el.n = n; // nije potrebno zapravo\r
+ el.adr = 4;\r
+ s.stavi(el);\r
+ y = rez;\r
+ n = n - 3;\r
+ System.out.printf("%d %d %d %d\n",el.adr,x,y,n);\r
+ nemaPoziva = false;\r
+ } // adr 2 i 4\r
+ // rez = rez; nema smisla pisati\r
+ }\r
+ } while (!s.jePrazan());\r
+ return rez;\r
+ }\r
+\r
+ public static void main(String[] args) {\r
+ System.out.println(g(2, 3, 11));\r
+ System.out.println(gS(2, 3, 11));\r
+ }\r
+}\r