ソフトウェア概論A/B (2020/06/05)
Ver. 1.0

目次

講義資料

当日の OHP 資料

• 当日のOHP資料です。
  • 表示用(HTML)
  • 印刷用(PDF)

講議中に作成したプログラム

• 20200529-01-9999.c (20200529-01-9999.c (SJIS))
  20200529-01-9999.c

  /*
   * 20200529-01-QQQQ.c
   *	一進数のフィボナッチ数
   *
   *                          0            (n=0)
   *      fib(n) = {          1            (n=1)
   *                 fib(n-1) + fib(n-2)   (n>1)
   */
  
  #include <stdio.h>
  #include <string.h>
  
  /*
   * 一進数のフィボナッチ数列
   */
  
  void fib ( char *n ) {
  
  	 if ( !strcmp ( n, "" ) ) {					/* n = 0 */
  	 	/* 何もしなくてよい */					/*		fib(0) = 0 */
  	 } else if ( !strcmp ( n + 1, "" ) ) {		/* n = 1 */
  		printf ( "0" );							/*		fib(1) = 1 */
  	 } else {									/* n > 0 */
  	 	/* f(n-1) f(n-2) を並べて書く */
  	 	fib ( n + 1 );							/* fib(n-1) + fib(n-2) */
  	 	fib ( n + 2 );
  	 }
  
  }
  
  int main ( void ) {
  
  	/* fib 3 */
  	fib ( "000" );
  	printf ( "\n" );
  
  	/* fib 10 */
  	fib ( "0000000000" );
  
  	printf ( "\n" );
  
    return 0;
  }
  
  
  /*
  
   	f0 = 0
   	f1 = 1
   	f2 = f0 + f1 = 0 + 1 = 1
   	f3 = f2 + f1 = 1 + 1 = 2
   	f4 = f3 + f2 = 2 + 1 = 3
   	f5 = f4 + f3 = 3 + 2 = 5
      0  1  2  3  4  5  6  7  8  9 10
   	0, 1, 1, 2, 3, 5, 8,13,21,34,55 ...
  
   	f(N) = F(N-1) + F(N-2)
  
   		一進数の足し算				十進数足し算
   			111							3
   										+
   			11111						5
   										|
   										v
   			11111111					8
  
   	F(N) を計算するには、
  	 	F(N-1) と F(N-2) をそれぞれ、並べて出力するえばよい
  
   	前回の課題との違い
   		前回の課題 => 数学的関数の再帰的定義からプログラムを作成
  	 	今回の場合 => 一進数の性質 ( + するには、並べればよい )
  */
   	
  

• 20200529-02-9999.c (20200529-02-9999.c (SJIS))
  20200529-02-9999.c

  /*
   * 20200529-02-QQQQ.c
   *	一進数の階乗
   *
   *               1       		( n = 0 の時 : 0! = 1 )
   *     n! = {
   *				n * ((n-1)!)	( n > 0 の時 )
   */
  
  #include <stdio.h>
  #include <string.h>
  
  /*
   * n_time_fac ( n, n1 )
   *	fac ( n1 ) を n 回行う
   *		=> n * fac(n1)
   */
  
  void n_time_fac ( char *n, char *n1 ) {
  
  	 if ( !strcmp ( n, "" ) ) {					/* n = 0 */
  		/* 何もしない */
  	 } else {									/* n > 0 */
  	 	fac( n1 );
  		n_time_fac ( n + 1, n1 );				/* n * fac ( n-1 ) */
  	 }
  }
  
  /*
   * 一進数の階乗
   *						1		(n=0)
   *    fac(n) = {
   *					n * fac(n-1)
   */
  
  void fac ( char *n ) {
  
  	 if ( !strcmp ( n, "" ) ) {					/* n = 0 */
  	 	printf ( "0" );							/*		fac(0) = 1 */
  	 } else {									/* n > 0 */
  		n_time_fac ( n, n + 1 );
  	 }
  
  }
  
  /*
   * main
   */
  
  int main ( void ) {
  
  	/* fac(3) */
  	fac ( "000" );
  	printf ( "\n" );
  
  	/* fac(5) */
  	fac ( "00000" );
  	printf ( "\n" );
  
    return 0;
  }
  
  
  /*
  
   			一進数				十進数
   				11					2
   									*
   				111					3
   									|
   									v
   				111111				6
   				111 111
  
   	times ( char *n, char *m ) {
   		printf ( m ) を 文字列 n の長さの回数だけ繰り返す
   			=> 再帰が使える
   	}
  
  */
  

