Teilen und Herrschen

Statt Lösungskandidaten der Reihe nach aufzuzählen, können wir einige Problem auch lösen, indem wir den durchsuchten Bereich geschickter eingrenzen. Das Verfahren Teile und Herrsche zerlegt ein Problem in, beispielsweise, zwei halb so große Teilprobleme, die dann mit der selben Technik gelöst werden können. Als Beispiel für ein solches Problem betrachten wir das Spiel Zahlenraten.

Eine Spielerin denkt sich eine Zahl zwischen 1 und 100 ohne sie zu verraten. Die Gegenspielerin muss die gedachte Zahl möglichst schnell erraten, wobei sie auf Rateversuche jedoch nur die Antworten “Ja, erraten.”, “Nein, meine Zahl ist kleiner.” oder “Nein, meine Zahl ist größer.” erhält.

Natürlich können wir, um die gedachte Zahl zu erraten einfach alle Zahlen der Reihe nach abfragen, bis wir die richtige Zahl gefunden haben. Deutlich schneller gelangen wir jedoch ans Ziel, wenn wir den durchsuchten Bereich in jedem Schritt halbieren.

Das folgende Programm implementiert diese Idee.

min = 1
max = 100
geheim = 37

erraten = False

while not erraten:
  kandidat = (min + max) // 2
  print("Ist die Zahl gleich " + str(kandidat) + "?")
  
  if geheim == kandidat:
    print("Ja, erraten.")
    erraten = True

  if geheim < kandidat:
    print("Nein, meine Zahl ist kleiner!")
    max = kandidat - 1

  if geheim > kandidat:
    print("Nein, meine Zahl ist größer!")
    min = kandidat + 1

Hier wird der durchsuchte Bereich von min bis max in jedem Schleifendurchlauf halbiert. Wenn die Zahl erraten wurde, wird die Schleife durch die Zuweisung erraten = True beendet.

Die Ausgabe dieses Programms ist

Ist die Zahl gleich 50?
Nein, meine Zahl ist kleiner.
Ist die Zahl gleich 25?
Nein, meine Zahl ist größer.
Ist die Zahl gleich 37?
Ja, erraten.

Die gedachte Zahl wird mit dem Verfahren Teile und Herrsche in diesem Fall also nach drei Schritten gefunden. Der Algorithmus hat in diesem Fall Glück gehabt, weil er den Bereich garnicht bis zum Ende eingrenzen musste. Im schlimmsten Fall nähern sich min und max bei der Ausführung so weit an, dass sie gleich groß sind. In dem Fall ist das Problem dann aber einfach gelöst.