Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

IV_21_titel_doener

Wie man mit TigerJython Zahlen und anderes sortiert

Lila lebt sich in Berlin ein und besucht ihren Deutsch-Kurs. Heute Abend war eigentlich Kino vorgesehen, aber Max muss einen prominenten Gast seiner Firma betreuen. So geht Lila allein nach Hause. Sie hat von Charly die TigerJython-Files bekommen und schaut sie beim Nachhauseweg an. Als sie am Dönerladen vorbeikommt, ruft ein Mitarbeiter die fertigen Bestellungen aus:

4,\; 6,\; 1,\; 3,\; 9,\; 5,\; 4

Komisch, genau die kommen im Sortieralgorithmus vor. Sie studiert gerade ein Programm, das genau diese Zahlen der Größe nach sortiert:

1,\; 3,\; 4,\; 4,\; 5,\; 6,\; 9

Vielleicht steckt ein Zauber dahinter? Sie weiß es nicht. Schade, sie würde gern Max dazu fragen. Der Algorithmus „im Buch“ gefällt ihr wirklich. Er geht so:

Sortieralgorithmus

Man legt ein Array unsortiert fest:

\mathrm{unsortiert}\;=\;[4,\; 6,\; 1,\; 3,\; 9,\; 5,\; 4]

Man vereinbart ein Array sortiert, in das nacheinander die kleinsten Zahlen von unsortiert hineingeschrieben werden.

1. Schleife

(A) Zuerst bestimmt man die Länge von unsortiert:

\mathrm{len} (\mathrm{unsortiert}),

das ist die Anzahl der Elemente, also

\mathrm{len} (\mathrm{unsortiert})\;=\;7

Ist die Länge größer als 0, macht man weiter. Um die kleinsten Zahlen systematisch zu finden, fängt man mit der 1. Zahl von unsortiert an:

\min\; \leftarrow\; 4

2. Schleife

(B) Man geht alle Stellen von unsortiert durch und fragt, ob eine kleiner als 4 ist. Ja, es ist

1\; <\; 4

Dann ersetzt man das Minimum durch diese Zahl, sonst bleibt sie:

\min\; \leftarrow\; 1

Aus unsortiert wird das Minimum herausgenommen,

\mathrm{unsortiert}\; \leftarrow\; [4,\; 6,\; 3,\; 9,\; 5,\; 4]

in sortiert wird es angehängt:

\mathrm{sortiert}\; \leftarrow\; [1]

Mit diesen beiden Arrays geht man zu (A) und macht das erneut. Lila fragt sich, warum die Schüler in Deutschland kein Flowchart lernen, das wäre doch anschaulich, das gehört doch zum Programmieren dazu, auch Donald Knuth schreibt solche Flowcharts.

iV_21_flowchart_sort_03-06
Flowchart für den Sortieralgorithmus

 

IV_21_code_original_02
Code des Sortierens nach: Hromkovič & Kohn, S. 113.

 

Problem

Doch nun will sie keine feste Folge im Programm benutzen, sondern interaktiv was eingeben. Doch als sie das ausprobiert, klappt das nicht. Hauptschuld daran hat die Art der Datentypen in TigerJython – nämlich alles offen zu lassen. So kann sie mit dem im Buch empfohlenen Befehl

\mathrm{input}(\;\cdot\;)

  • Zeichenketten
  • ganze Zahlen
  • durch Komma getrennte Zahlen
  • Dezimalzahlen mit Dezimalpunkt
  • Sonderzeichen

eingeben. Doch eigentlich will sie nur ganze und Gleitkommazahlen zulassen. Und schlimmer noch, wenn sie so eine wiederholte Eingabe zulässt, wenn sie eine Schleife macht mit beliebig vielen Eingaben, wie beendet man dann die Eingabe, wenn jede Eingabe akzeptiert wird und „Abbrechen“ zum Abbruch des Programms führt?

iV_21_eingabe

