Fibonacci-Algorithmus
-
#include <iostream> // This enables us to use all std definitions directly. using namespace std; /** This function returns a Fibonacci number. */ int fib(int n) { if (n <= 0) return 0; if (n == 1) return 1; else return fib(n-1)+fib(n-2); } /** This is the entry point of the program. */ int main(int argc, char* argv[]) { int i = 7; cout << "Please wait...\n"; cout << "fib[" << i << "] = " << fib(i) << "\n"; }
Hallo, ich habe mal den rekursiven Fibonacci-Algorithmus implementiert. Das funktioniert auch. Jetzt kommt meine Frage.
Wie muss ich das ändern wenn ich anstelle der rekursiven Fibonacci-Algorithmus einen iterativen, linearen Algorithmus implementieren möchte. Ich kriege das nicht auf die Reihe.
Kann mir da einer helfen?Dankee
-
ich glaube ich habe es geschafft aber bin mir nicht sicher..
#include <iostream> // This enables us to use all std definitions directly. using namespace std; /** This function returns a Fibonacci number. */ int fib(int n) { int f2=0; int f1=1; int fib=0; int i; if (n==0 || n==1) return n; for(i=2; i<=n; i++){ fib = f1+f2; f2 = f1; f1 = fib; } return fib; } /** This is the entry point of the program. */ int main(int argc, char* argv[]) { int i = 42; cout << "Please wait...\n"; cout << "fib[" << i << "] = " << fib(i) << "\n"; }
-
Hallo capri03,
Willkommen im C++-Forum.
So geht's iterativ und linear:
/** This function returns a Fibonacci number. */ int fib(int n) { if (n <= 0) return 0; if (n == 1) return 1; int f1 = 1; // Bem.: f0 = 0 int f2 = 1; for( int i=2; i < n; ++i ) { int fneu = f2 + f1; f1 = f2; f2 = fneu; } return f2; }
eine etwas abgefahrene Lösung wäre auch:
int fib( int n ) { if( n < 1 ) return 0; int f2 = 1; for( int f1 = 0; --n; std::swap( f1, f2 ) ) // erfordert #include <algorithm> f1 += f2; return f2; }
Gruß
Werner
-
danke
wäre meins auch richtig?
LG
-
capri03, teste Deins doch mal. Es sieht jedenfalls auf den ersten Blick richtig aus.
Aus Spaß an der Freude kommt hier mal eine rekursiv implementierte "Square and Multiply"-Variante...
#include <iostream> #include <utility> #include <cassert> using ganzzahl = long long int; using ganzzahl_paar = std::pair<ganzzahl, ganzzahl>; // takes the i-th and j-th fib_pair and returns the (i+j)th fib_pair ganzzahl_paar produkt(ganzzahl_paar const& i, ganzzahl_paar const& j) { ganzzahl prev_i = i.second - i.first; return std::make_pair( prev_i * j.first + i.first * j.second, i.first * j.first + i.second * j.second ); } ganzzahl_paar fib_paar(int n) { if (n <= 1) return std::make_pair(n, 1); auto halb = fib_paar(n / 2); return produkt(fib_paar(n % 2), produkt(halb, halb)); } ganzzahl fib(int n) { return fib_paar(n).first; } int main() { int n = 42; std::cout << "fib(" << n << ") = " << fib(n) << "\n"; return 0; }
-
Was ist using ganzzahl = long long int;?
Ick kenne das bisher nur mittels typedef. Neu in C++11?
-
dsaqethjkgyhkkd schrieb:
Was ist using ganzzahl = long long int;?
Ick kenne das bisher nur mittels typedef. Neu in C++11?Jop. Bisschen verständlichere Syntax und man kann es mit Templates nutzen: https://en.wikipedia.org/wiki/C%2B%2B11#Template_aliases
-
sebi707 schrieb:
dsaqethjkgyhkkd schrieb:
Was ist using ganzzahl = long long int;?
Ick kenne das bisher nur mittels typedef. Neu in C++11?Jop. Bisschen verständlichere Syntax und man kann es mit Templates nutzen: https://en.wikipedia.org/wiki/C%2B%2B11#Template_aliases
Ok. Danke.