Project Euler 2 – Powershell Edition

0
293

Heute nehmen wir uns der zweiten Project Euler Aufgabe an und setzen diese in einer einfachen Variante in Windows Powershell um.
Sehen wir uns als erstes mal die Problembeschreibung an:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.


Unsere Aufgabe besteht also darin die Summe aller geraden Elemente der Fibonacci-Reihe unter vier Millionen zu finden.
Doch wie fangen wir hier an?
Zunächst einmal müssen wir, wie bei allen Problemen in der Programmierung zunächst, das große Problem in mehrere kleine Probleme zerlegen.

Da wir wieder die Laufzeit unseres Scripts tracken wollen benötigen wir, wie auch bei der ersten Euler-Aufgabe eine Stoppuhr. Auch hier benutzen wir wieder die .NET-Klasse, wie im letzten Beitrag erklärt.
Dies wird sich nun wie ein roter Faden durch die kommenden Aufgaben ziehen, damit wir immer sehen wie performant oder unperformant unsere Implementierung läuft.

#Starten der "Stoppuhr" unter Zuhilfenahme der .NET-Klasse system.diagnostics.stopwatch$timetracker = [system.diagnostics.stopwatch]::startNew()

#In $elapsedtime werden die zur Verarbeitung benötigten Sekunden seit dem Start der Stoppuhr geschrieben

#Ausgabe der Laufzeit des Scripts
write-host $timetracker.Elapsed.seconds "Sekunden`t" $timetracker.Elapsed.Milliseconds "Millisekunden"

Als nächstes gehen wir das Hauptproblem an, das Hochzählen der Fibonacci-Reihe.
Die Fibonacci-Reihe ist die unendliche Folge natürlicher Zahlen, beginnend mit 0,1,1, in welcher sich die nächste Zahl immer aus der Summe der beiden vorangegangenen ergibt.
Sie weist einige interessante mathematische Besonderheiten auf und steht in Zusammenhang mit dem Pascalschen Dreieck, sowie dem goldenen Schnitt, aber das ist eine andere Geschichte.

Hierfür benötigen wir einen Ausgangspunkt, sowie drei Variablen. In einer der beiden speichern wir die Summe und tauschen dann die Werte durch vor der nächsten Summenbildung.
Bspw: A = 1; B = 1 => C = 2
Im nächsten Durchlauf wäre es dann: A = 1; B = 2 => C = 3

Um die Operation im Rahmen der Schleife, welche wir benötigen um den Durchlauf zu automatisieren bis zur Grenze von 4.000.000, zu wiederholen müssen wir also die Werte tauschen.
Anhand unseres obenstehenden Beispiels wäre das dann nach dem ersten Durchlauf
A = B; B = C
In Summe ergibt das:


$fibosumme = 1;
$fibonacci1 = 0;
$fibonacci2 = 1;

while($fibosumme -lt 4000000){
    $fibosumme = $fibonacci1 + $fibonacci2;
    $fibonacci1 = $fibonacci2;
    $fibonacci2 = $fibosumme;
}

Zuletzt müssen wir beim hochzählen der Fibonacci-Folge lediglich noch prüfen, ob die nächste gefundene Zahl gerade ist und diese gegebenenfalls aufaddieren.


if($fibosumme % 2 -eq 0){
    $gesamtsumme += $fibosumme;
}

Nun müssen wir das Ganze nur noch zusammensetzen und mit einer Ausgabe versehen, welche uns die Summe präsentiert und die Aufgabe ist gelöst:

Weitere Project Euler-Aufgaben und andere Tutorials und Tipps im Kontext Powershell werden zeitnah folgen.
Apropos folgen, folgt Ihr uns eigentlich schon auf Facebook oder Instagram?
Falls nicht ist jetzt der perfekte Zeitpunkt das nachzuholen.
Gerne könnt Ihr Euch mit Kommentaren hier oder auf einem der Social Media Kanäle mit Ideen, Wünschen oder Kritik einbringen.
Wenn Ihr eine konkrete Frage zu Powershell Scripting oder Programmierung allgemein habt, könnt Ihr diese ebenfalls gerne auf den oben genannten Kanälen stellen wo wir diese gerne aufgreifen und entweder persönlich beantworten oder im Rahmen eines Beitrags thematisieren!

HINTERLASSEN SIE EINE ANTWORT

Bitte geben Sie Ihren Kommentar ein
Bitte geben Sie Ihren Namen ein