ハノイの塔についての質問

Question

ハノイの塔でn枚の円盤の移動手順を比較的短く出力するプログラムを下のプログラムを基にhanoimove関数の中を再帰呼び出しを使い完成させなさいという問題があるのですがどーすればいいのかわかりません。

ハノイの塔とは3つの棒あるいは杭を基に考えるのですが、移動前の塔をＡ，移動先の塔をＢ，残りの塔をＣとすると，
■　ＡからＣにＮ－１枚を移動
■　ＡからＢに1枚を移動
■　ＣからＢにＮ－１枚を移動
とすることができ、A.Bの組み合わせは　　A+B+C=6
の関係が成り立ち、　C = 6-(A+B)
とすることができるからint another = 6-(before+after)と表せるのかなと思いました。

void hanoidisk( int before, int after ){
printf("杭%dから杭%dに移動\n", before, after);
}

void hanoimove( int before, int after , int num){
int another = 6-(before+after);

}

int main(void) {
int n=5;
printf("%d枚の円盤を杭1から杭3に移動させる手順は次のとおり：\n", n);
hanoimove( 1, 3, n );
return 0;
}

Comments

[cateye]

“ハノイの塔 c言語 再帰”で検索すればかなりヒットしますが？

[Japanise]

検索したのですが、私はハノイの塔は三つの杭があるため全部で6通りあり6通りをもとにプラグラムを作りたいのですがそれについてのサイトがなかったのです。ですのでお願いしたいです。

[cateye]

>全部で6通りあり6通りをもとに・・・ちょっと意味不明？
再帰だから円盤が幾つでも良いんですよね？
http://www13.plala.or.jp/kymats/study/C++/Hanoi/Hanoi.html　じゃぁ分かりませんか？

[Japanise]

ハノイの塔とは3つの棒あるいは杭を基に考えるのですが、移動前の塔をＡ，移動先の塔をＢ，残りの塔をＣとすると，

　■　ＡからＣにＮ－１枚を移動
　■　ＡからＢに1枚を移動
　■　ＣからＢにＮ－１枚を移動

とすることができ、A.Bの組み合わせは　　A+B+C=6

の関係が成り立ち、

　　C = 6-(A+B)

とすることができると思ったのですが…
http://www.algolism.iinaa.net/50/53.htm

[cateye]

最短手順→2**N-1の事を言っていますか？
---->8---->8---->8---->8---->8---->8----
usr ~/Project/test % ./a.out 3
1 を A から C へ
2 を A から B へ
1 を C から B へ
3 を A から C へ
1 を B から A へ
2 を B から C へ
1 を A から C へ
usr ~/Project/test % ./a.out 2
1 を A から B へ
2 を A から C へ
1 を B から C へ

[Japanise]

そーです！
私の説明が下手すぎて申し訳ないです。

Answer 1

3つの棒に1, 2, 3と名前をつけます。ある円盤を移動させる際、移動前の棒の名前をA, 移動後の棒の名前をB, 残りの棒の名前をCとします。(A, B, Cはすべて異なる) すると、{A, B, C}={1, 2, 3}となるので、必ずA+B+C=6が成立します。({}は順序を考えないという意味)
そうすると、C=6-A-Bが成り立ちます。例えば1から3に円盤を移動させたいとなった時、A=1, B=3なので、C=6-1-3=2となります。つまり、この式に移動前と移動後の棒の名前を与えてやれば、その残りの棒の名前がわかるというだけで、それ以上の意味はありません。
なので、棒の選び方としては3!=6通りと言われればその通りなのですが、特にこれを考えたからといって問題を解けるわけではないと思います。(再帰を使うしかない)

Comments

[rubato6809]

> 6通りと言われればその通りなのですが、特にこれを考えたからといって問題を解けるわけではない

その通りです。現にcateyeさんのコードに「C = 6-(A+B)」に相当するコードはありません。「再帰を使うしかない」のであって、その都度３つの棒をどう使いまわすかを考えれば済むことです。

