アプリケーション演習No.１４　Ｃ言語ﾌﾟﾛｸﾞﾗﾐﾝｸﾞ -4 再帰的な関数(続き）, 4-5 ハノイの塔の問題

　　2000.09.08　KPC　情報技術科　関谷

1．今日の実習（4-4 再帰的な関数(続き）, 4-5 ハノイの塔の問題）への補足

Ａ。再帰的な関数

　階乗は、このテキストp.64の第２段落にあるように、再帰的に求めなくても、単純なforループで計算できる。
　例題4-4のフィボナッチ数列も、3章の演習問題１６で計算したように、ループで変数を置き換えるか、配列を使って計算できる。
　しかし、4-5での「ハノイの塔」などの問題は、再帰的な関数を使うと、非常に簡単に求められることが分かる。しかし、関数の呼び出しが指数関数的に増えるので、計算時間やスタック（後入れ先出しでのメモリ-関数の引数や戻り値を呼び出し毎に記憶する）などがそれに伴い、増える。
(スタック-和訳では棚です-については、「データ構造」とか「アルゴリズム」の本などで調べなさい。）

4-5 ハノイの塔の問題

　Ｃ言語での解き方のいろいろ

　プログラム４−７は、文字列を使って呼出された直後と、戻り時の円盤を表示しているが、n==1のケースを特別扱いしたり、最後に円盤の移動を行うなどで、却って分かりにくく感じる。以下に、単純に円盤の移動を表示するプログラムを紹介する。

/* hnoi.c     add level   1998.5.17, 2000.9.7 sekiya  */
/* tower of hanoi 再帰版 (Pascal と Ｃへの招待, P158) */

#include  

int seq=0;
int level = 0;

hanoi(int n, char origin, char target, char using);

main(){  
	int n;

	printf("How many pieces?");	scanf("%d",&n);
//	hanoi(n, 'A','C','B');
	hanoi(n, 's','t','w');		// Cﾌﾟﾛｸﾞﾗﾐﾝｸﾞ入門p.66-68
}

hanoi(int n, char origin, char target, char using)
{
    int	i; 

    level++; 	
    if( n > 0 ){		//　nが正の時だけ、移動処理を行う。
		hanoi(n-1, origin, using, target);	// （再帰）n-1枚をusingによける

		printf("%3d",++seq);				//　ｎ枚目を移す
		for (i=1; i<=level; ++i)	printf("  ");  
 		printf("Move piece %d from %c to %c\n",n, origin,target);

		hanoi(n-1, using, target, origin);	//　（再帰）n-1枚をtargetに移す
    }
    level--;
}
/*　実行例

H:\c00>hanoi
How many pieces?3
  1      Move piece 1 from s to t
  2    Move piece 2 from s to w
  3      Move piece 1 from t to w
  4  Move piece 3 from s to t
  5      Move piece 1 from w to s
  6    Move piece 2 from w to t
  7      Move piece 1 from s to t

*/

　上のプログラムの考え方を参考にして、テキストの例題p4_7.cを改造したものを参考までに示す。再帰処理のｱﾙｺﾞﾘｽﾞﾑに忠実にﾌﾟﾛｸﾞﾗﾐﾝｸﾞすると、分かりやすい。

　ＶＢでの解き方のいろいろ

　河西朝雄の「Visual Basicによるはじめてのｱﾙｺﾞﾘｽﾞﾑ入門、技術評論社、1999」から、その「4-4ハノイの塔」の例題(rei29）文字での移動表示、「5-1　スタック」練習問題32(dr32）文字での移動と結果の表示、参考(dr32-2）ｸﾞﾗﾌｨｯｸｽ表示のプログラムを紹介する。
　なお、これらは、サーバread(R:\）\sekiya\ｱﾌﾟﾘｹｰｼｮﾝ演習\河西_VB_ﾊﾉｲにある。皆さんのホームドライブ(h:\)にコピーして、改造しても良い。（*.vbp,*.frm, *.vbwの３つのファイルからなる。）

＜VBプログラムの起動、プロジェクトの解放＞
　VBプログラムの起動は、プロジェクトファイル(*.vbpのファイル)を開けばよい。途中で,　VisualSourceSafeへの保存、ファイルの書き換えの窓が出たときには、すべて、「いいえ」をクリックすればよい。終わったら、「プロジェクトの解放」をすること。

　Java言語でのハノイの塔アプレット

　Java言語でのアプレットは、ブラウザで実行できるので、紹介する。
ﾊﾉｲの塔アプレットは、参考書（Lalaniほか,ｽﾘｰｴｰｼｽﾃﾑｽﾞ訳,JAVAﾌﾟﾛｸﾞﾗﾐﾝｸﾞｹｰｽｽﾀﾃﾞｨ、翔永社,1997.2）の例題を、円盤枚数の増減やマウスでの一時停止など、改造したものである。
　このプログラムは、マウスのクリックで、開始・再開と一時停止とを交互に繰り返す。最初は円盤を４枚で実行するが、途中でキー(+,-,0)を押すことで、それぞれ、次の枚数を変えるようにしている。(枚数と遅れは、htmlファイルでのパラメータ）

２．今日の実習（4-4 再帰的な関数(続き）, 4-5 ハノイの塔の問題）

4-4 再帰的な関数(続き）, 4-5 ハノイの塔の問題

テキストのプログラム、例題を学習しよう。解説を読み、実際にプログラムを入力して動かす、さらに改造していろいろと実験をするのが良い。

　プログラミング実習では、C言語のプログラムの様式に合わせて作成のこと。なお、考察を先頭部分に書くのが良い。

４章の演習問題　17)−20)

　これまで、文字列の処理をいろいろと行ってきたが、それらを関数にする問題です。文字列は、文字の配列だから、引数にすれば、関数側での書き換えができます。

３．レポート

３．１　レポート用ファイルの作成

　レポートは、実習した全部のプログラムを順番に貼り付けて、レポート用のテキストファイルを作成のこと。

３．２　提出フォルダとファイル名

・フォルダ：w:\アプリケーション演習￥Ｃ言語rec9.8
・ファイル名：ｎｎ氏名ap14.txt

この科目の成績と授業の評価について

　前半は、Ｗｏｒｄ/Ｅｘｃｅｌの学習でしたが、後半はＣ言語の学習をしています。ﾌﾟﾛｸﾞﾗﾐﾝｸﾞは、論理の問題だから、向き不向きがあります。しかし、入学試験を合格してきた皆さんなら、ある程度やれば、できるのです。それでも、まじめに学習しないで、新しい言語の習得ができる訳がありません。これに付いていけない人は、早く、方向転換をした方が良いでしょう。

　小生の授業の進め方についての評価も最後にお願いするつもりです。お互いに真剣にやりましょう。