Algorithmen

Die drei Grundbausteine: Folge, Auswahl, Wiederholung

Mit genau drei Bausteinen lässt sich jeder Algorithmus bauen. Warum das so ist und wie man sie zeichnet.

Benötigte Grundlagen

Dieses Vorwissen brauchst du für das Kapitel. Schau kurz nach, wenn dir etwas davon nicht mehr präsent ist, sonst leg direkt los.

AlgorithmusKlasse 9

Einführung

Ein Programm kann eine Rakete steuern, ein Spiel berechnen oder Musik abspielen. Trotzdem besteht jedes einzelne davon aus nur drei Arten von Bausteinen. Das ist keine schöne Faustregel, sondern ein Ergebnis: Man kann zeigen, dass Folge, Auswahl und Wiederholung ausreichen, um jeden berechenbaren Ablauf zu beschreiben. Für dich heißt das etwas sehr Praktisches: Wenn du diese drei sicher beherrschst, kannst du jeden Algorithmus lesen, den du je sehen wirst, und du weißt beim Entwerfen immer, welche Bauteile zur Auswahl stehen.

Das kannst du nach diesem Kapitel

$die drei Grundbausteine Folge, Auswahl und Wiederholung erkennen und benennen.$
$einfache Auswahl, zweiseitige Auswahl und Mehrfachauswahl unterscheiden.$
$kopfgesteuerte und fußgesteuerte Wiederholung unterscheiden und begründen, wann welche passt.$
$einen Algorithmus als Struktogramm darstellen.$
$begründen, warum jede Wiederholung eine Abbruchbedingung braucht, die auch erreicht wird.$

Baustein 1: die Folge

Der einfachste Fall. Mehrere Anweisungen werden nacheinander ausgeführt, jede genau einmal, in der aufgeschriebenen Reihenfolge. LIES preis LIES anzahl gesamt := preis * anzahl SCHREIBE gesamt Die Reihenfolge ist dabei nicht beliebig: Man kann nicht multiplizieren, bevor die Werte eingelesen sind. Das klingt selbstverständlich, ist aber eine der häufigsten Fehlerquellen bei eigenen Entwürfen.

Die Folge

Drei Kästen, einer unter dem anderen, mehr ist die Folge nicht. Wichtig ist, was das Bild nicht zeigt: keine Bedingung, keinen Pfeil, keine Wahl. Von oben nach unten, jeder Schritt genau einmal. Alles Weitere im Fach ist eine Abweichung von genau diesem Grundfall.

Baustein 2: die Auswahl

Hier hängt der weitere Ablauf von einer Bedingung ab, also von einer Aussage, die entweder wahr oder falsch ist. Einseitige Auswahl: Etwas passiert nur, wenn die Bedingung zutrifft. WENN alter >= 18 DANN SCHREIBE "volljährig" ENDE WENN Zweiseitige Auswahl: Für beide Fälle ist etwas vorgesehen. WENN note <= 4 DANN SCHREIBE "bestanden" SONST SCHREIBE "nicht bestanden" ENDE WENN Mehrfachauswahl: Mehrere Bedingungen werden der Reihe nach geprüft. Wichtig ist, dass die Reihenfolge hier eine Rolle spielt, denn geprüft wird von oben nach unten, und der erste zutreffende Zweig gewinnt.

Die Auswahl

Das Dreieck oben ist die Bedingung, links steht der Ja-Zweig, rechts der Nein-Zweig. Beide sind gleich breit gezeichnet, und das ist Absicht: Keiner der beiden Wege ist der „eigentliche“. Ein leeres Feld auf einer Seite wäre übrigens auch eine Aussage. „Dann passiert eben nichts“ ist ein Zweig, kein Weglassen.

Baustein 3: die Wiederholung

Eine Anweisungsfolge wird mehrfach ausgeführt. Es gibt zwei Bauformen, und der Unterschied ist wichtiger, als er aussieht. Kopfgesteuert: Die Bedingung wird vor dem Durchlauf geprüft. Trifft sie von Anfang an nicht zu, wird der Rumpf nie ausgeführt. SOLANGE vorrat > 0 WIEDERHOLE verkaufe ein Stück vorrat := vorrat - 1 ENDE SOLANGE Fußgesteuert: Die Bedingung wird nach dem Durchlauf geprüft. Der Rumpf läuft deshalb mindestens einmal . WIEDERHOLE frage nach dem Passwort BIS passwort ist richtig Woran erkennt man, welche man braucht? An einer einzigen Frage: Muss der Rumpf mindestens einmal laufen? Nach dem Passwort muss man mindestens einmal fragen, also fußgesteuert. Aus einem leeren Lager darf man nichts verkaufen, also kopfgesteuert. Kennt man die Anzahl der Durchläufe vorher, schreibt man meist kürzer: FÜR i VON 1 BIS 10 WIEDERHOLE SCHREIBE i ENDE FÜR Das ist keine vierte Bauform, sondern eine bequeme Schreibweise für eine kopfgesteuerte Wiederholung mit Zähler.

