Fibonacci Zahlen rekursiv Array

[bruce00]

Hallo liebe Community,

ich habe folgende Fragestellung:
Wir sollen ein Programm schreiben, das die Fibonacci Zahlen in einer rekursiv Methode berechnen soll, aber ohne dass die Werten immer wieder neu bestimmt werden müssen.
Es gilt:
F(n) = F(n-1) + F(n-2)
F(0)=F(1)=1

Verwenden Sie einen Array, der die bereits berechneten Werte speichert.(Den Array kann man auch zusätlich als Parameter übergeben)

Ich weiss, es gibt so viele Beiträge zu Fibonacci Zahlen und auch in diesem Forum. Ich bin alles durch und durch.
Auch diese Methode: Fibonacci Sequence - Recursion with memoization, habe ich auch durchgelesen. Aber es ist nicht die Fragestellung.

Ich kann die Zahlen rekursiv berechnen aber ich weiss nicht, wie man die bereits berechnete Werte in einem Array
abspeichern kann. Bin seit Stunden dran, aber ich krieg das nicht hin.
Das Problem ist mir klar. Die Berechnung wiederholt sich , und mit n großen Folgen wächst auch die Laufzeit exponential.

Ich bin soweit gekommen und hoffe, ihr könnt mir helfen.

public class Fibonacci
{
    public static void main(String[] args)
    {
        System.out.println(fibonacci(6));
    }

