# Fibonacci-Folge



## MaxMustermann (27. Oktober 2018)

Hallo,

ich muss ein Programm schreiben, welches die Fibonacci-Zahlen berechnet und ausgibt.

Laut Aufgabenstellung ist so ein Programm mit vier Variablen und einer Schleife realisierbar. 

Mein aktuelles Programm: 

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

int main()
{


int zahl1 = 0;
int zahl2 = 1;
int max = 10;
int fib;
int n = 2;

printf("%d\t %d\t" ,zahl1,zahl2);
while(n <= max)
    {
        fib = zahl1 + zahl2;
        zahl1 = zahl2;
        zahl2 = fib;
        n++;

        printf("%d\t", fib);

    }

return EXIT_SUCCESS;
}

Eigentlich sollte es die Zahlen 0 1 1 2 3 5 8 ausgeben, aber es rechnet hoch bis 55...

Wenn ich der Variable n den Wert 6 zuweise, funktioniert es. Aber sobald ich den Maxwert wieder verändere ,zählt es viel viel weiter hoch. 

Würde mich über eine Hilfestellung freuen. 

Viele Grüße


----------



## cwriter (27. Oktober 2018)

MaxMustermann hat gesagt.:


> Eigentlich sollte es die Zahlen 0 1 1 2 3 5 8 ausgeben, aber es rechnet hoch bis 55...