• 20200605-01-9999.c (20200605-01-9999.c (SJIS))
  20200605-01-9999.c

  /*
   * 20200605-01-QQQQ.c
   *	「Hanoi の塔」を解くプログラム
   */
  
  #include <stdio.h>
  #include <string.h>
  
  /*
   * one_to_ten ( char *n );
   *  n が、一進数 "1" 〜 "111111111" の時、十進数の 1 〜 9 に変換する
   */
  
  void one_to_ten ( char *n ) {
  
  	if ( !strcmp ( n, "" ) ) {
  	 	printf ( "0" );
  	} else if ( !strcmp ( n, "1" ) ) {
  	 	printf ( "1" );
  	} else if ( !strcmp ( n, "11" ) ) {
  	 	printf ( "2" );
  	} else if ( !strcmp ( n, "111" ) ) {
  	 	printf ( "3" );
  	} else if ( !strcmp ( n, "1111" ) ) {
  	 	printf ( "4" );
  	} else if ( !strcmp ( n, "11111" ) ) {
  	 	printf ( "5" );
  	} else if ( !strcmp ( n, "111111" ) ) {
  	 	printf ( "6" );
  	} else if ( !strcmp ( n, "1111111" ) ) {
  	 	printf ( "7" );
  	} else if ( !strcmp ( n, "11111111" ) ) {
  	 	printf ( "8" );
  	} else if ( !strcmp ( n, "111111111" ) ) {
  	 	printf ( "9" );
  	} else {
  	 	printf ( "?" );
  	}
  
  }
  
  
  /*
   * move ( char *n, char *f, char *t )
   *	幅 n の円盤を、f から t に移動する
   */
  
  void move ( char *n, char *f, char *t ) {
  
  	/* 画面に 「棒 f から、円盤 (n) を、棒 t に移動 」と出力する */
  
  	printf ( f );
  	printf ( " から、" );
  	printf ( "円盤 (" );
  	one_to_ten ( n );
  	printf ( ")" );
  	printf ( "を、" );
  	printf ( t ); 
  	printf ( " に移動\n" );
  
  }
  
  /*
   * hanoi ( char *n, char *f, char *t, char *w )
   *   高さ n の塔を f から t へ w を利用して、移動する
   */
  
  void hanoi ( char *n, char *f, char *t, char *w ) {
  
  	if ( !strcmp ( n, "" ) ) {		/* 高さ 0 の塔 */
  		/* 何もしなくて良い (動かすものはない) */
  	} else {
  		/* f にある n-1 の塔 を、一旦 w に移動する (この時、t を作業場として利用可能) */
  		hanoi ( n + 1, f, w, t );
  		/* f に、長さ n の円盤があるので、これを t に移動 */
  		move ( n, f, t );
  		/* w にある n-1 の塔 を、t に移動する (この時、f を作業場として利用可能) */
  		hanoi ( n + 1, w, t, f );
  	}
  
  }
  
  /*
   * main
   */
  
  int main ( void ) {
  
  	printf ( "高さ 3 の「Hanoi の塔」\n" );
  	hanoi ( "111", "棒 1", "棒 2", "棒 3" );
  
  	printf ( "------\n" );
  	printf ( "高さ 5 の「Hanoi の塔」\n" );
  
  	/*
  	**	 この部分を完成させなさい
  	*/
  
  
  	return 0;
  }
  

