/*
* 20200522-02-QQQQ.c
* 引数の文字列の長さに対するフィボナッチ数だけの文字 "*" を出力する関数
*
* 0 ( n = 0 の時 )
* fib(n) = { 1 ( n = 1 の時 )
* fib(n-1)+fib(n-2) ( その他 [n > 1 の時] )
*
fib(0) = 0
fib(1) = 1
fib(2) = fib(2-1) + fib(2-2)
= fib(1) + fib(0)
= 1 + 0
= 1
fib(3) = fib(3-1)+fib(3-2)
= fib(2) + fib(1)
= 1 + 1
= 2
fib(0), fib(1), fib(2), ...
0, 1, 1, 2, 3, 5, 8, 13, ...
[考え方のポイント]
フィボナッチ関数の定義にそって、
C 言語の関数定義を行えばよい
"" ( "" の時 )
f("123") = { "*" ( "*" <-> "*" + 1 = "" の時 )
f("123"+1)+fib("123"+2) ( その他 ["", "*" でもない時] )
*/
#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 */
printf ( "*" );
} else { /* その他 ( n の長さが 1 より長い ) */
/* 再帰呼出しを二度行う */
/* 一度目は、1 だけ長さを減らす */
c_fibnacci ( n + 1 );
/* ニ度目は、2 だけ長さを減らす */
c_fibnacci ( n + 2 );
}
}
/*
* main
*/
int main ( void ) {
/* fib(4) = 3 回だけ「*」を出す */
c_fibnacci ( "****" );
printf ( "\n" );
/* fib(7) = 13 回だけ「*」を出す */
/*
** この部分を完成させなさい
*/
printf ( "\n" );
return 0;
}
#include <stdio.h>
/*
関数定義と関数呼び出し
関数呼び出しによって、
関数定義の本体の部分が呼び出される
*/
void f(void) { /* 関数定義 */
printf ( "Hello, World\n" ); /* 他の関数を呼び出す */
}
void g(void) {
f();
f();
}
int main(void) {
f(); /* 関数呼び出し */
/* 関数の定義部分を実行しなさい */
/*
f()
関数 f の定義が探される
f()
=> printf ( "Hello, World\n" );
printf ( "Hello, World\n" );
*/
g();
/*
g() =>
f()
=> printf
f()
=> printf
g() は結局
printf 二回に置き換わる
*/
return 0;
}
/*
main()
+- f()
+- printf
+- g()
+- f()
+- printf
+- f()
+- printf
main()
+- printf
+- printf
+- printf
*/
#include <stdio.h>
void f(void) {
printf ( "Hello, World\n" );
}
void g(void) {
f();
f();
}
int main(void) {
f();
g();
return 0;
}
/*
main()
+- printf
+- printf
+- printf
=>
main()
+- f()
+- printf
+- f()
+- printf
+- f()
+- printf
=>
main()
+- f()
+- printf
+- g()
+- f()
+- printf
+- f()
+- printf
プログラムを作成する
基本命令を並べるだけ(順接の仕組み)
基本命令を組み合わせて関数を作り
関数呼び出しの組み合わせでもよい
もし、
目的とする関数が
いつも同じ振る舞いであれば、
単に基本命令を「順接」だけでよい
条件によって、異なる振る舞いをする
if 構文や再帰を利用必要がある
プログラムを一度に作るのは大変
例 : 100 以上、プリントする
=> 100 行の命令を書けばよい
<= 大変
関数を定義する
=> プログラムの記述を減らす事ができる
=> 大きな家をいきなり作るのは大変
まず、土台を作る
つぎに、柱をたて
屋根をあげたり、かべを作り
窓や、ドアを備え付ける
内装をしっかり
全体を、いくつかの部分に分割し、
分割したもの(もとより簡単になっている)を実現する
もし、分割したものも複雑なら、これをさらに分割する
問題を解決するために、
その問題をより簡単な問題に分割してから解くという考え方
分割統治法
関数を定義して利用する
プログラムを作成するときに「分割統治法」を適用している
*/
#include <stdio.h>
/*
再帰を無制限に利用すると、
無限ループになる
*/
void f(void) {
printf ( "Hello, World\n" );
f(); /* 再帰呼び出し */
}
int main(void) {
f();
return 0;
}
/*
main
+- f
+- printf
+- f
+- printf
+- f
+- printf
+- f
....
=>
main
+- printf
+- printf
+- printf
.... 無限に続く
*/
#include <stdio.h>
#include <string.h>
/*
再帰を無制限に利用すると、
無限ループになる
*/
void f(char *n) {
if ( !strcmp ( n, "" ) ) {
printf ( "End\n" ); /* 再帰呼び出しをしない場合 */
} else {
printf ( n );
f( n ); /* 再帰呼び出しをする場合 */
}
}
int main(void) {
f( "abc\n" );
return 0;
}
/*
main
+- f
+- printf
+- f
+- printf
+- f
+- printf
+- f
....
=>
main
+- printf
+- printf
+- printf
.... 無限に続く
*/
#include <stdio.h>
#include <string.h>
/*
再帰を無制限に利用すると、
無限ループになる
if 構文と、引数の処理の組み合わせで、
お行儀のよい ( 無限ループしない ) 再帰的定義関数が作れる
*/
void f(char *n) {
if ( !strcmp ( n, "" ) ) { /* 引数の文字列の長さが 0 */
printf ( "End\n" ); /* 再帰呼び出しをしない場合 */
} else {
printf ( n );
f( n + 1 ); /* 再帰呼び出しをする場合 */
/* 引数の文字列の長さが 1 減る */
}
}
int main(void) {
f( "abc\n" );
return 0;
}
/*
main
+- f ( "abc\n" );
+- printf ( "abc\n" );
+- f ( "bc\n" );
+- printf ( "bc\n" );
+- f ( "c\n" );
+- printf ( "c\n" );
+- f ( "\n" );
+- printf ( "\n" );
+- f ( "" );
+- printf ( "End\n" );
=>
main
+- printf ( "abc\n" );
+- printf ( "bc\n" );
+- printf ( "c\n" );
+- printf ( "\n" );
+- printf ( "End\n" );
*/
#include <stdio.h>
#include <string.h>
/*
繰り返しのイデオム(成形句:パータン)
関数 f() を、引数 n (文字列) の長さだけ繰り返す
関数 fn(n) は、次のような、再帰的定義関数として定義可能
void fn(char *n) {
if ( !strcmp ( n, "" ) ) {
} else {
f();
fn ( n + 1 );
}
}
*/
void f(void) {
printf ( "こんにちは\n" );
}
void fn(char *n) {
if ( !strcmp ( n, "" ) ) { /* 引数の文字列の長さが 0 */
/* なにもしない */
} else {
f(); /* 繰り返したい関数呼び出し */
fn( n + 1 ); /* 再帰呼び出し */
/* 引数の長さを一つ減らす */
}
}
int main(void) {
fn( "abc\n" );
return 0;
}
/*
main
+- f ( "abc\n" );
+- printf ( "abc\n" );
+- f ( "bc\n" );
+- printf ( "bc\n" );
+- f ( "c\n" );
+- printf ( "c\n" );
+- f ( "\n" );
+- printf ( "\n" );
+- f ( "" );
+- printf ( "End\n" );
=>
main
+- printf ( "abc\n" );
+- printf ( "bc\n" );
+- printf ( "c\n" );
+- printf ( "\n" );
+- printf ( "End\n" );
*/
前回(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
課題プログラム内の「/*名前:ここ*/」の部分を書き換え「/*この部分を完成させなさい*/」の部分にプログラムを追加して、プログラムを完成させます。
Download : 20200529-01.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 */
fib ( n + 1 ); /* fib(n-1) + fib(n-2) */
/*
** この部分を完成させなさい
*/
}
}
int main ( void ) {
/* fib 3 */
fib ( "000" );
printf ( "\n" );
/* fib 10 */
/*
** この部分を完成させなさい
*/
printf ( "\n" );
return 0;
}
$ ./20200529-01-QQQQ.exe 00 0000000000000000000000000000000000000000000000000000000 $
Download : 20200529-02.c
/*
* 20200529-02-QQQQ.c
* 一進数の階乗
*/
#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 */
/*
** この部分を完成させなさい
*/
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 );
}
}
/*
* main
*/
int main ( void ) {
/* fac(3) */
fac ( "000" );
printf ( "\n" );
/* fac(5) */
/*
** この部分を完成させなさい
*/
printf ( "\n" );
return 0;
}
$ ./20200529-02-QQQQ.exe 000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 $