Euler Problem 002 - Die Fibonacci-Folge

 Project-Euler  No Responses »
Feb 222012
 

Das 2. Problem von Project-Euler zeigt uns die Fibonacci-Folge.

Die ersten Elemente der Fibonacci-Folge lauten: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Die Aufgabe dazu lautet:

Addiere alle geraden Elemente der Fibonacce-Folge die kleiner als vier Millionen sind.

Eine einfache und auch schnelle Lösung lässt sich schnell finden, mann kann sogar alle notwendigen Elemente bei Wikipedia ablesen und mit dem Taschenrechner oder per Hand aufaddieren.

Ein einfacher Programmcode mag so aussehen:

uint erg = 0, a = 1, b = 2;
do {
    if (b % 2 == 0)
        erg += b;
    uint bneu = a + b;
    a = b;
    b = bneu;
} while (b < 4000000);

Jetzt kann man noch die temporäre Variable eliminieren:

b += a;
a = b - a;

Man kann auch noch die Teilbarkeitsprüfung in der Schleife eliminieren, da genau jedes 3. Element der Fibonacci-Folge gerade ist. (1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...)

Oder man nutzt die Eigenschaft: f(n+3) = 3f(n)+2f(n-1), hier braucht man jedoch wieder eine Zwichenvariable, oder man führt immer drei Schritte der Fibonacci-Iteration hintereinander aus und addiert dann ohne Abfrage auf.

Euler Problem 001 - Addier' das mal!

 Project-Euler  No Responses »
Feb 202012
 

Das Erste der Probleme von Project-Euler ist, wie zu erwarten war, auch das einfachste aller Probleme.

Finde die Summe aller Vielfachen von 3 oder 5 unter 1000.

Bis Tausend durchzählen dauert nicht lange. Dann überprüfen ob die Zählvariable ein Vielfaches ist, um gegebenenfalls auf die Ergebnisvariable aufzuaddieren.

Klingt einfach - ist auch so!

uint erg = 0;
for (uint i = 1; i < 1000; i++)
    if (i % 3 == 0 || i % 5 == 0)
        erg += i;