4. Fibonacci zahlen

Fibonacci zahlen

  • G

    ...um zu testen, ob dein Algorithmus richtig ist, gib mal die Fibonaccizahlen von 47,48,93 und 94 an. 🙂 ...am Besten mit der iterativen Variante testen, die andere wird etwas lange brauchen!

    0
  • ?

    die andere wird etwas lange brauchen!

    java forum ist weiter unten 😉

    0
  • G

    Original erstellt von <f>:
    java forum ist weiter unten 😉

    Hmmm... ach so, stimmt ja: C++ ist schneller als Java. ...du kannst dann ja mal mit folgendem Programm testen:

    #include <iostream>

long long fibo (const int n)
{
   if (n == 0) return 0;
   if (n == 1) return 1;
   return fibo(n-1) + fibo (n-2);
}

int main ()
{
   for (int n = 1 ; n < 94 ; ++n)
   {
      std::cout << n << " : " << fibo (n) << std::endl;
   }
}

    😉 ...sag bitte Bescheid, wie lange das Programm braucht, um durchzulaufen! 🙂

    [ Dieser Beitrag wurde am 06.05.2003 um 03:35 Uhr von Gregor editiert. ]

    0
  • ?

    @C Newbie: Versteh nicht, wie du das meinst, kannste vielleicht mal die porten, wie die kernschleife aussehn müsste?

    @Gregor: Wie gesagt, rekursiv is kein Problem, da die Funktion ja x mal ineinander geschachtelt ist, sodass immer alle lokalen Variablen der Funktion erhalten bleiben. Es entstehen durch aufrufen von return fibo(n-1) + fibo (n-2) ja immer 2 neue Werte.

    0
  • G

    @fraglos: Das Programm war ja auch nicht für dich gedacht! 🙂 ...aber wenn du genug Zeit hast, kannst du es ja auch mal durchlaufen lassen! 😉

    0
  • C
     

    int Zahl1 = 0, Zahl2 = 1, Ergebnis;
printf("0 1 ");
do
{
    Ergebnis = Zahl1 + Zahl2;
    Zahl1 = Zahl2;
    Zahl2 = Ergenis;
    printf("%i ", Ergebnis);    
}while(Ergebnis <= Endzahl);
    0
  • S

    Wenn du deinem Lehrer tief in den Hintern kriechen willst kannst du noch ne weitere Variante hinzufügen.Die Fibonaccizahl lässt sich auch direkt berechnen!

    MfG Spacelord 🙂

    0
  • G

    Original erstellt von Spacelord:
    **Die Fibonaccizahl lässt sich auch direkt berechnen!
    **

    Ja, aber die Formel ist zum Kotzen! ...und solle auch nicht schneller sein als die iterative Variante:

    1    /  /1+sqrt(5)\^(n+1)   /1-sqrt(5)\^(n+1)  \
F(n) = ------- |  |---------|       - |---------|        |
       sqrt(5) \  \    2    /         \     2   /        /

    EDIT : Hier gilt aber F(0) = F(1) = 1. Das ganze ist also um eins verschoben.

    [ Dieser Beitrag wurde am 06.05.2003 um 13:05 Uhr von Gregor editiert. ]

    0
  • G

    Also ich kenn die Formel anders:

    fib(n) = (1/sqrt(5)*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n)))

    Also nicht hoch (n+1), sondern hoch n
    Dann stimmts mit dem Index wieder.

    [ Dieser Beitrag wurde am 06.05.2003 um 20:02 Uhr von Gary editiert. ]

    0
  • G

    Original erstellt von Gary:
    **Also ich kenn die Formel anders:

    fib(n) = (1/sqrt(5)*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n)))

    Also nicht hoch (n+1), sondern hoch n
    Dann stimmts mit dem Index wieder.
    **

    Das ist ne Frage, wie man die ersten beiden Fibonaccizahlen setzt. Bei dir wird wohl F(0)=0 gelten.

    0
  • S

    int fib_acc(int n, int acc1, int acc2) {
    if (n == 0) return acc1;
    else return fib_acc(n-1, acc1+acc2, acc1);
    }

    int fib(int n) {
    if (n == 0) return 0;
    else return fib_acc(n-1, 1, 0);
    }

    Aua, ich hab zu viel funktional programmiert...

    <edit>ein int vergessen</edit>

    [ Dieser Beitrag wurde am 06.05.2003 um 23:37 Uhr von SG1 editiert. ]

    0
Anmelden zum Antworten