Vertiefung

Dieser Abschnitt beschreibt Programme, die die bisher behandelten Sprachmittel imperativer Programmiersprachen am Beispiel neuer Algorithmen vertiefen.

Geschachtelte Wiederholungen

Bisher kamen in den Wiederholungsrümpfen unserer Programme keine weiteren Wiederholungen vor. Insbesondere beim Aufzählen und Überprüfen kann es passieren, dass Wiederholungen geschachtelt werden, wenn der Test selbst eine Wiederholung verwendet oder mehrere Wiederholungen verwendet werden, um Kandidaten aufzuzählen.

Als Beispiel für ein Programm, das Kandidaten mit Hilfe mehrerer geschachtelter Wiederholungen aufzählt, berechnen wir sogenannte Pythagoräische Tripel. Positive ganze Zahlen \(a \leq b \leq c\) heißen Pythagoräisches Tripel, wenn \(a^2 + b^2 = c^2\) gilt. Das folgende Programm listet alle solche Tripel aus Werten zwischen 1 und 20 auf.

n = 20

for a in range(1, n+1):
  for b in range(a, n+1):
    for c in range(b, n+1):
      if a*a + b*b == c*c:
        print(str(a) + ', ' + str(b) + ', ' + str(c))

Hier besteht der Test aus einer einfachen Bedingung, aber die Aufzählung geschieht mit Hilfe von drei geschachtelten Wiederholungen mit fester Anzahl.

Die Ausgabe dieses Programms ist

3, 4, 5
5, 12, 13
6, 8, 10
8, 15, 17
9, 12, 15
12, 16, 20

Als Beispiel für die Programmiertechnik Aufzählen und Überprüfen, bei dem auch der Test eine Wiederholung verwendet, berechnen wir vollkommene Zahlen. Eine Zahl heißt vollkommen, wenn sie gleich der Summe aller ihrer Teiler ist, die kleiner sind als sie selbst. Die kleinste vollkommene Zahl ist 6, deren Teiler 1, 2 und 3 sind, die addiert wieder 6 ergeben. Dasselbe gilt für 28 = 1+2+4+7+14.

Das folgende Programm gibt alle vollkommenen Zahlen zwischen 1 und 1000 aus:

n = 1000

for i in range(1, n+1):
  sum = 0
  for j in range(1, i):
    if i%j == 0:
      sum = sum + j
  if i == sum:
    print(i)

Hier besteht der Test aus der Berechnung der Summe aller kleineren Teiler von i und dem anschließenden Vergleich dieser Summe mit i.

Die Ausgabe dieses Programms ist

6
28
496

Anscheinend gibt es relativ wenige vollkommene Zahlen.

Euklidischer Algorithmus

Der größte gemeinsame Teiler zweier Zahlen lässt sich mit dem Euklidischen Algorithmus berechnen. Der Algorithmus wurde etwa 300 v. Chr. von Euklid beschrieben und ist einer der ältesten heute noch verwendeten Algorithmen. Der Algorithmus basiert auf der Idee, dass der größte gemeinsame Teiler zweier natürlicher Zahlen sich nicht ändert, wenn man die größere Zahl durch die Differenz der beiden Zahlen ersetzt. Es genügt also, den ggT dieser beiden neuen Zahlen zu berechnen, wodurch das Problem verkleinert wird.¹ Dieses Verfahren wird so lange fortgesetzt, bis beide Zahlen gleich groß sind. Sie entsprechen dann dem ggT der ursprünglichen Zahlen.

Als Beispiel berechnen wir den ggT der Zahlen 49 und 21 anhand dieser Idee:

• \(ggT(49,21) = ggT(49-21,21) = ggT(28,21)\)
• \(ggT(28,21) = ggT(28-21,21) = ggT(7,21)\)
• \(ggT(7,21) = ggT(7,21-7) = ggT(7,14)\)
• \(ggT(7,14) = ggT(7,14-7) = ggT(7,7)\)
• \(ggT(7,7) = 7\)

Also ist der ggT von 49 und 21 gleich 7.

