解きながら学ぶC言語の問題8-9のハノイの塔のプログラムについです。ソースコードは
#include<stdio.h>
#define N 3
void move(int no,int x,int y)
{
if(no>1)
move(no-1,x,6-x-y);
printf("%dを%d軸から%d軸へ移動\n",no,x,y);
if(no>1)
move(no-1,6-x-y,y);
}
int main(void)
{
move(N,1,3);
return 0;
}
==============================
実行結果
1を1軸から3軸へ移動
2を1軸から2軸へ移動
1を3軸から2軸へ移動
3を1軸から3軸へ移動
1を2軸から1軸へ移動
2を2軸から3軸へ移動
1を1軸から3軸へ移動
==============================
最近大学の講義でこのプログラムの実行の流れを習ったのですが、どうにもよく理解することができません。
まず、move(no,x,y)にはそれぞれno=3,x=1,y=3の数が入っていますよね。
そして、no>1なので、move(no-1,6-x-y,y)の式に代入してmove(3-1,1,6-1-3)となるとno=2,x=1,y=2となるのでmove(2-1,1,6-1-2)となるのでこのときno=1,x=1,y=3。
この時点でno>1ではなくなりprintf関数によって、1を1軸から3軸へ移動、2を1軸から2軸へ移動と表示されると言うことだと思っているのですが。
ここから先がさっぱりです、なぜ1を3軸から2軸へ移動となるのでしょうか?
一つもどってno=2,x=1,y=2のときmove(no-1,6-x-y,y)の式に代入されるということなのでしょうか?
どうして急にmove(no-1,x,6-x-y)の式で計算していたものがmove(no-1,6-x-y,y)の式で計算するようになるのか、がわかりません。
どちらも条件分岐はif(no>1)ですし、このif文が何のためにあるのかもよくわからないのです。
自分でも書いていて要点がはっきりしませんが、どなたかお願いいたします。
No.1
- 回答日時:
こんばんは。
ハノイの塔を攻略せよ!
http://www13.plala.or.jp/kymats/study/C++/Hanoi/ …
状態を「イメージする」が重要ではないかと。
あと、ハノイの塔のルールを確認することですね。
このページの説明でなんとかなりませんかね。
御回答ありがとうございます。
確かに、リンク先では図がふんだんに使われていてイメージがつかみやすそうですね…。
参考にしたいと思います。ありがとうございました。
No.3ベストアンサー
- 回答日時:
move(no, x, y)の動作を言葉で書くと「x軸(以下from軸)にあるno枚の円盤を、y軸(以下to軸)へ移動させる」となります。
関数の中の、「6-x-y」というのは、from軸でも、to軸でもない残りのもう一つの軸(以下other軸)番号を示します。move関数の動作を説明すると以下の様になります。
まず、from軸にあるno枚の円盤を、「一番下の円盤」と「一番下を除く円盤の残りの円盤グループ」の2つに分けて考えます。そしてその2つに対して、動作は以下の3項目を順番に実行します。
1.if(no>1) move(no-1,x,6-x-y);
「一番下を除く円盤の残りの円盤グループ」をfrom軸から、other軸へ移動(move関数を再帰呼び出しして対応)
2.printf("%dを%d軸から%d軸へ移動\n",no,x,y);
"「一番下の円盤」をfrom軸から、to軸へ移動"を表示
3.if(no>1) move(no-1,6-x-y,y);
「一番下を除く円盤の残りの円盤グループ」をother軸から、to軸へ移動(move関数を再帰呼び出しして対応)
1と3に該当する部分で「if(no>1)」とあるのは、no=1(from軸の円盤が1枚)の場合は「一番下の円盤」のみ存在して「一番下を除く円盤の残りの円盤グループ」が無いので1と3を実行する必要が無いためです。
実際のプログラムでmainで呼ばれたmove(3, 1, 3) 「1軸の3枚の円盤を1軸から3軸へ移動」の動作を書くと以下の様になります。move関数の再帰呼び出し部分は、段付けをしました。段の深さが同じ部分が同じmove関数の動作を示しています。
頭の数字は前記move関数の動作の項目番号を示しています。
例えば「1-1」は、
「move(3, 1, 3)の1項目で呼び出されたmove関数の、更に1項目で呼び出されたmove関数」となります。
move(3, 1, 3) 「1軸の3枚の円盤を1軸から3軸へ移動」
1. move(2, 1, 2)…「1軸の上2枚の円盤を1軸から2軸へ移動」
1-1. move(1, 1, 3)…「1軸の上1枚の円盤を1軸から2軸へ移動」
no=1なので再帰呼び出しはしません
1-1-2. print "1を1(from)軸から3(to)軸へ移動"
1-2. print "2を1(from)軸から2(to)軸へ移動"
1-3. move(1, 3, 2)…「1軸の上1枚の円盤を3軸から1軸へ移動」
no=1なので再帰呼び出しはしません
1-3-2. print "1を3(from)軸から2(to)軸へ移動"
2. print "3を1(from)軸から3(to)軸へ移動"
3. move(2, 2, 3)…「2軸の上2枚の円盤を2軸から3軸へ移動」
3-1. move(1, 2, 1)…「1軸の上1枚の円盤を2軸から1軸へ移動」
no=1なので再帰呼び出しはしません
3-1-2. print "1を2(from)軸から1(to)軸へ移動"
3-2. print "2を2(from)軸から3(to)軸へ移動"
3-3. move(1, 1, 3)…「1軸の上1枚の円盤を1軸から3軸へ移動」
no=1なので再帰呼び出しはしません
3-3-2. print "1を1(from)軸から3(to)軸へ移動"
move(3, 1, 3)は以上のような動作をしますので、上から順番にprintの行を拾い出せば実行結果と同じになるはずです。
ちょっと、ごちゃごちゃしましたがご理解の一助になれば幸いです。
返事が遅れて申し訳ありません。
大変ご親切のお答えいただいてありがとうございます。
まさに求めていた答えでした。
どうにも試験に出そうだったので心配だったのですが、おかげさまで理解することができました。
有難うございました。
No.4
- 回答日時:
引数をもう一つ増やした、こういうプログラムの方がわかりやすい気はしますが。
#include <iostream>
void move(int from, int to)
{
std::cout << "move a disk from " << from << " to " << to << "\n";
}
void hanoi(int n, int a, int b, int c)
{ // n 枚の円盤を a から b に移動する。ワークとして、c を使う
if (n > 0)
{
hanoi(n - 1, a, c, b); // n - 1 枚を、b をワークにして、c に運んで、
move(a, b); // 最後の1枚を b に運んで、
hanoi(n - 1, c, b, a); // c に運んだ n - 1 枚を a をワークに、b に移動
}
}
int main()
{
hanoi(3, 1, 3, 2);
return 0;
}
No1. で引用されている、http://www13.plala.or.jp/kymats/study/C++/Hanoi/ … もこの形からスタートしています。
いずれにしても、再帰呼び出しを使う場合、流れを追いかけるとわからなくなるケースが多いです。
少なくとも、なぜ再起を使うとありがたいのかという御利益がわからなくなるケースは多いです。
この場合、ハノイの塔を解くアルゴリズムがあったとすると、n段の円盤をある軸からある軸へと動かすことはできるわけです。
だったら、n - 1 段の円盤を動かすこともできます。
それなら、
・(既にあるはずのアルゴリズムで)n - 1 枚の円盤を、目的ではない軸に動かして、
・最後の円盤を目的の軸において、
・目的でない軸にある n - 1 枚の円盤を、目的の軸に(既にあるはずのアルゴリズムで)もどす。
と考えればできるわけです。
じゃ、具体的にはどう動かせば良いの? というのを見かけ上考えずに「そのアルゴリズムは既にあるもの」という前提で問題が解決できてしまうと言うのが、再帰呼び出しの御利益です。
で、あきらかに、冒頭の処理の方が考えやすいかなと思いますが。
例題のソースについて言えば、少なくとも、6 - x - y はやめてほしいなと思います。
せめて、x でも y でもない軸 というコメントはほしいかなと。
御回答ありがとうございます。
別の考え方を示していただきありがとうございました。
どうにも自分は再帰呼び出しと言うものを分かっていないようですね…。参考にさせていただきます。
有難うございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) 物理の斜方投射で目盛りに数値を入れたい 2 2023/05/27 06:32
- 数学 【 数1 二次関数 グラフの平行移動 】 写真では、x軸方向にp、y軸方向にqだけ平行移動したグラフ 3 2022/06/19 08:34
- 数学 【 数I 2次関数の対称移動 】 問題 ※写真 疑問 放物線y=2x²+xをy軸に関して対称移動 す 3 2022/07/02 23:28
- その他(プログラミング・Web制作) 物理の斜方投射の目盛り線とx軸、y軸の追加について 3 2023/05/26 21:11
- 数学 数学 x軸に関して対称に移動した放物線の式は x軸に関して対称に移動された放物線の式のyに−をつけて 1 2022/07/14 21:03
- 数学 【 数I 対称移動 】 問題 直線y=-x+1をx軸、y軸、原点に関して それぞれ対称移動して得られ 2 2022/07/02 19:54
- 哲学 ウソの問題 理論編:《虚数人間》の成り立ちについて 2 2022/05/23 22:25
- 数学 写真の問題の(2)の解IIについてですが、 なぜ「x+y≦1(x≧0,y≧0)の部分とそれをx軸,y 2 2023/08/04 17:02
- Excel(エクセル) 【Excel:条件付き書式 データバー】 正負の軸の位置を変更する方法を教えてください 3 2023/01/08 19:41
- 物理学 ミンコフスキー時空図の作図の仕方について 2 2023/04/30 10:01
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
Excel VBAで、グラフを特定のセ...
-
matplotlib
-
【VBA】Excel等高線グラフの...
-
Excel VBA グラフ ChartType に...
-
Excelのグラフ機能で横軸xに時...
-
C言語によるハノイの塔のプログ...
-
Excel VBAでグラフをクリックし...
-
C#のChartで目盛線をグラフの前...
-
Matlabによる複素数・・・
-
VBA グラフの存在の判定について
-
論文に載せるグラフを作成したい
-
onedriveで同期解除をしたら、...
-
共有しているファイルを削除し...
-
vlan internal allocation poli...
-
YAHAMA RTXシリーズのコマンド...
-
TXTファイルを上書き保存する前...
-
teratarmでコマンド入力すると...
-
沢山のフォルダにあるファイル...
-
マイドキュメントのフォルダの...
-
読み取り専用ファイルを上書き...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VBA グラフの存在の判定について
-
論文に載せるグラフを作成したい
-
【VBA】Excel等高線グラフの...
-
グラフの元のデータを消しても...
-
excelのグラフをLaTexに挿入す...
-
Excel VBAでグラフをクリックし...
-
Excel VBAで、グラフを特定のセ...
-
グラフを「似ている」順に並べ...
-
Excel VBA グラフ ChartType に...
-
MFCプログラミング
-
c言語 正負の値それぞれでの最...
-
グラフの色を数値で変わるように!
-
C#のChartで目盛線をグラフの前...
-
Excel VBAでグラフ作成。A,C列...
-
excelで散布図に線を追加したい
-
matlabのy軸を2つ利用したグラ...
-
Google Chart APIでランキング表示
-
gnuplotで関数を途切れさせるに...
-
Scilabのグラフの凡例
-
C言語によるハノイの塔のプログ...
おすすめ情報