![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
★自分が理解している事
「(n-1)ハノイが解けると仮定するとnハノイも解けること」
は理解できます。
そして数学的帰納法によりすべての自然数についてハノイは「解ける」
ここまではわかります。
★わからないのは、その「解き方」です。
「解ける」ことはわかるのですが「解き方」がわからないのです。
何故このプログラムで正解が表示されるのかが理解できないのです。
確かに、紙と鉛筆でプログラムの流れを追っていくと解けています。
しかし、何でこのプログラムで解けるのかがわからないのです。
棒xは出発点
棒yは目的地
棒zは作業棒
です。
(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ベストアンサー
- 回答日時:
恐れ入ります。
「(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
- 回答日時:
★アドバイス
・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
- 回答日時:
> 「解ける」ことが証明済みであることと
> 「解き方」がわかることは全く別なのですが。
解き方がわかるかわからないかは、その人の理解力の話ですね。
この回答への補足
ちなみに私は6回ぐらい「やっと理解できた」という感覚にいたりました。
しかし、数日後、「いや、やはり理解できていない」
「このプログラムで正解が出るのはたまたまなのではないか?」
「偶然なのではないか?必然性はあるのだろうか?」
と思ってしまうのです。
「これを理解するには証明が無ければダメだ」
そう思っているのです。
いや、ですから、
hanoi(n-1,x,z,y);
hanoi(n-1,z,y,x);
この引数の変え方で正解をだせることの証明がほしいのです。
あなたはせいぜいn=4ぐらいで満足しているのではないのですか?
それともすべての自然数nにおいて、この引数の入れ替え方でOKであることの
証明を持っているのでしょうか?
n=4か5ぐらいで満足することに何の価値もありません。
一般的、つまり∀nについて成り立つ証明にこそ、価値があるのです。
ハノイに関しては5冊ぐらい読みました。
しかし∀nに関しての証明が書いてある本は皆無でした。
そして私には理解力がない、だから質問をさせていただいているのです。
No.1
- 回答日時:
再帰関数なので最初の呼び出しから見たら関数が呼ばれるたびに
hanoi(n - 1, )
hanoi(n - 2, )
.
.
.
hanoi(1, )
hanoi(0, )
となります。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# C言語初心者 構造体 課題について 2 2023/03/10 19:48
- C言語・C++・C# 質問です 下記のコードを分かりやすく解説お願いします 初心者です #include ‹stdio.h 3 2022/05/26 22:03
- C言語・C++・C# C言語でif文が予想と違う動きをする件について7 4 2023/03/20 00:26
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# カードシャッフルのブログラムを使ってc言語でブラックジャックをしたい 2 2022/04/12 15:13
- C言語・C++・C# C言語初心者 ポインタについて、お助けください、、 2 2023/03/15 23:50
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
パスカルの三角形についてのCプ...
-
【C言語教えてください】sin波...
-
配列データをExcelファイルとし...
-
プログラム(C言語)
-
C言語初心者です。次の問題で質...
-
%P と %X の違い
-
10進数を2進数に変換するには・...
-
複素数の四則計算
-
LU分解法のピボット選択機能実...
-
10個出力で改行したいのですが...
-
c言語でAからZまでを表示する...
-
すごろくに使用するサイコロ
-
三角形の判別
-
int型 00 を表示するのに0とな...
-
C言語 プログラミング
-
なぜgccはstdio.hをインクルー...
-
ピラミッド表示プログラム。
-
コマンドラインに出力した文字...
-
C言語に関する質問です
-
コンパイルエラーについて
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
10個出力で改行したいのですが...
-
printf で二進表示を行いたい。
-
【C言語教えてください】sin波...
-
strcmp
-
コンパイルエラーについて
-
c言語でAからZまでを表示する...
-
コマンドラインに出力した文字...
-
cshの文字列操作(0埋め)
-
4の倍数を論理演算で表す。。
-
C言語 プログラミング
-
%P と %X の違い
-
8人分のテストの点数を入力し、...
-
C言語での、年複利の計算方法...
-
printf( " %2d", p * q );
-
hit&bolwのプログラミングがで...
-
scanfに文字が入力されたときに...
-
error C2143: 構文エラー : ';'...
-
printfの出力内の文字をdefine...
-
テキストカーソル位置の取得
-
unsigned int型について
おすすめ情報