Fibonacci-Folge

[MaxMustermann]

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]

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.

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]

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.


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

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]

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]

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

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]

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]

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

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

Gruss
cwriter

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]

zahl1++;
zahl2++;

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

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.

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

Nächster Durchlauf:

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

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

Gruss
cwriter

 

[MaxMustermann]

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.


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

Gruss
cwriter

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]

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