• Wir präsentieren Dir heute ein Stellenangebot für einen Java Entwickler - m/w/d in Augsburg, München, Stuttgart oder Bamberg. Hier geht es zur Jobanzeige

Rekursion Funktion in eine Iterativ Funktion umwandeln

A

AClassyWarius

Mitglied
Hallo, ich komme gerade an einer Klausur Aufgabe überhaupt nicht weiter, ich soll eine rekursive Funktion in eine Iterative Funktion durch dynamisches Programmieren umschreiben.
a für b = 0
f(a,b) = b für a = 0
f(a - 1, b) + f(a, b-1) für a > 0 , b > 0

wäre echt genial wenn mir jemand einen kleinen Denkanstoß geben könnte, hab schon mehrere Wege versucht aber klappt einfach nicht.


Java:
public int getF(int a, int b) {
        if (b == 0) {
            return a;
        } else if (a == 0) {
            return b;
        } else if (a > 0 & b > 0) {
            return getF(a - 1, b) + getF(a, b - 1);
        }
        return -1;
    }
 
JCODA

JCODA

Top Contributor
Naja bei dynamischer Programmierung verwendet man ja meinst ein Array, um Teilergebnisse abzuspeichern. Dann benötigt man noch ein Verfahren, um das Array zu befüllen, aber dies ergibt sich meist einfach aus der Funktionsvorschrift, indem man sich anschaut, von welcher "Seite" man das Array ausrechnen kann. Zeichne dir hierfür am besten eine kleine Skizze für a=b=5 oder so.
 
A

AClassyWarius

Mitglied
ich hab mir schon aufrufsbäume aufgezeichnet, leider hat es mir nicht viel gebracht.
 
JCODA

JCODA

Top Contributor
Ich habe es mal implementiert, so sieht das Gerüst aus:

Java:
public static int getFIter(int a, int b) {
        int mem[][] = new int[a + 1][b + 1];
        //TODO fill mem
        return mem[a][b];
    }

Welche Stellen von mem kann man sofort ausfüllen?
Welche kann man danach füllen?
 
A

AClassyWarius

Mitglied
naja wenn a = 0, dann ist mem, wenn b = 0 ist mem[a][a] wenn a >0 , b > 0 dann ist mem[a-1] + mem[a][b-1] ? ^^

aber danke für den Ansatz
 
A

AClassyWarius

Mitglied
Java:
public static int getFIterativ(int a, int b) {
        int [][] memory = new int [a + 1][b + 1];
        memory[0][1] = 1;
        memory[1][0] = 1;
        for(int i = 1; i <= a; i++) {
            for(int j = 1; j <= b; j++) {
                memory[i][j] = memory[i-1][j] + memory[i][j-1];
            }
        }
        return memory [a][b];
    }

aber etwas passt noch nicht ganz
 
A

AClassyWarius

Mitglied
Java:
public static int getFIterativ(int a, int b) {
        int [][] memory = new int [a + 1][b + 1];
        memory[a][0] = a;
        memory[0][b] = b;
        for(int i = 1; i <= a; i++) {
            for(int j = 1; j <= b; j++) {
                memory[i][j] = memory[i-1][j] + memory[i][j-1];
            }
        }
        return memory [a][b];
    }


also für getF(1,3) = 7 aber ich bekomme nur 4 raus, leider finde ich den Fehler nicht -.-
 
JCODA

JCODA

Top Contributor
Java:
public class DynProg {

    public static void main(String[] args) {
        for (int a = 0; a < 10; a++) {
            for (int b = 0; b < 10; b++) {
                System.out.println("f(" + a + "," + b + ") = " + getFRec(a, b) + " : " + getFIter(a, b));
            }
        }
    }

    public static int getFIter(int a, int b) {
        int mem[][] = new int[a + 1][b + 1];
        /*for (int i = 0; i <= a; i++) {
            mem[i][0] = i;
        }
        for (int i = 0; i <= b; i++) {
            mem[0][i] = i;
        }*/
        for (int aa = 0; aa <= a; aa++) {
            for (int bb = 0; bb <= b; bb++) {
                if(aa == 0){
                    mem[aa][bb] = bb;
                }else if(bb==0){
                    mem[aa][bb] = aa;
                }else{
                    mem[aa][bb] = mem[aa - 1][bb] + mem[aa][bb - 1];
                }
            }
        }
        return mem[a][b];
    }

