2010年03月11日

【非再帰】ハノイの塔を解くプログラム


ちなみにiPhoneでもハノイの塔を題材とした「Hanoi」というゲームが出てます




ハノイの塔とは



大きさの違う円盤が積まれて塔になっていて



小さい円盤の上にそれより大きい円盤を置けないというルールのもとで



最初にあった円盤の塔を別の位置に再現するものです(説明下手でごめんなさい



これは計算機的に再帰的な解法プログラムが書けることで有名らしいですがなかなか頭がこんがらがって思いつかねぇ!



再帰的に考えるのって難しいですよね・・・授業でやったLispも苦手だった




ということで今回はとりあえず再帰的じゃない解き方を実装



hanoi.py

n=input('how many disks do you have?\n')

a=[[],[],[]]

def sethanoi(n):
for i in xrange(n):
a[0].append(i)

print a



def hanoi(n):
while True:
zero_position=0

for i in xrange(3):
if a[i].count(0)>0:
a[i].remove(0)
if i==2:
a[0].insert(0,0)
zero_position=0
break
else:
a[i+1].insert(0,0)
zero_position=i+1
break

print a

if len(a[1])==n or len(a[2])==n:
break

minmum=n+1
min_position=0

for i in xrange(3):
if i!=zero_position:
try:
if min(a[i])
minmum=min(a[i])
min_position=i
except ValueError:
pass


a[min_position].remove(minmum)

for i in xrange(3):
if i!=min_position:
if i!=zero_position:
a[i].insert(0,minmum)

print a


sethanoi(n)
hanoi(n)

↑wordpressのsyntaxhighlighterを導入してコード表示してみました


javascriptを使ってるのでRSSリーダーで見たら意味ないけど

実行結果(数値は円盤の大きさと思っていただければ)
$ python hanoi.py
how many disks do you have?
4
[[0, 1, 2, 3], [], []]
[[1, 2, 3], [0], []]
[[2, 3], [0], [1]]
[[2, 3], [], [0, 1]]
[[3], [2], [0, 1]]
[[0, 3], [2], [1]]
[[0, 3], [1, 2], []]
[[3], [0, 1, 2], []]
[[], [0, 1, 2], [3]]
[[], [1, 2], [0, 3]]
[[1], [2], [0, 3]]
[[0, 1], [2], [3]]
[[0, 1], [], [2, 3]]
[[1], [0], [2, 3]]
[[], [0], [1, 2, 3]]
[[], [], [0, 1, 2, 3]]




汚いコードですいません



プログラミングって条件分岐と配列くらいできていればある程度簡単な問題だったら解けてしまうため



便利なライブラリ関数とかそういうものを新たに学ぶ機会がなかなか無い



結果、少ない知識で実装しようとするため力技になって汚いコードになってしまう



俺の場合は場当たりコーディングに近い



是非、Python詳しい方がいましたらここはこうしたほうがいいんじゃないかとかコメント頂けるとありがたいです




上のコードの解き方なんですが、実際に手を動かしてみるとパターンが見つかるのでそのパターンを実装した感じです





一番小さな円盤を右へ一つ動かす(一番右の位置から動かす場合は一番左へ



動かせる円盤の中で一番小さな円盤の次に小さな円盤を動かす(一番小さな円盤がどこかにあってそこには動かせないので動かす先は一つしかない



一番小さな円盤を右へ....





これを繰り返すだけで解ける



冒頭に紹介したゲームもこれを使ったら解けてしまうわけです




「再帰的」と友達になりたい






この記事へのコメント

name:

mail:

HP:

comment:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバックURL
http://blog.seesaa.jp/tb/143309692

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。