Warum sollte es denn nur bis 8 gehen?
https://de.wikipedia.org/wiki/Fibonacci-Folge#Definition_der_Fibonacci-Folge
Dein max bestimmt ja, welche Fibonacci-Zahl du Schlussendlich haben willst (naja, fast, für max < 2 ist's was anders.)
n solltest du nicht verändern, es zeigt ja nur an, bei welcher Fibonaccizahl du gerade bist.



MaxMustermann hat gesagt.:


> Aber sobald ich den Maxwert wieder verändere ,zählt es viel viel weiter hoch.


Die Fibonaccifolge ist per definitionem unendlich - und ich sehe keine Begrenzung in der Aufgabenstellung. Dein max bestimmt die höchste Zahl - wenn du nur die veränderst, passt alles - der Rest des Programmes stimmt nämlich (mit Ausnahme der "kleinen" Fibonaccizahlen).
Wenn du max=6 setzt, sollte deine erwartete Ausgabe auftreten.

Gruss
cwriter


----------



## MaxMustermann (27. Oktober 2018)

cwriter hat gesagt.:


> Warum sollte es denn nur bis 8 gehen?
> https://de.wikipedia.org/wiki/Fibonacci-Folge#Definition_der_Fibonacci-Folge
> Dein max bestimmt ja, welche Fibonacci-Zahl du Schlussendlich haben willst (naja, fast, für max < 2 ist's was anders.)
> n solltest du nicht verändern, es zeigt ja nur an, bei welcher Fibonaccizahl du gerade bist.
> ...


Verstehe, danke  

In der Angabe steht eben, dass wenn man  z.B. n = 10 setzt, sollte es 0 1 1 2 3 5 8 ausgeben. Das n sollte bei mir die max Variable sein. 

Wie könnte ich das am besten lösen?


----------



## cwriter (27. Oktober 2018)

MaxMustermann hat gesagt.:


> In der Angabe steht eben, dass wenn man z.B. n = 10 setzt, sollte es 0 1 1 2 3 5 8 ausgeben. Das n sollte bei mir die max Variable sein.


Oh, dann ist die grösste Fibonacci-Zahl gesucht, die kleiner als 10 ist?

Dann darfst du nicht n mit max vergleichen. Stattdessen musst du als Loopbedingung setzen, dass "aktuelle Fibonaccizahl + Fibonaccizahl davor < max" ist.

(Dies lässt sich mit zahl1 und zahl2 ausdrücken, aber das überlasse ich mal dir  )

Gruss
cwriter


----------



## MaxMustermann (27. Oktober 2018)

cwriter hat gesagt.:


> Oh, dann ist die grösste Fibonacci-Zahl gesucht, die kleiner als 10 ist?
> 
> Dann darfst du nicht n mit max vergleichen. Stattdessen musst du als Loopbedingung setzen, dass "aktuelle Fibonaccizahl + Fibonaccizahl davor < max" ist.
> 
> ...



Ist das mit meiner aktuellen Schleife machbar oder brauch ich da noch  etwas? Hab jetzt ein bisschen herumprobiert, bin aber noch nicht auf die Lösung gekommen.


----------



## cwriter (27. Oktober 2018)

MaxMustermann hat gesagt.:


> Ist das mit meiner aktuellen Schleife machbar oder brauch ich da noch etwas? Hab jetzt ein bisschen herumprobiert, bin aber noch nicht auf die Lösung gekommen.


Es ist machbar. Kleiner Tip: "n" brauchst du gar nicht mehr.

Das einzige, was du ändern musst, ist die Loopbedingung.

Gruss
cwriter


----------



## MaxMustermann (27. Oktober 2018)

cwriter hat gesagt.:


> Es ist machbar. Kleiner Tip: "n" brauchst du gar nicht mehr.
> 
> Das einzige, was du ändern musst, ist die Loopbedingung.
> 
> ...



Bin jetzt an diesem Punkt (nur die Schleife und das printf): 



while(zahl1 + zahl2 < max)
{
        fib = zahl1 + zahl2; 
        zahl1 = zahl2;
        zahl2 = fib;
        zahl1++;
        zahl2++;

       printf("%d\t", fib);
}


Wenn ich max den Wert 10 gebe, bekomme ich als Ausgabe: 0 1 1 4 8 

Verstehe nicht, wie diese Ausgabe zustande kommt. 

Denn: 

while(0 + 1 < 10)
{
    fib = 0 + 1;
    zahl1 = 1;
    zahl2 = 1;
} 
Dann wird für fib 1 ausgegeben, was für mich noch klar ist. 

Nächster Durchlauf: 

while(1 + 2 < 10)
{
  fib = 1 + 2;
  zahl1 = 2;
  zahl2 = 3; 
}

Müsste jetzt nicht statt 4, 3 ausgegeben werden oder übersehe ich da etwas? 

So oder so wäre es noch nicht ganz richtig, aber nur  fürs Verständnis.


----------



## cwriter (27. Oktober 2018)

MaxMustermann hat gesagt.:


> zahl1++;
> zahl2++;


Woher kommt das denn jetzt plötzlich? Der ursprüngliche Code war doch korrekt (bis auf die Schleifenbedingung)...



MaxMustermann hat gesagt.:


> while(0 + 1 < 10)
> {
> fib = 0 + 1;
> zahl1 = 1;
> ...


Sollte es aber nicht. zahl1 und zahl2 sollten nach dem ersten Fibonaccizahl durch das "++" ja zahl1 == 1 und zahl2 == 3 sein.


MaxMustermann hat gesagt.:


> Nächster Durchlauf:
> 
> while(1 + 2 < 10)
> {
> ...



Nö. Wie kommst du denn darauf, dass zahl1 und zahl2 nach dem ersten Durchlauf 1 sind?

Gruss
cwriter


----------



## MaxMustermann (27. Oktober 2018)

cwriter hat gesagt.:


> Woher kommt das denn jetzt plötzlich? Der ursprüngliche Code war doch korrekt (bis auf die Schleifenbedingung)...
> 
> 
> Sollte es aber nicht. zahl1 und zahl2 sollten nach dem ersten Fibonaccizahl durch das "++" ja zahl1 == 1 und zahl2 == 3 sein.
> ...



Habs jetzt, die Bedingung in der Schleife zu while(zahl1 + zahl2 < max) umzuändern, ohne zahl1 und zahl2 um 1 zu erhöhen, reicht.

Wieso das funktioniert, ist mir aber nicht ganz klar, da ich dachte, dass zahl1 und/oder zahl2 nach einem Durchlauf um ein 1 erhöht werden müssen, dass die Schleife ordnungsgemäß weiterläuft.


----------



## cwriter (27. Oktober 2018)

MaxMustermann hat gesagt.:


> Wieso das funktioniert, ist mir aber nicht ganz klar, da ich dachte, dass zahl1 und/oder zahl2 nach einem Durchlauf um ein 1 erhöht werden müssen, dass die Schleife ordnungsgemäß weiterläuft.


Wir können ja mal in etwas höhere Informatik vorstossen:
Damit der Loop Fortschritte macht, muss sich der Programmstatus in jeder Iteration ändern. Denn da das Programm ja deterministisch ist, würde bei derselben Eingabe auch dieselbe Ausgabe auftreten. Sobald eine Iteration keine Veränderung mehr vornimmt, bliebe das Programm stecken.

Ok, nun kennt man "Variante" und "Invariante". Die Invariante gibt Regeln an, die am Anfang und Ende jeder Iteration gelten müssen. Meistens ist die Invariante wichtiger als die Variante, da sie für die Korrektheit eines Programmes verwendet wird. Z.B. wäre hier die Invariante, dass zahl1 und zahl2 immer positiv sein müssen (negative Fibonaccizahlen machen ja nicht wirklich Sinn).

Für deine Frage interessanter: Die Variante. Sie bestimmt, welche Variablen garantieren, dass ein Loop in endlicher Zeit beendet. Z.B.

```
int i = 10;
while(i > 0) {
    --i;
}
```
Hier ist i die Variante: Sie geht nämlich streng monoton nach 0, und dann ist der Loop vorbei. (streng monoton sinkend = die Funktion wird immer kleiner)
Bei dir ist die Variante "max - zahl1 - zahl2". (oder anders geschrieben: max < zahl1 + zahl => loop beendet)
Wenn du ein bisschen darüber nachdenkst, wirst du das sicher sehen 

Gruss
cwriter


----------



## MaxMustermann (28. Oktober 2018)

cwriter hat gesagt.:


> Wir können ja mal in etwas höhere Informatik vorstossen:
> Damit der Loop Fortschritte macht, muss sich der Programmstatus in jeder Iteration ändern. Denn da das Programm ja deterministisch ist, würde bei derselben Eingabe auch dieselbe Ausgabe auftreten. Sobald eine Iteration keine Veränderung mehr vornimmt, bliebe das Programm stecken.
> 
> Ok, nun kennt man "Variante" und "Invariante". Die Invariante gibt Regeln an, die am Anfang und Ende jeder Iteration gelten müssen. Meistens ist die Invariante wichtiger als die Variante, da sie für die Korrektheit eines Programmes verwendet wird. Z.B. wäre hier die Invariante, dass zahl1 und zahl2 immer positiv sein müssen (negative Fibonaccizahlen machen ja nicht wirklich Sinn).
> ...


Ja, ich muss noch das Ganze noch vertiefen, danke für die Tipps und Hilfestellung


----------



## vfl_freak (29. Oktober 2018)

Moin MaxMustermann,

und nutze bitte die Code-Tags - das macht Deinen Code deutlich lesbarer (und erhöht die Chance, dass er auch gelesen wird  )
--> im Editor oben der Button mit den drei Punkten !!

VG Klaus


----------

