Ein einfacher Algorithmus zur Bestimmung des maximalen Werts einer beliebig großen Menge von Zahlen ist wie folgt definiert:
Eingabe: Menge \(\mathsf A\) von \(\mathsf n\) Zahlen, hier durchnumerierte Werteliste \(\mathsf A=A_0, \dots, A_{n-1}\).
Setzte Hilfswert (Variable) \(\mathsf m\) auf das erste Element der Liste, d.h. \(\mathsf m = A_0\).
Gehe alle Elemente von \(\mathsf A\) durch, wobei das aktuelle Element als \(\mathsf a\) bezeichnet wird:
Falls das aktuelle Element \(\mathsf a\) größer ist als \(\mathsf m\): * setzte \(\mathsf m = a\) *, dann mache weiter mit dem nächsten Element in Schritt 3
Falls nicht: mache weiter mit dem nächsten Element in Schritt 3
Nachdem alle Elemente aus \(\mathsf A\) in Schritt 3 durchlaufen wurden, enthält \(\mathsf m\) den maximalen Wert der Liste \(\mathsf A\).
Dieser Algorithmus mag Ihnen auf den ersten Blick kompliziert. Gehen wir nochmal einen Schritt zurück und schauen uns einen Algorithmus an den wir bereits kennengelernt haben: Prüfen ob eine Zahl gerade ist.
Eingabe: Eine Zahl X
Berechne \(X\text{ mod }2\)
Prüfe ob das Ergebnis gleich Null ist
Falls ja ist die Zahl gerade und wir geben den Text “die Zahl ist gerade” aus.
Falls nein ist die Zahl ungerade und wir geben den Text “die Zahl ist ungerade” aus.
Diesen Auflistung können wir uns besser visualisieren. Dazu benutzen wir sogenannte Flussdiagramme.
Flussdiagramme - Visuelle Darstellung von Abläufen
Ein Flussdiagramm (engl. flowchart) ist eine grafische Methode zur Darstellung von Algorithmen. Es zeigt den Ablauf eines Programms oder Prozesses durch standardisierte Symbole und Pfeile. So lassen sich komplexe Abläufe leicht nachvollziehen und logisch überprüfen.
Typische Symbole:
Prozess (Anweisung): Rechteck – z. B. „Berechne Fläche“
Entscheidung: Raute – z. B. “Ist x > 0?”
Start/Ende: Ellipse – z. B. “für alle a in A”
Pfeile: Zeigen den Ablauf von einem Schritt zum nächsten
Beispiel: Der Algorithmus zur Bestimmung, ob eine Zahl gerade ist:
Flussdiagramm
Flussdiagramme sind nicht der einzige Weg, um komplexere Algorithmen verständlicher aufzuschreiben. Eine weitere Möglichkeit bieter hier sogenannter Pseudocode:
Pseudocode – Vom Gedanken zum Programm
Pseudocode ist eine formalisierte Beschreibung eines Algorithmus in einfacher, strukturierter Sprache – eine Mischung aus natürlicher Sprache und Programmierlogik. Er ist sprachunabhängig und dient zur Planung, nicht zur direkten Ausführung.
Typische Merkmale: - Klare Schritt-für-Schritt-Struktur - Verwendung von Kontrollstrukturen wie wenn, solange, wiederhole - Keine konkrete Syntax einer Programmiersprache
Beispiel:
BEGIN
Lese Zahl x ein
WENN x mod 2 = 0 DANN
Gib "x ist gerade" aus
SONST
Gib "x ist ungerade" aus
ENDE
Kommen wir nun zu dem “komplexeren Algorithmus zurück, der das Maximum in einer Liste von Zahlen finden soll:
Eingabe: Menge \(\mathsf A\) von \(\mathsf n\) Zahlen, hier durchnumerierte Werteliste \(\mathsf A=A_0, \dots, A_{n-1}\).
Setzte Hilfswert (Variable) \(\mathsf m\) auf das erste Element der Liste, d.h. \(\mathsf m = A_0\).
Gehe alle Elemente von \(\mathsf A\) durch, wobei das aktuelle Element als \(\mathsf a\) bezeichnet wird:
Falls das aktuelle Element \(\mathsf a\) größer ist als \(\mathsf m\): * setzte \(\mathsf m = a\) *, dann mache weiter mit dem nächsten Element in Schritt 3
Falls nicht: mache weiter mit dem nächsten Element in Schritt 3
Nachdem alle Elemente aus \(\mathsf A\) in Schritt 3 durchlaufen wurden, enthält \(\mathsf m\) den maximalen Wert der Liste \(\mathsf A\).
Testen Sie einmal selbst, ob Sie das passende Flussdiagramm erstellen können. In der folgenden Box finden Sie die Musterlösung. Sie brauchen hierfür auch die Verzweigung für Schleifen: Verzweigung (blau): Abfrage einer Bedingung, welche entscheidet welche folgenden Elemente ausgeführt werden, hier wird geprüft ob \(\mathsf a > m\)
Flussdiagramm: Maximumsuche
Algorithmus zur Bestimmung des Maximums einer Zahlenliste
Wie oben beschrieben, können wir aber nicht nur Flussdiagramme zur Darstellung von Algorithmen nutzen, sondern auch sogenannten Pseudocode. Versuchen Sie einmal selbst den ALgorithmus zur Maximumsuche in Pseudocode zu formulieren.
Pseudocode: Maximumsuche
Eingabe: Liste von Zahlen L (z. B. L = [5, 8, 2, 9, 3])
1. Setze max_wert := L[0] // Initialisiere Hilfswert mit dem ersten Element der Liste
2. Für jedes Element x in L:
a. Falls x > max_wert:
i. Setze max_wert := x
b. Andernfalls:
i. Tue nichts (fortfahren)
3. Ausgabe: max_wert // max_wert enthält nun den größten Wert der Liste
Ein Beispiel für den Ablauf des Algoritmus für eine Liste von 20 Zahlen ist:
import numpy as npnp.set_printoptions(linewidth=50)# A = np.random.randint(0, high=1000, size=20)A = np.array([203, 433, 504, 602, 567, 762, 183, 482, 471, 741, 854, 486, 350, 550, 885, 395, 203, 288, 909, 644])print('Schritt 1:')print('==========')print('A =', np.array2string(A, separator=', '))print()print('Schritt 2:')print('==========')m = A[0]print('m = A[0] =', m)print()print('Schritt 3:')print('==========')for a in A:print('a = {:3d}, m = {:3d}'.format(a, m), end='')if a > m: m = aprint(', da a > m ist, setzte m auf m=', m)else:print()print()print('Schritt 4:')print('==========')print('Maximaler Wert in A: m =', m)
Schritt 1:
==========
A = [203, 433, 504, 602, 567, 762, 183, 482, 471, 741,
854, 486, 350, 550, 885, 395, 203, 288, 909, 644]
Schritt 2:
==========
m = A[0] = 203
Schritt 3:
==========
a = 203, m = 203
a = 433, m = 203, da a > m ist, setzte m auf m= 433
a = 504, m = 433, da a > m ist, setzte m auf m= 504
a = 602, m = 504, da a > m ist, setzte m auf m= 602
a = 567, m = 602
a = 762, m = 602, da a > m ist, setzte m auf m= 762
a = 183, m = 762
a = 482, m = 762
a = 471, m = 762
a = 741, m = 762
a = 854, m = 762, da a > m ist, setzte m auf m= 854
a = 486, m = 854
a = 350, m = 854
a = 550, m = 854
a = 885, m = 854, da a > m ist, setzte m auf m= 885
a = 395, m = 885
a = 203, m = 885
a = 288, m = 885
a = 909, m = 885, da a > m ist, setzte m auf m= 909
a = 644, m = 909
Schritt 4:
==========
Maximaler Wert in A: m = 909
30.1 Kapitelübersicht
In diesem Kapitel werden folgende Themen behandelt:
