ハノイの塔

ハノイの塔は、再帰の問題で頻繁に取り上げられる問題である。 ハノイの塔の問題とは、次のようなものである。 「3本の棒a, b, cがあり、中央に穴の空いたn枚の円盤が、最初は下の方が大きい順に棒aに 積まれている。この円盤を、棒bに移動させる。ただし、 移動の途中で円盤の大小関係が逆転してはならない。また、 棒cは作業用として使用してもよいが、そこでも円盤の大小関係を逆転させてはならない。」 という問題である。

Figure 8.2: ハノイの塔

例えば、円盤の数が2枚の場合には、図8.3のような手順になる。

Figure 8.3: ハノイの塔：2枚の場合の移動の仕方

また、円盤の数が3枚の場合には、次のような手順になる。

1番の円盤をaからbへ移動

2番の円盤をaからcへ移動

1番の円盤をbからcへ移動

3番の円盤をaからbへ移動

1番の円盤をcからaへ移動

2番の円盤をcからbへ移動

1番の円盤をaからbへ移動

上記の手順をヒントに、円盤の数がnの場合の一般的な解を求めることを考える。 一般解を求める上で、問題を図8.4のように分解して考える。 n枚すべての円盤をaからbへ移動するためには、 (n-1)枚をaからcへ何らかの手順で移動し、 次にn番目をaからbへ移動し、最後に(n-1)枚をcからbへ何らかの手順で移動する。

Figure 8.4: ハノイの塔の求解のための移動イメージ

この分解により、再帰呼び出しとして実装する方法が明らかになった。 具体的には、次のように実装すればよい。

void hanoi(int n, char a, char b, char c){

/* n : 円盤の数 */

/* a : 移動元の棒の名称, b : 移動先の棒の名称, c : 作業用の棒の名称 */

if( n > 0 ){

hanoi(n-1, a, c, b);

printf(”%d 番の円盤を %c から %cへ移動 \n”, n, a, b);

hanoi(n-1, c, b, a);

}

}

4枚の場合の移動のさせ方を以下に示す。

実行結果

1 番の円盤を a から c へ移動

2 番の円盤を a から b へ移動

1 番の円盤を c から b へ移動

3 番の円盤を a から c へ移動

1 番の円盤を b から a へ移動

2 番の円盤を b から c へ移動

1 番の円盤を a から c へ移動

4 番の円盤を a から b へ移動

1 番の円盤を c から b へ移動

2 番の円盤を c から a へ移動

1 番の円盤を b から a へ移動

3 番の円盤を c から b へ移動

1 番の円盤を a から c へ移動

2 番の円盤を a から b へ移動

1 番の円盤を c から b へ移動