★自分が理解している事
「(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で質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
strcmp
-
UnixでC言語を学習中(初心者で...
-
printf で二進表示を行いたい。
-
摂氏の値を計算するプログラム...
-
C言語での、年複利の計算方法...
-
c言語でAからZまでを表示する...
-
三角形の判別
-
c言語で2000年以降カレンダーを...
-
【C言語教えてください】sin波...
-
関数をこえてプログラムを強制...
-
球の体積と表面積を表示するプ...
-
コマンドラインに出力した文字...
-
二つの整数値の大小比較
-
改行について 1行に何個かづ...
-
16bitのパラレル送信がうまくい...
-
C++でfprintfやprintf,fopenな...
-
printf( " %2d", p * q );
-
2の累乗を計算するプログラム...
-
5×5の転置行列を求めるC言語の...
-
解説お願いします。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
コンパイルエラーについて
-
printf で二進表示を行いたい。
-
c言語でAからZまでを表示する...
-
テキストカーソル位置の取得
-
4の倍数を論理演算で表す。。
-
cshの文字列操作(0埋め)
-
【C言語教えてください】sin波...
-
10個出力で改行したいのですが...
-
wsprintfの書式制御文字列につ...
-
error C2143: 構文エラー : ';'...
-
printfの出力内の文字をdefine...
-
%P と %X の違い
-
C言語
-
strcmp
-
(C言語)めちゃくちゃな値にな...
-
コマンドラインに出力した文字...
-
スレッドとメッセージキューに...
-
printf( " %2d", p * q );
-
Visual Sutdio 2017 でのC言語...
-
defineで定数が置き換えられな...
おすすめ情報