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_10_titel_kunst_programm

Die Kunst des Programmierens

Lila verbringt ein paar Tage bei ihrer Freundin Maya in Mandarmani, am Meer. Dort sind die beiden oft am Strand. Lila diskutiert mit Maya, ob sie wohl Mathe oder Informatik in Deutschland studieren sollte. Aber was liegt ihr mehr? Sie hat bis jetzt ein kleines Programm zur Suche von Mersenne-Primzahlen ausgeführt und verstanden, doch was muss man wirklich lernen? Kann sie Informatik lernen? Kann sie es systematisch erlernen? Oder verbringt man einfach sehr viel Zeit mit dem Rechner? Was ist das Wesen von Informatik?

Schließlich empfiehlt ihr Maya das Buch von Donald Knuth: The Art of Computer Programming. Hier wird viel von Zahlen, vollständiger Induktion und Sortieren gesprochen. Am Beispiel des größten gemeinsamen Teilers zweier Zahlen bekommt sie eine Ahnung von der Kunst des Programmierens.

Maya Wenn man zwei natürliche Zahlen m und n hat, dann ist deren größten gemeinsamen Teiler gesucht. Das ist die Einstiegsaufgabe.

Lila Hm, wenn ich von jeder dieser beiden Zahlen die Teiler wüsste, könnte ich den größten gemeinsamen leicht raussuchen. Aber wie finde ich die Teiler? Soll ich alle Zahlen, die kleiner als m und n sind, ausprobieren?

Euklidischer Algorithmus

Maya Nein, schau mal, das dauert bei großen Zahlen zu lange, das ist nicht effizient. Donald Knuth schlägt den euklidischen Algorithmus vor. Der geht so:

  1. Du nimmst die beiden Zahlen m und n und dividierst sie durcheinander: \frac{m}{n}\;.
  2. Ist das ohne Rest möglich, dann teilt n die Zahl mn ist der größte gemeinsame Teiler.
  3. Bleibt ein Rest r, dann ersetzt Du m durch n und n durch r. Und fängst wieder beim 2. Punkt an.

Beispiel

Lila Ich durchschaue es nicht. Ich rechne mal ein Beispiel. Gut, nehmen wir seins:

m\;=\;544,\; n\;=\;119

Dann kriege ich

\frac{m}{n}\;=\;4, 57\dots

Zur Berechnung des Restes brauche ich nur den ganzen Anteil von \frac{m}{n}\;, das ist dann 4, so gehts weiter:

r\;=\;544\;-\;4 \;\cdot\; 119\;=\;68.

Okay, r\;\ne\;0, dann ist jetzt

m\;=\;119,\; n\;=\;68

\frac{m}{n}\;=\;1,75

Das ergibt für den Rest

r\;=\;119\;-\;1\;\cdot\; 68\;=\;51.

Der Rest ist ungleich Null, dann

m\;=\;68,\; n\;=\;51

\frac{m}{n}\;=\;1,33\dots

Für den Rest kriege ich

r\;=\;68\;-\;1 \;\cdot\; 51\;=\;17.

Weiter, r\;\ne\;0,

m\;=\;51,\; n\;=\;17

\frac{m}{n}\;=\;3

Da gibt es keinen Rest, dann hast Du gesagt….

Maya n teilt m, n ist der größte gemeinsame Teiler.

Lila Gut. 17 ist der größte gemeinsame Teiler von 544 und 119. Stimmt. Ich wäre nie auf diesen Algorithmus gekommen. Wie funktioniert der?

Endlichkeit des Algorithmus

Maya Hier, Du hast gerechnet:

Schrittmnr
154411968
21196851
3685117
451170

Dabei hast Du intuitiv die Definition des Restes benutzt:

m\;=\;k\; \cdot \; n\;+\;r

k,\; r\; \in \; \mathbf{N},

0\; \le\; r\; <\; n.

Das r ist immer kleiner als n, das ist wichtig. Auf diese Weise wird die Folge der Reste r immer kleiner und muss bei Null enden.

Korrektheit des Algorithmus

Lila Cool! Aber wieso kommt die richtige Zahl raus?

Maya Wenn beim ersten Schritt r\;=\;0 ist, dann teilt n die Zahl m. Das ist natürlich bei jedem Schritt so. Wenn r\;\ne\;0, dann ist

m\;=\;k\;\cdot\; n\;+\;r,

wieder mit natürlichen k und r,  0\; < \;r\; <\;  n. Oder umgestellt:

m\;-\;k\; \cdot \;n\;=\;r.

Jede Zahl, die m und n teilt, muss auch r teilen. Das ist so ein typisch algebraisches Argument, das sind gleiche Eigenschaften der Ausdrücke rechts und links vom Gleichheitszeichen.

Lila Gut, verstehe.

Maya Und für jede größte Zahl von Teilern gilt das auch. Also können wir statt der Aufgabe, den größten Teiler von m und n zu suchen, die Aufgabe lösen, den größten Teiler von n und r zu suchen.

Lila Verstehe. Ziemlich intelligent. Jetzt versuche ich mal, das zu programmieren. Hast Du ein schönes Beispiel für mich?

Maya Na, 2 166 und 6 099! Viel Spaß!

Lila Dann versuch ich‘s mal!

***

Übungsaufgaben

  1. Löse Mayas Aufgabe!
  2. Finde den größten gemeinsamen Teiler von 2 167 und 7 000.
  3. Finde den größten gemeinsamen Teiler von 971 230 541 und
    2 964 081.
  4. Was ist, wenn \frac{m}{n}\; < \;1?

Lösungen

  1. ggT(2 166, 6 099) = 57
  2. ggT(2 167, 7 000) = 1
  3. ggT(971 230 541, 2 964 081) = 988 027
  4. Dann tausche die Zahlen m und n.