# Fibonacci Zahlen generieren mit C



## studine (18. Dezember 2013)

Hallo, 

ich habe die Aufgabe ein C-Programm zu schreiben mit einer Unterfunktion, welche die Fibonacci Zahlen an den Monitor ausgibt. Die Unterfunktion soll je eine Fibonacci Zahl als Rückgabewert liefern. Der Benutzer soll mittels cin eingeben, wie viele Zahlen er haben möchte. Mein Program sieht wie folgt aus (Wenn ich es laufen lassen kommt: Fibonaccizahlen.exe funktioniert nicht  mehr.)

```
#include <stdio.h>
int fibonacci (int, int *,int,int,int);

int main ()

{
    printf("Wie viele Fibonacci Zahlen moechten Sie generieren?\n");
    int max;
    scanf("%i", &max);

    int a=0;
    int b=1;
    int i;
    int feld [i];

    feld[0]=a;
    feld[1]=b;
    int fibonaccizahlen;

    fibonaccizahlen=fibonacci(i,feld, a,b,max);
    printf ("%i", fibonaccizahlen);


    return 0;
}

int fibonacci(int i,int *feld, int a, int b, int max)
{
    for (i=1;i<max;i++)
        {feld[i+1]=feld[i]+feld[i-1];
        return feld[i];}

}
```

Vielen Dank schon mal für eure Hilfe


----------



## Bratkartoffel (18. Dezember 2013)

Hi,

siehe Zeilen 14 und 15. Du definierst das Array "feld" mit einer Größe von 0. Somit bekommst du früher oder später (denke mal Zeile 18) einen Segfault.

Grüße,
BK


----------



## Cromon (18. Dezember 2013)

Ich würde sogar sagen er initialisiert ein Array 'feld' der Grösse 'undefiniert'.

Grüsse
Cromon


----------



## Bratkartoffel (18. Dezember 2013)

Cromon hat gesagt.:


> Ich würde sogar sagen er initialisiert ein Array 'feld' der Grösse 'undefiniert'.



Soweit ich es richtig im Kopf habe gilt das nicht für primitive Zahlen (short, int, long, double, float), sondern nur für Speicherbereiche / structs / Arrays.

// Edit: Oh, meine Einschätzung ist auch nicht ganz richtig. Hier eine vollständige Erklärung: http://stackoverflow.com/a/1597426/1164913

Grüße,
BK


----------



## Technipion (18. Dezember 2013)

Hallo studine,

leider ist dein Code noch etwas wenig formatiert, achte bitte darauf dir gleich anzugewöhnen Leerzeichen und Zeilenumbrüche einzubauen.

Ich habe hier mal die korregierte Version, ich denke die Kommentare sind selbsterklärend.
Falls du noch Fragen haben solltest einfach posten.


```
#include <stdio.h>
int fibonacci (int *,int,int,int); //prototyp

int main ()

{
    printf("Wie viele Fibonacci Zahlen moechten Sie generieren?\n");
    int f_max; //Bitte keine Sprachinternen Stichwörter als Variablenname verwenden!
    scanf("%i", &f_max); //du möchtest wissen wie viele Zahlen der User generiert haben will -> f_max

    int a = 0;
    int b = 1;
    ///int i; //wofür?!
    ///int feld [i]; //du musst vorher initialisieren!
    int feld[f_max]; //so meintest du es wahrscheinlich
    /* Es wäre besser long oder long long zu verwenden */

    feld[0] = a;
    feld[1] = b; //Startvariablen festlegen, ok...
    int fibonaccizahlen; //wofür brauchst du einen Rückgabewert?

    fibonaccizahlen = fibonacci(feld, a, b, f_max); //Du brauchst kein int i!
    printf("%i", fibonaccizahlen); //Das gibt 0 aus => hat geklappt...

    for(int i = 0; i < f_max; i++) //über alle Zahlen von feld[] hinweg...
        printf("\n%ite Fzahl: %i", i, feld[i]); //... die Fibonacci-Zahl ausgeben


    return 0;
}

int fibonacci(int *feld, int a, int b, int f_max)
{
    for (int i = 1; i < f_max; i++) //hier int i definieren!
        {
            feld[i+1] = feld [i] + feld [i-1];
            ///return feld[i]; //Warum tust du das?!
        }
    return 0; //Wenn die Schleife bis hierher durchgelaufen ist, ist alles gut gelaufen

}
```

