[Java] Rekursiv zu Iterativ

Smokers · 14. November 2012

Rekursiv zu Iterativ

Hi,

hier mal ein Problem aus der Algorithmik.

Ich habe eine Funktion :

Code:

f (a , b , c) == if a <= b 
then c + 1
else f (f (a - 1 , b , c) , f (b - 1 , c , a) , f (c - 1 , a , b)) 
;}

oder in Java:

Code:

 private static int deno (int a,int b, int c){
 int k;
 //##############################################################
 if(a<=b){
 k = c+1;
 }else {
 k = deno(deno(a-1,b,c),deno(b-1,c,a),deno(c-1,a,b));
 }
 //##############################################################
 System.out.println("Call: deno("+a+","+b+","+c+") = "+k);
 return k;
 }

Diese muss in einen iterativen Aufruf umgewandelt werden.

ich will nicht die Lösung haben, ich suche aber ein einfaches Paradigma mit dem man das ganze leichter lösen kann.

Für eine lineare Funktion, mit einemParameter ist das noch einfach (so war die Übungsaufgabe), dort betrachte ich mir mehr oder weniger den Kurvenverlauf und kann sagen
>>' if x < 8 then 10 else 11 '<< oder sonst wie,

aber bei der obigen Funktion?
Auch beim spielen mit den Funktionswerten gelingt mir nicht so richtig der Durchbruch...

Jemand eine Idee? Bitte wenn möglich NICHT die Lösung posten.

Danke

Anzeige

010100111001 · 17. November 2012

AW: Rekursiv zu Iterativ

f(a - 1 , b , c) , t (b - 1 , c , a) , t (c - 1 , a , b)

Anhand deines Java-Codes sollte dort anstelle von den 2 t jeweils ein f stehen, oder? Typo?

War mir nur so aufgefallen. Konkret weiterhelfen kann ich dir leider auch nicht, ist schon ziemlich unanschaulich die rekursive Funktion...

Smokers · 21. November 2012

AW: Rekursiv zu Iterativ

ohhh, entschuldigung ^^°
ja natürlich muss überall f(A,B,C ) stehen...also das war nen typo fehler bei mir, richtig.

danke dafür, ;-)

ich hab den Tipp bekommen ich solle es mir über ne größere Wertetabelle herleiten.... also weniger direkt über ersetzungen und bloßes grübeln, sondern über ne abschätzung...^^°

Code:

f(0,0,0)=1
f(0,0,1)=2
f(0,0,2)=3
f(0,0,3)=4
f(0,0,4)=5
f(0,1,0)=1
f(0,1,1)=2
f(0,1,2)=3
f(0,1,3)=4
f(0,1,4)=5
f(0,2,0)=1
f(0,2,1)=2
f(0,2,2)=3
f(0,2,3)=4
f(0,2,4)=5
f(0,3,0)=1
f(0,3,1)=2
f(0,3,2)=3
f(0,3,3)=4
f(0,3,4)=5
f(0,4,0)=1
f(0,4,1)=2
f(0,4,2)=3
f(0,4,3)=4
f(0,4,4)=5
f(1,0,0)=2
f(1,0,1)=2
f(1,0,2)=4
f(1,0,3)=4
f(1,0,4)=4
f(1,1,0)=1
f(1,1,1)=2
f(1,1,2)=3
f(1,1,3)=4
f(1,1,4)=5
f(1,2,0)=1
f(1,2,1)=2
f(1,2,2)=3
f(1,2,3)=4
f(1,2,4)=5
f(1,3,0)=1
f(1,3,1)=2
f(1,3,2)=3
f(1,3,3)=4
f(1,3,4)=5
f(1,4,0)=1
f(1,4,1)=2
f(1,4,2)=3
f(1,4,3)=4
f(1,4,4)=5
f(2,0,0)=2
f(2,0,1)=2
f(2,0,2)=5
f(2,0,3)=5
f(2,0,4)=5
f(2,1,0)=3
f(2,1,1)=3
f(2,1,2)=3
f(2,1,3)=5
f(2,1,4)=5
f(2,2,0)=1
f(2,2,1)=2
f(2,2,2)=3
f(2,2,3)=4
f(2,2,4)=5
f(2,3,0)=1
f(2,3,1)=2
f(2,3,2)=3
f(2,3,3)=4
f(2,3,4)=5
f(2,4,0)=1
f(2,4,1)=2
f(2,4,2)=3
f(2,4,3)=4
f(2,4,4)=5
f(3,0,0)=2
f(3,0,1)=2
f(3,0,2)=6
f(3,0,3)=6
f(3,0,4)=6
f(3,1,0)=3
f(3,1,1)=3
f(3,1,2)=3
f(3,1,3)=6
f(3,1,4)=6
f(3,2,0)=4
f(3,2,1)=4
f(3,2,2)=4
f(3,2,3)=4
f(3,2,4)=6
f(3,3,0)=1
f(3,3,1)=2
f(3,3,2)=3
f(3,3,3)=4
f(3,3,4)=5
f(3,4,0)=1
f(3,4,1)=2
f(3,4,2)=3
f(3,4,3)=4
f(3,4,4)=5
f(4,0,0)=2
f(4,0,1)=2
f(4,0,2)=7
f(4,0,3)=7
f(4,0,4)=7
f(4,1,0)=3
f(4,1,1)=3
f(4,1,2)=3
f(4,1,3)=7
f(4,1,4)=7
f(4,2,0)=4
f(4,2,1)=4
f(4,2,2)=4
f(4,2,3)=4
f(4,2,4)=7
f(4,3,0)=5
f(4,3,1)=5
f(4,3,2)=5
f(4,3,3)=5
f(4,3,4)=5
f(4,4,0)=1
f(4,4,1)=2
f(4,4,2)=3
f(4,4,3)=4
f(4,4,4)=5

