再帰方程式の理解度確認の解答
再帰呼び出しと再起方程式の資料の中の「理解度確認」の解答
解答
pyraをループで
// pyra() をループで書いたら。
int pyra( int x ) {
int ans = 0 ;
for( int i = 1 ; i <= x ; i++ )
ans += i * i ;
return ans ;
}
2分探索法を再帰で
// 2分探索を再帰で書いたら
int find( int array[] , int L , int R , int key ) {
if ( R == L ) {
return 0 ; // みつからない
} else {
int M = (L + R) / 2 ;
if ( array[ M ] == key ) // みつかった
return 1 ;
else if ( array[ M ] > key ) // 左側にある - 末尾再帰
return find( array , L , M , key ) ;
else // 右側にある
return find( array , M+1 , R , key ) ;
}
}
このプログラムでは、検索する範囲がLとRで与えられ、この範囲の幅が再帰が呼び出される毎に半分になっていく。
であれば、処理時間は対象となるデータ件数 N = R – L によって、処理時間は変化するので、T(N) で考えると、(ただし途中でデータが見つからない最悪の場合で式を示す)
データ件数0件では、if,R==L,return 0の処理を行う。このため、以下の様な再帰方程式の細小時での処理時間は、
… ①
となる。(find(件数=1)の次は必ずfind(件数=0)が実行されるのででも良い。)
Nは整数という条件をつけないと、N=1/2, 1/4, 1/8…で止まらない…と勘違いする人もいるし、データ件数が1件になったら再帰がとまると考えた方が分かりやすいので、の方が都合がいいかな…
データが1以上の時で、対象データが L..Mの範囲にあるのなら、再帰の時に対象データ件数は半分になるから、if,R==L,else,if,array[M]==key,else-if,array[M]>keyの処理時間(Tb) と find(…,L,M,…) の処理時間を要するので、次の式となる。
… ②
一方、(M+1)..Rの範囲にあるのなら同様に、if,R==L,else,if,array[M]==key,else-if,array[M]>key,elseの処理時間(Tc)と、find(…,M+1,R,…) の処理時間なので、
… ③
となる。ただ、処理時間の見積もりでは厳密な分析が求められないので、(N-1)/2 だと一般式が複雑になるので、N/2 で考える。さらにTbとTcの処理時間は少しの時間の違いだし、確率1/2でTbとTcのどちらかを実行するので、その平均時間をTbで表すことにすれば、③は②とほぼ同じと見なすことができるので、再帰方程式は①と②で良い。
fib()の再帰方程式
再帰のフィボナッチ数 fib() の処理時間に相応しい再帰方程式は、xの値(Nとする)が2以下の時は、return を実行するだけ。3以上の時は、if,else,return,+ の処理時間と、fib(x-2)の処理時間、fib(x-1)の処理時間を要する。
よって、再帰方程式は、以下の式となる。
これを代入法で一般式を求めると、T(N)=fib(N-2)×Tb+fib(N+1)×Ta かな？よって、再帰のfib()の処理時間は、フィボナッチ数に比例する。ちなみに、フィボナッチ数はピネの公式で一般項が示されているので、処理時間のオーダーは、次式となる。
コンピュータとN進数
3年の情報制御基礎の授業の一回目。この授業では、情報系以外の学生も受講することから、基礎的な共通的な話題を中心に説明を行う。
情報制御基礎のシラバス
情報制御基礎では、ここに上げたシラバスに沿って授業を行う。
基本的に、センサーから読み取ったデータを使って動くシステムを作る場合の、知識ということでアナログ量・デジタル量の話から、移動平均やデータ差分といった数値処理や、そこで求まった値を制御に用いるための基礎的な話を行う。
コンピュータと組み込み系
最近では、コンピュータといっても様々な所で使われている。(1)科学技術計算用の大型コンピュータやインターネットの処理を行うサーバ群、(2)デスクトップパソコン、(3)タブレットPCやスマートフォンのような端末、(4)電化製品の中に収まるようなワンチップコンピュータなどがある。
(1) サーバ：ブレードサーバ
(4) ワンチップコンピュータ：PIC
身近で使われている情報制御という点では、(4)のような小型のコンピュータも多く、こういったものは組み込み型コンピュータとも呼ばれる。しかし、こういったコンピュータは、小さく機能も限られているので、
- 組み込み系では、扱える数値が8bit や 16bit といった精度しかなかったり、
- 複雑な計算をするには、処理時間がかかったりする
ため、注意が必要である。
この情報制御基礎の授業では、組み込み系のコンピュータでも数値を正しく扱うための知識や、こういった小さいコンピュータで制御を行うことを踏まえた知識を中心に説明を行う。
2進数と10進数
コンピュータの中では、電圧が高い/低いといった状態で0と1の2通りの状態を表し、その0/1を組み合わせて、大きな数字を表す(2進数)。
練習として、2進数を10進数で表したり、10進数を2進数に直してみよう。
N進数を10進数に変換
N進数で “abcde” があったとする。(2進数で”10101″とか、10進数で”12345″とか)
この値は、以下のような式で表せる。
(例1)
(例2)
10進数をN進数に変換
N進数のは、前式を変形すると、以下のような式で表せることから、
値をNで割った余りを求めると、N進数の最下位桁eを取り出せる。
このため、10進数で与えられた35を2進数に変換するのであれば、35を2で次々と割った余りを、下の桁から書きならべれば2進数100011)2が得られる。
実数の場合
途中に小数点を含むN進数のab.cde)Nであれば、以下の値を意味する。
ここで、小数点以下だけを取り出した、0.cde)Nを考えると、
の値に、Nをかけると、次のように変形できる。
この式を見ると、小数部にNをかけると、整数部分に小数点以下1桁目が取り出せる。
このため、10進数で与えられた、0.625を2進数に変換するのであれば、0.625に次々と2をかけて、その整数部を上の桁から書きならべれば、2進数0.101)2が得られる。
ただし、10進数で0.1という値で、上記の計算を行うと、延々と繰り返しが発生する。つまり、無限小数になるので注意せよ。
2の補数と負の数
コンピュータの中で引き算を行う場合には、2の補数がよく使われる。2の補数とは、2進数の0と1を入替えた結果(1の補数)に、1を加えた数である。
元の数に2の補数
を加えると(2進数が8bitの数であれば)、どのような数でも1,0000,0000という値になる。この先頭の9bit目が必ずはみ出し、この値を覚えないのであれば、元の数+2の補数=0とみなすことができる。このことから、2の補数= (-元の数) であり、負の数を扱うのに都合が良い。
練習問題
(1) 自分の誕生日で、整数部を誕生日の日、小数点以下を誕生日の月とした値について、2進数に変換せよ。(例えば、2月7日の場合は、”7.02″という小数点を含む10進数とする。)
変換の際には、上の説明の中にあるような計算手順を示すこと。また、その2進数を10進数に直し、元の値と同じか確認すること。(ただし、結果の2進数が無限小数になる場合最大7桁まで求めれば良い。同じ値か確認する際には無限少数の場合は近い値になるか確認すること)
(2) 自分の誕生日の日と、自分の学籍番号の下2桁の値を加えた値について、8bitの2進数で表わせ。(2月7日生まれの出席番号13番なら7+13=21)
その後、8bitの2進数として、2の補数を求めよ。また、元の数と2の補数を加えた値についても検証すること。