Fibonacci Zahlen



  • Hallo Programmierer!
    Ich habe erst vor kurzem mit C++ angefangen und mache grad dieses Tutorial: http://tutorial.schornboeck.net/rekursion.htm
    Da mir in diesem Forum schon mal geholfen wurde, hoffe ich dass ihr mir weiterhelfen könnt. ➡
    Nun ist es meine Aufgabe die Fibonacci Zahlen auszugeben (Zahl = Summer der 2 vorhergehenden Zahlen: 1,1,2,3,5,8,13,...) - iterativ und rekursiv! 😮
    Ich scheitere schon bei der iterativen Ausgabe. Keine Ahnung was ich flasch mache. Ich hoffe ihr könnt mir helfen: 🙄

    //Fibonacci Zahlen
    //version 0.2
    //compiled with Dev-C++ 4.9.9.2
    //last modified on 2006/08/08
    
    #include <iostream>
    using namespace std;
    
    int fibonacci_iter(int, int);
    //int fibonacci_rekur(int, int);
    
    int main()
    {
        cout << "Fibonacci Zahlen:\n";
        int a = 1, b = 1;
        for (;;)
        {
                  cout << fibonacci_iter(a,b) << endl;
        }
    
        cin.get();
        return 0;
    }
    
    int fibonacci_iter(int a, int b)
    {
        int c, i;
        for (;a == b && c < a; i++)
        {
              return a, b;
              c = a + b;
        }
    
        if (c > a && c > b)
        {
               return c;
               a = b + c;
               if (a > b && a > c)
               {
                     return a;
                     b = a + c;
                     if (b > a && b > c)
                     {
                           return b;
                           c = a + b;
                     }
               }
        }
    }
    

    Vielen Dank für eure Hilfe,

    aWak3N 😉



  • Hallo aWak3N,

    Ehrlich gesagt, ich kann in Deinem Programm nicht erkennen, wie Du Dir die Berechnung der Fibonacci Zahlen vorgestellt hast. Ich habe mal ein paar Kommentare eingefügt, vielleicht hilft es Dir ja.

    aWak3N schrieb:

    //Fibonacci Zahlen
    //version 0.2
    //compiled with Dev-C++ 4.9.9.2
    //last modified on 2006/08/08
    
    #include <iostream>
    using namespace std;
    
    int fibonacci_iter(int, int);
    //int fibonacci_rekur(int, int);
    
    int main()
    {
        cout << "Fibonacci Zahlen:\n";
        int a = 1, b = 1;
        for (;;)   // Das ist eine Endlosschleife, wozu? 
        {
                  // Da a und b nicht verändert werden, wird hier immer wieder fibonacci_iter(1,1) berechnet.
                  cout << fibonacci_iter(a,b) << endl; 
        }
            
        cin.get();
        return 0;
    }
    // Welche Bedeutung haben die Parameter a und b. Sollen es die beiden zuvor berechneten Zahlen sein?
    int fibonacci_iter(int a, int b) 
    {
        int c, i; // c und i werden nicht initialisiert!
        
        // Die Bedingung verstehe ich nicht, aber sowohl c als auch i sind undefiniert, also weißt Du nicht was passiert.
        for (;a == b && c < a; i++) 
        {
              // Du kannst nicht mehrere Werte zurückgeben. Was willst Du eigentlich zurückgeben?
              return a, b; 
              c = a + b;   // Das wird nie ausgeführt, da vorher schon das return steht.
        }
        
        if (c > a && c > b) // c ist immer noch undefiniert. (Falls die Schleife nie betreten wurde.)
        {
               return c;    // Du gibst das undefinierte c zurück.
               a = b + c;   // Der Rest wird nicht ausgeführt, da vorher schon das return steht.
               if (a > b && a > c)
               {
                     return a;
                     b = a + c;
                     if (b > a && b > c)
                     {
                           return b;
                           c = a + b;
                     }
               }
         }
         // Hier fehlt ein return für den Fall das die Bedingung des if nicht erfüllt ist.
    }
    


  • Nimm doch ein Vektor:

    std::vector< int > v;
    
    // Anfangswerte 0, 1
    v.push_back( 0 );
    v.push_back( 1 );
    
    int size = 0;
    
    // Zahl 2-22
    for ( int i = 0; i < 20; ++i )
    {
    	size = v.size();
    	v.push_back( v[ size-2 ] + v[ size-1 ] );
    }
    

    Und Rekursiv:

    void fibonacci_recursive( std::vector< int > &container, int count=20 )
    {
    	int size = container.size();
            // lalala :)
    	if ( size == 0 )
    	{
    		container.push_back( 0 );
    		container.push_back( 1 );
    		size += 2;
    	}
    
    	if ( count-- )
    	{
    		container.push_back( container[ size-2 ] + container[ size-1 ] );
    		fibonacci_recursive( container, count );
    	}
    }
    

    Oder sowas ähnliches...



  • //Functors sind universell verwendbare Funktionsobjekte.
    //Sie erweitern das aus C bekannte Konzept der Funktionszeiger
    //Ein Functor ist ein Objekt, welches operator() definiert.
    
    class iotaGen {//iota Generator kontinuierlich aufsteigenden Zahlenfolge 0, 1, 2, ...
    public:
        int operator()() { return n++; }
        iotaGen() : n(0) {}
    
    private:
        int n;
    };
    //Es handelt sich also um eine ganz normale Klassendefinition, lediglich das Vorhandensein von operator()
    //macht ein Objekt vom Typ iotaGen automatisch zum Functor.
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    int main()
    {
    
        vector <int> a(10);
        vector <int>::iterator Iter1;
        generate( a.begin(), a.end(), iotaGen());
    
        for (Iter1 = a.begin(); Iter1 != a.end(); ++Iter1)
            cout << *Iter1 << endll;
    
    	return 0;
    }
    

    Mein Vorschlag, bau diesen iota-Generator in einen fibonacci-Generator um, womit der erste Teil Deiner
    Aufgabe, ohne wo abzuschreiben, geschafft wäre. 👍



  • danke für die antworten. ich habs jetzt geschafft. nun mach ich mich mal an das rekursive lösen... 🙂

    @David_pb: vektoren hab ich noch nicht behandelt...

    @Helmut S.: ich versuch die "programme" lieber mit sachen zu lösen die ich kenne. trotzdem thx! 👍

    hier mal meine lösung:

    //Fibonacci Zahlen
    //version 0.3
    //coded by aWak3N
    //compiled by aWak3N
    //compiled with Dev-C++ 4.9.9.2
    //last modified on 2006/08/08
    
    #include <iostream>
    using namespace std;
    
    int fibonacci_iter(int, int);
    int fibonacci_rekur(int, int);
    bool groesser(int, int, int);
    
    int main()
    {
        cout << "Fibonacci Zahlen:\n";
        int a = 1, b = 1;
        cout << a << endl << b << endl;
        for (;a < 100;)   // bedingung kann verändert werden
                          // gibt die ersten 14 zahlen aus
        {
                  int c = a + b;
                  if (groesser(c,a,b));
                  {
                                     cout << c << endl;
                                     b = c + a;
                                     if (groesser(b,a,c));
                                     {
                                                          cout << b << endl;
                                                          a = b + c;
                                                          if (groesser(a,b,c))
                                                          {
                                                                             cout << a << endl;
                                                          }
                                     }
                  }                                                                                                                               
        }
    
        cin.get();
        return 0;
    }
    
    bool groesser(int i, int j, int k)
    {
         if (i > j && i > k)
         {
               return true;
         }
    }
    


  • Hi!

    int main( void ) 
    { 
    
    	double q = sqrt( 5 );
    	int c;
    
    	for ( int i = 0; i < 10; ++i )
    	{
    		c = ( 1.0 / q ) * ( powf( ( 1.0+q ) / 2.0, i )-powf( ( 1.0-q ) / 2.0, i ) );
    		std::cout << c << std::endl;
    	}
    
    	return 0; 
    }
    

    Ha, zwar keine Rekursion aber dafür umso langsamer! 😃 😉



  • Ne, das ist schnell. Die Rekursion ist nämlich böse bei den Fibonaccis. Zumindest wenn man's so hinschreibt, wie die Folge definiert ist. Man braucht nämlich für die n-te Fibonacci-Zahl genauso so viele Funktionsaufrufe wie die Zahl groß ist. Die wachsen aber exponentiell, also hat man exponentielle Laufzeit. Man könnte sich also auch die ganze Rechnerei sparen und nur die Funktionsaufrufe zählen. 😃



  • Die ersten Zahlen dürften schneller berechnet werden, per Rekursion. Man muss nun also den Schnittpunkt der beiden Kurven berechnen um effizient Fibonacci-Zahlen zu berechnen! 😉

    grüße



  • Jester schrieb:

    Ne, das ist schnell. Die Rekursion ist nämlich böse bei den Fibonaccis. Zumindest wenn man's so hinschreibt, wie die Folge definiert ist. Man braucht nämlich für die n-te Fibonacci-Zahl genauso so viele Funktionsaufrufe wie die Zahl groß ist. Die wachsen aber exponentiell, also hat man exponentielle Laufzeit. Man könnte sich also auch die ganze Rechnerei sparen und nur die Funktionsaufrufe zählen. 😃

    Ach, man muss es natürlich schon so implementieren, wie man es auch auf dem Papier machen würde, d.h. auf bereits berechnete Zahlen Bezug nehmen.

    std::pair<int, int> fib_rec(std::pair<int, int> const& prev, int n)
    {
        if (--n == 0)
            return prev;
        else
            return fib_rec(std::make_pair(prev.second, prev.first + prev.second), n);
    }
    
    int fib(int n)
    {
        return fib_rec(std::make_pair(0, 1), n).second;
    }
    


  • Mach hier nochmal Functor - Werbung!

    //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 ersten 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;
    }
    


  • Helmut S. schrieb:

    Mach hier nochmal Functor - Werbung!

    Deine Functor's sind ja recht elegant, aber warum muß
    die Generierungsmethode unbedingt operator() heißen? 😮

    Ein einfaches next() (+ evtl. noch ein reset())
    sind doch wesentlich verständlicher.

    BTW: iotaGen. Kann es sein, daß du aus der APL-Ecke kommst?

    +/iota 100



  • Javaner schrieb:

    Deine Functor's sind ja recht elegant, aber warum muß
    die Generierungsmethode unbedingt operator() heißen? 😮

    Weil es eben ein Funktor ist. Es muss ja keine Struktur dahinter stehen, ein Funktionszeiger tut's auch (z.B. eine Fib-Funktion, welche die aktuelle Zahl statisch speichert). Und da bist Du mit 'next' schlecht beraten.

    PS: z.B. so:

    int fib_gen()
    {
        static std::pair<int, int> a(0, 1);
    
        std::swap(a.first, a.second);
        a.second += a.first;
        return a.first;
    }
    

    Natürlich ist das hier nicht sinnvoll, da dieser Generator nur "einmal" verwendet werden könnte aber in anderen Situationen ergibt das evtl. Sinn.



  • Aber operator hört sich genauso nichtssagend an wie Functor.

    Da machen next und Generator doch mehr Sinn!

    Oder bin ich auf dem falschen Dampfer, und der Name
    Functor hat schon eine Bedeutung? (Eine Art Konzept)?



  • Ich will auch noch eine Art loswerden 😃

    class fib_iterator
    {
    public:
        fib_iterator (unsigned int N = 0) : _n (N)
        {
            _pred[0] = _pred[1] = 1;
        }
    
        const fib_iterator& operator++ () const
        {
            --_n;
            return *this;
        }
    
        unsigned int operator* ()
        {
            return _pred[_n % 2] = _pred[0] + _pred[1];
        }
    
        bool operator== (const fib_iterator& other) const
        {
            return _n == other._n;
        }
    
    private:
        unsigned int _n;
        unsigned int _pred[2];
    };
    
    // ...
    
    std::copy (fib_iterator (100), fib_iterator (), vector.begin ());
    

    Keine Ahnung, obs funktioniert, aber ich finds toll ;).



  • Javaner schrieb:

    Aber operator hört sich genauso nichtssagend an wie Functor.

    Klar, "Molekül" hört sich auch genauso nichtssagend an wie "Atom" -- wenn man von Chemie/Physik keine Ahnung hat. Worauf willst Du hinaus?

    Oder bin ich auf dem falschen Dampfer, und der Name
    Functor hat schon eine Bedeutung? (Eine Art Konzept)?

    Ja. Ein Funktor ist eben ein Funktionsobjekt, d.h. ein Objekt, das sich so benutzen lässt (syntaktisch) als sei es eine Funktion.

    Und dass Dir als Javaner Operatorenüberladung nicht passt ist zwar verständlich, aber ich denke, Du solltest Dich damit (zumindest in C++) anfreunden, das Konzept ist sehr mächtig.



  • Konrad Rudolph schrieb:

    Und dass Dir als Javaner Operatorenüberladung nicht passt ist zwar verständlich, aber ich denke, Du solltest Dich damit (zumindest in C++) anfreunden, das Konzept ist sehr mächtig.

    Irgendwie ist heute nicht mein Tag. Schon innerhalb von 5 Minuten
    das zweite Mal mißverstanden. 😞

    Ich habe doch nirgendwo geschrieben, daß mir Operatorenüberladung
    nicht paßt!

    Im Gegenteil: Sie gehört zu den Aspekten (const-Modifier, Referenzübergabe, ...)
    die ich in Java vermisse.



  • Javaner schrieb:

    Ich habe doch nirgendwo geschrieben, daß mir Operatorenüberladung
    nicht paßt!

    Oh, irgendwie hatte ich das in Deine Aussage "Aber operator hört sich genauso nichtssagend an wie Functor" reininterpretiert. Tut mir leid.



  • 👍 😃

    Nicht einfach sich im Feindesland zu bewegen. 😞 😃



  • .filmor schrieb:

    Ich will auch noch eine Art loswerden 😃
    [Code als Iterator]
    Keine Ahnung, obs funktioniert, aber ich finds toll ;).

    Nö, klappt nicht, aber da ich die Idee toll fand, habe ich's auch nochmal versucht:

    struct FibIter : public std::iterator<std::input_iterator_tag, int> {
    
        FibIter() : n(0), a(0, 1) {}
        FibIter(int n) : n(n), a(0, 1) {}
    
        FibIter& operator ++()
        {
            ++n;
            std::swap(a.first, a.second);
            a.second += a.first;
            return *this;
        }
    
        FibIter operator ++(int)
        {
            FibIter ret(*this);
            ++*this;
            return ret;
        }
    
        int operator *() const { return a.second; }
    
        bool operator ==(FibIter const& other) const { return n == other.n; }
        bool operator !=(FibIter const& other) const { return not (*this == other); }
    
    private:
        std::pair<int, int> a;
        int n;
    };
    
    // ...
    
    std::copy(FibIter(), FibIter(10), vector.begin());
    


  • Konrad Rudolph schrieb:

    Nö, klappt nicht

    Sagen wir mal "nicht ganz". Hier die um die iterator_tags, operator!= und einen funktionierenden operator* erweiterte Variante (bei der allerdings immernoch die erste 1 fehlt ;)):

    class fib_iterator : public std::iterator<std::input_iterator_tag, unsigned int>
    {
    public:
        fib_iterator (unsigned int N = 0) : _n (N)
        { _pred[0] = _pred[1] = 1; }
    
        fib_iterator& operator++ ()
        {
            --_n;
            _pred[_n % 2] = _pred[0] + _pred[1];
            return *this;
        }
    
        unsigned int operator* ()
        { return _pred[(_n - 1) % 2]; }
    
        bool operator== (const fib_iterator& other) const
        { return _n == other._n; }
    
        bool operator!= (const fib_iterator& other) const
        { return !(*this == other); }
    
    private:
        unsigned int _n;
        unsigned int _pred[2];
    };
    

Anmelden zum Antworten