Answer 2

「n-1枚を○○して、残る1枚を○○し、先程のn-1枚を○○する」

○○を埋めてみた。

#include<stdio.h>

void hanoidisk( int before, int after ){
  printf("杭%dから杭%dに移動\n", before, after);
}

void hanoimove( int before, int after , int num){
  int another = 6-(before+after); // 底板の上に重なった板を退避させる杭の番号

  // before から after へ num 枚を移動するには

  // before から another へ(底板の上に重なる)num-1 枚を移動し、
  if ( num != 1 ) hanoimove(before, another, num-1);

  // 底板を before から after へ
  hanoidisk(before, after);

  // another から after へ(退避しておいた)num-1 枚を移動する
  if ( num != 1 ) hanoimove(another, after, num-1);
}

int main(void) {
  int n=5;
  printf("%d枚の円盤を杭1から杭3に移動させる手順は次のとおり：\n", n);
  hanoimove( 1, 3, n );
  return 0;
}

Answer 3

ハノイの塔を攻略せよ！の月刊アスキーからの引用。まんまですが・・・

#include <stdio.h>
#include <stdlib.h>
//
static void Hanoi(int n, char *from, char *work, char *dest)
{
    if(n >= 1) {
        Hanoi(n - 1, from, dest, work);

        printf("%d を %s から %s へ\n", n, from, dest);

        Hanoi(n - 1, work, from, dest);
    }
}

int main(int agc, char *agv[])
{
    if(agc != 2){
        return 1;
    }
    //
    int num = (int)strtol(agv[1], 0, 10);
    Hanoi(num, "A", "B", "C");

    return 0;
}

１８枚で手元(Linux)では１秒かかります。

Comments

[Japanise]

なぜ回答に引用したものを貼ったのでしょうか？何の回答にもなっていません。

[cateye]

私は「“ハノイの塔 c言語 再帰”で検索すればかなりヒットしますが？ 」と言いました。
あなたは、それに対して『それについてのサイトがなかったのです。』と言ったので、
ヒットしたものを（テストのために一部変更して）「引用」として提示しました。
・・・で、「再帰呼び出し」↓は、解決しましたか？・・・
　“static void Hanoi(int n, char *from, char *work, char *dest)”

[Japanise]

ごめんなさい。私の勘違いでした。申し訳ないです。
6-(before+after);とはどのようにつなげれば良いでしょうか？

[dodox86]

横からすみません。今後の混乱を避けて欲しいがためのコメントなのですがが：
質問者さんは当初、cateyeさんの「“ハノイの塔 c言語 再帰”で検索すればかなりヒットします」のアドバイスに対して、検索はしたものの
> 私はハノイの塔は三つの杭があるため全部で6通りあり6通りをもとにプラグラムを作りたい
と述べられていました。で、この点、つまり6通りになることについて説明しているサイトが無かった、と言われているのだと思いました。再帰の話はとりあえず置いておいて。

ですが、質問者さんが挙げたサイトで、A+B+C=6通りを示す表がその文中で何を示そうとしているのか正直、私自身も分かりませんでしたね。
(N-1)の円盤のかたまりを1つとして、3つの棒の間をどのように配置できるか、の組み合わせかな？

質問者さんの当初の質問に回答として応えることは私にはできそうにありませんが、ハノイの塔では円盤が何枚あろうと、（N-1）の円盤を1つのかたまりとして考えると、円盤3枚の移動になぞらえることができます。それを踏まえて再帰を考えるともしかしたら少し分かりやすくなるかもしれません。いかがでしょう。で、結局再帰が必要になります。

[episteme]

>（N-1）の円盤を1つのかたまりとして考えると、円盤3枚の移動になぞらえることができます。

円盤2枚の移動。

[dodox86]

epistemeさん、ご指摘どうもありがとうございます。