Die Wiederholung

Der Rumpf sitzt eingerückt im Wiederholungskasten. Er gehört dazu, er steht nicht daneben. Die Bedingung steht oben, weil sie oben geprüft wird: Ist die Tasse schon voll, läuft der Rumpf null -mal. Das ist der Unterschied zur nachprüfenden Schleife, bei der die Bedingung unten steht und der Rumpf mindestens einmal läuft.

Die Bedingung, die jede Wiederholung braucht

\texttt{vorrat}

Struktogramme: die Bausteine zeichnen

Ein Struktogramm stellt die Bausteine als ineinandergeschachtelte Kästen dar. Der große Vorteil gegenüber Pfeildiagrammen: Man kann keine wilden Sprünge zeichnen, weil ein Kasten immer vollständig in einem anderen liegt. Die Zeichnung erzwingt also eine saubere Struktur. Folge : Kästen untereinander. Auswahl : ein Kasten, oben durch eine Diagonale in einen Ja- und einen Nein-Bereich geteilt; darunter je ein Zweig. Wiederholung : ein Rahmen, dessen obere (oder untere) Leiste die Bedingung trägt; der wiederholte Teil liegt eingerückt darin. Verschachteln ist ausdrücklich erlaubt: In einem Wiederholungsrahmen darf eine Auswahl stehen und darin wieder eine Wiederholung. Genau daraus entsteht die Ausdruckskraft der drei Bausteine.

Alle drei Bausteine in einem Bild

Hier stecken alle drei Bausteine: Die Folge sind die beiden Kästen unter der Raute, die Auswahl ist die Raute selbst, und die Wiederholung ist der Weg an der linken Schiene zurück nach oben. Genau diesen Rücksprung kann ein Struktogramm nicht zeichnen. Dort ist die Wiederholung ein Kasten, hier ein Weg. Deshalb lohnt es sich, beide Darstellungen zu kennen.

Bausteine in einem Alltagsablauf erkennen

Bestimme die Grundbausteine im Ablauf „Fahrkarte am Automaten kaufen“.

1 $„Ziel auswählen, dann Preis anzeigen, dann Zahlung anfordern“ ist eine Folge : drei Schritte nacheinander.$
2 $„Wenn Ermäßigung gewählt wurde, ziehe 50 Prozent ab, sonst nimm den vollen Preis“ ist eine zweiseitige Auswahl .$
3 $„Solange der eingeworfene Betrag kleiner als der Preis ist, warte auf weitere Münzen“ ist eine kopfgesteuerte Wiederholung . Sie muss kopfgesteuert sein, denn wer sofort passend zahlt, soll gar nicht warten.$
4 $„Wiederhole: drucke ein Ticket, bis alle bestellten Tickets gedruckt sind“ ist eine fußgesteuerte Wiederholung, denn mindestens ein Ticket wird immer gedruckt.$
5 $Der gesamte Ablauf ist eine Folge, in der Auswahl und Wiederholungen ineinander verschachtelt sind. Mehr Bausteine braucht es nicht.$

Folge, zweiseitige Auswahl, kopfgesteuerte und fußgesteuerte Wiederholung, ineinander verschachtelt.

Kopf oder Fuß? Ein Fall, in dem es zählt

Ein Programm soll Geld auszahlen, solange noch Guthaben da ist. Was passiert bei Guthaben 0 mit einer kopfgesteuerten und mit einer fußgesteuerten Schleife?

1 $Kopfgesteuert: Zuerst wird geprüft, ob das Guthaben größer als 0 ist. Bei 0 ist die Bedingung falsch, der Rumpf läuft nullmal, es wird nichts ausgezahlt. Richtig.$
2 $Fußgesteuert: Zuerst wird ausgezahlt, danach geprüft. Bei Guthaben 0 wird also einmal ausgezahlt, obwohl nichts da war. Das Konto steht danach im Minus.$
3 $Beide Schleifen sehen im Quelltext fast gleich aus und unterscheiden sich nur in der Stelle der Prüfung. Der Unterschied ist hier ein echter Schaden.$
4 $Die Entscheidung folgt immer aus der Sache: Darf der Rumpf nullmal laufen, dann kopfgesteuert. Muss er mindestens einmal laufen, dann fußgesteuert.$

Hier ist die kopfgesteuerte Schleife richtig. Die fußgesteuerte zahlt bei leerem Konto einmal zu viel aus.