Wir implementieren nun die Anwendung des Euklidischen Algorithmus auf 49 und 21 in Python. Zu Beginn des Programms weisen wir die Eingabezahlen zwei Variablen a und b zu. Anschließend weisen wir schrittweise der größeren der beiden Variablen die Differenz der gespeicherten Zahlen zu, bis beide Variablen, die gleiche Zahl enthalten. Da wir nicht wissen, wieviele Schritte dazu notwendig sind, verwenden wir eine bedingte Wiederholung.

a = 49         #1
b = 21         #2

while a != b:  #3
  if a > b:    #4
    a = a - b  #5
  else:
    b = b - a  #6
    
print(a)       #7

Zur Veranschaulichung werten wir dieses Programm wie folgt tabellarisch aus.

In diesem Beispiel wird deutlich, dass unter Umständen eine Variable mehrfach von der anderen abgezogen wird; nämlich solange wie das Ergebnis größer ist als die abgezogene Zahl. Im obigen Beispiel wird die 21 zunächst von 49 und dann von 28 abgezogen, bis das Ergebnis 7 ist. Dann wird die 7 zuerst von 21 und dann von 14 abgezogen, bis das Ergebnis 7 ist. Der beschriebene Prozess der wiederholten Subtraktion der 21 von 49 endet mit dem Rest der Division von 49 durch 21. Würden wir die 7 am Ende noch einmal von 7 abziehen, würde der Prozess der wiederholten Subtraktion der 7 von 21 ebenfalls mit dem Rest der Division von 21 durch 7 enden. Diese Idee können wir verwenden, um die Anzahl der Wiederholungs-Durchläufe bei der Berechnung des Euklidischen Algorithmus zu verringern, indem wir die Subtraktion durch den Modulo-Operator ersetzen.

a = 49                     #1
b = 21                     #2

while a >= 0 and b != 0:   #3
  if a > b:                #4
    a = a % b              #5
  else:
    b = b % a              #6
    
print(a+b)                 #7

Als Wiederholungsbedingung testen wir, dass keine der Eingabezahlen Null ist, um Division durch Null zu vermeiden. Die Bedingung a != b kann entfallen, da in dem Fall im nächsten wiederholungsdurchlauf a = 0 gesetzt wird, wonach die Wiederholung endet und die Ausgabe-Anweisung a+b, also b ausgibt. Da am Ende der Wiederholung entweder a oder b gleich Null ist und die andere Variable das Ergebnis enthält, können wir die beiden Variablen einfach aufsummieren, um das Ergebnis auszugeben.

Die folgende Tabelle dokumentiert die Ausführung dieses Programms:

Diese Implementierung verwendet nur noch halb so viele Wiederholungsdurchläufe wie die vorherige. Außerdem wechselt der Test der Bedingung a < b in jedem Durchlauf seinen Wert.

Da der Divisionsrest immer kleiner ist als die Zahl, durch die geteilt wurde, ist der Vergleich innerhalb des Wiederholungs-Rumpfes, welche der beiden Variablen a und b größer ist, nicht mehr nötig. Stattdessen können wir die Rollen der Variablen in jedem Schritt vertauschen und den Algorithmus beenden, sobald der berechnete Divisionsrest Null ist. Das folgende Programm implementiert diese Idee.

a = 49         #1
b = 21         #2

while b != 0:  #3
  x = b        #4
  b = a % b    #5
  a = x        #6
  
print(a+b)     #7

Dieses Programm kommt ebenfalls mit der Hälfte der Wiederholungsdurchläufe aus, wie die tabellarische Auswertung zeigt. Statt drei Vergleichen benötigen wir pro Durchlauf nur noch einen:

Im Allgemeinen lässt sich zeigen, dass diese Variante des Euklidischen Algorithmus höchstens fünfmal so viele Schritte benötigt, wie die Anzahl der Ziffern der kleineren Zahl. Der Beweis dieser Eigenschaft markierte 1844 den Beginn der Komplexitätstheorie, die heute als Teil der Theoretischen Informatik erforscht wird.