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

Question

解きながら学ぶ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軸へ移動
",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文が何のためにあるのかもよくわからないのです。
自分でも書いていて要点がはっきりしませんが、どなたかお願いいたします。

siffon9 · Accepted Answer

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軸へ移動
",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の行を拾い出せば実行結果と同じになるはずです。

ちょっと、ごちゃごちゃしましたがご理解の一助になれば幸いです。

AsanoNagi · Answer

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

#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/ … もこの形からスタートしています。

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

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

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

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

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

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

kmee · Answer

http://oshiete.goo.ne.jp/qa/6791162.html
少し前に答えたものです。

LEVELUP100 · Answer

こんばんは。

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

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

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

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

move(no, x, y)の動作を言葉で書くと「x軸（以下from軸）にあるno枚の円盤を、y軸（以下to軸）へ移動させる」となります。

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

こんばんは。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

　こんばんは。