    public static int fibonacci(int n)
    {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        else
        {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

Nun meine Frage:
Wie speichere ich die Werte in den Array?
Mit meinen Lösungen bin ich nicht weiter gekommen, daher steht da nichts.

Danke im Voraus!
Bruce

 

[franky27]

Na du erstellst dir ein Array mit der gewünschten Anzahl an Zahlen zB

int []zahlen = new int[20];

Dann speicherst du in einer for Schleife deine Ergebnisse in dem array ab

 for (int i = 0; i<zahlen.length; i++){
    	zahlen[i] = fibonacci(i);
    }

Musst halt aufpassen das du im int Wertebereich bleibst, oder halt den Datentyp
ändern das du auch grössere Ergebnisse speichern kannst. Wird ab einer gewissen
Grösse aber sowieso ne ganze Weile dauern.

 

[bruce00]

public class Fibonacci
{
    public static void main(String[] args)
    {
        System.out.println(fibonacci(6));
    }

    public static int fibonacci(int n)
    {
        int []zahlen = new int[n];
        
            for (int i = 0; i<zahlen.length; i++){
                zahlen[i] = fibonacci(i-1) + fibonacci(i - 2);
            }

            return zahlen[n];
    }
}

Mit For Schleife hatte ich auch gemacht. Aber da kommt, IndexOutOFBound Fehlermeldung.
Muss überprüfen, ob die Werte schon berechnet sind. Und so funktioniert es nicht. Denn fib(0) und fib(1) können nicht berechnet werden.

 

[franky27]

Du sollst alle "Zwischenergebnisse" speichern? Oder die Endergebnisse?

 

[bruce00]

Also die Zwischenergebnisse speichern. z.B fib(5) = fib(4) + fib(3). fib(4) = fib(3) + fib(2) Wie man hier sieht wird ja fib(3) zweimal berechnet.
Diese sollen wir speichern. Das Ergebnis soll in einem Array gespeichert werden.

public class Fibonacci
{
    public static void main(String[] args)
    {
        System.out.println(fibonacci(6));
    }

    public static int fibonacci(int n)
    {
        int []zahlen = new int[n];

            for (int i = 2; i <zahlen.length; i++){
                if(i == 0){//fib(0) = 0
                    zahlen[0] = 0;
                    return zahlen[0];
                }
                if(i == 1){//fib(1) = 1
                    zahlen[1] = 1;
                    return zahlen[1];
                }
                else {
                    if(n != 0) { //bereits berechnete nicht rechnen
                        zahlen[i] = fibonacci(i - 1) + fibonacci(i - 2);
                    }
                }
            }

            return zahlen[n];
    }
}

Bin gerade hier. Krieg wieder IndexOutOfBounds.

 

[franky27]

Also sowas: http://www.java-forum.org/java-basics-anfaenger-themen/128438-rekursive-fibonaccizahlen-array.html

 

[bruce00]

Ja richtig. Habe ich versucht aber nicht hingekriegt.

Ich habe umgesetzt

public class Fibonacci {
    public static int fib(int n) {
        int []fibs = new int[n + 1];

        if(n == 0)
        fibs[0] = 0;
        if(n == 1)
        fibs[1] = 1;

        if (fibs[n] == 0 && n > 0) { //Wert nicht im Array
            int newFib = fib(n-1) + fib(n-2); //berechnen
            fibs[n] = newFib; //abspeichern
        }
        return fibs[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(40));
    }
}

Bei n = 40 dauert es wieder zulange,

Das Problem ist einfach die rekursive Mehode. Bei normalen hätte ich schon längst das hingekriegt. Ich gehe im Compiler die
rek Methode durch. Ich kenne das Verhalten von dieser Methode nicht,

 

[Enceladus271]

Der Fehler besteht darin, dass du das Array als lokale Variable erzeugst. Dadurch wird bei jedem Aufruf der Methode das Array neu erzeugt (und ist jedesmal wieder leer). Du muss statt dessen das Array als Klassenvariable verwenden.

 

[bruce00]

Nun jetzt gebe ich mal einen Feedback. Ich habe mich ausführlich mit Fibonacci Zahlen beschäftigt und habe selber versucht eine Lösung zu finden, die ich SELBST verstehe. Nun hab ich leider nichts gehört, was meiner Frage irgendwie etwas beträgt.

Ich bin euch dankbar für eure Antworten aber das ist dürftig. ich will auch keine vorgefertigte Lösung, sondern eine Idee. Die habe ich bis jetzt nicht gekriegt.

 

[Enceladus271]

Der Code den du gepostest hast funktioniert doch bis auf den Fehler auf den ich hingewiesen habe. Was genau ist den jetzt noch dein Problem?

 

[franky27]

Dürftig?
Also jetzt mal im Ernst, dass ist schon nahe an der Grenze zu unverschämt. Du machst uns dafür verantwortlich das du keine Lösung findest die DU verstehst? Was willst du denn eigentlich? Du hast eine Lösung fehlerhaft umgesetzt, Enceladus hat dich darauf aufmerksam gemacht, was dein Fehler ist. Wenn eine Lösung + Erklärung was bei dir noch falsch ist nichts ist, was zu deiner Frage IRGENDETWAS beiträgt, dann solltest du vielleicht lernen wie man richtig Fragen stellt.

 

[bruce00]

Hallo zusammen,

Verseht mich nicht falsch. İch habs probiert mit den Lösungen aber der Fehler besteht wieder. Entschuldigt mich bitte, wenn es böse rübergekommen ist.

İch habe die Lösungen umgesetzt und wieder und wieder Fehlermeldung bekommen. ich habe mich auch bedankt aber das hat nicht gereicht, um Fehlerfrei zu kompilieren.
Freundliche Grüsse

Peace

 

[Enceladus271]

public class Fibonacci {
    private static int[] fibs = new int[50];

    public static int fib( int n ) {

        if ( n == 0 )
            fibs[0] = 0;
        if ( n == 1 )
            fibs[1] = 1;

        if ( fibs[n] == 0 && n > 0 ) { // Wert nicht im Array
            System.out.println( "Berechne fib " + n );
            int newFib = fib( n - 1 ) + fib( n - 2 ); // berechnen
            fibs[n] = newFib; // abspeichern
        }
        return fibs[n];
    }

    public static void main( String[] args ) {
        System.out.println( fib( 40 ) );
        System.out.println( fib( 45 ) );
    }
}

Habe ausgehend vom letzen Code den du gepostet hast den Fehler behoben auf den ich hingewiesen habe. Hab noch zusätzlich eine Ausgabe auf der Konsole gemacht. Dadurch sieht man das einmal berechnete Ergebnisse nicht nochmal berechnet werden, sondern aus dem Array genommen werden. Funktioniert also.