X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa1-materijali.git;a=blobdiff_plain;f=kodovi%2Fsimulacija-rekurzije%2FRek1.java;fp=kodovi%2Fsimulacija-rekurzije%2FRek1.java;h=2cc562a1d797cbd2900d9e425fa0eaaa694728be;hp=0000000000000000000000000000000000000000;hb=97f70a20a007f00cc96c4c2beaac709cf5b79d87;hpb=06b67cca15377341d248c55dccff07d2738f60c6

diff --git a/kodovi/simulacija-rekurzije/Rek1.java b/kodovi/simulacija-rekurzije/Rek1.java
new file mode 100644
index 0000000..2cc562a
--- /dev/null
+++ b/kodovi/simulacija-rekurzije/Rek1.java
@@ -0,0 +1,106 @@
+/**
+ * Kompleksniji primer sa sukcesivnim pozivima.
+ * 
+ * Sama funkcija nalazi maksimum niza polovljenjem intervala, medjutim
+ * nije neophodno razumeti funkciju da bi se ona simulirala.
+ * 
+ * Funkcija je simulirana detaljno u skladu sa datim algoritmom, a naznacene
+ * su neke komande koje nisu bile neophodne da se navode posto nemaju efekta,
+ * no nije greska navesti ih.
+ * 
+ * Pazljivom analizom funkcionisanja originalne funkcije mozemo videti
+ * da polje m2 nema svrhe pamtiti na steku, posto se vrednost postavlja
+ * tek nakon poslednjeg poziva. Medjutim ni ovo nije greska da se navede
+ * u simuliranoj verziji jer ne utice na ispravnost programa.
+ */
+public class Rek1 {
+
+	static int[] niz;
+
+	static int max(int d, int g) {
+		System.out.println(String.format("%d %d",d,g));
+		if (d > g) {
+			return Integer.MIN_VALUE;
+		}
+		if (d == g) {
+			return niz[d];
+		}
+		int m1 = max(d, (d + g) / 2);
+		int m2 = max((d + g) / 2 + 1, g);
+		if (m1 > m2) {
+			return m1;
+		} else {
+			return m2;
+		}
+	}
+
+	private static class InfoTip {
+		int d, g, m1, m2, adr;
+	}
+
+	static int maxS(int d, int g) {
+		int rez;
+		int m1,m2;
+		InfoTip el;
+		Stek<InfoTip> s = new Stek<InfoTip>();
+		
+		do {
+			// rekurzivni spust
+			while (d < g) {
+				el = new InfoTip();
+				el.d = d;
+				el.g = g;
+				el.m1 = 0;//nije postavljeno jos
+				el.m2 = 0;//nije postavljeno jos
+				el.adr = 1;
+				s.stavi(el);
+				g = (d + g) / 2;
+			}
+
+			// trivijalni slucaj
+			if (d > g) {
+				rez = Integer.MIN_VALUE;
+			} else { // d == g
+				rez = niz[d];
+			}
+
+			// povratak iz rekurzije
+			boolean nemaPoziva = true;
+			while (!s.jePrazan() && nemaPoziva) {
+				el = s.skiniVrh();
+				d = el.d;
+				g = el.g;
+				m1 = el.m1;
+				m2 = el.m2;
+				if (el.adr == 1) {
+					m1 = rez;
+					el.m1 = m1;
+					el.adr = 2;
+					el.m2 = 0;//nije potrebno zapravo
+					el.d = d;//nije potrebno zapravo
+					el.g = g;//nije potrebno zapravo
+					s.stavi(el);
+					d = (d + g) / 2 + 1;
+					nemaPoziva = false;
+				} else { // adr je 2
+					m2 = rez;
+					if (m1 > m2) {
+						rez = m1;
+					} else {
+						rez = m2;
+					}
+				}
+			}
+		} while (!s.jePrazan());
+		
+		return rez;
+	}
+
+	public static void main(String[] args) {
+		niz = new int[] { 300, 2, 5, -7, 20, 66, 128 };
+
+		System.out.print(max(0, niz.length - 1));
+		System.out.print(" = ");
+		System.out.println(maxS(0, niz.length - 1));
+	}
+}