ハノイの塔を解くプログラムを作ってみます。ご存知ない方はWikipedia – ハノイの塔をどうぞ。もしくはリンクした結城浩さんの「プログラマの数学」に詳しい解説があります。結城さんのほとんどの本がそうであるように、この本もプログラムの初心者から上級者まで楽しく読める良書です。

—–

以下のhanoi.pyはハノイの塔の高さnを引数にとり、ハノイの塔の解法プロセスを表示するプログラムです。ただし表示といっても面倒くさかったので、棒が横向きに表示されております。右側を上だと思ってください。また番号は円盤の大きさを表していると思ってください。クラスで書いてますけれど、そこに特に意味はないです。

hanoi.py

import sys
class Hanoi:
def __init__(self, hgt):
self.hgt = hgt
self.bars = [range(hgt, 0, -1),[],[]]
self.step = 0
print self
self.dohanoi(hgt, 0, 1, 2)
def __repr__(self):
str1 = 'step -> %s' % str(self.step)
str2 = 'BAR1 : ' + str(self.bars[0])
str3 = 'BAR2 : ' + str(self.bars[1])
str4 = 'BAR3 : ' + str(self.bars[2])
return str1 + '\n' + str2 + '\n' + str3 + '\n' + str4
def dohanoi(self, n, start, end, other):
if n == 1:
self.bars[end].append(self.bars[start].pop())
self.step += 1
print self
else:
self.dohanoi(n - 1, start, other, end)
self.bars[end].append(self.bars[start].pop())
self.step += 1
print self
self.dohanoi(n - 1, other, end, start)
if __name__ == '__main__':
hanoi = Hanoi(int(sys.argv[1]))

3段での実行結果。

C:\Python24>python.exe hanoi.py 3
step -> 0
BAR1 : [3, 2, 1]
BAR2 : []
BAR3 : []
step -> 1
BAR1 : [3, 2]
BAR2 : [1]
BAR3 : []
step -> 2
BAR1 : [3]
BAR2 : [1]
BAR3 : [2]
step -> 3
BAR1 : [3]
BAR2 : []
BAR3 : [2, 1]
step -> 4
BAR1 : []
BAR2 : [3]
BAR3 : [2, 1]
step -> 5
BAR1 : [1]
BAR2 : [3]
BAR3 : [2]
step -> 6
BAR1 : [1]
BAR2 : [3, 2]
BAR3 : []
step -> 7
BAR1 : []
BAR2 : [3, 2, 1]
BAR3 : []

5段での実行結果。

C:\Python24>python.exe hanoi.py 5
step -> 0
BAR1 : [5, 4, 3, 2, 1]
BAR2 : []
BAR3 : []
step -> 1
BAR1 : [5, 4, 3, 2]
BAR2 : [1]
BAR3 : []
step -> 2
BAR1 : [5, 4, 3]
BAR2 : [1]
BAR3 : [2]
step -> 3
BAR1 : [5, 4, 3]
BAR2 : []
BAR3 : [2, 1]
step -> 4
BAR1 : [5, 4]
BAR2 : [3]
BAR3 : [2, 1]
step -> 5
BAR1 : [5, 4, 1]
BAR2 : [3]
BAR3 : [2]
step -> 6
BAR1 : [5, 4, 1]
BAR2 : [3, 2]
BAR3 : []
step -> 7
BAR1 : [5, 4]
BAR2 : [3, 2, 1]
BAR3 : []
step -> 8
BAR1 : [5]
BAR2 : [3, 2, 1]
BAR3 : [4]
step -> 9
BAR1 : [5]
BAR2 : [3, 2]
BAR3 : [4, 1]
step -> 10
BAR1 : [5, 2]
BAR2 : [3]
BAR3 : [4, 1]
step -> 11
BAR1 : [5, 2, 1]
BAR2 : [3]
BAR3 : [4]
step -> 12
BAR1 : [5, 2, 1]
BAR2 : []
BAR3 : [4, 3]
step -> 13
BAR1 : [5, 2]
BAR2 : [1]
BAR3 : [4, 3]
step -> 14
BAR1 : [5]
BAR2 : [1]
BAR3 : [4, 3, 2]
step -> 15
BAR1 : [5]
BAR2 : []
BAR3 : [4, 3, 2, 1]
step -> 16
BAR1 : []
BAR2 : [5]
BAR3 : [4, 3, 2, 1]
step -> 17
BAR1 : [1]
BAR2 : [5]
BAR3 : [4, 3, 2]
step -> 18
BAR1 : [1]
BAR2 : [5, 2]
BAR3 : [4, 3]
step -> 19
BAR1 : []
BAR2 : [5, 2, 1]
BAR3 : [4, 3]
step -> 20
BAR1 : [3]
BAR2 : [5, 2, 1]
BAR3 : [4]
step -> 21
BAR1 : [3]
BAR2 : [5, 2]
BAR3 : [4, 1]
step -> 22
BAR1 : [3, 2]
BAR2 : [5]
BAR3 : [4, 1]
step -> 23
BAR1 : [3, 2, 1]
BAR2 : [5]
BAR3 : [4]
step -> 24
BAR1 : [3, 2, 1]
BAR2 : [5, 4]
BAR3 : []
step -> 25
BAR1 : [3, 2]
BAR2 : [5, 4, 1]
BAR3 : []
step -> 26
BAR1 : [3]
BAR2 : [5, 4, 1]
BAR3 : [2]
step -> 27
BAR1 : [3]
BAR2 : [5, 4]
BAR3 : [2, 1]
step -> 28
BAR1 : []
BAR2 : [5, 4, 3]
BAR3 : [2, 1]
step -> 29
BAR1 : [1]
BAR2 : [5, 4, 3]
BAR3 : [2]
step -> 30
BAR1 : [1]
BAR2 : [5, 4, 3, 2]
BAR3 : []
step -> 31
BAR1 : []
BAR2 : [5, 4, 3, 2, 1]
BAR3 : []