Fibonacci-Algorithmus

capri03

#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

capri03

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";
}

Werner Salomon

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

capri03

danke

wäre meins auch richtig?

LG

krümelkacker

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.