Entwickler-Ecke :: Thema anzeigen

GericasS - Mo 07.12.09 22:08
Titel: C++ Fibonacci

Guten Abend liebe Community,

ich hab heute mit C++ angefangen und mich an der Fibonacci Reihe versucht, sieht wie folgt aus :

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

#include<iostream>
#include<windows.h>

using namespace std;

unsigned int fibonacci(unsigned int zahl)
{
  if (zahl == 0)
  {
    return 0 ;
  }
  if (zahl == 1)
  {
    return 1;
  }
  return fibonacci(zahl-1)+ fibonacci(zahl-2);
}
int main() 
{
    unsigned int zahl;

    cout << "Bitte Zahl eingeben: ";
    cin >> zahl;                                
    cout << "Die Fibonacci-Zahl von " << zahl <<
        " ist " << fibonacci(zahl) << "!" << endl;
  system("Pause");
}

Die main() verstehe ich, aber in der fibonacci Funktion steige ich einfach nicht durch wie er wenn ich als "zahl" z.B die 6 angebe auf die Fibnacci 8 kommt.
Wenn mir vll. jemanden genauer zeigen könnte wie es innerhalb dieser Funktion abläuft wäre ich sehr dankbar.

Vll. so ? fib(6-1)+fib(5-2) usw. ?

LG

GericasS

Gausi - Mo 07.12.09 22:18

Das Prinzip der "Rekursion" ist dir aber geläufig? Hier hat man halt eine baumartige Rekursion, d.h. zur Berechnung werden zwei rekursive Aufrufe hintereinander gestartet - ist für die Laufzeit natürlich nicht gerade toll.
Bei anderen rekursiven Berechnungen wie z.B. der Fakultät hat man nur einen rekursiven Aufruf pro Schritt.

Gausi - Mo 07.12.09 22:28

Grob, ja. :D

Für die Berechnung von fib(6) wird zunächst fib(6-1) berechnet, danach fib(6-2), das Ergebnis beider Berechnungen wird dann addiert.
Für die Berechnung von fib(6-1) = fib(5) wird zuerst fib(4) und dann fib(3) berchnet. Ja, fib(4) wird doppelt berechnet. So geht das weiter runter.

Gausi - Mo 07.12.09 22:41

Nein, die Fibonacci-Zahlen sind so definiert:

0, 1, 1, 2, 3, 5, 8, 13, 21, ... also immer die Summe der beiden vorherigen. Also fib(6-1) = fib(5) = 5 (0 ist die Nullte Fibonacci-Zahl), und fib(6-2) = fib(4) = 3.

6-1 ist 5, und das wird als Argument für die fib-Funktion genommen.

gfoidl - Di 08.12.09 01:04

Hallo,

damit nicht immer alle Werte rekursiv erneut berechnet werden müssen können diese zwischengespeichert und wiederverwendet werden. Sie ändern sich ja nicht. (das führt in Richtung dynamischer Programmierung)

Gruss
Günther

Namenlosnameless - Di 08.12.09 01:37

naja ich bin mir ja nicht so sicher ob ich verstanden habe worum es geht: aber wenn ich mich nicht verlesen habe willst du alle Fibonacci-Zahlen bis zu einer bestimmten ausrechnen lassen??
Das geht aber irgendwie einfacher.

Wobei bei den ganzen Programmierprofis die am Thread teilnehmen habe ich mich sicher geirrt^^

mfg Namenlosnameless

gfoidl - Di 08.12.09 01:46

Zitat:

also bevor ich hier dynamische Programmierung verwende, verwende ich lieber ne Schleife!

Dann hast du wohl dynamische Programmierung nicht richtig verstanden :P
Der Bottom-Up Ansatz der dynamischen Programmierung wäre das was du mit Schleife meinen wirst.
(Vieles was logisch und einfach scheint wurde benamt, so auch hier.)

Gruss
Günther

elundril - Di 08.12.09 01:48

