01 Feb 2010

Die Fibonacci-Sequenz berechnen

Wenn man die Fibonacci-Sequenz berechnen will, kann man das klassisch rekursiv tun. Man kann es aber beschleunigen, wenn man sich in einem Array die Pfade merkt, die man schon berechnet hat, und diese nicht mehr berechnen. Hier ein Beispiel. Das ganze ist natürlich rein ein Proof-Of-Concept, ohne praktischen Nutzen.

// fibonacci by chrissie 2/2010
#include <iostream>
using namespace std;

int fib (int f);
int fib2 (int f);
void pr_a(void);
int a[50]={};

const int ende=45;

int main(void) {
    a[0]=1;
    a[1]=1;
    a[2]=1;
    int i;

// dauert ewig lang
    cout<<"klassisch"<<endl;
    cout<<fib(ende);
    cout<<endl<<"--"<<endl;

// geht saumaessig fix
    cout<<"getuned"<<endl;
    cout<<fib2(ende);
    cout<<endl<<"--"<<endl;
}

// fibonacci rekursiv
int fib (int f) {
    if (f<=2) return 1;
    return fib(f-2)+fib(f-1);
}
// fibonacci rekursiv, jedoch cachen wir die ergebnisse
// in einem array und rechnen nur, was noetig ist
// das spart rechenzeit
int fib2 (int f) {
    int i=0;
    if (f<=2) i=1;  // abbruchbedingung

    else {
        // ueberpruefen ob wir das schon mal gerechnet haben
        if (f>=2) {
            if (a[f-2]!=0 && a[f-1]!=0 ) {
                i= a[f-2]+a[f-1];
            }

            if (a[f-2]==0 && a[f-1]!=0 ){
                i= fib2(f-2)+a[f-1];
            }

            if (a[f-2]!=0 && a[f-1]==0 ){
                i= a[f-2]+fib2(f-1);
            }
        }

        // ergebnis noch nicht gerechnet, rechnen
        // und in array merken
        if (i==0) {
            i=fib2(f-2)+fib2(f-1);
            a[f]=i;
        //    pr_a();   // debug
        }
    }
    // ergebnis zurueckgeben
    return i;
}

// merker-array ausgeben zur kontrolle
void pr_a(void) {
    int i;
    for (i=1;i<=ende;i++) cout<<a[i]<<" ";
    cout<<endl;
}

Anwendung:

chrissie@fehmarn ~/fib $ g++ fib.cc
chrissie@fehmarn ~/fib $ ./a.out 
klassisch
1134903170
--
getuned
1134903170
--