3. Fibonacci Reihe

Fibonacci Reihe

  • ?

    Auszug aus C++ in 21 Tagen:

    int fib(int n);

int main(){

	int n,answer;

	cout<<"Zu findende Zahl eingeben: ";
	cin >>n;

	cout << "\n\n";

	answer=fib(n);

	cout<< "Die "<< n << ". Fibonacci Zahl"<< " lautet " <<answer;

	cout << endl;

	return 0;
}

int fib(int n){

	cout <<"Verarbeitung von fib("<<n<<")...";

	if(n<3){
		cout <<"Rueckgabewert 1!\n";
		return 1;
	}
	else {
		cout<<"Aufruf von fib("<<n-2<<") und fib("<<n-1<<").\n";

		return fib(n-2)+fib(n-1); // Fib-Algorithmus 
	}

}

    Frage zum Allgorithmus:

    Ich möchte gerne wissen warum bei der Ausgabe d. Codes
    unter Verarbeitung von fib(<<n<<) ständig die Zahlen die kleiner der eingegebenen Zahl sind wiederholt werden (klar die Rekursion).
    Laut Wissens, und C++ Buch steht drin, dass nur die 1 zweimal vorkommt in der Folge.
    Aber nicht die 4,3 oder 2.

    Würde mich freuen wenn einer die Frage beantworten könnte.

    Hab als Beispiel die 3 genommen, die wiederholt wird.

    Die Ausgabe:

    Zu findende Zahl eingeben: 6

    Verarbeitung von fib(6)...Aufruf von fib(4) und fib(5)
    Verarbeitung von fib(4)...Aufruf von fib(2) und fib(3)
    Verarbeitung von fib(2)...Rueckgabewert 1!
    Verarbeitung von fib(3)...Aufruf von fib(1) und fib(2)
    Verarbeitung von fib(1)...Rueckgabewert 1!
    Verarbeitung von fib(2)...Rueckgabewert 1!
    Verarbeitung von fib(5)...Aufruf von fib(3) und fib(4)
    Verarbeitung von fib(3)...Aufruf von fib(1) und fib(2)
    Verarbeitung von fib(1)...Rueckgabewert 1!
    Verarbeitung von fib(2)...Rueckgabewert 1!
    Verarbeitung von fib(4)...Aufruf von fib(2) und fib(3)
    Verarbeitung von fib(2)...Rueckgabewert 1!
    Verarbeitung von fib(3)...Aufruf von fib(1) und fib(2)
    Verarbeitung von fib(1)...Rueckgabewert 1!
    Verarbeitung von fib(2)...Rueckgabewert 1!
    Die 6. Fibonacci Zahl lautet 8

    0
  • C

    Du hast dort zwei rekursive Aufrufe in der Funktion drin und der Wert fib(3) wird dadurch mehrfach in der Berechnung benötigt - einmal als erster Summand von fib(4) und als zweiter Summand von fib(5). Und jedes Mal, wenn dieser Wert benötigt wird, wird er neu berechnet (das ist der Nachteil des rekursiven Ansatze).

    0
  • ?

    Hab noch mal eine Frage,

    warum ensteht ne Endlosschleife wenn ich z.B. 968 eingebe?

    Die Fib.Reihe ist doch eine endlose Folge , also muss der Wert doch irgendwann erreicht sein für die Eingabe 968.

    Oder liegt es am Datentyp?
    Kann ja sein dass sowas wie long long int oder int64... benötigt wird.

    Hab dazu noch ne Frage:
    Gibt es irgendwo die stdint.h zum Download/Kopieren?
    Hab nix gefunden bisher.

    0
  • C

    Nichtwissender schrieb:

    Hab noch mal eine Frage,

    warum ensteht ne Endlosschleife wenn ich z.B. 968 eingebe?

    Eigentlich sollte keine Endlosrekursion entstehen (Endlosschleife sowieso nicht). Aber bei 968 kann es eine Weile dauern, bis das Verfahren durch ist - da ist die iterative Lösung vermutlich schneller.

    0
  • ?

    Danke für die schnelle Antwort.

    P.S.:
    Hab trotzdem ne Frage nochmal wo ich die stdint.h herbekomme.

    0
  • C

    Frag mal google 😉

    Aber wozu brauchst du sie überhaupt?

    0
  • ?

    Lese grade noch einmal die Beiträge zu Rekursionen.

    Wie lässt man denn die Rekursionen zählen?

    Hier bei der Eingabe 6, 15 Rekursionen?

    Könnte man nicht eine Countfunktion anlegen?

    0
  • J

    Klar, Du könntest zum Beispiel am Anfang der Funktion immer einen globalen Counter hochzählen (oder eine Zählvariable per Referenz übergeben).

    Aber in diesem Fall ist es besonders einfach: Du machst ungefähr genauso viele Funktionsaufrufe wie das Ergebnis Deiner Berechnung groß ist. Deswegen dauert das auch so lange. Die Fibonacci-Zahlen wachsen exponentiell. Daher hast Du bei der 980. Zahl schon jede Menge Funktionsaufrufe.

    Ich frage mich sowieso wer auf die Idee gekommen ist anhand von sowas Rekursion in der Programmierung einzuführen. Die iterative Variante ist um Längen besser. Leider scheint sich das aber noch nicht rumgesprochen zu haben. 😞

    0
  • ?
     

    //Functors sind universell verwendbare Funktionsobjekte.