also dyn. Programmierung war, soweit ich AlgoDat1 noch in erinnerung hatte: Rekursion mit einem Array in dem schon gefundene lösungen zwischengespeichert werden und wo man dann einfach nachguckt. Oder hab ich da was falsch in erinnerung bzw falsch verstanden?

lg elundril

gfoidl - Di 08.12.09 02:13

Du hast eher die zweite Art der Interpretation/Anwendung nicht berücksichtigt.

Lass mich die dynamische Programmierung allgemeiner so erklären:

Die Lösungen kleinerer Teilprobleme werden dirket berechnet und zwischengespeichert und zu einer Lösung eines größeren Problems zusammengesetzt.

Somit gibt es die Möglichkeit per Rekursion von der großen Lösung auf die kleineren Lösungen zu kommen (top-down) oder beginnend mit der kleinsten Lösung die größeren zusammenzubauen (bottom-up). Es ist also beiden möglich und verwendet die selbe Technik, welche mit dynamischer Programmierung benamt wurde.

Genau das Beispiel der Fibonacci-Zahlen wird übrigens auch in der engl. Wiki [http://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence] angeführt.

Gruss
Günther

Gausi - Di 08.12.09 08:51

@Namenlosnameless: Ja, das geht einfacher. Ein Ansatz wurde ja in den letzten Beiträgen diskutiert. Aber hier geht es wohl um die Funktionsweise dieses Codes da oben. Das ist ein klassisches Beispiel für baumartige Rekursion mit einer absolut tollen Laufzeit. Dagegen geht Bubblesort ab wie Schmidts Katze. ;-)

GericasS - Di 08.12.09 21:14

Abend,

könnte mir bitte nochmal jemand erklären was genau in diesem Abschnitt passiert wenn die Zahl nicht 0 oder 1 ist :

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

unsigned int fibonacci(unsigned int zahl)
{
  if (zahl == 0)
  {
    return 0 ;
  }
  if (zahl == 1)
  {
    return 1;
  }
  return fibonacci(zahl-1)+ fibonacci(zahl-2);
}

Wenn die eingebene Zahl z.b 6 ist !

LG

GericasS

elundril - Di 08.12.09 22:33

in dem abschnitt rufst du die funktion noch mal auf und gibst das ergebnis von den beiden aufrufen zurück.

also fibonacci(5) + fibonacci(4). und die resultate davon gibst du zurück. im fibonacci(5) gibst du dann fibonacci(4) + fibonacci (3) zurück, usw. so lange bist du fibonacci(0) aufrufst. das gibt dann gleich 0 zurück. Wie du demnach siehst eignet sich fibonacci nicht wirklich für rekursionen. ;)

lg elundril

Flamefire - Di 08.12.09 23:51

oder aus wiki:

Zitat:

Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Jakob_Ullmann - Mi 09.12.09 19:46

Also ich würde es ja so machen (Pseudocode):

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

prozedur Fibonacci(x: ganzzahl)
wenn x > 2 dann
  Fibonacci(x) = Fibonacci(x - 2) + Fibonacci(x - 1)  
sonst wenn x = 0 dann
  Fibonacci(x) = 0
sonst wenn x <= 2 dann
  Fibonacci(x) = 1
ende prozedur

Ich denke aber, das ganze würde ohne Rekursion trotzdem wesentlich schneller gehen:

Quelltext

1:
2:
3:
4:
5:

fib[0] = 0
fib[1] = 1
fib[2] = 2
für i = 3 bis x tue
  fib[i] = fib[i - 2] + fib[i - 1]

EDIT: Wobei ich jetzt ehrlich gesagt nicht weiß, inwieweit man sowas in C++ umsetzt. Dynamosche Arrays gibt es da ja afaik nicht. Höchstens über Pointer vielleicht...

Gausi - Mi 09.12.09 20:02

Geht auch ohne Arrays - man braucht ja immer nur die letzten beiden Zahlen. ;-)

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

vorletzteFib := 0;
letzteFib := 1;

for i := 2 to n do
begin
  neueFib := letzteFib + vorletzteFib;
  vorletzteFib := letzteFib;
  letzteFib := neueFib;
end;
result := letzteFib;

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!