gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
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