3 ハノイの塔

平成17年度横浜国立大学工学部編入試験に出題された問題である。

3.1 問題

3本の棒(src, dst, work)が立っており、そのうち、左端の棒(src)に大きさの異なるn枚の円盤が、大きさの順に差し込まれている。円盤を一枚ずつ、棒から棒へ移動させ、最終的にsrcにあるn枚の円盤すべてを中心の棒(dst)に移動させるアルゴリズムを考える。ただし、各円盤は、各棒において、常により小さい円盤がより大きな円盤の上に乗るようにしか移動できず、すべての円盤が移動した結果もまた、大きさの順に積まれていなければならないとする。この制約を満たす移動手順を求めるアルゴリズムは「ハノイの塔」と呼ばれている。

**図 1:** ハノイの塔
$\includegraphics[keepaspectratio, scale=0.7]{figure/hanoi.eps}$

下記のプログラムは、「ハノイの塔」アルゴリズムをC言語で実現した例である。ここで、例えば"src->work"という出力は、srcにある一番上の円盤を、workの一番上に移動させることを意味する。また、任意のnを#define DISK_NUM nとして指定している。

   1 #include <stdio.h>
   2 #define DISK_NUM 3
   3 
   4 void hanoi(int n, char* a, char* b, char* c){
   5 
   6   if(0==n)return;
   7 
   8   hanoi(n-1, a, c, b);
   9   printf("%4s -> %4s \n", a, b);
  10   hanoi(n-1, c, b, a);
  11 }
  12 
  13 int main(){
  14   int n = DISK_NUM;
  15   hanoi(n, "src", "dst", "work");
  16   return 0;
  17 }

[問1]: 関数hanoi()中では、hanoi()が2回呼ばれている。このように、関数の中で自分自身を関数として呼び出すことを「_(a)_呼び出し」という。(a)に当てはまる言葉を答えなさい。
[問2]: このプログラムを実行すると下記の出力が得られた。(b), (c)の行に相当する結果を答えなさい。ただし、空白(スペース)は明記する必要はない。
$\fbox{\parbox[t]{40mm}{ \texttt{ src -> dst}\\ \texttt{ src -> work}\\ \rul... ...rc}\\ \rule{8mm}{0.5pt}(c)\rule{8mm}{0.5pt}\\ \texttt{ src -> dst}\\ \\ }}$
[問3]: #define disk_num 4 とした場合に、出力される行数は_(d)_行である。(d)に相当する数を答えなさい。
[問4]: 任意のnについて、初期状態からdstへ円盤がすべて移動するまでに要する hanoi()の呼び出し総数(e)と、ディスクの移動回数(f)を、それぞれn を用いてできるだけ簡潔な式で表しなさい。