Jede neue Zahl in der Fibonaccifolge wird durch die Summe der beiden Vorgänger gebildet. Die ersten beiden Reihenglieder sind definiert als 0 und 1. Die ersten Folgeglieder sind also:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Finde die Summe aller geraden (Vielfache von 2) Folgeglieder, deren Betrag nicht größer ist als 4 Millionen!
Lösung
Möglichkeit 1
Die einfachste Möglichkeit ist es, zunächst die gesamte Folge bis 4000000 aufzustellen und zu speichern. Anschließend wird jedes Folgeglied getestet, ob es gerade ist. Die geraden Folgeglieder werden aufaddiert:
fib = [0 1]; act = 1; it = 3; grenze = 4000000; summe = 0; while act <= grenze fib = [fib act]; it = it + 1; act = fib(it-2) + fib(it-1); end for i=1:length(fib) if mod(fib(i),2) == 0 summe = summe + fib(i); end end summe
Das Ergebnis ist 4613732.
Rechenzeit: 0.002278 Sekunden.
Möglichkeit 2
Den Test, ob die Folgeglieder gerade sind, können wir uns bei genauerem Hinschauen sparen. Die ersten Folgeglieder:
0, 1, 1, 2, 3, 5, 8, 13, 21, 43, 55, 89, 144, …
Es lässt sich zeigen, dass jedes dritte Glied der Fibonacci-Folge gerade ist:
Die Summe von zwei (un)geraden Zahlen ist gerade, die Summe einer geraden und einer ungeraden Zahl ist ungerade. Daher ist die Fibonacci-Folge:
ungerade, ungerade, gerade, ungerade, ungerade, gerade, ungerade, …
Alle drei Zahlen wiederholt sich die Abfolge. Präzise lässt sich dies mit der Modulo-Rechnung zeigen. Wir ersetzen also die zweite Schleife:
fib = [0 1]; act = 1; it = 3; grenze = 4000000; summe = 0; while act <= grenze fib = [fib act]; it = it + 1; act = fib(it-2) + fib(it-1); end for i=1:3:length(fib) summe = summe + fib(i); end summe
Rechenzeit: 0.002010 Sekunden, also kein großer Vorteil.
Möglichkeit 3
Wir wollen nun versuchen, um das Aufstellen der gesamten Fibonacci-Folge herumzukommen. Wir schreiben dazu die geraden Folgeglieder auf:
2, 8, 34, 144, 610, 2584, …
Mit ein bisschen Nachdenken findet man für diese Teilfolge eine rekursive Definition:
Dies müssen wir allerdings noch beweisen. Wir beweisen dazu für die “echte” Fibonacci-Folge:
Vor dem Weiterlesen unbedingt selber versuchen 🙂
Wir gehen von der Definition der Fibonacci-Folge aus:
q.e.d.
Wir können also auf das Aufstellen der gesamten Fibonacci-Folge verzichten und brauchen nur die Glieder der Teilfolge:
fib_teil = 2; act = 8; it = 2; grenze = 4000000; while act <= grenze fib_teil = [fib_teil act]; it = it + 1; act = 4 * fib_teil(it-1) + fib_teil(it-2); end summe = sum(fib_teil)
Rechenzeit: 0.001152 Sekunden, also noch einmal fast 50% Verbesserung.