Blog

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, 34, 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 &amp;amp;amp;amp;amp;lt;= 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 &amp;amp;amp;amp;amp;lt;= 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.