再帰的アルゴリズム - ハノイの塔

ハノイの塔は1883年にフランスのＥ．Lucas（リュカ）が考案したゲームと言われています。著書『数学遊戯』の中にあるそうです。 これは次のようなゲームです。 台の上に３本の棒A，B，Cが固定されていて，そのうちの一本に何枚かの円盤が棒を通して重ねられています。円盤は下へいくほど半径が大きくなっています。 このとき，次の規則に従って，円盤をＡからBに移動してください。 一回に一枚の円盤しか動かしてはいけません。 移動の途中で円盤の大小を逆に積んではいけません。常に大きい方の円盤が下になるようにして下さい。 棒A，B，C以外のところに円盤を置いてはいけません。 このゲームは元々手で実際にやるものですし，実際に玩具としてこのようなものがあるそうです。しかしここではこれをプログラミングの問題，即ち，解く手順をコンピュータを使って求める問題としましょう。 プログラミングの問題

[knowledgefort]

ハノイの塔

[kiyo_hiko]

1動作3stepで考えるという話　「dec(X, Y) :- Y is X - 1. one(A, B) :- write(A), write(' -> '), write(B), nl. all(0, _, _, _) :- !. all(N, A, B, C) :- dec(N, M), all(M, A, C, B), one(A, B), all(M, C, B, A). hanoi(N) :- all(N, 'left ', center, 'right ').」

[takuma510]

hanoi

[fumokmm]

ハノイの塔のアルゴリズム解説と解法。