ベストアンサー

ハノイの塔

2009/07/17 19:14

ハノイの塔の解き方がわかりません。解き方と理解のコツなどを教えてください。

79562
お礼率68% (164/239)

C・C++・C#
回答数5
ありがとう数2

みんなの回答 （5）
専門家の回答

質問者が選んだベストアンサー

ベストアンサー

noname#113783

2009/07/21 07:07 回答No.3

ハノイとハノイの再帰プログラムの解き方(わかりやすい)です。まずソースコード。 #include<stdio.h> void Hanoi(int n,char *from,char *work,char *dest) { if(n>=2) Hanoi(n-1,from,dest,work); printf("%d を %s から %s へ\n",n,from,dest); if(n>=2) Hanoi(n-1,work,from,dest); } void main(void) { Hanoi(4,"A","B","C"); } ↑これ実行してみてください。では説明しますね。まずハノイの塔のとき方。ルールは知ってますね？棒Ａ，Ｂ，Ｃがあるとして、Ａにある4つの輪をＣに移すとします。輪は小さい順に1,2,3,4という名前を付けます。輪全てをＣに移すには、4をＣに移せないといけません。そうするためには、4の上に輪がなく、Cの上にも何も詰まれていない状態でないといけません。つまり、4以外の輪(1,2,3)がBに乗っていないといけません。なので、”なんとかして”、輪1,2,3をＢに移します。輪1,2,3をＢに移すには、輪3を棒A(4をCに移したので空っぽ)に移さなくてはいけません。その為には”なんとかして”輪1,2を棒Aに移します。・・・ループしていますね。そして、1回目はAにある輪の1番下以外をBに移しましたが、次はBに置かれた輪の1番下以外をAに移しています。Ａに置かれている輪をＢに移したいときと、Ｂに置かれている輪をＡに移したいときは、交互に来ます(何故なんて考えないでください)。では、いつＣに移すのか？それは後で説明します。ここからソースの説明です。関数Hanoiの引数は、 int n　　　＝移したい輪の本数 char *from ＝移したい輪が乗っている棒の名前 char *work ＝輪を移すために、一番下の輪以外の輪を1時的に置いとく輪 char *dest ＝最終的に輪を移したい棒です。関数Hanoiは、指定した本数の輪を指定した棒に全て移してくれる関数なのです。これをmain関数から呼び出せば、移したい輪が移したい棒移ってくれます。ソースの説明です。 Hanoi(n-1,from,dest,work); 　ifの部分は後回しです。関数Hanoiは輪いくつかを棒へ移したいけど、一番下の輪が移したい棒に行くためには、その上の輪をworkに移さないといけません。なので、Ａ(from)にある1番下以外の棒(上からn-1本の輪)、をＢ(work)に移したいので、Ａ(from)をfromとして送り出し、Ｂ(work)をdectとして送り出します。これで、↑のHanoi関数が帰ってきた暁にはAにある1番下の棒をCに移せます。そのソースが、 printf("%d を %s から %s へ\n",n,from,dest); 　これ。これで1番下の棒が置かれていたfromからdectに移せました。nには移したい輪の最大本数が入っています。1番下の輪のナンバー＝輪の最大本数＝n。さっきのHanoi関数が1番下以外の輪を移してくれるなら、このprintfは1番下の輪を移してくれるのです。では次。 Hanoi(n-1,work,from,dest); 　さっきのHanoi関数で一番下以外の棒がfromからworkに移っているので、今度はworkをfromにして、空いたfromをworkにして移します。これを繰り返せばハノイの塔攻略完了です。あとはif文ですね。 if(n>=2) 2以下の場合は実行するな、と。もし1だった場合実行してまうと、「n(1)-1」本の棒を移せ、といっていることになってしまいます。Hanoi関数はprintfで1番下に置いてある輪を移すので、残り本数1になったらprintfがdestに1を乗せてくれます。なのでifを実行してはいけません。これで説明は終わりです。ソースコードはリンクに書いてあるものを使いました。そのサイトも分かりやすく説明してくれます。図にするなら下のような感じです。 http://mb1.net4u.org/bbs/mi-koxxx/img/3.jpg 読んでくださってありがとうございました。