/*
* 20210507-02-QQQQ.c
* 引数の文字列の長さに対するフィボナッチ数だけの文字「*」を出力する関数
*
* 0 ( n = 0 の時 )
* fib(n) = { 1 ( n = 1 の時 : n-1 = 0 )
* fib(n-1)+fib(n-2) ( その他 [n > 1 の時] )
*/
#include <stdio.h>
#include <string.h> /* strcmp を利用するために必要 */
/*
* void c_fibnacci ( char *n )
* n : その長さで、整数値を表す文字列
*/
void c_fibnacci ( char *n ) {
if ( !strcmp ( n, "" ) ) { /* n の長さが 0 */
/* 何もしなくて良い (関数は終了) */
} else if ( !strcmp ( n + 1, "" ) ) { /* n の長さが 1 */
putchar ( '*' );
} else { /* その他 ( n の長さが 1 より長い ) */
/* 再帰呼出しを二度行う */
/* 一度目は、1 だけ長さを減らす */
/* fib(n-1) */
c_fibnacci ( n + 1 );
/* fib(n-2) */
/* ニ度目は、2 だけ長さを減らす */
c_fibnacci ( n + 2 ); /* n <> 0, n <> 1 => n >= 2 */
}
}
/*
* main
*/
int main ( void ) {
/* fib(4) = 3 回だけ「*」を出す */
c_fibnacci ( "****" );
putchar ( '\n' ); /* 改行 */
/* fib(7) = 13 回だけ「*」を出す */
c_fibnacci ( "*******" );
putchar ( '\n' ); /* 改行 */
return 0;
}
/*
* 20210514-02-QQQQ.c
* 一進数の階乗
*
* 1 (N=0)
* fac N = {
* N * fac(N-1) (N>0)
* 0 (N=0)
* {
* (N-1)*fac(N-1) + fac(N-1) (N>0)
*/
#include <stdio.h>
#include <string.h>
/*
* prototype
*/
extern void fac ( char *n );
/*
* n_time_fac ( n, n1 )
* fac ( n1 ) を n 回行う
* => n * fac(n1)
* fac(n1) + (n-1)*fac(n1)
*/
void n_time_fac ( char *n, char *n1 ) {
if ( !strcmp ( n, "" ) ) { /* n = 0 */
/* 何もしない */
} else { /* n > 0 */
/*
** fac(n1)
*/
fac(n1);
/*
** (N-1)*fac(N-1)
*/
n_time_fac ( n + 1, n1 ); /* 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 ); /* fac(n) = n * fac(n-1) */
}
}
/*
* main
*/
int main ( void ) {
/* fac(3) */
fac ( "000" );
printf ( "\n" );
/* fac(5) */
fac ( "00000" );
printf ( "\n" );
return 0;
}
/*
* 20210514-01-QQQQ.c
* 一進数の割り算
*
* (a-b)/b + 1 (a>=b)
* a/b = {
* 0 (a<b) <= a=0 の場合でない
*
*/
#include <stdio.h>
#include <string.h>
/*
* prototype
*/
extern void one_div ( char *a, char *b );
/*
* one_sub_div ( a, b, c )
* a >= b なら 1+(a-b)/c を出力、そうでなければ、何もしない (0)
* 真 (a-b)/c=a/c (b=0)
* a >= b = { 偽 何もしない (b<>0 かつ a=0)
* (a-1)>=(b-1) (b<>0 かつ a<>0)
*/
void one_sub_div ( char *a, char *b, char *c ) {
if ( !strcmp ( b, "" ) ) { /* b = 0 */
/* b = 0 の時 : 1+(a-b)/c = 1+a/c */
/* +1 */
putchar ( '0' );
/* a/c */
one_div( a, c );
} else if ( !strcmp ( a, "" ) ) { /* a = 0 */
/* a = 0, b > 0 の時 : (a-b)/c = 0 */
/* do nothing */
} else {
/* a, b > 0 の時 : 1+(a-b)/c = 1+((a-1)-(b-1))/c */
one_sub_div ( a+1, b+1, c );
}
}
/*
* 一進数の割り算
*/
void one_div ( char *a, char *b ) {
if ( !strcmp ( b, "" ) ) {
printf ( "0 で割る事はできません\n" );
} else if ( !strcmp ( a, "" ) ) { /* a = 0 の時は 0 */
/* do nothing */ /* a/b = 0 */
} else {
/* 0 ( a < b )
a/b = {
1+(a-b)/b ( a >= b )
*/
one_sub_div ( a, b, b );
}
}
/*
* main
*/
int main ( void ) {
/* 5/2 = ? */
one_div ( "00000", "00" );
printf ( "\n" );
/* 12/3 = ? */
one_div ( "000000000000", "000" );
printf ( "\n" );
return 0;
}
#include <stdio.h>
#include <string.h>
void rec(char *arg) {
if ( !strcmp ( arg, "" ) ) { /* 引数の値が最小になったら */
/* 何もしない */ /* 終わり */
} else {
/* ここから */
printf ( arg );
printf ( "\n" );
/* ここまでの部分が「繰り返される」 */
rec ( arg + 1 ); /* 自分自身を呼び出す */
/* 引数の値が「小さく」なる */
}
}
int main(void) {
rec ( "abc" ); /* 長さ 3 の文字列 */
return 0;
}
#include <stdio.h>
/*
二つの一進法で表現された数の和を一進法で表したい
one_add( char *a, char *b )
one_add( "111", "11" ): 3 + 2 => 5 ( "11111" );
*/
void one_add ( char *a, char *b ) {
printf ( a );
printf ( b );
}
int main(void) {
/* 3 + 2 = 5 */
one_add ( "111", "11" );
printf ( "\n" );
/* 7 + 4 = 11 */
one_add ( "1111111", "1111" );
printf ( "\n" );
return 0;
}
#include <stdio.h>
#include <string.h>
/*
二つの一進法で表現された数の積を一進法で表したい
one_mul( char *a, char *b )
one_mul( "111", "11" ): 3 * 2 => 5 ( "111111" );
0 ( a = 0 の時 a * b = 0 * b = 0 )
a * b = {
(a - 1) * b + b ( a <> 0 の時 )
a * b = ( ( a - 1 ) + 1 ) * b
= (a - 1) * b + b
*/
void one_mul ( char *a, char *b ) {
if ( !strcmp ( a, "" ) ) {
/* 0 なので何も出力しない */
} else {
/* ((a - 1) * b) + b */
one_mul ( a + 1, b ); /* (a-1)*b を出力 */
printf ( b ); /* +) b を出力 */
/* -------- */
/* (a-1)*b+b = a*b が出力 */
}
}
int main(void) {
/* 3 * 2 = 6 */
one_mul ( "111", "11" );
printf ( "\n" );
/* 7 * 4 = 28 */
one_mul ( "1111111", "1111" );
printf ( "\n" );
return 0;
}
#include <stdio.h>
#include <string.h>
/*
二つの一進法で表現された数の差を一進法で表したい
引かれる数は、引く数より小さくなくない(結果が一進法で表現可能)
one_sub( char *a, char *b )
one_mul( "111", "11" ): 3 - 2 => 1 ( "1" );
a ( b = 0 の時 a - b = a - 0 = a )
a - b = {
(a-1) - (b-1) ( a <> 0 の時 )
*/
void one_sub ( char *a, char *b ) {
if ( !strcmp ( b, "" ) ) { /* b = 0 */
printf ( a ); /* a - b = a */
} else {
/* a - b = (a-1) - (b-1) */
one_sub ( a+1, b+1 ); /* (a-1)-(b-1) */
}
}
int main(void) {
/* 3 - 2 = 1 */
one_sub ( "111", "11" );
printf ( "\n" );
/* 7 - 4 = 3 */
one_sub ( "1111111", "1111" );
printf ( "\n" );
return 0;
}
#include <stdio.h>
#include <string.h>
/*
一進法で表現された数が偶数か奇数かを判定したい
偶数 ( a = 0 )
偶数 a = {
奇数 a - 1 ( a <> 0 )
奇数 ( a = 0 ) <= 1 引いた後
奇数 a = {
偶数 a - 1 ( a <> 0 )
奇数と偶数が互いに呼び合っている
間接的に奇数は自分自身を(偶数を経由して..)呼び出している
=> 再帰呼び出しになっている
!! 偶数も同様
*/
void one_even ( char *a ) {
if ( !strcmp ( a, "" ) ) { /* a = 0 */
printf ( "偶数" ); /* a は偶数 */
} else {
one_odd ( a+1 ); /* a-1 が奇数なら a は偶数 */
}
}
void one_odd ( char *a ) {
if ( !strcmp ( a, "" ) ) { /* a-1 = 0 */
printf ( "奇数" ); /* a は奇数 */
} else {
one_even ( a+1 ); /* a-1 が偶数なら a は奇数 */
}
}
int main(void) {
/* 3 : 奇数 */
one_even ( "111" );
/*
=>
a <- "111"
if ( !strcmp ( a, "" ) ) {
printf ( "偶数" );
} else {
one_odd ( a+1 );
}
=>
if ( !strcmp ( "111", "" ) ) {
printf ( "偶数" );
} else {
one_odd ( "111"+1 );
}
=>
one_odd ( "11" );
=>
a <- "11"
if ( !strcmp ( a, "" ) ) {
printf ( "奇数" );
} else {
one_even ( a+1 );
}
=>
if ( !strcmp ( "11", "" ) ) {
printf ( "奇数" );
} else {
one_even ( "11"+1 );
}
=>
one_even ( "1" );
=>
a <- "1"
if ( !strcmp ( a, "" ) ) {
printf ( "偶数" );
} else {
one_odd ( a+1 );
}
=>
if ( !strcmp ( "1", "" ) ) {
printf ( "偶数" );
} else {
one_odd ( "1"+1 );
}
=>
one_odd ( "" );
=>
a <- ""
if ( !strcmp ( a, "" ) ) {
printf ( "奇数" );
} else {
one_even ( a+1 );
}
=>
if ( !strcmp ( "", "" ) ) {
printf ( "奇数" );
} else {
one_even ( a+1 );
}
=>
printf ( "奇数" );
=>
「奇数」と表示される
*/
printf ( "\n" );
/* 8 : 偶数 */
one_even ( "11111111" );
printf ( "\n" );
return 0;
}
#include <stdio.h>
#include <string.h>
void rec(char *arg) {
printf ( arg );
printf ( "\n" );
printf ( arg + 1 );
printf ( "\n" );
printf ( arg + 2 );
printf ( "\n" );
}
int main(void) {
rec ( "abc" ); /* 長さ 3 の文字列 */
/* あらかじめ、三行である事がわかっていれば.. */
rec ( "12345" ); /* 長さ 3 でなくすると、ダメ */
return 0;
}
前回(2021/05/14)の内容
関数の再帰的な定義
=> 関数を定義するときに、
その内容の中で、自分自身を呼び出す関数
=> (結果として..)命令の一部を「繰り返す」事になる
三つ制御構造
順接
命令を並べる
命令が並べた順に実行される
例: printf ( "a" ); printf( "b" ); => ab
条件分岐
if 構文を使う
条件によって、二つ命令のどちか一方が実行される
例: if ( !strcmp( arg, "" ) ) { printf ( "空っぽ\n" ); } else { printf ( "中身がある\n" ); }
if ( !strcmp( arg, "" ) ) {
printf ( "空っぽ\n" );
} else {
printf ( "中身がある\n" );
}
=>
arg が空文字列("")の時、
「空っぽ」と出力される
そうでない時、
「中身がある」と出力される
繰り返し
関数の再帰呼び出し(関数再帰的定義)
関数の命令の一部が繰り返される
例: p-001.c
=>
(ちいさな/基本的な/すでに作れた)命令を
組み合わせて、新しく、(複雑な/特殊な/これから作られる)命令を作る仕組み
!! 順接, if 構文, 再帰呼び出し、そのものは命令じゃない
!! => 命令を組み合わせるための仕組み(表現)
再帰的定義と数学的帰納法
数学では、たくさん、数学的帰納法を利用した証明を学んでいる
「証明(の記述)」から、「プログラム」が生成(自動変換)できる事がわかっている
=> 証明をしっている人は、プログラムが書ける
一進数
1 を n 個数並べて、自然数 n を表現する数の表現方法
普通の十進表現 一進数
0 <空>
1 1
2 11
3 111
4 1111
一進数を使って、数が表現できる
!! これまでやった命令(関数)は printf => 文字列を出力する事しかしない
一進数の計算やってみる
一進数の足し算
一進数の掛け算
一進数の引き算
一進数で計算ができる
=> 万能である ( 計算機で計算できるものは、実は、
一進数と、printf 命令 [と三つの制御構造] だけでできる );
判断もできる
例: 一進数が偶数か奇数かを判定する
[2021/05/21]
パズルを解く
ハノイの塔
有名なパズル
=> C のプログラム
砂漠の旅行の問題
現在地点 S にいる旅人が、幅 N の砂漠を渡って、地点 G に行きたい
S 1 2 3 ... 9 G
^
1 升移動する場合は、食料を 1 単位消費する
砂漠の途中で保持する食料が 0 になったら移動ができなくなる
=> 死んでしまう (ゲームオーバー)
G に達した時点で、食料が 0 になっていてもよい
旅人が持つ事ができる食料は最大で 3 つ迄である
S には、食料が無限にあり、いくつでも補給できる
最初の状態では、砂漠には、食料はない
旅人は、食料を持っていれば、砂漠に食料を置く事ができる
砂漠に置く事ができる食料の個数は最大 2 個である
旅人は、砂漠に食料があり、保持数が 3 より少ないなら食料を拾う事ができる
!! 最大三つしかもてない
<スタート>
0 0 0 0
S 1 2 3 4 G
@
0
食料を三つ拾う
0 0 0 0
S 1 2 3 4 G
@
3
右に移動
0 0 0 0
S 1 2 3 4 G
@
2
食料を 1 つ置く
1 0 0 0
S 1 2 3 4 G
@
1
左移動
1 0 0 0
S 1 2 3 4 G
@
0
三個拾う
1 0 0 0
S 1 2 3 4 G
@
3
右に移動
1 0 0 0
S 1 2 3 4 G
@
2
置く
2 0 0 0
S 1 2 3 4 G
@
1
左
2 0 0 0
S 1 2 3 4 G
@
0
三個拾う
2 0 0 0
S 1 2 3 4 G
@
3
右に移動
2 0 0 0
S 1 2 3 4 G
@
2
拾う
1 0 0 0
S 1 2 3 4 G
@
3
右に移動
1 0 0 0
S 1 2 3 4 G
@
2
置く
1 1 0 0
S 1 2 3 4 G
@
1
左
1 1 0 0
S 1 2 3 4 G
@
0
拾う
0 1 0 0
S 1 2 3 4 G
@
1
左
0 1 0 0
S 1 2 3 4 G
@
0
三個拾う
0 1 0 0
S 1 2 3 4 G
@
3
右
おいて
左
三個拾う
1 1 0 0
S 1 2 3 4 G
@
3
右
1 1 0 0
S 1 2 3 4 G
@
2
拾う
0 1 0 0
S 1 2 3 4 G
@
3
右
0 1 0 0
S 1 2 3 4 G
@
2
拾う
0 0 0 0
S 1 2 3 4 G
@
3
右
0 0 0 0
S 1 2 3 4 G
@
2
右
0 0 0 0
S 1 2 3 4 G
@
1
右
0 0 0 0
S 1 2 3 4 G
@
0 ゴール !!
==
再帰の考え方
例: 三角形の描画 (cf. p-001.c)
[目的]
abc
bc
c
printf は使えるので、1 行分の出力は簡単
=> 一挙に全体を書く事は簡単でない
ましてや、サイズが固定でないと、工夫が必要
どんな工夫をするか ?
=> できるところからやる
rec( "abc" );
=>
...
=>
abc
bc
c
求めたい結果のうち、
すぐにできるものと、残り物にわける
例:
abc
bc
c
|
v
abc <= すぐできる [A]
bc <= 後回しに [B]
c
[A] printf ( "abc" );
printf ( "\n" );
[B]
bc
c
ここで、もし、
rec( "abc" ); => abc
bc
c
となるのであれば、
rec( "bc" ); => bc
c
となるだろう
rec( "abc" );
=>
printf ( "abc" );
printf ( "\n" );
rec( "bc" );
!! 一般に
!! n個
!! a....z
!! b...z
!! ..
!! z
!! の時、一行目と残りを分ける
!! a....z => printf
!!
!! n-1個
!! b...z => 再帰呼び出し
!! ..
!! z
rec( "abc" );
=>
printf ( "abc" );
printf ( "\n" );
rec( "bc" );
!! 命令の中で、計算するまえの状況をつくって、
!! 同じ値(同じ変数に入っているもの)で表現するようにする
rec( "abc" );
=>
printf ( "abc" );
printf ( "\n" );
rec( "abc" + 1 );
!! 共通の値を保持する変数を用意し、値を変数におきかえる
!! => 式の計算の一般化
rec( str );
=>
printf ( str );
printf ( "\n" );
rec( str + 1 );
!! 引数の値が、小さくなっているところをみつけて、
!! その値が、最小値になるパターンを考え、
!! 最小値の時には、再帰呼び出ししない
rec( str );
=>
if ( !strcmp( str, "" ) ) {
} else {
printf ( str );
printf ( "\n" );
rec( str + 1 );
}
!! 再帰的定義のプログラムにする
void rec ( char *str ) {
if ( !strcmp( str, "" ) ) {
/* Do Nothing */
} else {
printf ( str );
printf ( "\n" );
rec( str + 1 );
}
}
一般論
問題を解くときに、それが困難ならば、分割しなさい
分割した結果、できる事があれば、それをやり、
残りは、もう一度考える
最初の問題
=> 解く
分割する
最初の問題 => 部分問題 + 部分問題
もし、分割した問題がとければ、それを行い、
残りは、改めて解く
! 再帰構造になっている
!!! 運が良い
!!! => 残りが、元の問題の縮小版になっている
!!! => 再帰で片が付く
==
ハノイの場合
3 ハノイ (1) => (3)
1|1 | |
22|22 | |
333|333 | |
---+--- ---+--- ---+---
(1) (2) (3)
| | |
| 1|1 |
333|333 22|22 |
---+--- ---+--- ---+---
(1) (2) (3)
| | |
| 1|1 |
| 22|22 333|333
---+--- ---+--- ---+---
(1) (2) (3)
| | 1|1
| | 22|22
| | 333|333
---+--- ---+--- ---+---
(1) (2) (3)
=>
* 1 を 333 の上からどかす
22
=> 1 を (1) -> (2)
22
<= もとの問題の縮小版
=> 再帰が使える
* 333 を (1) -> (3)
* 1 を 333 の上にのせる
22
=> 1 を (2) -> (3)
22
Hanoi(3)
Hanoi(2)
3 を移動
Haoni(2)
==
1 1 1 1 .. 0
S 1 2 3 4 .. k .. N G
@
3
0 0 0 0 .. 0
S 1 2 3 4 .. k .. N G
@
2
砂漠の食料を拾いながら移動する
所持している食料をへらさず S から k まで移動するには、
1 から k - 1 に食料が 1 つなければならない
移動するたびに、一つ消費する
所持している食料をへらさず S から k まで移動して S に戻るには、
1 から k - 1 に食料が 2 つなければならない
移動するたびに、一つ消費する
2 2 2 2 .. 0
S 1 2 3 4 .. k .. N G
@
3
1 1 1 1 .. 0
S 1 2 3 4 .. k .. N G
@
2
0 0 0 0 .. 0
S 1 2 3 4 .. k .. N G
@
1
Sで食料を三個もったをへらさず k に食料を一つおくには
1 から k - 1 に食料が 2 つなければならない
移動するたびに、一つ消費する
1 ? k まで食料をおくには
k におく
k-1 におく
...
1 におく
3 におく
1 ? 2 に 2 にこずつおく
1 ? 2 に 1 こずつ置くを二回
1 ? 2 に一個ずつ置く
2 におく
1 におく <= 再帰
課題プログラム内の「/*名前:ここ*/」の部分を書き換え「/*この部分を完成させなさい*/」の部分にプログラムを追加して、プログラムを完成させます。
Download : 20210521-01.c
/*
* 20210521-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;
}
$ ./20210521-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 に移動 $
Download : 20210521-02.c
/*
* 20210521-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;
}
$ ./20210521-02-QQQQ.exe 4 まで行く 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ拾う 一つ進む 一つ進む 一つ進む 6 まで行く 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ拾う 一つ進む 一つ置く 一つ戻る 一つ戻る 一つ拾う 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ拾う 一つ進む 一つ置く 一つ戻る 一つ戻る 一つ拾う 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ拾う 一つ進む 一つ拾う 一つ進む 一つ置く 一つ戻る 一つ戻る 一つ拾う 一つ戻る 一つ拾う 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ拾う 一つ進む 一つ置く 一つ戻る 一つ戻る 一つ拾う 三つ拾う 一つ進む 一つ置く 一つ戻る 三つ拾う 一つ進む 一つ拾う 一つ進む 一つ拾う 一つ進む 一つ拾う 一つ進む 一つ進む 一つ進む $