kodovi/simulacija-rekurzije/Rek1.java

   1 /**
   2  * Kompleksniji primer sa sukcesivnim pozivima.
   3  *
   4  * Sama funkcija nalazi maksimum niza polovljenjem intervala, medjutim
   5  * nije neophodno razumeti funkciju da bi se ona simulirala.
   6  *
   7  * Funkcija je simulirana detaljno u skladu sa datim algoritmom, a naznacene
   8  * su neke komande koje nisu bile neophodne da se navode posto nemaju efekta,
   9  * no nije greska navesti ih.
  10  *
  11  * Pazljivom analizom funkcionisanja originalne funkcije mozemo videti
  12  * da polje m2 nema svrhe pamtiti na steku, posto se vrednost postavlja
  13  * tek nakon poslednjeg poziva. Medjutim ni ovo nije greska da se navede
  14  * u simuliranoj verziji jer ne utice na ispravnost programa.
  15  */
  16 public class Rek1 {
  17
  18         static int[] niz;
  19
  20         static int max(int d, int g) {
  21                 System.out.println(String.format("%d %d",d,g));
  22                 if (d > g) {
  23                         return Integer.MIN_VALUE;
  24                 }
  25                 if (d == g) {
  26                         return niz[d];
  27                 }
  28                 int m1 = max(d, (d + g) / 2);
  29                 int m2 = max((d + g) / 2 + 1, g);
  30                 if (m1 > m2) {
  31                         return m1;
  32                 } else {
  33                         return m2;
  34                 }
  35         }
  36
  37         private static class InfoTip {
  38                 int d, g, m1, m2, adr;
  39         }
  40
  41         static int maxS(int d, int g) {
  42                 int rez;
  43                 int m1,m2;
  44                 InfoTip el;
  45                 Stek<InfoTip> s = new Stek<InfoTip>();
  46
  47                 do {
  48                         // rekurzivni spust
  49                         while (d < g) {
  50                                 el = new InfoTip();
  51                                 el.d = d;
  52                                 el.g = g;
  53                                 el.m1 = 0;//nije postavljeno jos
  54                                 el.m2 = 0;//nije postavljeno jos
  55                                 el.adr = 1;
  56                                 s.stavi(el);
  57                                 g = (d + g) / 2;
  58                         }
  59
  60                         // trivijalni slucaj
  61                         if (d > g) {
  62                                 rez = Integer.MIN_VALUE;
  63                         } else { // d == g
  64                                 rez = niz[d];
  65                         }
  66
  67                         // povratak iz rekurzije
  68                         boolean nemaPoziva = true;
  69                         while (!s.jePrazan() && nemaPoziva) {
  70                                 el = s.skiniVrh();
  71                                 d = el.d;
  72                                 g = el.g;
  73                                 m1 = el.m1;
  74                                 m2 = el.m2;
  75                                 if (el.adr == 1) {
  76                                         m1 = rez;
  77                                         el.m1 = m1;
  78                                         el.adr = 2;
  79                                         el.m2 = 0;//nije potrebno zapravo
  80                                         el.d = d;//nije potrebno zapravo
  81                                         el.g = g;//nije potrebno zapravo
  82                                         s.stavi(el);
  83                                         d = (d + g) / 2 + 1;
  84                                         nemaPoziva = false;
  85                                 } else { // adr je 2
  86                                         m2 = rez;
  87                                         if (m1 > m2) {
  88                                                 rez = m1;
  89                                         } else {
  90                                                 rez = m2;
  91                                         }
  92                                 }
  93                         }
  94                 } while (!s.jePrazan());
  95
  96                 return rez;
  97         }
  98
  99         public static void main(String[] args) {
 100                 niz = new int[] { 300, 2, 5, -7, 20, 66, 128 };
 101
 102                 System.out.print(max(0, niz.length - 1));
 103                 System.out.print(" = ");
 104                 System.out.println(maxS(0, niz.length - 1));
 105         }
 106 }