So implementieren Sie das Tower of Hanoi-Problem mit Python

Vorwort

Das Problem des Turms von Hanoi ist ein klassisches Problem. Der Hanoi-Turm, auch Hanoi-Turm genannt, geht auf eine alte Legende in Indien zurück. Als Brahma die Welt erschuf, schuf er drei Diamantsäulen. Auf einer Säule wurden 64 Goldscheiben in der Reihenfolge ihrer Größe von unten nach oben gestapelt. Brahma befahl dem Brahmin, die Scheiben auf einer anderen Säule in der Reihenfolge ihrer Größe von unten neu anzuordnen. Es ist auch festgelegt, dass die Scheibe zu keinem Zeitpunkt auf der kleinen Scheibe vergrößert werden kann und jeweils nur eine Scheibe zwischen den drei Säulen bewegt werden kann. Fragen Sie, wie man funktioniert?

1. Lassen Sie uns zunächst darüber sprechen, was Rekursion ist.

Mein eigenes Verständnis ist: Reduzieren Sie weiterhin die Größe Ihrer eigenen Probleme, bis sie so weit reduziert sind, dass sie nicht mehr reduziert werden können. (Die Endbedingung der Rekursion ist erreicht) Beginnen Sie dann mit der Lösung der kleinen Probleme, nachdem Sie die kleinen Probleme einzeln gelöst haben (die Rekursion ist zurück)

2. Kurz gesagt:

Das ursprüngliche Problem wird kontinuierlich auf einen kleineren Maßstab des ursprünglichen Problems reduziert, und dann wird das kleine ursprüngliche Problem gelöst, wodurch das ursprüngliche große Problem gelöst wird!

3. Der Prozess ist:

Reduzieren Sie den Maßstab, lösen Sie ihn von einer kleinen Größe, rekursieren Sie zurück und lösen Sie das ursprüngliche Problem! ! !

4. Der Schlüssel zur Rekursion ist:

(1) Es gibt eine Rekursionsendbedingung.

(2) Ruft sich ständig auf, um die Größe des Problems zu verringern und näher an die Endbedingung der Rekursion heranzukommen.

Problem mit dem Turm von Hanoi

1. Problembeschreibung

Es gibt drei Säulen mit den Namen A, B und C. Zu Beginn gibt es n Scheiben auf der Säule A, sie sind von unten nach oben und die Größe der Scheiben reicht von groß nach klein. Beim Bewegen und Platzieren müssen die kleinen Platten auf den großen Platten liegen. Verschieben Sie unter Beachtung der Regeln alle Platten der Säule A zur Säule C. Sie können während des Umzugs die Säule B nutzen, müssen aber darauf achten, dass die kleinen Platten während des Umzugs auf den großen Platten liegen müssen! ! ! Bitte den Umzugsvorgang ausdrucken?

2. Rekursiver Prozess der Problemanalyse:

(1) Verschieben Sie die oberen n-1 Platten mit Hilfe von C

(2) Verschieben Sie die untere Platte von A nach C

(3 ) Verschieben Sie die oberen n-1 Platten mit Hilfe von A von B nach C

Die Endbedingung der Rekursion:

Die Problemskala wird, wenn die Anzahl der Platten 0 ist, denn wenn die Anzahl der Platten 0 ist, ist dies nicht erforderlich umziehen! ! !

3. Code (Python)

# coding:utf-8

"""
    n为初始时A柱上的盘子数
    a为起始盘子所在的柱子
    b为中转柱子
    c为目的地柱子
"""


def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c, b)
        print("盘子从%s移动到%s" % (a, c))
        hanoi(n-1, b, a, c)



hanoi(3, "A", "B", "C")

4

Das obige ist der detaillierte Inhalt vonSo implementieren Sie das Tower of Hanoi-Problem mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!