www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "C/C++" - Fibonacci Rekursiv
Fibonacci Rekursiv < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "C/C++"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Fibonacci Rekursiv: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:02 Sa 15.12.2007
Autor: Auron2009

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!


        
Bezug
Fibonacci Rekursiv: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Fibonacci Rekursiv: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:23 Sa 15.12.2007
Autor: Auron2009

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. :/

Bezug
                        
Bezug
Fibonacci Rekursiv: Antwort
Status: (Antwort) fertig Status 
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]

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


Bezug
                                
Bezug
Fibonacci Rekursiv: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:08 Sa 15.12.2007
Autor: Auron2009

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.

Bezug
                                        
Bezug
Fibonacci Rekursiv: Antwort
Status: (Antwort) fertig Status 
Datum: 00:02 So 16.12.2007
Autor: BiGfReAk

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

Bezug
                                                
Bezug
Fibonacci Rekursiv: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:44 So 16.12.2007
Autor: Auron2009

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."


Bezug
                                                        
Bezug
Fibonacci Rekursiv: Antwort
Status: (Antwort) fertig Status 
Datum: 12:01 So 16.12.2007
Autor: Martin243

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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "C/C++"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]