Fibonacci zahlen

Hi,

ich habe als schulaufgabe, ein programm zu schreiben, dass zu einer im Programm festgelegten Zahl die Fibonacci Zahl ausgeben soll. Zu den Fibonacci Zahlen ist folgendes zu sagen (ich weiß nicht wie ich es in worte fassen soll):

fib(n)=fib(n-1)+(fib-2)
fib(1)=1
fib(0)=0

So, nun soll ich die Sache einmal rekursiv und einmal iterativ lösen. Rekursiv is kein Problem. Iterativ wäre auch keins, jedoch haben wir im Unterricht noch gar nicht das Array durchgenommen, sodass ich das nicht verwenden darf.
Es entstehen doch immer mehr Werte, dessen Anzahl ich vorher doch gar nicht genau definieren kann, oder?

Danke für Antwort

C Newbie

Wieso Array ?
Du brauchst um eine Zahl zu berechnen die beiden Vorgänger. Also fängst du bei
0 + 1 an, die letzte der beiden Zahlen speicherst du und das Ergebnis.
Diese beiden Zahlen addierst du dann wieder u.s.w.

Gregor

...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!

die andere wird etwas lange brauchen!

java forum ist weiter unten

Gregor

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. ]

@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.

Gregor

@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!

C Newbie

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

Spacelord

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

Gregor

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. ]

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.

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

Gregor

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.

SG1

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. ]