UL/FRI/VSP-RI/OAPS2/HitriZapiski/2006-02-23:B-D

Skoči na: navigacija, iskanje

UL/FRI/VSP-RI/OAPS2

rekurzija - iteracija

• ADT sklad - LIFO
• repna rekurzija
• splošna shema
• primer permutacije

---

rekurzivna definicija:

novi pojem: znani pojmi + novi pojem

rekurzivna definicija obsega 2 dela:

• robni pogoj

definira novi pojem pri robni vrednosti nove spremenljivke

novipojem(o) = znani pojem

• splošni primer

definira novi pojem tako, da uporabi znane pojme + novi pojem, vendar pri vrednostih rekurzijske spremenljivke, ki so manjše od tiste katero definiramo

novipojem(n) = znanipojem + novipojem(n')

---

primer: definicija faktoriele

• robni primer

• splošni primer

rekurzivni algoritem, ki implementira zgornjo rekurzivno definicijo:

static public int f (int n) {
  if (n == 0) return 1
  else if (n > 0) return n * f(n-1);
}

---

rekurzivnih klicev je lahko več

primer problema ki zahteva 2 rekurzivna klica: hanoiski stolpi

imamo 3 palice na katere premikamo plošče, naloga je da prenesemo plošče iz prve na zadnjo tako, da nikoli ne preložimo večjo ploščo na manjšo ploščo - premikamo lahko samo po 1 ploščo naenkrat

n : a -> b

zadevo rešujemo tako, da poizkušamo nalogo razbiti na manjše podprobleme

najočitnejši podproblem je ta, da želimo premakniti največjega iz 1. na 2. palico - če jo želimo premakniti torej ne sme biti na 1. noben obroček razen največjega ker drugače največjega ne moremo dvigniti in na 2. ne sme biti nobenega, ker drugače nanj ne moremo premakniti največjega - torej želimo vse razen največjega premakniti na zadnjo palico

     |       |       |
     |       |      ###
  #######    |     #####
--------------------------

torej rešujemo problem, kako premakniti n-1 iz a na c ( n-1 : a-> c)

ko rešimo ta problem imamo problem enega - premakni iz a -> b (1 : a->b)

potem želimo premakniti vse iz c na b - (n-1 : c -> b)

Algoritem:

public class HanoiRek {
  public static void main (String[] args) {
    hanoi(3, 'A', 'B', 'C');
  }
 
  private static void hanoi (int n, char a, char b, char c) {
    if (n==1)
      System.out.println("Prestavi obroc s palice "+a+" na palico "+c);
    else {
      hanoi(n-1, a, c, b);
      hanoi(1, a, b, c);
      hanoi(n-1, b, a, c);
    }
  }
}

ali bolj teoretično:

static public void hanoi (char A, char B, char C, int n)
{
  if (n>0)  //robni primer
  {
    hanoi(A,C,B,n-1);
    izpis A -> B
    hanoi(C,B,A,n-1);
  }
}

---

Kako rekurzijo spremeniti v iteracijo?

Repno rekurzijo lahko trivialno spremenimo v iteracijo.

Repna rekurzija je rekurzivni klic, ki se zaključi takoj, ko se zaključi funkcija, ki je klicala rekurzivni klic.

Hanoiski stolpiči so delni primer repne rekurzije.

static public void hanoi (char A, char B, char C, int n)
{
  /*if (n>0)*/  //robni primer zamenjamo z:
  char T;
  while(n > 0)
  {
    hanoi(A,C,B,n-1);  //še vedno rekurzivno ker ni na repu
    izpis A -> B
    /*hanoi(C,B,A,n-1);*/  //zamenjamo z:
    T = A; A=C; C=T;
    n = n-1;
  }
}

---

dinamično programiranje

Dinam. prog. je reševanje problema od spodaj navzgor, ko iz rešitev enostavnih podproblemov sestavljamo rešitev težjih problemov.

To delamo tako da rešitve enostavnejših problemov shranjujemo in jih pri kasnejših klicih kompleksnejših problemov uporabimo.

---

Splošna sprememba iz rekurzije v iteracijo

Shraniti moramo stanje izvajanja, da ga lahko potem rekonstruiramo po rekurzivnem klicu:

Stanje izvajanja obsega:

• lokalne spremenljivke
• parametre
• pomnilniški naslov

Realizacija s skladom:

definiramo abstraktni podatkovni tip ADT:

definiramo programsko strukturo preko vmesnika - vmesnik ščiti podatkovno strukturo, da nimamo neposrednega dostopa in lahko dostopamo samo do smiselnih podatkov - s tem se izognemo največjemu številu programerskih napak

ker uporabljamo vmesnik, se nam tudi ni treba ukvarjati z implementacijo, zato lahko hitreje in učinkovitejše rešujemo probleme na višjem nivoju

deklariramo:

• makenull()

ustvarimo prazen sklad

• empty()

vrne boolean če je sklad prazen

• top()

vrne vrh sklada

• push(x,sklad)

postavi x na vrh sklada

• pop(sklad)

zbriše vrhnji element sklada

en element sklada (x) mora vsebovati vse kar obsega stanje izvajanja

---

splošna shema

v njej deklariramo kaj bomo dali na sklad - en element sklada

class StackElType {
  ArgsType args;
  locals VarType locals;
  int address; //0..RECCALLS = število rekurzivnih klicev
}

splošna rekurzivna procedura:

public void recursive(ArgsType args0) {
  LocalVarType locals0;
  if ( robniPogoj() ) sRobni;  //robni pogoj - robni stavki
    else { s0;
           recursive(args1);
           s1;
           recursive(args2);
           .
           .
           recursive(argsRECCALLS); 
           sRECCALLS;
         }

adrese nam povedo kam se moramo vrniti iz rekurzivnega klica

iteracija

kako iterativno implementiramo rekurzijo

public void iterative (ArgsType args0) {
  LocalVarType locals0;
  stack st = ...
  stackElType e;
  st.makenull();  //na zacetku je naš sklad prazen
  e.args = args0; //shranimo zacetne parametre v element
  e.aggress = 0;
  st.push(e);     //postavimo 1. element na sklad
  do {
    e = st.top(); st.pop();
    args0 = e.args; //rekonstruiranje stanja izvajanja
    locals0 = e.locals;
    switch(e.address) {
      case 0:
        if (robniPogoj()) sRobni;
        else {
          s0;
 
          //povratek
          e.address=1;
          e.args=args0;
          e.locals= locals0;
          st.push(e);
 
          //rekurzivni klic
          e.address = 0;
          e.args1;
          st.push(e);
      break;
      case i: //0 < i < RECCALLS
          si;
          e.address = it1;
          e.args = args0;
          e.locals = locals0;
          st.push(e);
          e.address=0;
          e.args = args_(i+1);
          st.push(e);
      break;
      case RECCALLS: sRECCALLS;
    } //switch
  while (!st.empty()) 
  } //iterative

---

primer razvoja algoritma - pretvorba iz rekurzije v iteracijo s pomočjo sklada

izpiši vse permutacije n števil

a[i] = i+1

a [1|2|       | n ]
   0,1,2,.....,n-1
   

permutacije [1,2,3]:

123

132

213

231

312

321

n! variant

permutacijo razvijemo tako, da fiksiramo en element in permutiramo vse ostale elemente

rekurzivni algoritem

static public void permRec(int n0) {
  int i;
  //robni primer
  if (n0==0) izpisPermutacije
  else {
  //rekurzija
    for( i=0; i < n; i++ ) {
      //en element fiksiramo
      zamenjaj(i,n0-1)
      permRec(n0-1);
    }
  }
}

iterativni algoritem

class StackEl {
  int n,i,address;
}
 
static public void permIt(int n0) {
  stack s = ... ;
  stackEl e;
  e.address=0;
  e.n=n0;
  s.push(e);
  do{
    e = s.top();
 
  switch(e.address) {
    case 0:
      if (e.n == 0) izpis
      else {
        e.i = 0;
        zamenjaj(e.i,e.n-1)
 
        //povratek
        e.address = 1;
        s.push(e);
 
        //rekurzivni klic
        e.address = 0;
        e.n = e.n - 1;
        e.push(e);
      }
      break;
    case 1:  //povratek iz rekurzivnega klica
      zamenjaj(e.i,e.n-1);
      e.i++;
      if(e.i < e.n) {
        zamenjaj(e.i,e.n-1)
        e.address=1;
        s.push(e);
        e.address=0;
        e.n=e.n-1;
        s.push(e);
      }
      break;
  } //switch
  } while(!s.empty())
}