Typischer Fehler

\texttt{i := 1;}\quad \texttt{SOLANGE i < 10 WIEDERHOLE: SCHREIBE i}

\texttt{i < 10}

Übung 1

leicht

Welcher Grundbaustein steckt jeweils dahinter? a) „Zähne putzen, dann Haare kämmen, dann Schuhe anziehen.“ b) „Wenn es regnet, nimm den Schirm mit.“ c) „Rühre so lange, bis der Teig glatt ist.“ d) „Wenn die Ampel grün ist, geh los, sonst warte.“

Tipp anzeigen

Achte auf die Signalwörter.

Lösung anzeigen

a) Folge b) Einseitige Auswahl (für den Fall ohne Regen ist nichts vorgesehen) c) Fußgesteuerte Wiederholung (einmal rühren muss man in jedem Fall) d) Zweiseitige Auswahl (beide Fälle sind geregelt)

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

1
Nach Signalwörtern suchen, nicht nach dem Inhalt
$Die Grundbausteine erkennt man an den Wörtern, die die Struktur anzeigen: „dann“ und Aufzählungen deuten auf eine Folge, „wenn“ auf eine Auswahl, „so lange bis“ oder „wiederhole“ auf eine Wiederholung . Der Inhalt (Zähne, Ampel, Teig) ist dabei völlig gleichgültig.$
2
a) Die Folge: eine Reihenfolge ohne Bedingung
$„Zähne putzen, dann Haare kämmen, dann Schuhe anziehen.“ nennt drei Schritte, die in fester Reihenfolge nacheinander abgearbeitet werden. Es wird nichts geprüft und nichts wiederholt: eine reine Folge .$
3
b) und d): einseitige und zweiseitige Auswahl unterscheiden
$„Wenn es regnet, nimm den Schirm mit.“ regelt nur den Regenfall, für schönes Wetter ist nichts vorgesehen: einseitige Auswahl . „Wenn die Ampel grün ist, geh los, sonst warte.“ regelt beide Fälle: zweiseitige Auswahl .$
4
c) Wiederholung: Warum sie hier fußgesteuert ist
$„Rühre so lange, bis der Teig glatt ist.“ wiederholt einen Schritt, bis eine Bedingung erfüllt ist. Entscheidend: Gerührt wird auf jeden Fall mindestens einmal, denn ob der Teig glatt ist, kann man erst nach dem Rühren beurteilen. Das ist eine fußgesteuerte Wiederholung.$

Übung 2

mittel

n

Tipp anzeigen

Führe zwei Namen mit: einen für die laufende Zahl und einen für die bisherige Summe.

Lösung anzeigen

n = 4

Durchlauf	i vorher	summe vorher	summe nachher	i nachher
1	1	0	1	2
2	2	1	3	3
3	3	3	6	4
4	4	6	10	5

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

1
Die beiden Namen festlegen
$n$
$\texttt{summe} := 0 \qquad \texttt{i} := 1$
Zwischenergebnis
$Startzustand: noch nichts addiert, nächste Zahl ist 1.$
$Der Startwert 0 für die Summe ist kein Zufall: Er ist der Wert, der bei Addition nichts verändert. Bei einem Produkt wäre der richtige Startwert 1.$
2
Den Rumpf schreiben
$Im Rumpf passieren genau zwei Dinge, und beide sind nötig: Die aktuelle Zahl wird zur Summe addiert, und die aktuelle Zahl wird weitergeschaltet. Fehlt das Weiterschalten, endet die Schleife nie.$
$\texttt{summe} := \texttt{summe} + \texttt{i} \qquad \texttt{i} := \texttt{i} + 1$
Zwischenergebnis
$\texttt{summe}$
3
Teil b): Durchspielen statt raten
$Eine Wertetabelle mit einer Spalte je Name und einer Zeile je Durchlauf macht den Ablauf überprüfbar. Man trägt für jeden Durchlauf ein, welche Werte vorher galten und welche nachher gelten.$
Zwischenergebnis
$\texttt{summe} = 10$
$1+2+3+4 = 10$
4
Teil c): Warum die Schleife endet
$Für die Endlichkeit genügt es nicht, dass eine Bedingung dasteht. Man muss zeigen, dass der Rumpf den geprüften Wert in die Richtung bewegt, in der die Bedingung falsch wird.$
Zwischenergebnis
$i$

Übung 3

schwer