Sie verzweifelt fast. Dann findet sie 2 Befehle:

\mathrm{ord}\;:\;\mathcal{L} \rightarrow \mathbf{N},

für

\mathcal{L}\;=\;\{\; a,\; b,\; c,\; \dots,\; z,\; A,\; B,\; C,\; \dots,\; Z,\; +, \;-,\; *,\; (,\; ),\; !,\; \dots\;\}

als Menge aller eingebbaren Zeichen einer Tatstatur und den Befehl

\mathrm{chr}\;:\;\mathbf{Z}\; \rightarrow\; \mathcal{L},

die ihr brauchbar erscheinen. Doch der 1. Befehl wandelt alle Buchstaben u.ä. Zeichen in eine natürliche Zahl – nur Zahlen sind als Eingabe nicht zugelassen! Und der 2. Befehl wandelt alle ganzen Zahlen in Buchstaben oder Zeichen um, lässt aber als Eingaben keine Elemente von \mathcal{L} zu. Wie soll sie vor der Eingabe wissen, welche Eingabe kommt? Doch sie will nicht aufgeben. Es muss doch möglich sein, mit fehlerhaften Eingaben umzugehen – ohne Absturz des Programms. Warum spielt das eigentlich im Schulbuch keine Rolle? Geben alle Kinder in Deutschland nur korrekte Werte ein?

Ein spezieller Eingabebefehl

Doch endlich kommt Max. Zusammen finden sie eine Liste aller TigerJython-Befehle im Netz. Das kann Max wirklich gut. Einer davon ist geeignet, er sieht ein bisschen kompliziert aus, aber zusammen verstehen sie den:

\mathrm{inputFloat}\;:\;(\mathcal{L}^n\; \cup\; \mathbf{Z}\; \cup\;\mathbf{Q}\prime )\; \times \; \{\mathrm{True},\; \mathrm{False}\}

\; \rightarrow\; \mathbf{Q}\prime\; \cup\; \{\mathrm{True, \; None}\}

Dabei bezeichnet \mathbf{Q}\prime die Gleitkommazahlen. \mathrm{inputFloat} ist eine Funktion, die ganze und Gleitkommazahlen in Gleitkommazahlen umwandelt:

\mathrm{inputFloat}( \mathbf{Z}\; \cup\; \mathbf{Q}\prime,\; \mathrm{False})\; \subset\; \mathbf{Q}\prime,

\mathrm{inputFloat}( z,\; \mathrm{False})\;=\;z\; \forall \; z \;\in\;\mathbf{Z}\; \cup\; \mathbf{Q}\prime

Bei Buchstaben u.a. Zeichen gibt sie eine Fehlermeldung aus:

\mathrm{inputFloat}(l,\; \mathrm{False})\;=\;\mathrm{True}\; \forall\; l \;\in \;\mathcal{L}^n

Außerdem hat sie eine weitere Option True oder False für den Abbruch. Bei „Abbruch“ wird nur die Eingabe beendet, so wie Lila sich das wünscht, und das Programm wird weiter ausgeführt.

\mathrm{inputFloat}(z,\; \mathrm{True})\;=\;\mathrm{None}\; \forall\; z\; \in\; \mathcal{L}^n \;\cup \;\mathbf{Z}\; \cup\; \mathbf{Q}\prime

Jetzt muss Lila das nur noch geschickt anwenden und mit dem Sortierprogramm „verknüpfen“.

***

Übungsaufgaben

  1. Schreibe ein Flowchart für so eine Eingabe-Funktion!
  2. Schreibe den Code für den Sortieralgorithmus mit allgemeiner Eingabe!

Lösungen

iV_21_flowchart_input_01-04
Flowchart für die Eingabefunktion input_f mit allgemeiner Eingabe für Gleitkommazahlen

 

IV_21_code_02
Code für das Sortierprogramm mit allgemeiner Eingabe für Gleitkommazahlen