Aufzählen und Überprüfen

Ein Vorteil eines Computers gegenüber einem Menschen ist die Fähigkeit, viele Werte sehr schnell aufzählen und gewisse Eigenschaften für diese Werte testen zu können. Somit können viele Probleme, bei denen der Bereich der möglichen Lösungen endlich ist und aufgezählt werden kann, mit der Programmiertechnik Aufzählen und Überprüfen gelöst werden.

Als Beispiel für diese Technik betrachten wir die Berechnung des größten gemeinsamen Teilers zweier natürlicher Zahlen. Der größte gemeinsame Teiler zweier Zahlen wird z.B. beim Kürzen von Brüchen verwendet, wobei Zähler und Nenner durch ihren größten gemeinsamen Teiler dividiert werden.

Mathematisch kann der größte gemeinsame Teiler (ggT) wie folgt definiert werden. Für gegebene natürliche Zahlen \(a, b \in \mathbb{N}\) ist ((ggT(a,b) = c \in \mathbb{N}\) diejenige natürliche Zahl für die gilt: c teilt a ohne Rest, c teilt b ohne Rest und für alle weiteren Teiler d von a und b gilt \(c > d\).

Als Beispiel betrachten wir folgende Zahlen.

• 21 hat die Teiler 1,3,7 und 21.
• 18 hat die Teiler 1,2,3,6,9 und 18.

Der größte gemeinsame Teiler von 21 und 18 ist also \(ggT(21,18) = 3\).

Jede positive Zahl ist ein Teiler der Null. Für alle \(a > 0\) gilt also \(ggT(a,0) = ggT(0,a) = a\). Der Wert von \(ggT(0,0)\) ist nicht definiert, da alle positiven Zahlen Teiler von 0 sind; es gibt also keinen größten gemeinsamen Teiler.

Für die Überprüfung, ob eine Zahl eine andere ohne Rest teilt kann der Modulo-Operator verwendet werden, welcher den Rest einer ganzzahligen Division liefert. Falls a und b ganzzahlige Werte sind, so liefert % den Rest der ganzzahligen Division von a durch b.

Wie können wir das Problem der Berechnung größter gemeinsamer Teiler algorithmisch lösen? Eine einfache Methode ist die Berechnung durch Aufzählen und Überprüfen.¹

Der ggT von a und b liegt sicherlich zwischen 1 und der kleineren der beiden Zahlen. Wir können also diese Werte der Reihe nach aufzählen und jeweils testen, ob die entsprechende Zahl beide gegebenen Zahlen ohne Rest teilt.

Für die Überprüfung, ob eine Zahl eine andere ohne Rest teilt kann der Modulo-Operator verwendet werden, welcher den Rest einer ganzzahligen Division liefert. Falls a und b ganzzahlige Werte sind, so liefert % den Rest der ganzzahligen Division von a durch b.

Das folgende Programm berechnet zunächst das Minimum min gegebener Zahlen a und b und sucht dann in einer Zähl-Schleife den größten gemeinsamen Teiler dieser Zahlen.

a = 4                           #1
b = 6                           #2

if a < b:                       #3
    min = a                     #4
else:
    min = b                     #5

for i in range(1,min+1):        #6
    if a%i == 0 and b%i == 0:   #7
        ggT = i                 #8

print(ggT)                      #9

Wir verwenden eine Zähl-Schleife, da wir alle Werte zwischen 1 und min daraufhin testen wollen, ob sie ein Teiler von sowohl a als auch b sind. Wir wissen also vorher, wieviele Schleifendurchläufe dafür gebraucht werden. Die Bedingung für den Test ist wegen der Präzedenzen der beteiligten Operatoren so geklammert: ((a%i) == 0) and ((b%i) == 0). Bei Programmende ist die größte Zahl i, die diese Bedingung erfüllt (also der ggT von a und b) in der Variablen ggT gespeichert.

Die folgende Tabelle dokumentiert die Ausführung dieses Programms.

Statt alle Zahlen zu durchlaufen, können wir auch von oben anfangen aufzuzählen. Diese Vorgehensweise hat den Vorteil, dass der erste gefundene gemeinsame Teiler auch der größte ist. Wir können dann die Schleife beenden, sobald wir einen gemeinsamen Teiler gefunden haben.

Da wir hierbei nicht wissen, wieviele Schleifendurchläufe gebraucht werden, verwenden wir zur Implementierung dieser Idee eine bedingte Schleife. Das folgende Programm bestimmt zunächst mit einer bedingten Verzweigung die kleinere der beiden Eingabezahlen und sucht dann mit einer bedingten Schleife abwärts nach dem größten gemeinsamen Teiler, der schließlich mit einer print-Anweisung ausgegeben wird.

a = 4                            #1
b = 6                            #2

if a < b:                        #3
  ggT = a                        #4
else:
  ggT = b                        #5

while a%ggT != 0 or b%ggT != 0:  #6
  ggT = ggT - 1                  #7

print(ggT)                       #8

Die folgende Tabelle dokumentiert die Ausführung dieses Programms.

Setzen wir eine der Zahlen a und b gleich 0, liefert dieses Programm einen Laufzeitfehler wegen Division durch Null. Um dies zu verhindern müssen wir die Randfälle, in denen mindestens eine der Eingabezahlen Null ist, prüfen und unseren Algorithmus nur dann ausführen, wenn beide Zahlen ungleich Null sind.

a = 4
b = 6

if a == 0 and b == 0:
  print("nicht definiert")
else:
  if a == 0:
    print(b)
  if b == 0:
    print(a)
  if a != 0 and b != 0:
    if a < b:
      ggT = a
    else:
      ggT = b

    while a%ggT != 0 or b%ggT != 0:
      ggT = ggT - 1

    print(ggT)

Hier zeigt sich, dass es beim Testen von Programmen wichtig ist, Randfälle systematisch zu überprüfen. Manchmal wird ein Programm leider bei korrekter Behandlung der Randfälle wie hier etwas aufgebläht.