fibonacci zahlen

dEUs schrieb:

du weisst, was konstant bedeutet?

hey ich bin newbie, da muss ich das nich wissen

ne ich weiß schon was ihr meint, aber hauptsache ist erstmal dass alles funzt.

Mis2com

Wenn du das allerdings auf einen anderen, besseren Compiler übertragen willst, dann wirst du die Welt nicht mehr verstehen.
Ich sage dir, mach es richtig, du eignest dir da einen schlechten Stil an.

Mis2com schrieb:

Wenn du das allerdings auf einen anderen, besseren Compiler übertragen willst, dann wirst du die Welt nicht mehr verstehen.
Ich sage dir, mach es richtig, du eignest dir da einen schlechten Stil an.

naja das seh ich ein... aber wie gehts denn richtig? wenn ich das anders machen soll, muss ich doch eigentlich das ganze programm umorganisieren, oder?

ich will ja nich direkt am zweiten tag auf den falschen weg kommen.

sorry für den doppelpost, aber ich habs jetzt mal mit ner funktion gemacht.

#include <iostream>

using namespace std;

int fib (int n)

{
        if ( n <= 2 ) return 1;

        else return fib(n-1) + fib(n-2);
}

main ()

{
        int  i,x;
        char wh;

        cout << "\n" << "n: ";
        cin >> x;
        cout << endl;

        for ( i = 1 ; i <= x ; i++ )
        {
                cout << "fib(" << i << "): " << fib(i) << endl;
        }

        cout << endl;
        cout << "wh? ";
        cin >> wh;

        switch (wh)
        {
                case 'j' : main();
                default  : exit;
        }
}

jetzt wirds (aufgrund der rekursion nehme ich an) aber immer langsamer. so ab fib(40) muss man schon geduldig sein...

tipps?

mfg

John Doe

1.) Du verwendest eine Formel zur Berechnung

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char* argv[])
{
  unsigned int arg = atoi(argv[1]);
  long double fib = floor(powl((1.0 + powl(5.0, 0.5)) 
                    / 2.0, arg) 
                    / (powl(5.0, 0.5)) + 0.5);
  printf("Fib(%u): %.lf\n", arg, fib);

  return 0;
}

2.) Du reduziert den Aufwand der Berechnung . Im Moment rechnest du in eine Schleife jeden Wert extra aus. Du hast bei aufsteigender Schleife den "Vorgänger"-Wert jedoch schon. Ich hoffe du vesteht wie ich das meine. Für i = 40 beispielsweise berechnest du 20 mal den wert von fib(20). Das heisst, du solltest den erhaltenen Wert weiter verwenden. Wenn du fib(40) ausrechnest bestimmst du automatisch alle die Werte von fib(1) bis fib(39). Ich hoffe du kannst folgen. Wenn du dein Programm entsprechend umstellst veringert sich die Laufzeit erheblich.

mfg JJ

HumeSikkins

jetzt wirds (aufgrund der rekursion nehme ich an) aber immer langsamer

Die Fibonacci-Zahlen rekursiv zu berechnen ist so ein typisches Anti-Beispiel aus Programmierbüchern.

Iterativ:

int fib2(int n) 
{ 
	int a = 0; 
	int b =1;
	for (int i = 1; i < n; ++i)
	{
		b = b + a;
		a = b - a;
	}
	return b;
}

danke für die tipps leute!

ich habs jetzt iterativ und in gültigem c++ hingekriegt ( hoffe ich ).

#include <iostream>

using namespace std;

main ()

{
        int n,i;
        char wh;

        cout << "\nn: ";
        cin >> n;

        cout << "\nfib(1): 1\n";

        long long a = 0;
        long long b = 1;

        for ( i = 2 ; i <= n ; i++ )
        {
                b = b + a;
                a = b - a;
                cout << "fib(" << i << "): " << b << endl;
        }

        cout << "\nwh? ";
        cin >> wh;

        switch (wh)
        {
                case 'j' : main(); break;
                default  : exit;
        }
}

das einzige problem ist jetzt aber immer noch das mit den zu großen zahlen.

also wäre einer bitte so nett und erklärt mir wie das mit der GNU MP bibliothek geht?

mfg

virtuell Realisticer

Hallo,

ich hab mir das mal angeschaut und in der GNU MP Lib gibt es die mpz_fib_ui
Funktion, die das fuer dich macht, aber ich nehme mal an, dass du das selbst
machen willst :).

#include <iostream>
#include <gmpxx.h>

using namespace std;

int main()
{
    int n;

        cout << "\nn: ";
        cin >> n;

        cout << "\nfib(1): 1\n";

        mpz_class a = .0,
                  b = 1.0;

        for ( int i = 2 ; i <= n ; i++ )
        {
                b = b + a;
                a = b - a;
                cout << "fib(" << i << "): " << b << endl;
        }

        char wh;

        cout << "\nwh? ";
        cin >> wh;

        switch (wh)
        {
                case 'j' : main(); break;
                default  : exit;
        }
    return 0;
}

Das sollte es eigentlich tun. Hab mich noch nicht so weit in die Doku gelesen.
Aber das solltest du eh tun, wenn du es in Erwägung ziehst diese Lib zu nutzen.

mfg
v R

Bashar

virtuell Realisticer schrieb:

case 'j' : main(); break;
                default  : exit;

*räusper*

virtuell Realisticer

Bashar schrieb:

virtuell Realisticer schrieb:
case 'j' : main(); break;
                default  : exit;
*räusper*

Dat hab ich kopiert

mfg
v R

m0rph3uz

naja das Forum ist ja dazu da um was zu lernen *g*

Bashar

Also dann:

main() aufzurufen ist vom Standard her nicht erlaubt. Wenn's bei deinem Compiler geht, OK, aber du hast dafür keine Garantie.
Rekursion ist hier völlig unangebracht. Guck dir do..while an.
Wenn schon exit, dann musst du die Funktion auch aufrufen: exit**()**. Compiler müsste bei sowas eigentlich warnen, «Statement has no effect» oder sowas.
exit() ist in (fortgeschrittenem) C++ bäh, weil keine Destruktoren aufgerufen werden.

ich werd mich wohl noch etwas mehr mit c++ beschäftigen müssen...

danke für die vielen tipps, ihr habt mir echt geholfen!

mfg