前回(2020/05/22)の内容 再帰的に関数を定義する 関数定義の中で、自分自身を呼び出す事 f() { f(); f(); } f() => f() => f() => f() f() => f() => f() ... f() が無限に増殖して、置き換えが終わらない !!! 再帰呼び出しを無制限に行うと、無限の展開になり !!! 意味が定まらない !!! <= 再帰呼び出しの「マナー」が重要 再帰呼び出しのマナー 再帰呼び出しをする場合としない場合に分ける => if 構文が必須 引数 ( if 構文の中の条件式で利用する ) 再帰的に定義されている関数を呼び出すとき 引数の値が同じであれば、振る舞いも同じになる 再帰呼びだしをするときに、引数の値が変換する必要がある 最終的に、その変換を繰り返すと、再帰しない条件を満たすようになる必要がある 例: 終了する条件(再帰しない条件) => 引数の文字列の長さが 0 => 引数が空文字列("")になる 引数の変換規則 => 文字列の長さを一つ減らす ( +1 ) !! 「文字列の長さ」は、0 以上 => 任意の長さの文字列を与えても その長さを減らしてゆけば、 必ず 0 になる 事が保証されている ので、 引数の文字列の長さが 0 となり、 再帰呼び出しをしない場合が必ず起きる 事が、保証される。 一般的に 引数が有限の値をもち、 その値を減らす事が可能で 最低値を終了(再帰呼び出しをしない)条件とすれば、 無限ループをしない再帰的定義関数が作れる <<現状>> 終了条件は、「引数の文字列が空である」 引数の操作は、「引数の文字列の長さを 1 減らす(+1 する)」 の一択 # ほかのパターンもあるが、これだけは、まず覚える <<復習>> 関数定義と関数呼び出しの関係 => 「関数呼び出し」の表現が 「関数定義の本体」の表現に置き換わる 関数定義の中で、 他の関数呼び出しが可能 => 「置き換え」が何度も行われる 複数の関数定義と関数呼び出しを与わせて、 main 関数から、関数を呼び出すと 「置き換え」が何度もおきて、 最終的に、既存の関数(printf)呼び出しに置き換わる up( "abc") => .. => printf ( "\n" ); printf ( "c\n" ) printf ( "bc\n" ); printf ( "abc\n" ); => c bc abc 何度か、置き換えが行われて、最終的に、 既存の命令(関数呼び出し)の列に代わる # 暗黙の内に # 「置き換えがいつかは終わる事」 # を仮定 # <= 置き換えが終わらなければ、どの関数をどれだけ実行してよいかわからない # プログラムの意味(どの関数を実行するか?)が定まらない # もし、関数の定義をするときに、 # 既存の関数 ( 基本の関数か、定義済の関数 ) # しか、本体で呼び出さなければ、 # 置き換えが有限である事はすぐにわかる # # 置き換えに関する構造帰納法で示すことができる プログラムを作成する C 言語では、main 関数を定義する 基本命令の実行 ( printf しか知らない ) やりたいこと 基本命令の列として考える 基本命令をいくつか、組み合わせて関数を作り 最終的に main 関数が、組み合わせの組み合わせとして定義さればよい 「分割統治法」を利用して、 簡単な関数に分割してゆく !! 分割をする事により、問題が簡単になる 分割 => それを統合する <= 統合ができるように分割する 統合の仕方に従って分割すると便利 三つの基本構文 命令文を「組み合せ」て、新しい命令を作る仕組み => 命令の統合の仕方 順接 : 命令を並べる => 命令を、並べた順に実行する 条件分岐 : if 構文 => 条件によって二つの命令の何方か一方を実行する 繰返し : 再帰 => 条件が成立するまで命令を繰り返し実行する !! 統合の仕方を逆を考える事によって、 !! 分割ができる 万能性 任意のプログラムは、三つの基本構文を (有限回) 適用して作れる # 任意の問題が、この三つの統合の逆の分割によって、 # 最終的に、簡単に解ける問題に分割できる # 事が、保証されている [2020/05/29] 再帰的定義と数学的帰納法 再帰的定義 関数 f() を定義する本体に f() 自身を含める仕組み 「繰返し」を表現 最低一つの引数があり、 引数の値が「小く」なり、 「最小」で終了になるように定義 例 : 文字列を引数して、その「文字列の長さ」に着目 そうしないと、 「無限ループ」になってしまう 数学的帰納法 自然数に関する命題 P(n) (n は任意の自然数) 例: P(n) : n には、必ず n より大きい自然数が存在する 任意の自然数に関する命題の証明をどのように行うか ? P(0), P(1), P(2), ... <= 無限個の命題を証明する必要がある => すべてを確かめる事はできない => 数学的帰納法 有限な証明(記述)で、無限個の命題の証明(とみなす)仕組み # 数学的帰納法の原理 # 原理:これこれの形をした証明は、こうゆう証明とみなす # 背理法 : 命題 P()の否定を仮定して、矛盾がみちびければ、 # P() が成立するとみなす原理 # # 「普通の」式の変形の証明 # a^2+2ab+b^2 = (a+b)^2 # a^2+2ab+b^2 = a^2+ab+ab+b^2 # = a(a+b)+(a+b)b # = a(a+b)+ b(a+b) # = (a+b)(a+b) # = (a+b)^2 任意の自然数 n に関する命題 P(n) を証明するための「枠組み」 # 帰納法に基づく証明 次の「(証明)手順」で、 「P(n) が、任意の自然数 n で成立する事」を示す [Start Step] 「P(1) が成立」する事を示す [Next Step] 「P(k) が成立」すれば、「P(k+1)が成立」する事を示す 上記の 2 つと 「数学的帰納法の原理」から、 「P(n) の成立」を示す 例 P(n) : n より大きな自然数が存在する n=0) 1 は、0 より大きいので、0 より大きい自然数が存在する n=k の場合を仮定して n=k+1 の場合を示す) n=k の時に命題 P(n) = P(k) が成立するので、 k より大きな自然数 k' が存在する k < k' よって、 k + 1 < k' + 1 となる ここで、k'+1 は自然数なので k + 1 より大きな自然数 (k'+1)が存在する P(k+1) が成立する。 なので、 P(k)を仮定してP(k+1)を示す 事ができた。 n=0 の時成立し、n=k を仮定して n=k+1 を示す事ができたので、 数学的帰納法(の原理)により、 命題 P(n) は任意の自然数 n について成立する。 再帰的定義と数学的帰納法の関係 再帰的定義された関数の性質は、 数学的帰納法を適用して、証明しやすい α (n=0 の時) f(n) = { f(n-1) の式 (n>0 の時：再帰的定義) P(f(n)) : P は、関数 f の性質 任意の自然数 n に対してい P(f(n)) を示したい場合 帰納法を利用して、 [Start Step] P(f(0)) = P(α) を示す [Next Step] P(f(k+1)) = P(f(n-1) の式)を示す をそれぞれ利用するだけ 再帰的定義された関数の性質は、数学的帰納法で証明しやすい 再帰的定義には、[Start Step] と [Next Step] がそのまま書いてある 数学的帰納法の証明をする時に、その記述がそのまま利用できる P(f(n)) が 任意の自然数 n で成立する f(n) の性質が P である P(y) となる y を計算する y=f(n) を決めている => ある条件 P を示す数を計算する関数 f を定めている 数学的帰納法の証明があると、 その証明記述から、その性質をもったものを計算する関数が、 再帰的定義を利用して、定義可能 帰納法の証明の [Start Step] と [Next Step] を抜き出せばよい [一進数] n 進数 ( n > 1 ) 自然数の表現 ( 大学の数学では、自然数は 0 から始める事が多い ) 0,1,2,..,9,10,11,..,99,100,.. 零、一、..九、十、...、百、千 I,II,III,IV,V,..X,.. n 個のものが集ったら桁上げをする仕組み 1,2,..,9 の次は 10 ( 十 : 1 と 0 ) 桁(数字の位置)によって、意味を変えている 0 という数字(何もない)が必要なのは、 桁を示すために、必要 !! そろばんは、0 がない !! 100 => 1 !! 10 => 1 !! 筆算では、桁の位置を表現するために 0 という数字が必要 例 1 : 十進数 => 普段使っている数の仕組み 例 2 : ニ進数 => コンピュータの世界で利用される数の仕組み 0, 1, 10, 11, 100, .. 0 => 何もない / 1 => 数(一つある) 0 〜 n-1 を表す「n 個の『数字』」を利用する 最低 0 と 1 が必要なので、二進法は、数字が最小の表現(桁) それ以外は「桁」を利用して表現 一進数 ( n 進数のノリではあるが、全然異る原理 ) 数字の 1 のみを利用する 1 の個数で数を表現する 十進数 ニ進数 一進数 0 0 無 1 1 1 2 10 11 3 11 111 4 100 1111