Algorithmische Grundstrategien

Motivation

Bei den bisher betrachteten Algorithmen lassen sich in ganz verschiedenen konkreten Problemstellungen bestimmte, häufig in ähnlicher Form wiederkehrende Muster erkennen: Diese Muster lassen sich als algorithmische Grundstrategien verstehen, die es uns – wenn wir sie kennen – erleichtern können, auf systematische Weise Algorithmen zur Problemlösung zu entwickeln. Sie stellen uns nämlich Grundgerüste bereit, die wir auf die konkrete Problemstellung hin anpassen und ergänzen können.

Im Folgenden werden wir uns mit einer einfachen algorithmischen Grundstrategie beschäftigen: das elementweise Verarbeiten von Eingabedaten mit dem Programmierschema “Aufzählen und Überprüfen”. Mit dieser Strategie lässt sich eine ganze Reihe konkreter Problemstellungen systematisch lösen, denen wir in Programmieraufgaben häufig begegnen.

Aufzählen und Überprüfen

Listenverarbeitung

Beispiele

Bedingtes Zählen

Bedingtes Summieren

Bedingtes Suchen

Bedingtes Ersetzen

Primzahltest

Eine Ganzzahl n ≥ 2 heißt Primzahl, wenn sie nur durch 1 und sich selbst ohne Rest teilbar ist. Mit anderen Worten, sie ist keine Primzahl, wenn es eine Zahl z aus dem Bereich 2, …, n−1 gibt, die ein Teiler von n ist. An dieser Formulierung lässt sich schnell erkennen, dass wir die Frage, ob eine gegebene Zahl n eine Primzahl ist, auch mit dem Schema “Aufzählen und Überprüfen” lösen können: Wir prüfen der Reihe nach für jede Zahl z von 2 bis n−1, ob n durch z ohne Rest geteilt wird. Sobald wir eine solche Zahl gefunden haben, können wir die Suche abbrechen und “nein” zurückmelden. Wenn wir dagegen alle Zahlen durchgegangen sind ohne einen Teiler zu finden, melden wir “ja” zurück.

Wir können den Bereich der zu testenden Zahlen noch etwas weiter einschränken, da die Zahl n keinen echten Teiler haben kann, der größer als die Quadratwurzel von n ist (in mathematischer Schreibweise √n).

Wir beginnen beim Algorithmenentwurf also mit dem Grundgerüst für “Aufzählen und Überprüfen” und passen es so an, dass die Variable z bei 2 beginnt und in jedem Schritt um 1 hochgezählt wird, bis z > √n erreicht wurde. Als Bedingung testen wir in jedem Schritt, ob z Teiler von n ist:

Ist die Bedingung erfüllt, merken wir uns, dass wir einen Teiler von n gefunden haben. Dazu führen wir eine weitere Variable namens “gefunden” ein, die zu Beginn den Wert FALSCH hat. Diese Variable wird auf WAHR gesetzt, wenn in einem Wiederholungsschritt die Bedingung “z ist Teiler von n” erfüllt ist:

Bei genauerer Betrachtung stellen wir fest, dass unser Algorithmus unnötigerweise weitere Zahlen überprüft, nachdem er bereits einen Teiler gefunden hat. Besser wäre es, die Wiederholung in diesem Fall vorzeitig zu beenden. Dazu erweitern wir die Abbruchbedingung der Wiederholung so, dass sie auch dann beendet wird, wenn die Variable “gefunden” den Wert WAHR hat:

Als kleiner Feinschliff zum Schluss: Die Variable z muss in jedem Wiederholungsschritt nun nur noch dann hochgezählt werden, wenn sie kein Teiler von n ist – anderenfalls endet die Wiederholung ohnehin. Wir können die Anweisung “erhöhe z um 1” als in den “falls”-Teil der Fallunterscheidung verschieben. Das hat den Vorteil, dass wir am Programmende nicht nur wissen, ob n eine Primzahl ist oder nicht, sondern außerdem einen Teiler von n kennen, falls n keine Primzahl ist – in diesem Fall enthält die Variable z am Ende den gefundenen kleinsten Teiler von n.

Wir ergänzen nun ganz am Ende noch eine Ausgabe (“keine Primzahl” oder “Primzahl”, je nachdem, welchen Wert die Variable “gefunden” am Ende enthält) und erhalten damit den vollständigen Algorithmus:

Trace-Tabellen

Um den Ablauf der Ausführung von Algorithmen mit Variablen zu überprüfen, können wir Trace-Tabellen (Ablaufverfolgungstabellen) verwenden, die wir bereits im Kontext der visuellen Programmierung mit Scratch kennengelernt haben (siehe Trace-Tabellen.