//Sie erweitern das aus C bekannte Konzept der Funktionszeiger
//Ein Functor ist ein Objekt, welches operator() definiert.

class FibonacciGen {//fibonacci Generator Die ersten beiden Glieder der Folge sind 1, jedes danach die Summe seiner beiden direkten Vorgänger.

public:
    FibonacciGen() : x(1), y(0), tmp(0) {}
    int operator()() {
        tmp = x + y;
        x = y;
        y = tmp;
        return tmp;
    }
private:
    int x, y, tmp;
};
//Es handelt sich also um eine ganz normale Klassendefinition, lediglich das Vorhandensein von operator()
//macht ein Objekt vom Typ FibonacciGen automatisch zum Functor.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    vector <int> a(10);       //Die erste 10 Fibonacci-Zahlen
    vector <int>::iterator Iter1;
    generate( a.begin(), a.end(), FibonacciGen());//speichern

    for (Iter1 = a.begin(); Iter1 != a.end(); ++Iter1)
         cout << *Iter1 << endl;                  //ausgeben
	return 0;
}

    🕶

    0
  • C

    Nichtwissender schrieb:

    Auszug aus C++ in 21 Tagen:

    int fib(int n){

	cout <<"Verarbeitung von fib("<<n<<")...";

	if(n<3){
		cout <<"Rueckgabewert 1!\n";
		return 1;
	}
	else {
		cout<<"Aufruf von fib("<<n-2<<") und fib("<<n-1<<").\n";

		return fib(n-2)+fib(n-1); // Fib-Algorithmus 
	}

}

    Bist du sicher, dass das SO drinstand?
    Denn die ersten Fibonaccizahlen sind 0, 1, 1 und nicht 1,1,1 wie hier dargestellt 😮 ... müsste doch eher so heißen, oder:

    if(n==0){
  cout <<"Rueckgabewert 0!\n";
  return 0;
}
else if( n==1 || n==2 ) {
  cout << "Rückgabewert1!\n";
  return 1;
}
else{
		cout<<"Aufruf von fib("<<n-2<<") und fib("<<n-1<<").\n";

		return fib(n-2)+fib(n-1); // Fib-Algorithmus 
	}

    (außerdem ist die Fibonaccizahl2 bereits durch die Fibonaccizahl0 und die Fibonaccizahl1 berechenbar 😉 )

    0
  • .

    Checker&Murckser schrieb:

    Bist du sicher, dass das SO drinstand?
    Denn die ersten Fibonaccizahlen sind 0, 1, 1 und nicht 1,1,1 wie hier dargestellt

    Das ist Definitionssache. Da Folgen i.A. einen Index aus den natürlichen Zahlen haben und in Deutschland diese meistens ohne 0 sind, ist das an sich nicht soo falsch (abgesehen davon, dass der Benutzer mit Fehlern beworfen gehört, falls n == 1 ist ;)).

    Wo da grad ein alternativer Vorschlag kommt, wenn man die Suche bemüht findet man sicher auch noch die Fibonacci-Iteratoren von Konrad Rudolph und mir (kA wer da noch so dran beteiligt war).

    0
Anmelden zum Antworten