Fibonacci Zahlen dynamische Programmierung

[baker333]

Servus,

ich habe ein Verständnisproblem bei der dynamischen Programmierung der Fibonacci Folge. Hier mein Code aus dem Skript:

private long [] berechneteFiboWerte;

//Fibonacci Zahlen mittels dynamischer Programmierung
    public long fibDynProg (int n) {
        if (n < 0 ) {
            throw new IllegalArgumentException();   
        }
    
        //erstellt ein neues Array für bereits berechnete Werte
        berechneteFiboWerte = new long[n +1];
        //ruft die Methode,die unten implementiert wird auf
        fibRekursivDyn(n);
        
        //gibt den uns interessierenden Wert aus
        return berechneteFiboWerte[n];
    
    }
    
    private long fibRekursivDyn(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        
        if(berechneteFiboWerte[n] != 0) {
            
            return berechneteFiboWerte[n];
        }
            return berechneteFiboWerte[n] =
                    fibRekursivDyn(n-1) + fibRekursivDyn (n-2);
        }

Ich verstehe, dass ich ein Array erstelle und dort die Werte speichere. Aber ich verstehe die erste "return" Anweisung in der Methode fibRekursivDyn nicht. Wenn der Wert an der Stelle n ungleich 0 ist warum gebe ich ihn zurück? Irgendwie stehe ich auf dem Schlauch Ist das einfach die Befüllung des Arrays?

Danke

 

[Meniskusschaden]

Wenn der Wert an der Stelle n ungleich 0 ist warum gebe ich ihn zurück?

Dann ist der Wert schon mal berechnet worden. Man kann ihn deshalb direkt zurück geben, ohne ihn aufwändig berechnen zu müssen. Das ist also ein Optimierung, damit es schneller läuft.

 

[baker333]

Stimmt, das ist ja Sinn und Zweck der Sache. Wenn er 0 ist, dann berechnet erihn ja im Schritt weiter unten.

 

[baker333]

Im Skript scheint ein Fehler zu sein:

private long fibRekursivDyn(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

es müsste eigentlich return n heißen. Mit return 1 berechnet er quasi die Fibonacci Zahl n+1. Da frage ich mich natürlich warum?

 

[kneitzel]

Nein, da ist die Frage, wie Du die Fibonacci Folge definierst.

Üblich ist;
1, 1, 2, 3, 5, ....

Manchmal wird aber eine 0 vorangestellt [1]. Das ist aber eher unüblich und habe ich in der Praxis noch nicht gesehen.

Also für 0 und 1 wird 1 zurück gegeben. Dann immer die Summe der beiden Vorgänger. Und so die optionale 0 nicht erwartet wird, ist der Code so in meinen Augen korrekt.

Referenzen:
[1] https://de.wikipedia.org/wiki/Fibonacci-Folge

 

[baker333]

Nunja, ich hab es mal ausprobiert:

wenn ich es so berechne:

private long fibRekursivDyn(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

kriege ich die Fibonacci Zahl für n+1.

private long fibRekursivDyn(int n) {
        if (n == 0 || n == 1) {
            return n;
        }

kriege ich die Fibonacci Zahl für n.

Wenn ich die Definition der Fibonacci Zahl ändere:

private long fibRekursivDyn(int n) {
        if (n == 1 || n == 2) {
            
            berechneteFiboWerte[n] = 1;
            
            return 1;
        }

dann erhalte ich mit return 1 auch den richtigen Wert.

 

[mihe7]

Nunja, ich hab es mal ausprobiert:

Im ersten Fall berechnest Du die Fibonacci-Zahl von n+1, weil Du für n==0 den Wert 1 zurückgibst. Der zweite Fall entspricht der Fibonacci-Folge mit 0 als ersten Wert (für n==0 gibst Du den Wert 0 zurück). Der dritte Fall entspricht der üblichen Fibonacci-Folge: für n==1 und n==2 gibst Du 1 zurück.

 

[baker333]

Alles klar, danke!