Kann mir jemand sagen, wie man die summe der ersten N fibonacci zahlen schnell berechnet?
Versuche die ganze zeit eine Formel zu erstellen.
zu beginn dachte ich, dass man einfach die Anfangszahl mal 2,3,4 usw nehmen kann, aber das funktioniert nicht. Fakt ist, ich möchte ein formel für eine möglichst schnelle berechnung haben
3 Antworten
Damit:
Du berechnest also die übernächste Fibonacci Zahl und ziehst 1 ab.
Kein Mensch definiert die Fibonacci-Folge so. Aber schön, dass Du mal wieder ein Haar in der Suppe gefunden hast.
Die Fibonacci-Folge (f_n) ist rekursiv durch das Bildungsgesetz
, für
definiert.
Daraus folgt zwar durch einen sehr einfachen Induktionsbeweis die von @evtldocha angegebene Formel, aber die gängige Der
Aus der gängigen rekursiven Definition per Rückgriff auf die jeweils zwei letzten vorherigen Werte folgt die angegebene Summenformel durch einen sehr einfachen Induktionsbeweis. Jedoch wäre es nicht nur unüblich, sondern auch schwerfällig für Beweise, die Fibonacci-Folge mit einer solchen Rekursionsformel zu definieren, die auf alle vorangehenden Glieder bis auf das unmittelbar vorhergehende zurückgreift.
1 1 2 3 5 8 13 21 34 ...
Jede Zahl = die Summe der beiden vorhergehenden Zahlen.
das ist mir klar, es geht mehr oder weniger darum eine formel zur schnellen berechnung zu finden
Ja Formel für was denn, also wo soll den die Formel funktionieren? In Excel ist es einfach =A1+A2 und die kannst du dann beliebig wir runter ziehen.
In einer beliebigen Programmiersprache musst du dir damit helfen die letzten beiden Ergebnisse in variablen zu speichern.
{
E = X1 + X2
Print E
X1 = X2
X2 = E
}
Und dann kannst du über eine Schleife festlegen wie oft das wiederholt werden soll.
Die einfache Formel ist: addiere die letzten beiden Ergebnisse!
Nutze die explizite Formel für die k-te Fibonacci Zahl und wende dann die Summenformel für endliche geometrische Reihen von 1 bis n an…
Genial. Den Trick kannte ich noch nicht.