• 20200605-02-9999.c (20200605-02-9999.c (SJIS))
  20200605-02-9999.c

  /*
   * 20200605-02-QQQQ.c
   *	「砂漠の旅行」を解くプログラム
   */
  
  #include <stdio.h>
  #include <string.h>
  
  /*
   * step()
   *	手持ちが 3 の時、一つ進んで、食料を置き、戻って来る
   *
   *    (0)   0   0000
   *    (3)   0   0000
   *    (2)   1   0000
   *    (1)   1   1000
   *    (0)   0   1000
   */
  
  void step ( void ) {
  
  	printf ( "一つ進む\n" );
  	printf ( "一つ置く\n" );
  	printf ( "一つ戻る\n" );
  }
  
  /*
   * forward ( char *n )
   *	n だけ、道に置かれている食料を消費しながら進む
   *              123..n0
   *    (0)   0   111..10
   *    (3)   0   111..10
   *    (3)   1   011..10
   *         ...
   *    (3)   n   0000000
   */
  
  void forward ( char *n ) {
  
  	 if ( !strcmp ( n, "" ) ) {
  		/* 最初に三つ拾う */
  	 	printf ( "三つ拾う\n" );
  	 } else {
  		/* n - 1 だけ進み */
  	 	forward ( n + 1 );
  		/* 最後の一歩 */
  		printf ( "一つ進む\n" );
  	 	printf ( "一つ拾う\n" );
  	 }
  }
  
  /*
   * back ( char *n )
   *	n だけ、道に置かれている食料を消費しながら戻る
   *              123..n
   *    (0)   n   111..10
   *    (0)   n-1 111..00
   *    		...
   *    (0)   0   000..00
   */
  
  void back ( char *n ) {
  
  	 if ( !strcmp ( n, "" ) ) {
  	 	/* なにもしない */
  	 } else {
  		/* 最初の一歩 */
  	 	printf ( "一つ拾う\n" );
  	 	printf ( "一つ戻る\n" );
  		/* n - 1 だけ戻る */
  		back ( n + 1 );
  	 }
  }
  
  /*
   * stocks ( char *n )
   *   1 〜 n の場所に食料を置く
   */
  
  void stocks ( char *n ) {
  
  	if ( !strcmp ( n, "" ) ) {
  		/* 何もしなくてよい */
  	} else {
  		/* n の場所に食料を置く */
  		stock ( n );
  		/* 1 〜 n - 1 の場所に食料を置く */
  		stocks ( n + 1 );
  	}
  }
  
  /*
   * stock ( char *n )
   *   n の場所に食料を置く
   */
  
  void stock ( char *n ) {
  
  	if ( !strcmp ( n, "1" ) ) {
  	 	printf ( "三つ拾う\n" );
  		step();
  	} else {
  		/* 行って帰るために、1 〜 n - 1 までに二つずつ食料を置く */
  		stocks ( n + 1 );
  		stocks ( n + 1 );
  
  		/* 食べながら、n - 1 まで進む */
  
  		forward ( n + 1 );
  		/* n に食料を置く */
  		step();
  		/* 食べながら、n - 1 から戻る */
  		back ( n + 1 );
  	}
  
  }
  
  /*
   * walk ( char *g )
   *   g の場所に旅をしたい
   */
  
  void walk ( char *g ) {
  
  	/* g は 4 以上を想定している */
  
  	/* g - 3 まで、片道を作る */
  	stocks ( g + 3 );
  
  	/* g - 3 まで、食料を拾いながら進む */
  	forward ( g + 3 );
  
  	/* 最後の 3 ステップは、手持ちを消費しつつ進む */
  	printf ( "一つ進む\n" );
  	printf ( "一つ進む\n" );
  	printf ( "一つ進む\n" );
  
  }
  
  /*
   * main
   */
  
  int main ( void ) {
  
  	printf ( "4 まで行く\n" );
  	walk ( "1111" );
  
  	printf ( "6 まで行く\n" );
  	walk ( "111111" );
  
  	return 0;
  }
  

• p-001.c (p-001.c (SJIS))
  p-001.c

  #include <stdio.h>
  #include <string.h>
  
  
  void times ( char *n, char *m ) {
  
  	if ( !strcmp ( n, "" ) ) {
  		/* 何もしない */
  	} else {
  		printf ( m );
  		times ( n + 1, m );
  	}
  }
  
  int main(void) {
  
  	printf( "11 * 111 = " );
  	times ( "11", "111" );
  	printf ( "\n" );
  
  	return 0;
  }
  