hier mal der relevante teil :

Code:

f(1,0,0)=2
f(1,0,1)=2
f(1,0,2)=4
f(1,0,3)=4
f(1,0,4)=4
f(2,0,0)=2
f(2,0,1)=2
f(2,0,2)=5
f(2,0,3)=5
f(2,0,4)=5
f(2,1,0)=3
f(2,1,1)=3
f(2,1,2)=3
f(2,1,3)=5
f(2,1,4)=5
f(3,0,0)=2
f(3,0,1)=2
f(3,0,2)=6
f(3,0,3)=6
f(3,0,4)=6
f(3,1,0)=3
f(3,1,1)=3
f(3,1,2)=3
f(3,1,3)=6
f(3,1,4)=6
f(3,2,0)=4
f(3,2,1)=4
f(3,2,2)=4
f(3,2,3)=4
f(3,2,4)=6
f(4,0,0)=2
f(4,0,1)=2
f(4,0,2)=7
f(4,0,3)=7
f(4,0,4)=7
f(4,1,0)=3
f(4,1,1)=3
f(4,1,2)=3
f(4,1,3)=7
f(4,1,4)=7
f(4,2,0)=4
f(4,2,1)=4
f(4,2,2)=4
f(4,2,3)=4
f(4,2,4)=7
f(4,3,0)=5
f(4,3,1)=5
f(4,3,2)=5
f(4,3,3)=5
f(4,3,4)=5

Smokers · 21. November 2012

AW: Rekursiv zu Iterativ

Code:

public class Main {

 /**
 * @param args
 */
 public static void main(String[] args) {
 
 for (int i = 0; i < 5; i++) {
 for (int j = 0; j < 5; j++) {
 for (int j2 = 0; j2 < 5; j2++) {
 int z = f(i,j,j2);
 if (i>j){
 System.out.println("f("+i+","+j+","+j2+")="+z);
 }
 }
 }
 }
 }
 
 private static int f (int x,int y, int z){
 int k;
 //##############################################################
 if(x<=y){
 k = z+1;
 }else {
 k = f(f(x-1,y,z),f(y-1,z,x),f(z-1,x,y));
 }
 //##############################################################
 //System.out.println("Call: f("+x+","+y+","+z+") = "+k);
 return k;
 }

}

Is mein snippet zum obigen output
hab nur mal die parameter ein wenig gedreht

Code:

f(1,0,0)=2
f(1,0,1)=2
f(1,0,2)=4
f(1,0,3)=4
f(1,0,4)=4
f(2,0,0)=2
f(2,0,1)=2
f(2,0,2)=5
f(2,0,3)=5
f(2,0,4)=5
f(3,0,0)=2
f(3,0,1)=2
f(3,0,2)=6
f(3,0,3)=6
f(3,0,4)=6
f(4,0,0)=2
f(4,0,1)=2
f(4,0,2)=7
f(4,0,3)=7
f(4,0,4)=7
f(2,1,0)=3
f(2,1,1)=3
f(2,1,2)=3
f(2,1,3)=5
f(2,1,4)=5
f(3,1,0)=3
f(3,1,1)=3
f(3,1,2)=3
f(3,1,3)=6
f(3,1,4)=6
f(4,1,0)=3
f(4,1,1)=3
f(4,1,2)=3
f(4,1,3)=7
f(4,1,4)=7
f(3,2,0)=4
f(3,2,1)=4
f(3,2,2)=4
f(3,2,3)=4
f(3,2,4)=6
f(4,2,0)=4
f(4,2,1)=4
f(4,2,2)=4
f(4,2,3)=4
f(4,2,4)=7
f(4,3,0)=5
f(4,3,1)=5
f(4,3,2)=5
f(4,3,3)=5
f(4,3,4)=5

Code:

f(1,0,0)=2
f(2,0,0)=2
f(3,0,0)=2
f(4,0,0)=2
f(2,1,0)=3
f(3,1,0)=3
f(4,1,0)=3
f(3,2,0)=4
f(4,2,0)=4
f(4,3,0)=5
f(1,0,1)=2
f(2,0,1)=2
f(3,0,1)=2
f(4,0,1)=2
f(2,1,1)=3
f(3,1,1)=3
f(4,1,1)=3
f(3,2,1)=4
f(4,2,1)=4
f(4,3,1)=5
f(1,0,2)=4
f(2,0,2)=5
f(3,0,2)=6
f(4,0,2)=7
f(2,1,2)=3
f(3,1,2)=3
f(4,1,2)=3
f(3,2,2)=4
f(4,2,2)=4
f(4,3,2)=5
f(1,0,3)=4
f(2,0,3)=5
f(3,0,3)=6
f(4,0,3)=7
f(2,1,3)=5
f(3,1,3)=6
f(4,1,3)=7
f(3,2,3)=4
f(4,2,3)=4
f(4,3,3)=5
f(1,0,4)=4
f(2,0,4)=5
f(3,0,4)=6
f(4,0,4)=7
f(2,1,4)=5
f(3,1,4)=6
f(4,1,4)=7
f(3,2,4)=6
f(4,2,4)=7
f(4,3,4)=5

Nützliche Suchen

[Java] Rekursiv zu Iterativ

Videos zum Themenbereich