Gruß Technipion


----------



## Cromon (18. Dezember 2013)

```
for (int i = 1; i < f_max; ++i) {
    feld[i + 1] = feld[i] + feld[i - 1];
}
```

Die Schleife solltest du nur bis f_max - 1 gehen lassen wegen dem i + 1.

Viele Grüsse
Cromon


----------



## Technipion (18. Dezember 2013)

In der Eile hatte ich das ganz übersehen...
Danke für den Hinweis!

Aber eigentlich würde sowieso kein Mensch solchen Code benutzen, zumindest nicht wenn es auch nur um einen Hauch Performance geht.

Gruß Technipion


----------



## studine (19. Dezember 2013)

Hey Leute, 

also erstmal vielen vielen Dank für die tolle Hilfe. Ich hab jetzt mal alles versucht umzusetzen.

@ technipion:

ich sollte ja in main() kein int i reinmachen. das habe ich weggelassen. aber in Zeile 25,26 taucht es ja wieder auf und mein programm meckert dann, dass er i nicht kennt. 

Wieso würde keiner so einen code benutzten? Wir haben die Aufgabe so gestellt bekommen. und da ich noch absoluter c anfänger bin, fällt mir das alles verdammt schwer. liegt mir nicht so das ganze, auch wenns spaß macht sobald man es verstanden hat....


----------



## studine (19. Dezember 2013)

so habe nun auch einmal in int main() die Variable i angelget und jetzt läuft es prima, genau so wie es soll! Echt super! DANKE******


----------



## Technipion (19. Dezember 2013)

Hey, schön dass dir C++ Spaß macht!

Den Integer i brauchst du in der Main nicht, weil du ja in deinem Code nur innerhalb von int fibonacci() iterierst.
Int i hat hier die Funktion einer Zählvariable, aber was willst du in main() zählen? Gezählt wird da wo die for-Schleife ist, also wird auch da int i erst benötigt.

Ich habe gesagt, dass die Performance von dem Programm schlecht ist, weil Programmierstil und Programmziel nicht zueinander passen:
Ziel ist es ein Programm zu schreiben, dass alle Fibonaccizahlen bis f_max ausgibt. Die Ermittlung von Fibonaccizahlen erfolgt rekursiv, d.h. man muss für die i-te Fibonaccizahl über alle Zahlen bis i iterieren (das macht übrigens die Funktion int fibonacci()...). Deswegen wäre es ressourcenschonend, einmal von 1 bis i zu iterieren und die Ergebnisse auszugeben ( die Laufzeit O (Ordnung) ist dann proportional zu f_max ).
Dein Code bedient sich jedoch einer Funktion die jeweils bis zur n-ten Fibonaccizahl iteriert und diese dann zurückgibt. Das heißt du hast bei jedem Funktionsaufruf eine Sublaufzeit mit O (Ordnung) n. Diese Funktion rufst du dann in main() für jede Zahl bis f_max auf -> du iterierst über eine Iteration -> enorme Laufzeiteinbuse!
Bsp: Programm soll ersten 5 Fibonaccizahlen berechnen:
Gute Version: berechnung 1, 1, 2, 3, 5 ---> ausgabe: 1, 1, 2, 3, 5
Schlechte Version:
berechnung 1
berechnung 1, 1
berechnung 1, 1, 2
berechnung 1, 1, 2, 3
berechnung 1, 1, 2, 3, 5 ---> ausgabe: 1, 1, 2, 3, 5

Verstehst du das?

Gruß Technipion


----------



## studine (19. Dezember 2013)

Ich glaube ich habe das verstanden, aber wie setzt man das dann um? ohne dass der für jede zahl die zahlen davor auch ausrechnen muss.


----------