• memo.txt (memo.txt (SJIS))
  memo.txt

  前回(2020/05/29)の内容
  	再帰的定義と数学的帰納法
  		再帰的定義
  			C 言語での関数の定義
  				自分自身を呼び出す
  					f(N) { ... f(N-1) .. }
  		数学的帰納法
  			数学上の証明の形式
  					P(N) {  ... P(N-1) .. }
  		再帰的に定義された関数の性質は、
  			数学的帰納法で証明しやすい
  		数学的帰納法を利用した証明から、
  			再帰的に定義された関数が定義できる
  
  	一進数
  		1 を n 個数並べて、自然数 n を表現する数の表現方法
  
  			十進数			一進数
  				0				
  				1				1
  				2				11
  				3				111
  				4				1111
  				5				11111
  
  一進数
  	足し算 => 二つ数を並べるだけ
  	掛け算 => 足し算を繰り返す ( 再帰 )
  		「計算」が printf *だけ* で
  			# 裏側では C 言語の
  			#		順接/条件分岐(if 構文)/繰り返し(再帰)
  			# 三つの構文を組み合わせて => 万能だから...
  
  [2020/06/05]
  
  	Hanoi の塔の問題
  		三本の棒 ( 1 ? 3 ) と、大きさの異る N 枚の円盤がある
  		最初は、その内の一番左の 1 番の棒に、大きさの順に円盤が積まれている
  		その円盤を、全て、真ん中の 2 盤の棒に移動したい
  		ただし、円盤を移動する場合には、次の制限を守る必要がある
  			一度に移動できるのは、棒の一番上の一枚の円盤のみである
  			空の棒にはどの大きさの円盤も積む事ができる
  				既に円盤が積まれた棒には、その一番上の円盤より小さい円盤しか積む事ができない
  
  
  	  [1|1]       |        |
  	 [22|22]      |        |
  	[333|333]     |        |
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(1) から (2) に [1] の円盤を移動する
  
  	    |         |        |
  	 [22|22]      |        |
  	[333|333]   [1|1]      |
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(1) から (3) に [2] の円盤を移動する
  
  	    |         |        |
  	    |         |        |
  	[333|333]   [1|1]   [22|22]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(2) から (3) に [1] の円盤を移動する
  
  	    |         |        |
  	    |         |      [1|1]
  	[333|333]     |     [22|22]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(1) から (2) に [3] の円盤を移動する
  
  	    |         |        |
  	    |         |      [1|1]
  	    |     [333|333] [22|22]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(3) から (1) に [1] の円盤を移動する
  
  	    |         |        |
  	    |         |        |
  	  [1|1]   [333|333] [22|22]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(3) から (2) に [2] の円盤を移動する
  
  	    |         |        |
  	    |      [22|22]     |
  	  [1|1]   [333|333]    |
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(1) から (2) に [1] の円盤を移動する
  
  	    |       [1|1]      |
  	    |      [22|22]     |
  	    |     [333|333]    |
  --------+---------+--------+------
         (1)       (2)      (3)
  
  この手順で、
  	高さ 3 のハノイの塔を (1) の棒から、(2) の棒に移動できた
  
  	[問題]
  		同様にして、
  			高さ 3 のハノイの塔を (1) の棒から、(3) の棒に移動
  		する手順を考えてください。
  
  	[解答]
  
  	  [1|1]       |        |
  	 [22|22]      |        |
  	[333|333]     |        |
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(1) から (3) に [1] を移動する
  
  	    |         |        |
  	 [22|22]      |        |
  	[333|333]     |      [1|1]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(1) から (2) に [2] を移動する
  
  	    |         |        |
  	    |         |        |
  	[333|333]  [22|22]   [1|1]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(3) から (2) に [1] を移動する
  
  	    |         |        |
  	    |       [1|1]      |
  	[333|333]  [22|22]     |
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(1) から (3) に [3] を移動する
  
  	    |         |        |
  	    |       [1|1]      |
  	    |      [22|22] [333|333]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(2) から (1) に [1] を移動する
  
  	    |         |        |
  	    |         |        |
  	  [1|1]    [22|22] [333|333]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(2) から (3) に [2] を移動する
  
  	    |         |        |
  	    |         |     [22|22]
  	  [1|1]       |    [333|333]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  	(1) から (3) に [1] を移動する
  
  	    |         |      [1|1]
  	    |         |     [22|22]
  	    |         |    [333|333]
  --------+---------+--------+------
         (1)       (2)      (3)
  
  まず、プログラムを作成するまえに、
  	自分の手で実現できるかどうかを試す
  		# 小さい問題で...
  	いきなりプログラムを書くの大変なので、手動で
  		!!! 手でてきない事がプログラムでできるようにできない
  		!!! ちいさな問題から解く
  
  一般のハノイの塔の問題
  
  							なにもしない		(N=0 の時)
  hanoi ( N, i, j, k ) = {
  							次の 3 ステップで行う
  								hanoi ( N-1, i, k )
  								円盤 N を i から j に移動
  								honai ( N-1, k, j )
  
  
  砂漠の旅行の問題
  
  	町ーーー砂漠ーーー町
  	０１２３
  	３２１０
  	町ーー町
  
  		旅人は、一枡移動するときに、食料を一食分消費する
  			もし、旅の途中で、食料がなくなったら、移動できなくなる
  				=> その場で餓死
  		旅人は、一度に三つまでの食料しかもてない
  			町では、いつでも、食料を買う事ができる
  				=> 目的の町が、３だけ離れているなら、問題ない
  					４以上離れていたらどうするか ?
  
  		目的の町が４以上離れている場合は、
  			途中の砂漠に、食料をおいて、途中で、補給する事を考える
  				砂漠には二個まで、食料を置く事ができる
  
  			食料数	位置	砂漠の状態
  			(0)		0		000G
  三つ買う
  			(3)		0		000G
  前に進む
  			(2)		1		000G
  食料を置く
  			(1)		1		100G
  後ろに戻る
  			(0)		0		100G
  三つ買う
  			(3)		0		100G
  前に進む
  			(2)		1		100G
  食料を拾う
  			(3)		1		000G
  前に進む
  			(2)		2		000G
  前に進む
  			(1)		3		000G
  前に進む
  			(0)		4[G]	000G
  
  [問題]
  	距離 4 の町までの手順を示した
  		距離 5 の町のまでの手順を考えなさい。
  
  [解答]
  			食料数	位置	砂漠の状態
  			(0)		0		0000G
  三つ買う
  			(3)		0		0000G
  前に進む
  			(2)		1		1000G
  食料を置く
  			(1)		1		1000G
  後ろに戻る
  			(0)		0		1000G
  三つ買う
  			(3)		0		0000G
  前に進む
  			(2)		1		1000G
  食料を置く
  			(1)		1		2000G
  後ろに戻る
  			(0)		0		2000G
  三つ買う
  			(3)		0		2000G
  前に進む
  			(2)		1		2000G
  食料を拾う
  			(3)		1		1000G
  前に進む
  			(2)		2		1000G
  食料を置く
  			(1)		2		1100G
  後ろに戻る
  			(0)		1		1100G
  食料を拾う
  			(1)		1		0100G
  後ろに戻る
  			(0)		0		0100G
  三つ買う
  			(3)		0		0100G
  前に進む
  			(2)		1		0100G
  食料を置く
  			(1)		1		1100G
  後ろに戻る
  			(0)		0		1100G
  三つ買う
  			(3)		0		1100G
  前に進む
  			(2)		1		1100G
  食料を拾う
  			(3)		1		0100G
  前に進む
  			(2)		2		0100G
  食料を拾う
  			(3)		2		0000G
  前に進む
  			(2)		3		0000G
  前に進む
  			(1)		4		0000G
  前に進む
  			(0)		5(G)	0000G
  

本日の課題

課題プログラム内の「/*名前:ここ*/」の部分を書き換え「/*この部分を完成させなさい*/」の部分にプログラムを追加して、プログラムを完成させます。

課題 CNAME-01 : 「Hanoi の塔」を解くプログラム

Download : 20200605-01.c

/*
 * 20200605-01-QQQQ.c
 *	「Hanoi の塔」を解くプログラム
 */

#include <stdio.h>
#include <string.h>

/*
 * one_to_ten ( char *n );
 *  n が、一進数 "1" 〜 "111111111" の時、十進数の 1 〜 9 に変換する
 */

void one_to_ten ( char *n ) {

	if ( !strcmp ( n, "" ) ) {
	 	printf ( "0" );
	} else if ( !strcmp ( n, "1" ) ) {
	 	printf ( "1" );
	} else if ( !strcmp ( n, "11" ) ) {
	 	printf ( "2" );
	} else if ( !strcmp ( n, "111" ) ) {
	 	printf ( "3" );
	} else if ( !strcmp ( n, "1111" ) ) {
	 	printf ( "4" );
	} else if ( !strcmp ( n, "11111" ) ) {
	 	printf ( "5" );
	} else if ( !strcmp ( n, "111111" ) ) {
	 	printf ( "6" );
	} else if ( !strcmp ( n, "1111111" ) ) {
	 	printf ( "7" );
	} else if ( !strcmp ( n, "11111111" ) ) {
	 	printf ( "8" );
	} else if ( !strcmp ( n, "111111111" ) ) {
	 	printf ( "9" );
	} else {
	 	printf ( "?" );
	}

}


/*
 * move ( char *n, char *f, char *t )
 *	幅 n の円盤を、f から t に移動する
 */

void move ( char *n, char *f, char *t ) {

	/* 画面に 「棒 f から、円盤 (n) を、棒 t に移動 」と出力する */

	printf ( f );
	printf ( " から、" );
	printf ( "円盤 (" );
	one_to_ten ( n );
	printf ( ")" );

	/*
	**	 この部分を完成させなさい
	*/

	printf ( " に移動\n" );

}

/*
 * hanoi ( char *n, char *f, char *t, char *w )
 *   高さ n の塔を f から t へ w を利用して、移動する
 */

void hanoi ( char *n, char *f, char *t, char *w ) {

	if ( !strcmp ( n, "" ) ) {		/* 高さ 0 の塔 */
		/* 何もしなくて良い (動かすものはない) */
	} else {
		/* f にある n-1 の塔 を、一旦 w に移動する (この時、t を作業場として利用可能) */
		hanoi ( n + 1, f, w, t );
		/* f に、長さ n の円盤があるので、これを t に移動 */
		move ( n, f, t );
		/* w にある n-1 の塔 を、t に移動する (この時、f を作業場として利用可能) */

	/*
	**	 この部分を完成させなさい
	*/

	}

}

/*
 * main
 */

int main ( void ) {

	printf ( "高さ 3 の「Hanoi の塔」\n" );
	hanoi ( "111", "棒 1", "棒 2", "棒 3" );

	printf ( "------\n" );
	printf ( "高さ 5 の「Hanoi の塔」\n" );

	/*
	**	 この部分を完成させなさい
	*/


	return 0;
}

$ ./20200605-01-QQQQ.exe
高さ 3 の「Hanoi の塔」
棒 1 から、円盤 (1) を、棒 2 に移動
棒 1 から、円盤 (2) を、棒 3 に移動
棒 2 から、円盤 (1) を、棒 3 に移動
棒 1 から、円盤 (3) を、棒 2 に移動
棒 3 から、円盤 (1) を、棒 1 に移動
棒 3 から、円盤 (2) を、棒 2 に移動
棒 1 から、円盤 (1) を、棒 2 に移動
------
高さ 5 の「Hanoi の塔」
棒 1 から、円盤 (1) を、棒 2 に移動
棒 1 から、円盤 (2) を、棒 3 に移動
棒 2 から、円盤 (1) を、棒 3 に移動
棒 1 から、円盤 (3) を、棒 2 に移動
棒 3 から、円盤 (1) を、棒 1 に移動
棒 3 から、円盤 (2) を、棒 2 に移動
棒 1 から、円盤 (1) を、棒 2 に移動
棒 1 から、円盤 (4) を、棒 3 に移動
棒 2 から、円盤 (1) を、棒 3 に移動
棒 2 から、円盤 (2) を、棒 1 に移動
棒 3 から、円盤 (1) を、棒 1 に移動
棒 2 から、円盤 (3) を、棒 3 に移動
棒 1 から、円盤 (1) を、棒 2 に移動
棒 1 から、円盤 (2) を、棒 3 に移動
棒 2 から、円盤 (1) を、棒 3 に移動
棒 1 から、円盤 (5) を、棒 2 に移動
棒 3 から、円盤 (1) を、棒 1 に移動
棒 3 から、円盤 (2) を、棒 2 に移動
棒 1 から、円盤 (1) を、棒 2 に移動
棒 3 から、円盤 (3) を、棒 1 に移動
棒 2 から、円盤 (1) を、棒 3 に移動
棒 2 から、円盤 (2) を、棒 1 に移動
棒 3 から、円盤 (1) を、棒 1 に移動
棒 3 から、円盤 (4) を、棒 2 に移動
棒 1 から、円盤 (1) を、棒 2 に移動
棒 1 から、円盤 (2) を、棒 3 に移動
棒 2 から、円盤 (1) を、棒 3 に移動
棒 1 から、円盤 (3) を、棒 2 に移動
棒 3 から、円盤 (1) を、棒 1 に移動
棒 3 から、円盤 (2) を、棒 2 に移動
棒 1 から、円盤 (1) を、棒 2 に移動
$ 

課題 CNAME-02 : 「砂漠の旅行」を解くプログラム

Download : 20200605-02.c

/*
 * 20200605-02-QQQQ.c
 *	「砂漠の旅行」を解くプログラム
 */

#include <stdio.h>
#include <string.h>

/*
 * step()
 *	手持ちが 3 の時、一つ進んで、食料を置き、戻って来る
 */

void step ( void ) {

	printf ( "一つ進む\n" );
	printf ( "一つ置く\n" );
	printf ( "一つ戻る\n" );
}

/*
 * forward ( char *n )
 *	n だけ、道に置かれている食料を消費しながら進む
 */

void forward ( char *n ) {

	 if ( !strcmp ( n, "" ) ) {
		/* 最初に三つ拾う */
	 	printf ( "三つ拾う\n" );
	 } else {
		/* n - 1 だけ進み */

	/*
	**	 この部分を完成させなさい
	*/


		/* 最後の一歩 */
		printf ( "一つ進む\n" );
	 	printf ( "一つ拾う\n" );
	 }
}

/*
 * back ( char *n )
 *	n だけ、道に置かれている食料を消費しながら戻る
 */

void back ( char *n ) {

	 if ( !strcmp ( n, "" ) ) {
	 	/* なにもしない */
	 } else {
		/* 最初の一歩 */

	/*
	**	 この部分を完成させなさい
	*/


		/* n - 1 だけ戻る */
		back ( n + 1 );
	 }
}


/*
 * stocks ( char *n )
 *   1 〜 n の場所に食料を置く
 */

void stocks ( char *n ) {

	if ( !strcmp ( n, "" ) ) {
		/* 何もしなくてよい */
	} else {
		/* n の場所に食料を置く */
		stock ( n );
		/* 1 〜 n - 1 の場所に食料を置く */

	/*
	**	 この部分を完成させなさい
	*/

	}
}

/*
 * stock ( char *n )
 *   n の場所に食料を置く
 */

void stock ( char *n ) {

	if ( !strcmp ( n, "1" ) ) {
	 	printf ( "三つ拾う\n" );
		step();
	} else {
		/* 行って帰るために、1 〜 n - 1 までに二つずつ食料を置く */
		stocks ( n + 1 );
		stocks ( n + 1 );

		/* 食べながら、n - 1 まで進む */

	/*
	**	 この部分を完成させなさい
	*/

		/* n に食料を置く */
		step();
		/* 食べながら、n - 1 から戻る */
		back ( n + 1 );
	}

}

/*
 * walk ( char *g )
 *   g の場所に旅をしたい
 */

void walk ( char *g ) {

	/* g は 4 以上を想定している */

	/* g - 3 まで、片道を作る */
	stocks ( g + 3 );

	/* g - 3 まで、食料を拾いながら進む */
	forward ( g + 3 );

	/* 最後の 3 ステップは、手持ちを消費しつつ進む */
	printf ( "一つ進む\n" );
	printf ( "一つ進む\n" );
	printf ( "一つ進む\n" );

}

/*
 * main
 */

int main ( void ) {

	printf ( "4 まで行く\n" );
	walk ( "1111" );

	printf ( "6 まで行く\n" );
	walk ( "111111" );

	return 0;
}

$ ./20200605-02-QQQQ.exe
4 まで行く
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ拾う
一つ進む
一つ進む
一つ進む
6 まで行く
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ拾う
一つ進む
一つ置く
一つ戻る
一つ戻る
一つ拾う
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ拾う
一つ進む
一つ置く
一つ戻る
一つ戻る
一つ拾う
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ拾う
一つ進む
一つ拾う
一つ進む
一つ置く
一つ戻る
一つ戻る
一つ拾う
一つ戻る
一つ拾う
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ拾う
一つ進む
一つ置く
一つ戻る
一つ戻る
一つ拾う
三つ拾う
一つ進む
一つ置く
一つ戻る
三つ拾う
一つ進む
一つ拾う
一つ進む
一つ拾う
一つ進む
一つ拾う
一つ進む
一つ進む
一つ進む
$