Fibonacci Rekursiv < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | Die Fibonacci-Zahlen Fn (n aus N) sind durch folgende Rekursionsvorschrift definiert:
Fn := Fn−1 + Fn−2 (n >=3)
F2 := 1
F1 := 1
Schreiben Sie ein C-Programm, das mit Hilfe einer rekursiven Funktion
int fib(int n)
F5, F10, F15, F20, F25 und F30 ermittelt. Sch¨atzen Sie die für F35 benötigte Zeit ab und begründen
Sie Ihre Vermutung.
Hinweis: Führen Sie eine globale int-Variable ein, in der die Aufrufe der fib-Funktion gezählt
werden. |
Ich weiß nicht, wie ich das Problem rekursiv angehen soll. Der Programmrahmen sollte ungefähr so aussehen:
#include <stdio.h>
int fib(int stellen)
{
ergebnis = fib(stellen-1) + fib(stellen-2);
printf("%d", stellen);
return stellen;
}
int main(void)
{
int stellen, i;
printf("Zahl eingeben: ");
scanf("%d", &stellen);
fib(stellen));
return 0;
}
Aber so klappt das natürlich noch nicht. Und das mit der Rekursion ist mir noch nicht geläufig genug. :(
Vielen Dank an alle, die mir helfen können!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:16 Sa 15.12.2007 | | Autor: | rainerS |
Hallo!
Wie wäre es, wenn du in deiner Funktion fib das ergebnis zurückgeben würdest statt des Eingabeparameters stellen.
Viele Grüße
Rainer
|
|
|
| |
|
Das ist eigentlich nicht so wichtig, da die Ausgabe der Folge in der Funktion fib stattfinden sollte und nicht in der Main Funktion. Die fib Funktion bräuchte also eigentlich gar keinen return Wert. Klappen tut es so oder so gar nicht. Da stimmen noch wesentliche Teile in der fib-Funktion noch nicht, und weiß nicht, wie es geht. :/
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:41 Sa 15.12.2007 | | Autor: | rainerS |
Hallo!
> Das ist eigentlich nicht so wichtig, da die Ausgabe der
> Folge in der Funktion fib stattfinden sollte und nicht in
> der Main Funktion.
Das steht so nicht in der Aufgabe.
> Die fib Funktion bräuchte also
> eigentlich gar keinen return Wert.
![[notok]](/images/smileys/notok.gif "[notok]")
Du benutzt den Rückgabewert beim rekursiven Aufruf. Kein sinnvoller Rückgabewert => keine sinnvolle Rechnung.
> Klappen tut es so oder
> so gar nicht. Da stimmen noch wesentliche Teile in der
> fib-Funktion noch nicht, und weiß nicht, wie es geht. :/
Ja, der Rückgabewert ist falsch. Gibt ergebnis zurück und verschiebe das Printf nach main.
Viele Grüße
Rainer
|
|
|
| |
|
Habe das jetzt glaube ich so gemacht, wie du meintest, aber es klappt immer noch nicht:
#include <stdio.h>
int fib(int stellen)
{
int ergebnis;
ergebnis = fib(stellen-1) + fib(stellen-2);
return ergebnis;
}
int main(void)
{
int stellen, ergebnis;
printf("Zahl eingeben: ");
scanf("%d", &stellen);
ergebnis = fib(stellen);
printf("%d", ergebnis);
return 0;
}
Er gibt überhaupt keine Ausgabe aus.
|
|
|
| |
|
Hi
Also als aller erstes musst du wissen, was eine Fibonacci-Folge überhaupt ist => Sie gibt eine Zahl an, die die Summe ihrer 2 vorgängern ist.
Hier siehst du die ersten paar Zahlen (aus Wikipedia):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1.597, 2.584, 4.181, 6.765, 10.946 ...
Erst wenn man das weis, kann man anfangen zu programmieren.
> Die fib Funktion bräuchte also
> eigentlich gar keinen return Wert.
Das eigentliche an einer rekursiven Funktion IST der Return Wert. Dieses zeichnet eben eine rekursive Funktion aus.
Das Programm müsste folgendermaßen aussehen:
#include <stdio.h>
int fib(int n);
int main() /* Ich denk main muss ich nicht erklären */
{
int zahl;
printf("Bitte Zahl eingeben: ");
scanf("%d",&zahl);
printf("Ergebnis: %d", fib(zahl));
getch();
return 0;
}
int fib(int n)
{
if(n==2 || n==1) return 1;
if(n>=3)
return(fib(n-1) + fib(n-2));
}
Erklärung:
Als erstes musst du die Bedingung prüfung ob n 2 oder 1 ist. Für diese 2 Fälle musst du die 1 zurückgegen (steht ja auch so in der Aufgabe: F2 := 1 F1 := 1 ). Wenn dein n gräßer oder gleich 3 ist, dann Bildest du die Fibonacci-Folge von n-1 (fib(n-1)) und addierst es mit der Summe der Folge von n-2 (fib(n-1)). Das das ist auch schon alles. Ist eigentlich ganz simpel ... Falls du das Programm nicht verstehen solltest, dann kannst du dir mal ne kleine Skizze machen, wie die Berechnung abläuft. Spätestens dann versteht man das. Andernfalls kannst du nochmal nachfragen. Wir beißen nicht :) ... zumindest ich nicht
|
|
|
| |
|
Zunächst einmal vielen Dank, es funktioniert und ich verstehe das Programm auch so weit. Außer der Fallunterscheidung für zahl = 1,2 ist es meinem Versuch ja auch schon ähnlich. :)
Eine kleine Frage hätte ich noch: Was bewirkt das "getchar()" am Ende der main-Funktion genau? Notwendig ist es ja nicht.
Und was müsste man ändern, wenn man als Ergebnis nicht nur die eine Zahl haben möchte, sondern die gesamte Fibonacci Folge bis zu der Zahl?
Und mir fehlt noch der letzte Teil der Aufgabenstellung:
"Führen Sie eine globale int-Variable ein, in der die Aufrufe der fib-Funktion gezählt
werden."
|
|
|
| |
|
Hallo,
> Außer der Fallunterscheidung für zahl = 1,2 ist es meinem Versuch ja auch schon ähnlich. :)
Ja, nur fehlte dir eben die Rekursionsbasis. Ohne die ist deine Rekursion quasi bodenlos.
> Eine kleine Frage hätte ich noch: Was bewirkt das "getchar()" am Ende der main-Funktion genau? Notwendig ist es ja nicht.
Es wartet einfach auf eine Benutzereingabe, bevor das Programm sich beendet. Das kann hilfreich sein, wenn das Programm z.B. unter Windows direkt von einer IDE aus oder per Doppelklick ausgeführt wird. Dann geht nämlich ein Konsolenfenster auf, du gibst deine Zahl ein, die Ausgabe läuft blitzschnell durch und das Fenster ist wieder weg. Das Problem scheinst du nicht zu haben.
> Und was müsste man ändern, wenn man als Ergebnis nicht nur die eine Zahl haben möchte, sondern die gesamte Fibonacci Folge bis zu der Zahl?
Dann müsstest du in der main-Funktion eine for-Schleife haben, die die Funktione auf alle Werte bis zu dieser Zahl anwendet. Das direkt in die Funktion einzubauen ist problematisch, da man ja rückwärts geht. Wenn das für dich kein Problem ist, könntest du innerhalb der Funktion ja immer fib(stellen-1) ausgeben (mit der Fallunterscheidung von BiGfReAk).
> Und mir fehlt noch der letzte Teil der Aufgabenstellung:
> "Führen Sie eine globale int-Variable ein, in der die Aufrufe der fib-Funktion gezählt werden."
Dann tu es doch. Deklariere eine int-Variable außerhalb aller Funktionen und inkrementiere sie in der fib-Funktion. So wird sie bei jedem Aufruf automatisch erhöht.
Gruß
Martin
|
|
|
|
