Lösungen

Aufgabe: Primzahltest

Hier ist ein Programm, dass testet, ob der Wert der Variable n eine Primzahl ist. Wir gehen dabei davon aus, dass dieser Wert eine natürliche Zahl ist.

n = 21                            #1

teilbar = False                   #2
k = 2                             #3
while not teilbar and k*k <= n:   #4
    teilbar = (n % k) == 0        #5
    k = k + 1                     #6

print(n > 1 and not teilbar)      #7

Wir suchen mit einer bedingten Schleife nach dem kleinsten Teiler von n, der größer als eins und ungleich n ist. Dabei können wir abbrechen, wenn wir alle Zahlen probiert haben, deren Quadrat kleiner oder gleich n ist, da der gesuchte Teiler nicht größer sein kann. Für die Ausgabe testen wir zusätzlich, ob n größer als eins ist, da die eins keine Primzahl ist, obwohl sie keinen Teiler größer als eins hat.

Wir verwenden eine bedingte Schleife, um bei gefundenem Teiler abzubrechen. Es ist also unklar, wie oft der Schleifenrumpf ausgeführt wird.

Die folgende Tabelle dokumentiert die Ausführung des obigen Programms.

Aufgabe: Programmtabelle zum Zahlenraten

Bonusaufgabe: Analyse zum Zahlenraten

Die maximale Anzahl Fragen, die das Programm stellt, ist sieben (siehe unten). Diese Zahl wird zum Beispiel bei n = 2 erreicht, wie die folgende Ausgabe demonstriert.

Ist die Zahl gleich 50?
Nein, meine Zahl ist kleiner!
Ist die Zahl gleich 25?
Nein, meine Zahl ist kleiner!
Ist die Zahl gleich 12?
Nein, meine Zahl ist kleiner!
Ist die Zahl gleich 6?
Nein, meine Zahl ist kleiner!
Ist die Zahl gleich 3?
Nein, meine Zahl ist kleiner!
Ist die Zahl gleich 1?
Nein, meine Zahl ist größer!
Ist die Zahl gleich 2?
Ja, erraten.

Um die maximale Anzahl von Fragen systematisch zu bestimmen, passen wir das Programm so an, dass für alle Zahlen zwischen 1 und 100 die gestellten Fragen gezählt werden.

maxcount = 0
for geheim in range(1,101):
  min = 1
  max = 100

  erraten = False
  count = 0

  while not erraten:
    kandidat = (min + max) // 2
    count = count + 1

    if geheim == kandidat:
      erraten = True

    if geheim < kandidat:
      max = kandidat - 1

    if geheim > kandidat:
      min = kandidat + 1

  if count > maxcount:
    maxcount = count

print(maxcount)

Dieses Programm gibt tatsächlich 7 aus. Wir passen das Programm nun so an, dass es alle Zahlen, für die sieben Fragen gestellt werden, ausgibt.

maxcount = 0
for geheim in range(1,101):
  min = 1
  max = 100

  erraten = False
  count = 0

  while not erraten:
    kandidat = (min + max) // 2
    count = count + 1

    if geheim == kandidat:
      erraten = True

    if geheim < kandidat:
      max = kandidat - 1

    if geheim > kandidat:
      min = kandidat + 1

  if count > maxcount:
    maxcount = count

  if count == 7:
    print(geheim)

Es gibt eine ganze Reihe von Zahlen, für die das Programm sieben Fragen braucht, deshalb verzichten wir an dieser Stelle darauf, die Ausgabe des Programms aufzulisten.

Bonusaufgabe: Quadratwurzel suchen

x = 100.0

genauigkeit = 0.001

min = 0.0
max = x

nah_genug = False

count = 0
while not nah_genug:
  kandidat = (min + max) / 2

  fehler = x - kandidat**2
  if -genauigkeit < fehler and fehler < genauigkeit:
    nah_genug = True

  if fehler < 0:
    max = kandidat
  else:
    min = kandidat

  count = count + 1

print(kandidat)
print(count)

Bonusaufgabe: Primzahlen aufzählen

Zum Aufzählen aller Primzahlen schachteln wir die Lösung aus einer vorherigen Aufgabe in eine Zählschleife ein, die alle Zahlen bis zur gegebenen Obergrenze durchläuft. Diejenigen Zahlen, die den Primzahltest bestehen, werden dann im Rumpf der Zählschleife ausgegeben.

max = 1000

for n in range(2,max+1):
  teilbar = False
  k = 2
  while not teilbar and k*k <= n:
    teilbar = (n % k) == 0
    k = k + 1

  if not teilbar:
    print(n)

Den Test n > 1 aus der vorherigen Aufgabe brauchen wir hier am Ende nicht zu verwenden, da die Zählvariable n nur Werte größer gleich zwei durchläuft.

Diese Implementierung zählt alle Zahlen bis zur Obergrenze auf und überprüft die Primzahleigenschaft für jede aufgezählte Zahl. Der Primzahltest verwendet seinerseits die Technik Aufzählen und Überprüfen, um Kandidaten für Teiler aufzuzählen und dann auf die Teilbarkeits-Eigenschaft zu überprüfen. Es handelt sich also um eine geschachtelte Anwendung der diskutierten Programmiertechnik.