Struktogramme
Flussdiagramme haben einen Nachteil: Mit ihren Pfeilen kann man Sprünge kreuz und quer zeichnen – auch solche, die sich gar nicht sauber programmieren lassen. Struktogramme (nach ihren Erfindern auch Nassi-Shneiderman-Diagramme) verhindern das durch ihre Bauweise: Sie bestehen nur aus ineinandergeschachtelten Kästen und kennen überhaupt keine Pfeile.
Die Bausteine
| Baustein | Aussehen | Bedeutung |
|---|---|---|
| Anweisung | ein Kasten mit Text | eine Anweisung oder Anweisungsfolge |
| Sequenz | Kästen untereinander | Anweisungen nacheinander |
| Verzweigung | Kasten mit Dreieck oben, darunter zwei Spalten | if / else |
| Kopfgesteuerte Schleife | Kasten, der oben und links um den Rumpf greift | while / for |
| Fußgesteuerte Schleife | Kasten, der unten und links um den Rumpf greift | do-while |
Ein leerer Zweig einer Verzweigung wird mit einem Strich oder dem Zeichen ∅ markiert – so ist klar, dass er nicht vergessen wurde.
Eine Sequenz
Das einfachste Struktogramm ist eine Folge von Kästen:
┌────────────────────────────────┐
│ radius einlesen │
├────────────────────────────────┤
│ flaeche ← PI · radius · radius │
├────────────────────────────────┤
│ flaeche ausgeben │
└────────────────────────────────┘Der Pfeil ← steht für die Wertzuweisung. In Struktogrammen schreibt man ihn so, damit klar wird, dass es keine Gleichung ist.
Eine Verzweigung
┌────────────────────────────────────────┐
│ alter einlesen │
├────────────────────────────────────────┤
│ alter >= 18 │
│ ja ╱────────╲ nein │
├───────────────────────┬────────────────┤
│ Ausgabe: volljährig │ Ausgabe: │
│ │ minderjährig │
├───────────────────────┴────────────────┤
│ Ausgabe: fertig │
└────────────────────────────────────────┘Die beiden Spalten stehen nebeneinander, weil immer nur eine von beiden ausgeführt wird. Darunter läuft es wieder in einem Kasten zusammen – genau wie im Programm.
Eine Schleife
┌──────────────────────────────────────────┐
│ summe ← 0 │
├──────────────────────────────────────────┤
│ i ← 1 │
├──────────────────────────────────────────┤
│ solange i <= n │
│ ┌────────────────────────────────────┐ │
│ │ summe ← summe + i │ │
│ ├────────────────────────────────────┤ │
│ │ i ← i + 1 │ │
│ └────────────────────────────────────┘ │
├──────────────────────────────────────────┤
│ summe ausgeben │
└──────────────────────────────────────────┘Der Schleifenkasten umschließt seinen Rumpf. Dadurch sieht man sofort, was wiederholt wird und was nicht – bei einem Flussdiagramm muss man dafür den Pfeilen folgen.
Aufgabe 1: Struktogramm lesen
Gegeben ist das folgende Struktogramm.
a) Beschreibe in Worten, was der Algorithmus tut.
b) Verfolge ihn auf Papier für die Eingabe n = 4. Notiere nach jedem Durchlauf die Werte von i und erg.
c) Setze ihn danach in Java um und prüfe deine Handrechnung.
┌──────────────────────────────────────────┐
│ n einlesen │
├──────────────────────────────────────────┤
│ erg ← 1 │
├──────────────────────────────────────────┤
│ i ← 1 │
├──────────────────────────────────────────┤
│ solange i <= n │
│ ┌────────────────────────────────────┐ │
│ │ erg ← erg · 2 │ │
│ ├────────────────────────────────────┤ │
│ │ i ← i + 1 │ │
│ └────────────────────────────────────┘ │
├──────────────────────────────────────────┤
│ erg ausgeben │
└──────────────────────────────────────────┘Auflösung zu a) und b)
a) Der Algorithmus berechnet 2 hoch n. Er startet bei 1 und verdoppelt n-mal.
b) Für n = 4:
| nach Durchlauf | i | erg |
|---|---|---|
| (Start) | 1 | 1 |
| 1 | 2 | 2 |
| 2 | 3 | 4 |
| 3 | 4 | 8 |
| 4 | 5 | 16 |
Die Schleife endet, weil 5 nicht mehr kleiner oder gleich 4 ist. Ausgegeben wird 16.
Aufgabe 2: Struktogramm entwickeln
Entwickle auf Papier ein Struktogramm für den folgenden Algorithmus:
Lies eine Zahl
nein. Gib alle Zahlen von 1 bisnaus. Bei jeder Zahl, die durch 3 teilbar ist, gib zusätzlich das Wort „Fizz“ aus.
Setze es danach in Java um.
Tipp: Wo steckt die Verzweigung?
Die Verzweigung liegt innerhalb der Schleife. Im Struktogramm heißt das: Der Verzweigungskasten steht im Rumpf des Schleifenkastens.
Und: Der Nein-Zweig ist leer. Markiere ihn mit ∅ – nicht weglassen.
Aufgabe 3: Darstellungen überführen
Denselben Ablauf in einer anderen Darstellungsform aufzuschreiben, ist eine eigene Fähigkeit. Genau die übst du hier.
Gegeben ist dieses Flussdiagramm.
a) Überführe es in ein Struktogramm.
b) Überführe es in ein Java-Programm.
c) Beschreibe in einem Satz, was der Algorithmus berechnet.
flowchart TD
S([Start]) --> E1[/a einlesen/]
E1 --> E2[/b einlesen/]
E2 --> B{a != b?}
B -- ja --> C{a > b?}
C -- ja --> D[a = a - b]
C -- nein --> F[b = b - a]
D --> B
F --> B
B -- nein --> G[/a ausgeben/]
G --> ENDE([Ende])
Tipp: Erst die Struktur erkennen
Es gibt eine äußere Schleife (die Raute mit a != b, zu der zwei Pfeile zurückführen) und darin eine Verzweigung (die Raute mit a > b).
Zusatzaufgabe
Der euklidische Algorithmus in der Fassung oben zieht immer nur ab. Bei den Zahlen 1000 und 3 braucht er dafür über 300 Durchläufe.
a) Überlege, wie man das Abziehen durch eine Rechenoperation ersetzen kann, die alle Subtraktionen auf einmal erledigt.
b) Zeichne das Struktogramm der schnelleren Fassung.
c) Was passiert bei deiner Fassung, wenn eine der beiden Zahlen 0 ist?