[GO] Turm von Hanoi - Retrospektiv / Nicht rekursiv (Python Edition)

Regel

Unten [Turm von Hanoi-Wikipedia](http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1% Ab 94)

Schließen Sie ab, wenn Sie alle Datenträger gemäß den folgenden Regeln auf den Stapel ganz rechts verschieben können.

1. Besteht aus 3 Stapeln und mehreren Scheiben unterschiedlicher Größe mit einem Loch in der Mitte.
2. Zuerst werden alle Scheiben in der Reihenfolge auf dem Stapel ganz links gestapelt, wobei die kleineren oben liegen.
3. Sie können eine Disc einzeln auf einen der Stapel verschieben, aber Sie können keine große Disc auf eine kleine Disc legen.

Denkweise

• Die Drehrichtung des Stapels jeder Scheibe wechselt
• Der rekursive Code ist ein Prozess, der die Bewegung von drei Platten (n, n-1, n-2) in einer bestimmten Phase wiederholt.
• Der nicht rekursive Code ist ein Prozess, der die Bewegung wiederholt, während ermittelt wird, ob die Festplatte verschoben werden kann, indem die Funktion verwendet wird, mit der sich die Bewegungsrichtungen der Festplatten abwechseln.
• Die Anzahl der Züge beträgt "2 ^ n - 1"

Rekursiver Code

# coding: utf-8

def hanoi(disk_number, f, t, w, tower_dict):

    if disk_number > 0:
        hanoi(disk_number-1, f, w, t, tower_dict)
        tower_dict[t].insert(0, tower_dict[f].pop(0))
        print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
        hanoi(disk_number-1, w, t, f, tower_dict)


if __name__ == '__main__':
    disk_number = int(input())
    tower_dict = {'left': [i for i in range(1, disk_number+1)], 'center': [], 'right': []}
    print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
    hanoi(disk_number, 'left', 'right', 'center', tower_dict)

Nicht rekursiver Code

def hanoi(tower_list, pile_list, disk_number):
    cnt = 0
    passed_list = [tower_list[:]]

    while True:

        for disk in range(1, disk_number+1):

            #Wenn sich die aktuelle Festplatte nicht oben auf dem Stapel befindet, wechseln Sie zur nächsten Festplatte
            if tower_list.index(tower_list[disk-1]) != disk-1:
                continue

            idx = pile_list.index(tower_list[disk-1])

            #Rechts abbiegen (links)-> center -> right -> left ...Drehen Sie in der Reihenfolge von)
            if (disk_number % 2 == 0 and disk % 2 == 1) or (disk_number % 2 == 1 and disk % 2 == 0) :

                if idx+1 >= len(pile_list):
                    idx = -1

                if pile_list[idx+1] not in tower_list or tower_list.index(pile_list[idx+1]) > disk-1:
                    tower_list[disk-1] = pile_list[idx+1]
                    passed_list.append(tower_list[:])
                    cnt += 1


            #Links-> right -> center -> left ...Drehen Sie in der Reihenfolge von)
            else:

                if 0 >= idx:
                    idx = len(pile_list)

                if pile_list[idx-1] not in tower_list or tower_list.index(pile_list[idx-1]) > disk-1:
                    tower_list[disk-1] = pile_list[idx-1]
                    passed_list.append(tower_list[:])
                    cnt += 1

            if tower_list == ['r'] * disk_number:
                return cnt, passed_list

if __name__ == '__main__':
    disk_number = int(input())
    pile_list = ['l', 'c', 'r']
    tower_list = ['l'] * (disk_number)

    cnt, passed_list = hanoi(tower_list, pile_list, disk_number)

    print(passed_list)

Bonus (nicht rekursiver Testcode)

# coding: utf-8

import unittest


class HanoiTest(unittest.TestCase):

    def setUp(self):
        self.pile_list = ['l', 'c', 'r']

    def test_first(self):
        disk_number = 3
        tower_list = ['l'] * (disk_number)
        cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
        self.assertEqual(cnt, 2 ** disk_number - 1)
        self.assertEqual(passed_list, [
            ['l', 'l', 'l'],
            ['r', 'l', 'l'],
            ['r', 'c', 'l'],
            ['c', 'c', 'l'],
            ['c', 'c', 'r'],
            ['l', 'c', 'r'],
            ['l', 'r', 'r'],
            ['r', 'r', 'r']
        ])

    def test_second(self):
        disk_number = 4
        tower_list = ['l'] * (disk_number)
        cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
        self.assertEqual(cnt, 2 ** disk_number - 1)
        self.assertEqual(passed_list, [
            ['l', 'l', 'l', 'l'],
            ['c', 'l', 'l', 'l'],
            ['c', 'r', 'l', 'l'],
            ['r', 'r', 'l', 'l'],
            ['r', 'r', 'c', 'l'],
            ['l', 'r', 'c', 'l'],
            ['l', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'r'],
            ['r', 'c', 'c', 'r'],
            ['r', 'l', 'c', 'r'],
            ['l', 'l', 'c', 'r'],
            ['l', 'l', 'r', 'r'],
            ['c', 'l', 'r', 'r'],
            ['c', 'r', 'r', 'r'],
            ['r', 'r', 'r', 'r']
        ])

    def test_third(self):
        disk_number = 5
        tower_list = ['l'] * (disk_number)
        cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
        self.assertEqual(cnt, 2 ** disk_number - 1)
        self.assertEqual(passed_list, [
            ['l', 'l', 'l', 'l', 'l'],
            ['r', 'l', 'l', 'l', 'l'],
            ['r', 'c', 'l', 'l', 'l'],
            ['c', 'c', 'l', 'l', 'l'],
            ['c', 'c', 'r', 'l', 'l'],
            ['l', 'c', 'r', 'l', 'l'],
            ['l', 'r', 'r', 'l', 'l'],
            ['r', 'r', 'r', 'l', 'l'],
            ['r', 'r', 'r', 'c', 'l'],
            ['c', 'r', 'r', 'c', 'l'],
            ['c', 'l', 'r', 'c', 'l'],
            ['l', 'l', 'r', 'c', 'l'],
            ['l', 'l', 'c', 'c', 'l'],
            ['r', 'l', 'c', 'c', 'l'],
            ['r', 'c', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'c', 'r'],
            ['l', 'c', 'c', 'c', 'r'],
            ['l', 'r', 'c', 'c', 'r'],
            ['r', 'r', 'c', 'c', 'r'],
            ['r', 'r', 'l', 'c', 'r'],
            ['c', 'r', 'l', 'c', 'r'],
            ['c', 'l', 'l', 'c', 'r'],
            ['l', 'l', 'l', 'c', 'r'],
            ['l', 'l', 'l', 'r', 'r'],
            ['r', 'l', 'l', 'r', 'r'],
            ['r', 'c', 'l', 'r', 'r'],
            ['c', 'c', 'l', 'r', 'r'],
            ['c', 'c', 'r', 'r', 'r'],
            ['l', 'c', 'r', 'r', 'r'],
            ['l', 'r', 'r', 'r', 'r'],
            ['r', 'r', 'r', 'r', 'r']
        ])

Referenz

Turm von Hanoi-Wikipedia Erobere den Turm von Hanoi Lösen des Turms in Hanoi durch Rekursiv