Summe von Fibonacci

[Zeppi]

Hallo,
ich bin gerade dabei die Summe von Fibonacci zu schreiben. Ich bin bisher noch nicht auf eine Lösung gekommen und habe daher im Internet nachgeguckt und bin darauf gestoßen:

int fib_sum(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return fib_sum(n-1) + fib_sum(n-2) + 1;
}

, aber ich verstehe nicht, wieso es reicht ein + 1 einfach dran zuhängen.


Vielleicht kann mir jemand das erklären, oder hat eine andere Lösung, die er mir erklären kann.

Danke Zeppi

 

[KonradN]

Wo hast Du das denn gefunden? Das ist so nicht richtig. Die Zahlenfolge ist ja:
0, 1, 1, 2, 3, 5, ...
Bei dir ist es 0, 1, 2, ...

Wenn Du eine Rekursion programmieren willst, dann ist es immer super, wenn man es mathematisch darstellen kann. Also eine Darstellung wie:
f(n) =

• 0 bei n = 0
• 1 bei n = 1
• f(n-1) + f(n-2) bei n > 1

Und das kann man dann so tatsächlich 1:1 in Code übernehmen.

 

[Zeppi]

Wo hast Du das denn gefunden? Das ist so nicht richtig. Die Zahlenfolge ist ja:
0, 1, 1, 2, 3, 5, ...
Bei dir ist es 0, 1, 2, ...

Ja genau, aber es geht um die aufaddierte Summe. Also bei n = 0 => 0; n = 1 => 1; n = 2 => 2; n = 3 => 4 und so weiter.

 

[yfons123]

Nth Fibonacci Number - GeeksforGeeks

The Fibonacci numbers are the numbers in the following integer sequence. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,....Program for Fibonacci Numbers:

www.geeksforgeeks.org

hier hast du eine detailierte erklärung

 

[KonradN]

Ja genau, aber es geht um die aufaddierte Summe. Also bei n = 0 => 0; n = 1 => 1; n = 2 => 2; n = 3 => 4 und so weiter.

Das ist dann aber keine fibonacci Reihe.

Fibonacci-Folge – Wikipedia

de.wikipedia.org

die Fibonacci Folge ist:
0, 1, 1, 2, 3, 5, 8, ....
==> 0 und 1 sind vorgegeben
==> jedes weitere Element ist die Summer der beiden Vorgänger.

 

[Zeppi]

Das ist dann aber keine fibonacci Reihe.

Fibonacci-Folge – Wikipedia

de.wikipedia.org

die Fibonacci Folge ist:
0, 1, 1, 2, 3, 5, 8, ....
==> 0 und 1 sind vorgegeben
==> jedes weitere Element ist die Summer der beiden Vorgänger.

Danke, Fibonacci verstehe ich. Aber ich möchte von der Folge alle Werte aufaddieren. Also wenn n = 3 ist, möchte ich 0 + 1 + 1 +2 rechnen.

 

[KonradN]

Danke, Fibonacci verstehe ich. Aber ich möchte von der Folge alle Werte aufaddieren. Also wenn n = 3 ist, möchte ich 0 + 1 + 1 +2 rechnen.

Dann nenne das bitte nicht Fibonacci Folge

Dann wäre der erste Schritt, das einmal korrekt zu formulieren. Dazu kann ich nur empfehlen, diese Zahlenreihe erst einmal richtig aufzuschreiben:
0
1
0+1 = 1
0+1+1 = 2
0+1+1+2 = 4
0+1+1+2+4 = 8
....

Und das kann man sich dann einfach einmal anschauen - siehst Du Regelmäßigkeit? Was ist der nächste Wert? Kannst Du diesen einfach ermitteln?

 

[fhoffmann]

Wenn man sich die Reihe der Fibonacci-Zahlen und die Reihe ihre Summen anschaut

0   1   1   2   3   5   8  13  21
0   1   2   4   7  12  20

sieht man, dass gilt:
fib_sum(n) = fib(n+2) - 1
Damit gilt
fib_sum(n) = fib_sum(n-1) + fib(n) = fib_sum(n-1) + fib_sum(n-2) + 1

 

[fhoffmann]

Die Aussage
fib_sum(n) = fib(n+2) - 1
lässt sich auch mit vollständiger Induktion einfach beweisen:
Die Induktionsverankerung folgt unmittelbar aus obiger Tabelle.
Der Induktionsschritt lautet:
fib_sum(n) = fib_sum(n-1) + fib(n) = fib(n+1) - 1 + fib(n) = fib(n+2) - 1
Dabei geht beim letzten Gleichheitszeichen die Definition der Fibonaccizahlen ein und beim vorletzten Gleichheitszeichen die Induktionsvoraussetzung.

 

[Zeppi]

Wenn man sich die Reihe der Fibonacci-Zahlen und die Reihe ihre Summen anschaut

0   1   1   2   3   5   8  13  21
0   1   2   4   7  12  20

sieht man, dass gilt:
fib_sum(n) = fib(n+2) - 1
Damit gilt
fib_sum(n) = fib_sum(n-1) + fib(n) = fib_sum(n-1) + fib_sum(n-2) + 1

Danke, die Antwort hat mir sehr weitergeholfen.

 

[berndoa]

Wenn man sich die Reihe der Fibonacci-Zahlen und die Reihe ihre Summen anschaut

0   1   1   2   3   5   8  13  21
0   1   2   4   7  12  20

sieht man, dass gilt:
fib_sum(n) = fib(n+2) - 1
Damit gilt
fib_sum(n) = fib_sum(n-1) + fib(n) = fib_sum(n-1) + fib_sum(n-2) + 1

Passt mathematisch nur beim Programmieren würde ich dann dann deine von fib(n+2) abhängige explizite Formel nehmen.
Und nicht mit fib_sum(n) über die Rekursion definieren, sonst ist da bei großen zahlen ruckzuck ein Error von wegen maximale Rekursionstiefe da.

Es gibt übrigens eine explizite Formel für die Fibonnacizahlen. kennt zwar keiner wenn man sie nciht mal zufällig gesehen aht aber es gibt sie. mit der könnte man sich vemrutlich auch eine explizite direkte Formel für die nte Fibonaccireihe bauen.

Man kann sich ja ausrechnen wie oft in fib_sum(n) die 1.,2. etc. Fibonaccizahl jeweils addiert wird. Und da eben jede fibouzahl mit der expliziten Formel berechnen.