ハノイの塔のプログラムがなぜ動くのかがわからない

Question

ハノイの塔を再帰で実装するプログラムを教わりましたが、なぜ、これだけのコードでハノイの塔が解けるのかがわかりません。
プログラムの動く道筋をひとつひとつ細かく教えてほしいです。
このコードがどうやって円盤の大きさや位置を考慮して円盤を動かしてるのかが知りたいです。プログラムの動きを言葉で表してほしいです。

#include<stdio.h>

void Hanoi(int n,char *from,char *work,char *dest)
{
  if(n>=2) Hanoi(n-1,from,dest,work);

  printf("%d を %s から %s へ\n",n,from,dest);

  if(n>=2) Hanoi(n-1,work,from,dest);
}

int main(void)
{
  Hanoi(4,"A","B","C");

  return 0;
}

Comments

[jimbe]

「これだけのコード」ですから道筋の説明もなにもありません。
ハノイの塔の解き方をお調べになって、 ABC がどう動くかを追ってみては如何でしょうか。

[m.ts10806]

どこから持ってきたコードなのでしょう。
事情も前提も知らない赤の他人に聞くより取得先の人に聞いたほうが確実なのでは。

[cx20]

ググっただけですが、こちらに当該コードの解説が記載されているようでした。

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

[numnum229]

コメントありがとうございます。
このコードがどうやって円盤の大きさや位置を考慮して円盤を動かしてるのかが知りたいです。

[Bull]

ハノイの塔は一旦忘れて、もっと単純な再帰関数ならば、動きを追いかけることはできますか？
例えば、次のプログラムはどうでしょうか？

#include <stdio.h>

void recursive_function(int n)
{
if (n > 0) {
printf("%d\n", n);
recursive_function(n - 1);
}
}

int main(void)
{
recursive_function(10);
}

[numnum229]

10が0になるまで引き算を続ける関数ということであってますか？

[Bull]

結果もさることながら、どのように動作しているかを理解できているかと言うことです。
動きが理解できているのであれば、すでに指摘されているように、質問のコードをデバッガーなどで、ステップ実行してみては如何でしょうか。

ハノイの塔のアルゴリズムは解説したページも多いので、それらをよく読んで、コードを追いかけていけば、やっていることは理解できるのではないかと思いますが。

[m.ts10806]

答えだけ知ったところで組めるようにはならないというところが本質ですね。
Bullさんが仰るようにもっと細分化して簡単なところから理解するように。

Answer 1

このコードがどうやって円盤の大きさや位置を考慮して円盤を動かしてるのかが知りたいです。

大きさや位置を直接的に考慮するコードを書いているのではなく、
大きさや位置が結果的に考慮されるような解き方をコードにしているという方が近いような気がします。

n=1から動作を追うのがいいかと。

Answer 2

プログラムと言うより、ハノイの塔の動かし方を理解できているかどうかの問題ですね。

高校で数学を学んでいれば数学的帰納法を知っているはずですが、
(1) 円盤が1枚の時にハノイの塔をどうやればいいわかる
(2) 円盤がN-1枚の時の動かし方がわかっている前提があれば、円盤がN枚の時のやり方もわかる
の両方が正しければ、Nが何枚でもOKということです。

(1)は自明として、
(2)は、
最初にAに積み上がったN個の塔を、Cに全部移すには、
・上からN-1枚の円盤をBに全部移す
・残ったN枚目（一番下）の円盤をCに移す
・BにあるN-1枚のの円盤をCに移す
という手順で行います。それをプログラムに書いただけです。

Comments

[numnum229]

回答ありがとうございます。
n-1枚の円盤をBに全部移す のところがわかりません。下から大きいものが積み重なるようにしてるはずですが、それがなぜこのコードで実現できるのかを教えていただきたいです。

[jimbe]

メソッド呼び出しと表示の組み合わせ方に因るものです。
例えばメソッド A からメソッド B を呼び出して B 内で "B" を表示し return、 A に戻ってから A 内で "A" を表示すれば、メソッドの実行開始順は A→B ですが表示は B→A となります。
その為、ご質問のコードでも再帰の始まりは大きな円盤からですが表示は小さな円盤からとなります。

Answer 3

// n枚の円盤をfromからwork経由でdestに移すには
void Hanoi(int n,char *from,char *work,char *dest)
{
  // 1: (最下段の1枚を除く)n-1枚をfromからdest経由でworkに移し
  if(n>=2) Hanoi(n-1,from,dest,work);

  // 2: 最下段の1枚をfromからdestに移し
  printf("%d を %s から %s へ\n",n,from,dest);

  // (1でworkに退避しておいた)n-1枚をworkからfrom経由でdestに移せばいい
  if(n>=2) Hanoi(n-1,work,from,dest);
}