ハノイの塔。 - 高森太郎の日記。

　再起呼び出し、というものについて、今日やったのだが、その中でハノイの塔というものが出てきた。

「うわ〜なつかし〜」と思われる方も多いらほどの、有名な再起呼び出しのプログラムだそうである。

　再起呼び出しというのは、「プログラムが、自分の中でさらに自分を呼び出す」という処理のことで……わけわからんですよね、自分もなにがなんだかさっぱりわからないわけなんだけれど、作ったプログラムは単純。

/*再起呼び出し。ハノイの塔。*/
#include 

	int i=0;

void hanoi(int n,char a,char b,char c);
void main(void)
{
	int m;
	char a='A',b='B',c='C';

	printf("ハノイの塔。枚数を入力してください：");
	scanf("%d",&m);

	hanoi(m,a,b,c);
}

void hanoi(int n, char a, char b,char c)
{
	if(n<=0){
		return;
	}
	else {
		hanoi(n-1,a,c,b);
		printf("処理%d回目　No.%4dの円盤を%cから%cへ移動\n",++i,n,a,c);
		hanoi(n-1,b,a,c);
	}
}

たったこれだけ。が、どうなるかというと、実は自分もさっぱりわからない（ぉ

　そして

入っている場所\hanoiproglam.exe >hanoilog.txt

　とかいって、コマンドプロンプトから実行して、10、とかいって入力すると

ハノイの塔をとくプログラム。枚数を入力してください：
処理1回目　No.   1番の円盤をAからBへ移動
処理2回目　No.   2番の円盤をAからCへ移動
処理3回目　No.   1番の円盤をBからCへ移動

　中略

処理1019回目　No.   1番の円盤をCからAへ移動
処理1020回目　No.   3番の円盤をBからCへ移動
処理1021回目　No.   1番の円盤をAからBへ移動
処理1022回目　No.   2番の円盤をAからCへ移動
処理1023回目　No.   1番の円盤をBからCへ移動

　などという風なものが出力される。

　そして、ハノイの塔の枚数を1枚増やすと、それがさらに倍というわけで、2の枚数乗倍ということになるようだ。なので、間違って
　100
　とか入力すると、ドライブ上に数百メガバイトのファイルとともに、処理回数カウンタのiの変数がおかしくなって異常終了するまで、延々と続くと……。

　しかし……プログラムは先生にいただいたアルゴリズムをそのままCにするだけ（というかするほどでもない気がする）なので、できたはできたんだけど、そして、動いたはうごいたんだけど、どうしてこうなるのかさっぱりわからん。なにがなんだかさっぱりわからん。

　どうしてこうなるのかさっぱりわからん。う〜ん。

　そして気づく。そういえば、基本情報で再起呼び出しの問題が午前問題に出たけど、思いっきり落としたんだった。いや、だって考えているとどんどん度つぼにはまるというか、の〜みそが煮えるというか……。