Fibonacci Zahlen



  • Hallo ich hab ein Problem mit der fibonacci Folge:

    Der code ist:

    # include <iostream>
    using namespace std;

    double fib(double fn,double f1, double f0) {
    if (fn == 0) { // Die Fibonacci-Zahl von null ist null
    return f0;
    }

    if (fn == 1) { // Die Fibonacci-Zahl von eins ist eins
    return f1;
    }

    // Ansonsten wird die Summe der zwei vorherigen Fibonacci-Zahlen zurückgegeben
    return fib(fn,f1,f0 - 1) + fib(fn,f1,f0 - 2);
    }
    int main ()
    {
    cout << "Fibonacci: " << fib(2,10,30) << "\n";
    return 0;
    }

    Aufgabenstellung ; Programmieren Sie eine Funktion
    double Fibonacci(double f0, double f1, int n),
    die bez¨uglich der ersten beiden Folgenglieder f0 und f1 die n-te verallgemeinerte
    Fibonacci-Zahl zur¨uckliefert.
    Testen Sie Ihre Funktion, indem Sie in der main die klassischen
    Fibonacci-Zahlen fn f¨ur n = 2, 10, 30 ausgeben.

    Wenn ich das Programm so abspiele dann beendet er dies.
    wäre dankbar wenn mir jemadn helfen könnte
    ich vermute es liegt am parameter aber ich weiß nicht genau was ich machen soll



  • Deine rekursiven Aufrufe sind falsch (falsche Argumente). Dadurch bekommst du eine unendliche Rekursion.



  • Danke für die schnelle Antwort, ich verstehe so halb was du meinst, das macht sinn deswegen wird das Programm beendet, aber jetzt stell ich mir die frage wie ich dieses Problem löse.

    Sitze da echt schon paar stunden dran und komme einfach nicht drauf

    danke im voraus, würdest mir den morgigen tag retten 🙂



  • Schreib mal eine Funktion für die Standard-Fibonacci-Zahlen 0, 1, 1, 2, 3, 5, 8, usw. und vergleiche mit deinem Programm, dann siehst du es.



  • # include <iostream>
    using namespace std;
    
    double fib(double fn) {
        if (fn == 0) { // Die Fibonacci-Zahl von null ist null
            return 0;
        }
    
        if (fn == 1) { // Die Fibonacci-Zahl von eins ist eins
            return 1;
        }
    
        // Ansonsten wird die Summe der zwei vorherigen Fibonacci-Zahlen zurückgegeben
        return fib(fn - 1) + fib(fn- 2);
    }
    int main ()
    {
    cout << "Fibonacci: " << fib(12) << "\n";
    return 0;
    }
    

    Meinst du es so ? aber da fällt mir nur auf das ich kein f0 als return bekomme falls fn=0 ist und kein f1 als return bekomme wenn fn=1 ist.

    Aber in der aufgaben stellung steht ja das die Funktion so aussehen soll: double Fibonacci(double f0, double f1, int n),



  • OK, jetzt halte wir mal die return-Statements gegeneinander:

    // Standard
    return fib(fn - 1) + fib(fn- 2);
    
    // Verallgemeinert
    return fib(fn,f1,f0 - 1) + fib(fn,f1,f0 - 2);
    

    Siehst du jetzt, dass -- und was -- du falsch verallgemeinert hast?

    Aber in der aufgaben stellung steht ja das die Funktion so aussehen soll: double Fibonacci(double f0, double f1, int n),

    Völlig anders als bei dir, irgendwie. Ich nehme mal an, dass das einen Grund hat und du weißt was du tust?



  • Für n=30 und höher könnte der rekursive Lösungsansatz uneeignet werden.
    Daher folgender Vorschlag - frei nach der Formel für große Fibonacci-Zahlen:

    #include <cmath>    // std::pow, std::floor
    
    double Fibonacci( double f0, double f1, int n )
    {
        if( n <= 0 )
            return f0;
        const double Phi = (1 + std::sqrt( 5. )) / 2;
        double tmp = (1. / std::sqrt( 5. )) * std::pow( Phi, n - 1 );
        double f0_ = std::floor( tmp + 0.5 );
        double f1_ = std::floor( tmp * Phi + 0.5 );
        return f0_ * f0 + f1_ * f1;
    }
    

    Und eine Lösung für Kurzi182:

    #include <algorithm>    // std::swap
    
    double Fibonacci( double f0, double f1, int n )
    {
        if( n <= 0 )
            return f0;
        for( ; n > 1; --n )
            std::swap( f0 += f1, f1 );
        return f1;
    }
    

    für weitere Inspirationen in Sachen Programmieren der Fibonacci Folge siehe hier.



  • sorry für die späte antwort aber danke hat mir weiter geholfen hab den fehler entdeckt 🙂


Log in to reply