python~ハノイの塔と再帰関数

はじめに

こんにちは，Keymaleです．今回はハノイの塔です．再帰関数として有名な問題ですね．ハノイの塔を解くにあたり，まずはスタックを実装します．

スタック

スタックとはLIFO（Last In First Out）と呼ばれ，最後に入れたものからしか取り出せない構造です．以下のクラスで実装しました．

class Stack():

    def __init__(self):
        self._container = []

    
    def push(self, item):
        self._container.append(item)
    

    def pop(self):
        return self._container.pop()
    

    def __repr__(self):
        return repr(self._container)

ハノイの塔

ハノイの塔を解く関数を作ります．

AからCにn枚のディスクを移動するとき，以下の再帰ステップが生じます

1：上のn-1枚のディスクをAからBにCをテンポラリで利用して移動
2：最後の一枚をAからCに移動
3：n-1枚をBからCにAをテンポラリで利用して移動

これを実装すると以下のようになります．

def hanoi(begin, end, temp, n):
    if n == 1:
        end.push(begin.pop())
    else:
        hanoi(begin, temp, end, n-1)
        hanoi(begin, end, temp, 1)    
        hanoi(temp, end, begin, n-1)

動かしてみる

最後にスタックとハノイの塔の関数を組み合わせて動かして見ます．

class Stack():

    def __init__(self):
        self._container = []

    
    def push(self, item):
        self._container.append(item)
    

    def pop(self):
        return self._container.pop()
    

    def __repr__(self):
        return repr(self._container)
    

disc = 3

tower_a = Stack()
tower_b = Stack()
tower_c = Stack()
##initialize
for i in range(1, disc + 1):
    tower_a.push(i)

    
def hanoi(begin, end, temp, n):
    if n == 1:
        end.push(begin.pop())
    else:
        hanoi(begin, temp, end, n-1)
        hanoi(begin, end, temp, 1)    
        hanoi(temp, end, begin, n-1)


if __name__ == "__main__":
    print('A:' + str(tower_a))
    print('B:' + str(tower_b))
    print('C:' + str(tower_c))
    hanoi(tower_a, tower_c, tower_b, disc)
    print('A:' + str(tower_a))
    print('B:' + str(tower_b))
    print('C:' + str(tower_c))

AからCにディスクが移動しました．