#Pythonで学ぶアルゴリズム< ハノイの塔 >
はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第13弾としてハノイの塔を扱う．
ハノイの塔
ハノイの塔はよく知られている．以下にそのルールを示す．
・端から端へ同じ形で移動させることで完成
・自分よりも小さなものの上に移動することはできない
実装
ここでは，3本の軸間を移動し，扱うブロック数のみ入力することで，そのときの移動手順を示すプログラムを以下に示す．さらに可視化まで試みようとしたが，アルゴリズムを知るという意味での本質とは少しずれているため，試みた部分のみ示すこととする．
コード
hanoi.py
"""
2020/12/31
@Yuya Shimizu
ハノイの塔
"""
#引数：ブロック数，移動元，移動先，経由
def hanoi(n, source, destination, via):
if n > 1:
hanoi(n-1, source, via, destination) #再帰
print(source + '->' + destination)
hanoi(n-1, via, destination, source) #再帰
else:
print(source + '->' + destination)
n = int(input('ハノイの段数 >> '))
hanoi(n, 'a', 'c', 'b')
出力
ハノイの段数 >> 3 #3と入力
a->c
a->b
c->b
a->c
b->a
b->c
a->c
コード
hanoi_v.py
"""
2020/12/31
@Yuya Shimizu
ハノイの塔（可視化）
"""
def tower(n):
result = ""
for i in range(1,n+1):
#偶数行
if i %2 == 0:
result += f"| {' '*(n-i+1)}{'- '*(i//2)}{'- '*(i//2)}\t| "
result += f"{' '*(n-i+1)}{'- '*(i//2)}{'- '*(i//2)}\t|"
result += f" {' '*(n-i+1)}{'- '*(i//2)}{'- '*(i//2)}\t| "
#奇数行
else:
result += f"| {' '*(n-i+1)}{'- '*(i//2)}- {'- '*(i//2)}\t| "
result += f"{' '*(n-i+1)}{'- '*(i//2)}- {'- '*(i//2)}\t|"
result += f" {' '*(n-i+1)}{'- '*(i//2)}- {'- '*(i//2)}\t| "
result += "\n"
return result
#引数：ブロック数，移動元，移動先，経由
def hanoi(n, source, destination, via):
if n > 1:
hanoi(n-1, source, via, destination) #再帰
print(source + '->' + destination)
hanoi(n-1, via, destination, source) #再帰
else:
print(source + '->' + destination)
#n = int(input('ハノイの段数 >> '))
#hanoi(n, 'a', 'c', 'b')
print(tower(4))
出力
| - | - | - |
| - - | - - | - - |
| - - - | - - - | - - - |
| - - - - | - - - - | - - - - |
とりあえず，すべて並べた図だけ作ってみた．また気が向いたらやってみようと思う．
なお，コメント欄にて@shiracamusにより，可視化のプログラムが紹介されている．
感想
ハノイの塔を解くアルゴリズムを知った，この時にかかる処理時間が指数関数的に増加することを知った．可視化までできると思ったが，それなりに時間が必要だということに気づき，アルゴリズムを学ぶという観点では少しずれていると思い，また気が向いたときに可視化に試みようと思う．ほかの人の記事を参考にすると，どうやら可視化までするモジュールもpythonにはあるらしく，以下のような操作で可視化というか既存のハノイの塔のプログラムが扱えるようだ．
$ pip install k-peg-hanoi
$ hanoi 4 4
自作プログラムでの可視化についてはコメント欄にて@shiracamusにより紹介されている．
参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社