ハノイの塔

質問

★自分が理解している事
「(n-1)ハノイが解けると仮定するとnハノイも解けること」
は理解できます。
そして数学的帰納法によりすべての自然数についてハノイは「解ける」
ここまではわかります。

★わからないのは、その「解き方」です。
「解ける」ことはわかるのですが「解き方」がわからないのです。
何故このプログラムで正解が表示されるのかが理解できないのです。
確かに、紙と鉛筆でプログラムの流れを追っていくと解けています。
しかし、何でこのプログラムで解けるのかがわからないのです。

棒ｘは出発点
棒ｙは目的地
棒ｚは作業棒

です。
(n-1)ハノイをひとかたまりと考え、作業棒Zに移す。
nハノイを目的地Yに移す。
(n-1)ハノイをひとかたまりと考え、目的地Yに移す。

そんな説明で確かに納得した気になりはします。
しかしこのプログラムでは(n-2)以下の場合についてはいっさい語っていません。
何かだまされてる気がします。

このプログラムでは(n-1)について語っていますが
(n-2)以下については全く語っていません。

数学的帰納法により「解ける」ことは証明済みですが、
「その解き方」がこのプログラムでよいという「証明」はありますでしょうか？

理解のコツはありますでしょうか？
よろしくお願いいたします。

#include<stdio.h>
#include<stdlib.h>

void hanoi(int n, char x, char y, char z)
{
if(n==0)
{/*　何もしない　*/}

else
{
hanoi(n-1,x,z,y);
printf("%c->%c,",x,y);
hanoi(n-1,z,y,x);
}
}

int main(void)
{
int num;
scanf("%d",&num);
hanoi(num,'A','B','C');

return 0;
}

回答No.2

fonera · ベストアンサー

恐れ入ります。
「(n-1)ハノイが解けると仮定すると、nハノイも解ける」が正しい場合、
「nハノイが解けると仮定すると、(n-1)ハノイも解ける」が正しいというのは理解されていますか？

「3ハノイが解けるときには、4ハノイが解ける」のが正しいときには常に
「4ハノイが解けるときには、3ハノイが解ける」は正しくなります。
# 判りづらければ、自然数の1からスタートしていると考えてみて下さい。

hanoi(3,'A','B','C');でスタートすると
　hanoi(n-1,x,z,y);→hanoi(2, 'A', 'C', 'B')
　printf("%c->%c,",x,y);→printf("A→C")
　hanoi(n-1,z,y,x);→hanoi(2, 'C', 'B', 'A')
となるのまでは理解されていると思います。

あとは、これを再帰（自分自身を呼び出す）していくだけです
hanoi(3,'A','B','C');でスタートすると
　hanoi(n-1,x,z,y);→hanoi(2, 'A', 'C', 'B')
　　hanoi(n-1,x,z,y);→hanoi(1, 'A', 'B', 'C')
　　　hanoi(n-1,x,z,y);→hanoi(0, 'A', 'C', 'B')
　　　printf("%c->%c,",x,y);→printf("A→B")
　　　hanoi(n-1,z,y,x);→hanoi(0, 'C', 'B', 'A')
　　printf("%c->%c,",x,y);→printf("A→C")
　　hanoi(n-1,z,y,x);→hanoi(1, 'B', 'C', 'A')
　　　hanoi(n-1,x,z,y);→hanoi(0, 'B', 'A', 'C')
　　　printf("%c->%c,",x,y);→printf("B→C")
　　　hanoi(n-1,z,y,x);→hanoi(0, 'A', 'C', 'B')
　printf("%c->%c,",x,y);→printf("A→B")
　hanoi(n-1,z,y,x);→hanoi(2, 'C', 'B', 'A')
　　hanoi(n-1,x,z,y);→hanoi(1, 'C', 'A', 'B')
　　　hanoi(n-1,x,z,y);→hanoi(0, 'C', 'B', 'A')
　　　printf("%c->%c,",x,y);→printf("C→A")
　　　hanoi(n-1,z,y,x);→hanoi(0, 'B', 'A', 'C')
　　printf("%c->%c,",x,y);→printf("C→B")
　　hanoi(n-1,z,y,x);→hanoi(1, 'A', 'B', 'C')
　　　hanoi(n-1,x,z,y);→hanoi(0, 'A', 'C', 'B')
　　　printf("%c->%c,",x,y);→printf("A→B")
　　　hanoi(n-1,z,y,x);→hanoi(0, 'C', 'B', 'A')

0ハノイは解ける→1ハノイは解ける→2ハノイは解ける→・・・→nハノイは解けるをやっているだけです。
nから逆に下って行ってるだけですね。

お礼