Ein Getränkeautomat arbeitet so: Er nimmt Münzen an, bis der Preis erreicht ist, gibt dann das Getränk aus und zahlt Restgeld zurück, falls zu viel eingeworfen wurde. a) Schreibe den Ablauf als Pseudocode mit allen drei Grundbausteinen. b) Begründe für die Wiederholung, ob sie kopf- oder fußgesteuert sein muss. c) Der Kunde drückt „Abbrechen“. Welchen Baustein brauchst du zusätzlich, und wo gehört er hin? d) Erkläre, warum ein Struktogramm hier hilfreicher ist als eine Liste von Sätzen.

Tipp anzeigen

Zu b): Was soll passieren, wenn der Kunde sofort passend einwirft?

Lösung anzeigen

a) Pseudocode: LIES preis eingeworfen := 0 SOLANGE eingeworfen < preis WIEDERHOLE warte auf Münze eingeworfen := eingeworfen + münzwert ENDE SOLANGE gib Getränk aus WENN eingeworfen > preis DANN zahle eingeworfen - preis zurück ENDE WENN b) Kopfgesteuert. Wirft der Kunde sofort den passenden Betrag ein, ist die Bedingung von Anfang an falsch, und es wird zu Recht keine weitere Münze verlangt. Eine fußgesteuerte Schleife würde in diesem Fall noch eine Münze fordern, obwohl bereits genug Geld da ist. c) Eine zusätzliche Auswahl innerhalb der Wiederholung : Nach jedem Warteschritt wird geprüft, ob der Abbruchknopf gedrückt wurde; falls ja, wird das eingeworfene Geld zurückgezahlt und die Schleife verlassen. Sie gehört in den Schleifenrumpf, weil die Abbruchmöglichkeit während des Wartens bestehen muss und nicht erst danach. d) Weil der Ablauf verschachtelt ist: In der Wiederholung steckt eine Auswahl, und nach der Wiederholung folgt eine weitere. In einer Satzliste muss der Leser sich merken, welcher Satz noch zur Schleife gehört; im Struktogramm sieht man es an der Lage der Kästen. Außerdem lässt ein Struktogramm gar nicht erst zu, dass man aus der Mitte eines Kastens irgendwohin springt.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

1
a) Den Ablauf in Worten ordnen, bevor Pseudocode entsteht
$Der Automat tut drei Dinge nacheinander: Münzen annehmen, bis der Preis erreicht ist (Wiederholung), das Getränk ausgeben (Folge), und Restgeld zurückzahlen, falls zu viel eingeworfen wurde (Auswahl). Damit steht die Struktur fest, und der Pseudocode schreibt sie nur noch auf.$
$\texttt{LIES preis}$
2
b) Kopf- oder fußgesteuert? Der passende Betrag entscheidet
$Kopfgesteuert. Wirft der Kunde sofort den passenden Betrag ein, ist die Bedingung von Anfang an falsch, und es wird zu Recht keine weitere Münze verlangt. Eine fußgesteuerte Schleife würde in diesem Fall noch eine Münze fordern, obwohl bereits genug Geld da ist.$
3
c) Den Abbruch dort einbauen, wo er wirken muss
$Nötig ist eine zusätzliche Auswahl innerhalb der Wiederholung : Nach jedem Warteschritt wird geprüft, ob der Abbruchknopf gedrückt wurde; falls ja, wird das eingeworfene Geld zurückgezahlt und die Schleife verlassen. Sie gehört in den Schleifenrumpf, weil die Abbruchmöglichkeit während des Wartens bestehen muss und nicht erst danach.$
4
d) Warum das Struktogramm mehr leistet als eine Satzliste
$Weil der Ablauf verschachtelt ist: In der Wiederholung steckt eine Auswahl, und nach der Wiederholung folgt eine weitere. In einer Satzliste muss der Leser sich merken, welcher Satz noch zur Schleife gehört; im Struktogramm sieht man es an der Lage der Kästen.$

Zusammenfassung

Jeder Algorithmus lässt sich aus drei Bausteinen zusammensetzen: der Folge, die Anweisungen nacheinander ausführt, der Auswahl, die abhängig von einer Bedingung verzweigt, und der Wiederholung, die eine Anweisungsfolge mehrfach ausführt. Die Auswahl gibt es einseitig, zweiseitig und als Mehrfachauswahl, wobei bei der Mehrfachauswahl die Prüfreihenfolge zählt. Die Wiederholung gibt es kopfgesteuert, dann läuft der Rumpf möglicherweise nullmal, und fußgesteuert, dann läuft er mindestens einmal; die Entscheidung ergibt sich aus der Sache. Jede Wiederholung braucht nicht nur eine Abbruchbedingung, sondern auch einen Rumpf, der auf diese Bedingung hinarbeitet. Struktogramme stellen die Bausteine als geschachtelte Kästen dar und machen unstrukturierte Sprünge schon zeichnerisch unmöglich.