再帰の定番 ハノイの塔

再帰手続きで有名なハノイの塔をPythonで解いてみました。

まずは、ハノイの塔の問題について

3本の棒a、b、cがあります。棒aに、中央に空いたn枚の円盤が大きい順に積まれています。
これを1枚ずつ移動させて棒bに移します。ただし、移動の途中で円盤の大小が逆に積まれては
いけません。また、棒cは作業用に使用するものとします。

基本操作は以下のようになります。

1. n - 1枚の円盤を始点から作業用の棒に移動させます。
2. n番目の円盤を始点から終点に移動させます。
3. nが0になるまで手順1、2を繰り返します。

これをPythonで実装すると次のようになりますね。

def hanoi(n, start, end, work):
	if n > 0:
		hanoi(n - 1, start, work, end)
		print "%d番目の円盤を%sから%sへ" % (n, start, end)
		hanoi(n - 1, work, end, start)

例：4枚の円盤を棒aから棒bに移動させます。

>>> hanoi(4, "a", "b", "c")
1番目の円盤をaからcへ
2番目の円盤をaからbへ
1番目の円盤をcからbへ
3番目の円盤をaからcへ
1番目の円盤をbからaへ
2番目の円盤をbからcへ
1番目の円盤をaからcへ
4番目の円盤をaからbへ
1番目の円盤をcからbへ
2番目の円盤をcからaへ
1番目の円盤をbからaへ
3番目の円盤をcからbへ
1番目の円盤をaからcへ
2番目の円盤をaからbへ
1番目の円盤をcからbへ

基本の動作を良く考えれば、実装はとてもシンプルですね。
ただし、棒a、bを0、1とすれば棒の総和 - (棒a + 棒b)で棒cを求めることができるので、
引数にわざわざ作業用の棒を渡さずにすっきり書けます。

total = 3
def hanoi(n, start, end):
	if n > 0:
		hanoi(n - 1, start, total - (start + end))
		print "%d番目の円盤を%sから%sへ" % (n, start, end)
		hanoi(n - 1, total - (start + end), end)

インターフェースはできる限りすっきりとさせたいですからね。。