＞「(n-1)ハノイが解けると仮定すると、nハノイも解ける」が正しい場合、
＞「nハノイが解けると仮定すると、(n-1)ハノイも解ける」が正しいというのは理解されていますか？

はい。というか、すべての自然数nにおいてハノイは解けることが
証明済みですので(n-1)ハノイも解けるのは当たり前です。
僕が知りたいのは
hanoi(n-1,x,z,y);
hanoi(n-1,z,y,x);
この引数の変え方で正解をだせることの証明がほしいのです。
確かに、n=4ぐらいで紙と鉛筆でやってみると確かに正解は出ます。
しかし、n=100でもこの引数の変え方でよいのはどこで担保されているのか、その証明がほしいのです。

回答No.5

Oh-Orange

★アドバイス
・n=3、n=4のハノイが理解出来ているとすると
　n=4は上に3枚、下には4枚目があることになる。
　この状態で4枚目を移動しないと考えると上の3枚までは
　ハノイの移動があなたでも正しく移動できることを証明できますよね。
・なら上の3枚が移動した状態で4枚目を移動するには
　4枚目を3枚ある以外の残りの場所に移動します。
　その後に3枚のハノイ移動を行うとn=4のハノイ移動が完了します。
・移動回数を列挙すると
　n=3…7回
　n=4…15回
　n=5…31回
　n=6…63回
　n=7…127回
　n=8…255回
　n=9…511回
　n=10…1,023回
　：
　n=20…1,048,575回
　：
　n=30…1,073,741,823回
　：
　n=50…1,125,899,906,842,623回
　：
　n=100…1,267,650,600,228,229,401,496,703,205,375回
　となります。
　ここでnの数と回数に規則的な法則があります。分かりますか？
　『回数』＝『(2のn乗)から1引く』
　このような関係があるのです。
・だから
　n=10のハノイ移動を考えるときは上に9枚、下に10枚目
　n=9のハノイ移動を考えるときは上に8枚、下に9枚目
　n=8のハノイ移動を考えるときは上に7枚、下に8枚目
　n=7のハノイ移動を考えるときは上に6枚、下に7枚目
　n=6のハノイ移動を考えるときは上に5枚、下に6枚目
　n=5のハノイ移動を考えるときは上に4枚、下に5枚目
　n=4のハノイ移動を考えるときは上に3枚、下に4枚目
　n=3のハノイ移動を考えるときは上に2枚、下に3枚目
　n=2のハノイ移動を考えるときは上に1枚、下に2枚目
　と考えていけばよいので
＞hanoi(n-1,x,z,y);
＞hanoi(n-1,z,y,x);
＞この引数の変え方で正解をだせることの証明がほしいのです。
　この引数の変え方だけで正解を出せることになるのです。
　上記の考えこそが『証明』なのです。

※本当は図形で考えれば分かりやすいんですよ。
※書くよりも。直感で分かるから。

参考にして下さい。

回答No.4

asuncion

> 「解ける」ことが証明済みであることと
> 「解き方」がわかることは全く別なのですが。

解き方がわかるかわからないかは、その人の理解力の話ですね。

お礼

いや、ですから、
hanoi(n-1,x,z,y);
hanoi(n-1,z,y,x);
この引数の変え方で正解をだせることの証明がほしいのです。
あなたはせいぜいn=4ぐらいで満足しているのではないのですか？
それともすべての自然数nにおいて、この引数の入れ替え方でOKであることの
証明を持っているのでしょうか？
n=4か5ぐらいで満足することに何の価値もありません。
一般的、つまり∀nについて成り立つ証明にこそ、価値があるのです。
ハノイに関しては5冊ぐらい読みました。
しかし∀nに関しての証明が書いてある本は皆無でした。
そして私には理解力がない、だから質問をさせていただいているのです。

補足

ちなみに私は6回ぐらい「やっと理解できた」という感覚にいたりました。
しかし、数日後、「いや、やはり理解できていない」
「このプログラムで正解が出るのはたまたまなのではないか？」
「偶然なのではないか？必然性はあるのだろうか？」
と思ってしまうのです。
「これを理解するには証明が無ければダメだ」
そう思っているのです。

回答No.3

asuncion

> すべての自然数nにおいてハノイは解けることが
> 証明済みですので(n-1)ハノイも解けるのは当たり前です。

これがおわかりなのでしたら、nがいくらであってもOKですよね。

お礼

「解ける」ことが証明済みであることと
「解き方」がわかることは全く別なのですが。

回答No.1

php504

再帰関数なので最初の呼び出しから見たら関数が呼ばれるたびに
hanoi(n - 1, )
hanoi(n - 2, )
.
.
.
hanoi(1, )
hanoi(0, )
となります。