前回(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 におく <= 再帰