C言語によるハノイの塔のプログラムの実行の流れ

質問

解きながら学ぶ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を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.3

siffon9 · ベストアンサー

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

麻野 なぎ（@AsanoNagi）

引数をもう一つ増やした、こういうプログラムの方がわかりやすい気はしますが。

#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); // 最後の１枚を 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/Hanoi.html もこの形からスタートしています。

いずれにしても、再帰呼び出しを使う場合、流れを追いかけるとわからなくなるケースが多いです。
少なくとも、なぜ再起を使うとありがたいのかという御利益がわからなくなるケースは多いです。

この場合、ハノイの塔を解くアルゴリズムがあったとすると、n段の円盤をある軸からある軸へと動かすことはできるわけです。
だったら、n - 1 段の円盤を動かすこともできます。
それなら、

・（既にあるはずのアルゴリズムで）n - 1 枚の円盤を、目的ではない軸に動かして、
・最後の円盤を目的の軸において、
・目的でない軸にある n - 1 枚の円盤を、目的の軸に（既にあるはずのアルゴリズムで）もどす。

と考えればできるわけです。
じゃ、具体的にはどう動かせば良いの？　というのを見かけ上考えずに「そのアルゴリズムは既にあるもの」という前提で問題が解決できてしまうと言うのが、再帰呼び出しの御利益です。

で、あきらかに、冒頭の処理の方が考えやすいかなと思いますが。

例題のソースについて言えば、少なくとも、6 - x - y はやめてほしいなと思います。
せめて、x でも y でもない軸　というコメントはほしいかなと。

お礼

御回答ありがとうございます。
別の考え方を示していただきありがとうございました。
どうにも自分は再帰呼び出しと言うものを分かっていないようですね…。参考にさせていただきます。
有難うございました。

回答No.2

kmee

http://okwave.jp/qa/q6791162.html
少し前に答えたものです。

お礼

御回答ありがとうございます。
なるほど、そのようなコードもあるのですか…。
参考にしたいと思います。ありがとうございました。

回答No.1

LEVELUP100

こんばんは。

ハノイの塔を攻略せよ！
http://www13.plala.or.jp/kymats/study/C++/Hanoi/Hanoi.html

　状態を「イメージする」が重要ではないかと。
　あと、ハノイの塔のルールを確認することですね。

　このページの説明でなんとかなりませんかね。

お礼

御回答ありがとうございます。
確かに、リンク先では図がふんだんに使われていてイメージがつかみやすそうですね…。
参考にしたいと思います。ありがとうございました。