## Technipion (19. Dezember 2013)

Ich denke der Code ist wieder mal selbsterklärend.


```
#include <stdio.h>


int main ()

{
    printf("Wie viele Fibonacci Zahlen moechten Sie generieren?\n");
    int f_max; //Anzahl der Zahlen, die der Benutzer generieren möchte
    scanf("%i", &f_max); //einlesen...

    if(f_max <= 0){ //falls der Benutzer <= 0 eingibt, brich ab. Hier wäre eine Erweiterung zu den negativen Fibonaccizahlen denkbar?
        printf("Depp!");
        return 0;
    }
    if(f_max == 1){ //falls der Benutzer 1 eingibt: gib direkt 0 zurück.
        printf("1te fzahl: 0\n");
        return 0;
    }
    if(f_max == 2){ //falls der Benutzer 2 eingibt: gib direkt 0 und 1 zurück
        printf("1te fzahl: 0\n2te fzahl: 1\n");
        return 0;
    }
    //sonst fahre fort:

    //Startwerte festlegen
    unsigned long long Fzahl1 = 0; //axiomatisch
    unsigned long long Fzahl2 = 1; //axiomatisch
    unsigned long long Fzahl3;
    /* insgesamt braucht man nur 3 Variablen */

    //printe schonmal die ersten beiden
    printf("1te fzahl: 0\n2te fzahl: 1\n");

    for(int i = 2; i < f_max; ++i){ //iteriere nun von der 3. Fzahl bis zur gewünschten
        Fzahl3 = Fzahl1 + Fzahl2; //3. Zahl sei Summe aus den beiden davor
        Fzahl1 = Fzahl2; //shifte 2. Zahl zu 1. Zahl
        Fzahl2 = Fzahl3; //shifte 3. Zahl zu 2. Zahl
        /* damit ist der nächste Durchlauf der Schleife vorbereitet, da wir alle Zahlen um eine Stelle verschoben haben */
        printf("%ite fzahl: %llu\n", i+1, Fzahl2); //gib Fzahl2 aus (das ist die aktuelle Fzahl)
        /* Hinweis: (unsigned long long) ist groß, aber da die Folge schnell divergiert ist bei etwa i = 70 Schluss! */
    }

    return 0;
}
```

Im Grunde ist das was ich jetzt getan habe bloß, dass ich den Algorithmus etwas vereinfacht habe. Am Anfang kann das sehr undurchsichtig für dich sein, aber glaube mir die üblichen Vorgehensweisen werden sich nach und nach in dir festigen.

Bleib am Ball und hab Spaß!

Gruß Technipion


----------



## studine (19. Dezember 2013)

puh, verstanden  und sieht echt gut aus. auf die idee mit den drei variablen wäre ich mit sicherheit  nie gekommen. 

Da du jetzt keine Unterfunktion drin hast, nehme ich an, dass wenn ich eine Unterfunktion reinmache, die immer je eine neue fibonacci zahl hochschickt. richtig? das was du vermeiden willst mit deinem programm


----------



## Matthias Reitinger (20. Dezember 2013)

Technipion hat gesagt.:


> ```
> int f_max; //Bitte keine Sprachinternen Stichwörter als Variablenname verwenden!
> ```


Wie kommst du darauf, dass max ein "sprachinternes Stichwort" sein sollte? Es spricht im Grunde nichts dagegen, in einem C-Programm eine Variable max zu nennen.

Grüße
Matthias


----------



## Technipion (20. Dezember 2013)

Du hast Recht, in dem Fall hier könnte studine 'int max' verwenden.
Aber damit er/sie später einen guten Programmierstil erhält, sollte man ihn/sie jetzt schon darauf aufmerksam machen, dass es bei solchen gängigen Stichwörtern wie max zu Komplikationen kommen kann.

So ist max z.B. eine Funktion in der Standardbibliothek:
http://en.cppreference.com/w/cpp/algorithm/max

Spätestens wenn man dann lokal das Standard-Namespace benutzt wird der Compiler verwirrt sein...

Grüße Technipion


----------

