ハノイの塔
Pythonでハノイの塔を解くプログラムを書きました。
GUIの表示にはmatplotlibの棒グラフを使いました。
import numpy as np import matplotlib.pyplot as plt import matplotlib.animation as animation def plot(): plt.cla() plt.xlim(-0.5,2.5) plt.ylim(0,N) left = np.array([0,1,2]) numl = [0,0,0] plt.bar(left,lis[N-1],color="0.0",linewidth = 0.5) numl = lis[N-1] for i in (reversed(range(N-1))): plt.bar(left,lis[i],bottom=numl,color=str(0.95-0.95*(i/N)),linewidth = 1) numl = lisum(numl,lis[i]) plt.pause(0.3) def hanoi(num,fro,des,wor): if num == 1: move(1,des) plot() else: hanoi(num-1,fro,wor,des) move(num,des) plot() hanoi(num-1,wor,des,fro) def move(n,tar): s = [0,0,0] s[tar] = 1 lis[n-1] = s def lisum(a,b): s = [] for i in range(len(a)): s.append(a[i]+b[i]) return s fig = plt.figure() N = int(input()) lis = [] for i in range(N): lis.append([1,0,0]) plot() hanoi(N,0,2,1)
def hanoi(num,fro,des,wor): if num == 1: move(1,des) plot() else: hanoi(num-1,fro,wor,des) move(num,des) plot() hanoi(num-1,wor,des,fro)
def hanoi(int,int,int,int)は、
num...解くハノイの塔のディスクの数
fro...棒の番号を左から0,1,2と振ったときのディスクがnum個ある開始位置の番号
des...num個のディスクを移動させたい棒の番号
wor...操作において利用可能な棒の番号
move(n,des)関数は、n番目のディスク、(小さい方から1..nとしています)をdesに移動させる操作です。
手続きを見ていきます。
基底: num = 1のとき
ディスクが一つのみなので、1のディスクをdesに移動させて終わりです。
帰納: num = nのとき
まずnum-1までのディスクを操作において利用可能な棒、worにすべて移動させます。これは、hanoi(num-1,fro,wor,des)で可能です。
次に、動かせるようになったnum番目のディスクをdesに移動させます。これはmoveの一手で可能です。
最後に、desに移動したnum番目のディスクの上にworに乗っているnum-1個のディスクをのせて終わりです。これはhanoi(num-1,wor,des,fro)で可能です。