    public static int getFRec(int a, int b) {
        if (b == 0) {
            return a;
        } else if (a == 0) {
            return b;
        } else if (a > 0 & b > 0) {
            return getFRec(a - 1, b) + getFRec(a, b - 1);
        }
        return -1;
    }
}

Zunächst dachte ich, das einkommentierte wird benötigt, dann ist mir aufgefallen, wenn die Schleife mit 0 beginnt, klappt alles trotzdem. Das sieht jetzt sehr kompakt und "einfach" aus, aber bedenke, dass es nur funktioniert, weil ein "zeilenweises" Auffüllen von unten nach oben speziell -hier- funktioniert. Das mag bei anderen Problemen komplizierter sein.
 
A

AClassyWarius

Mitglied
tausend dank, durch deine Hilfe hab ich es endlich verstanden ;) da kann die Klausur morgen ja kommen :D
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
T Rekursion Warum bricht meine Funktion nicht ab Java Basics - Anfänger-Themen 4
G Rekursion als FUNKTION Java Basics - Anfänger-Themen 3
V Backtracking und Rekursion Java Basics - Anfänger-Themen 15
L REKURSION Java Basics - Anfänger-Themen 13
Kirby.exe Rekursion Java Basics - Anfänger-Themen 7
N for Schleife durch Rekursion ersetzen Java Basics - Anfänger-Themen 6
X Rekursion Java Basics - Anfänger-Themen 3
H Rekursion Java Basics - Anfänger-Themen 2
D Erste Schritte Rekursion Java Basics - Anfänger-Themen 13
M Rekursion Tage Ansteckung gesamte Bevölkerung Java Basics - Anfänger-Themen 15
M Java Rekursion Java Basics - Anfänger-Themen 9
G Java Rekursion Java Basics - Anfänger-Themen 5
J Rekursion Klausur Aufgabe Java Basics - Anfänger-Themen 2
N Rekursion Java Basics - Anfänger-Themen 18
M Verständnisproblem der Rekursion bei Arrays Java Basics - Anfänger-Themen 8
X Rekursion Rätsel Java Basics - Anfänger-Themen 4
N Klassen Rekursion mit Feldern von Objekten Java Basics - Anfänger-Themen 14
W Rekursion Java Basics - Anfänger-Themen 0
D Konsolenausgabe Zahlenfolge Rekursion Java Basics - Anfänger-Themen 3
J Ping Pong Methode mit Rekursion Java Basics - Anfänger-Themen 1
N Rekursion Java Basics - Anfänger-Themen 1
B Rekursion Basic Java Basics - Anfänger-Themen 15
O Rekursion Mergesort Java Basics - Anfänger-Themen 18
G Rekursion Java Basics - Anfänger-Themen 20
M Rekursion Java Basics - Anfänger-Themen 7
F Hilfe bei Rekursion... Java Basics - Anfänger-Themen 4
A Mit Rekursion Zufallszahlen erstellen und größte finden Java Basics - Anfänger-Themen 5
B Rekursion Wurzel Java Basics - Anfänger-Themen 39
O Rekursion ordentlich aufschreiben Java Basics - Anfänger-Themen 2
B Rekursion verstehen Java Basics - Anfänger-Themen 4
O Rekursion Java Basics - Anfänger-Themen 2
E Rekursion verstehen. Java Basics - Anfänger-Themen 4
E Rekursion Kisten befüllen Java Basics - Anfänger-Themen 10
E Rekursion verstehen Java Basics - Anfänger-Themen 2
O Rekursion, String Java Basics - Anfänger-Themen 8
N Invertierte Rekursion??? Java Basics - Anfänger-Themen 5
M Bitte um Hilfe bei Quellcode (Rekursion) Java Basics - Anfänger-Themen 6
A Hilfe bei Rekursion,Ich verstehe nicht,wie funktioniert die Rekursion in der Methode "walk" Java Basics - Anfänger-Themen 13
L Rekursion im Baum Java Basics - Anfänger-Themen 9
E Pfade eines Baums angeben ohne Rekursion Java Basics - Anfänger-Themen 20
L Rekursion Baumknoten Java Basics - Anfänger-Themen 8
L Rekursion größtes Zeichen Java Basics - Anfänger-Themen 8
L Rekursion Modulo Java Basics - Anfänger-Themen 7
I Rekursion Java Basics - Anfänger-Themen 11
H Rekursion Java Basics - Anfänger-Themen 7
N Methoden zur Rekursion (catalansche Zahlen) Java Basics - Anfänger-Themen 4
S Frage zu Rekursion... Java Basics - Anfänger-Themen 15
N Java catalansche Zahlen (Rekursion) Java Basics - Anfänger-Themen 5
S Noch eine Frage zur Rekursion... Java Basics - Anfänger-Themen 11
S Frage zu einer Rekursion Java Basics - Anfänger-Themen 15
F Methoden Abbruchbedingung bei Rekursion Java Basics - Anfänger-Themen 2
Z Rekursion Primzahlen Java Basics - Anfänger-Themen 1
K Rekursion Verständnisfrage Java Basics - Anfänger-Themen 19
L Methoden Rekursion gibt alten Wert wieder Java Basics - Anfänger-Themen 37
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Rekursion Java Basics - Anfänger-Themen 5
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
N Rekursion Java Basics - Anfänger-Themen 2
B Rekursion - Übung Java Basics - Anfänger-Themen 2
B Problem beim grundsätzlichen Verständnis bei Rekursion mit 2-dimensionalen Array Java Basics - Anfänger-Themen 6
P Rekursion Java Basics - Anfänger-Themen 19
G Rekursion Beispiel Java Basics - Anfänger-Themen 3
M Rekursion schreiben Java Basics - Anfänger-Themen 16
T Array Rekursion Java Basics - Anfänger-Themen 1
B lineare und schlichte Rekursion Java Basics - Anfänger-Themen 1
A Rekursion Java Basics - Anfänger-Themen 2
B Rekursion Java Basics - Anfänger-Themen 3
A Rekursion stoppt an der falschen Stelle Java Basics - Anfänger-Themen 4
A Lineare Rekursion Java Basics - Anfänger-Themen 6
P Hilfe zur Rekursion? Java Basics - Anfänger-Themen 2
B Rekursion Schneeflocke - Kurze Frage zur Methode Java Basics - Anfänger-Themen 11
L Rekursion Java Basics - Anfänger-Themen 4
S Rekursion Rückgabe - Türme von Hanoi Java Basics - Anfänger-Themen 16
kilopack15 Rekursion und Schleifen Java Basics - Anfänger-Themen 27
E Rekursion Java Basics - Anfänger-Themen 10
JavaXava rekursion nicht verstanden Java Basics - Anfänger-Themen 5
K Rekursion-Verständnisfrage Java Basics - Anfänger-Themen 4
E Methoden String wird in Rekursion nicht überschrieben Java Basics - Anfänger-Themen 2
T 2fach Rekursion. Java Basics - Anfänger-Themen 4
N Rekursion mit if-Anweisung Java Basics - Anfänger-Themen 10
K Methoden Zahlensysteme umwandeln mittels Rekursion Java Basics - Anfänger-Themen 5
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
P Methoden Primzahltest mit Rekursion Java Basics - Anfänger-Themen 3
C Rekursion überführen in eine normale methode Java Basics - Anfänger-Themen 1
M Methoden Rekursion nachvollziehen Java Basics - Anfänger-Themen 4
C Rekursion Java Basics - Anfänger-Themen 6
B Rekursion - Variable initialisieren Java Basics - Anfänger-Themen 2
B Rekursion von Hand durchführen Java Basics - Anfänger-Themen 2
Z Rekursion Java Basics - Anfänger-Themen 4
C Rekursion auf einem Array(negative werte addieren) Java Basics - Anfänger-Themen 4
O Methoden rekursion Java Basics - Anfänger-Themen 7
P Rekursion mit 2 Aufrufen Java Basics - Anfänger-Themen 4
J Hilfe! Rekursion Java Basics - Anfänger-Themen 28
A Rekursion, Anzahl von Stellen ausgeben Java Basics - Anfänger-Themen 7
A Rekursion (anhand von Mergesort) nachvollziehen Java Basics - Anfänger-Themen 4
E Erste Schritte Verschiedene Anfängerfragen (Rekursion, Terminierung, Schleife, etc.) Java Basics - Anfänger-Themen 5
A Frage zur Rekursion Java Basics - Anfänger-Themen 8
D Klausur Vorbereitung: Listen, Rekursion, Bäume & Vererbung Java Basics - Anfänger-Themen 3
V Rekursion Java Basics - Anfänger-Themen 4
V Rekursion Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Anzeige

Neue Themen


Oben