高専プロコン連携シンポジウム2019
〜セキュリティの観点からプロコンに期待すること〜
高専プロコンの応募に合わせ、以下のような講演会が開催されます。
今年度は、課題部門で「ICT を活用した地域活性化」,自由部門で「クラウドコンピューティング」「オープンデータ」「サイバーセキュリティ」「人工知能」がキーワードに挙げられており、高専生に現場のニーズや動向を学習する機会として、開催されます。
日 時: | 5月20日(月) 16:20〜16:50 Skype for businessを用いた動画配信 |
学内場所: | 電子情報工学科3F 情報処理演習室 |
講 師: | 株式会社日立製作所 セキュリティ事業統括本部サイバーセキュリティ技術本部 セキュリティ人材統括センタセンタ長千葉寛之様 |
講演テーマ: | セキュリティの観点からプロコンに期待すること |
補 足: | 発言・質問は、Twitter(ハッシュタグ #procon30 にて)受付 |
再帰呼び出しと再帰方程式
再帰関数と再帰方程式
再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。
// 階乗 (末尾再帰) int fact( int x ) { if ( x <= 1 ) return 1 ; else return x * fact( x-1 ) ; } // ピラミッド体積 (末尾再帰) int pyra( int x ) { if ( x <= 1 ) return 1 ; else return x*x + pyra( x-1 ) ; } // フィボナッチ数列 (非末尾再帰) int fib( int x ) { if ( x <= 2 ) return 1 ; else return fib( x-1 ) + fib( x-2 ) ; }
これらの関数の結果について考えるとともに、この計算の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、 で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理に加え、x-1の値で再帰の処理時間がかかる。 このことから、
で表せる。
} 再帰方程式
このような再帰を使って表した式は再帰方程式と呼ばれる。これを代入によって解けば、一般式 が得られる。
fact() や pyra() のような関数は、プログラムの末端に再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に最適化が可能である。つまり繰り返し処理に書き換えが可能である。このため、ループにすれば局所変数を消費しない。
再帰を含む一般的なプログラム例
ここまでの再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的なプログラムで再帰方程式を使って処理時間を考えてみよう。
以下のプログラムを実行したらどんな値になるであろうか?それを踏まえ、処理時間はどのように表現できるであろうか?
int array[ 8 ] = { 3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 , } ; int sum( int a[] , int L , int R ) { // 非末尾再帰 if ( R - L == 1 ) { return a[ L ] ; } else { int M = (L + R) / 2 ; return sum( a , L , M ) + sum( a , M , R ) ; } } int main() { printf( "%d¥n" , sum( array , 0 , 8 ) ) ; return 0 ; }
このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端・右端を表している。そして、再帰のたびに2つに分割して解いている。
このような、処理を分割し、分割した処理を再帰で計算し、その分割した処理結果を組み合わせて結果を求めるような処理方法を、分割統治法と呼ぶ。
このことから、以下の再帰方程式が得られる。
これを、代入法により解いていくと、
ということで、このプログラムの処理時間は、 で表される。
最後に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。
ハノイの塔
ハノイの塔は、3本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。
一般解の予想
ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、
… ① ということが予想ができる。
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。
再帰方程式
上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、
… ②
… ③
ということが言える。(ハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、
枚では、
… ③
… ①
となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。
理解度確認
- 前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
- 前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)
- 再帰のフィボナッチ関数 fib() の処理時間にふさわしい再帰方程式を示せ
int a[ 10 ] = { 7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98 } ; int find( int array[] , int L , int R , int key ) { // 末尾再帰 // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。 if ( __________ ) { return ____ ; // 見つからなかった } else { int M = _________ ; if ( array[ M ] == key ) return ____ ; else if ( array[ M ] > key ) return find( array , ___ , ___ , key ) ; else return find( _____ , ___ , ___ , ___ ) ; } } int main() { if ( find( a , 0 , 10 , 56 ) ) printf( "みつけた¥n" ) ; }
コンストラクタと複素数クラス
コンストラクタ
プログラミングでは、データの初期化忘れによる間違いもよく発生する。これを防ぐために、C++ のクラスでは、コンストラクタ(構築子)がある。データ構造の初期化専用の関数。
// コンストラクタ #include <stdio.h> #include <string.h> class Person { private: char name[ 20 ] ; int age ; public: void print() { printf( "%s %d¥n" , name , age ) ; } Person() { // コンストラクタ(A) name[0] = '¥0' ; // 空文字列 age = 0 ; } Person( const char str[] , int ag ) { // コンストラクタ(B) strcpy( name , str ) ; age = ag ; } ~Person() { // デストラクタ print() ; // 内容の表示 } } ; int main() { Person saitoh( "t-saitoh" , 55 ) ; // (A)で初期化 Person tomoko() ; // (B)で初期化 saitoh.print() ; // "t-saitoh 55" の表示 tomoko.print() ; // " 0" の表示 return 0 ; // この時点で saitoh.~Person() // tomoko.~Person() が自動的に } // 呼び出される。
コンストラクタと反対に、デストラクタは、データが不要となった時に自動的に呼び出される関数。
このクラスの中には、引数無しのコンストラクタと、引数ありのコンストラクタが出てくる。C++では、同じ名前の関数でも引数の数や型に応じて呼出す関数を適切に選んでくれる。(関数のオーバーロード)
デストラクタは、データが不要となった時に自動的に呼び出してくれる関数で、一般的にはC言語でのファイルの fopen() , fclose() のようなものを使う処理で、コンストラクタで fopen() , デストラクタで fclose() を呼出すように使うことが多いだろう。同じように、コンストラクタで malloc() を呼出し、デストラクタで free() を呼出すというのが定番の使い方だろう。
複素数クラスの例
隠蔽化と基本的なオブジェクト指向の練習課題として、複素数クラスをあげる。ここでは、複素数の加算・乗算を例に説明をするので、減算・除算などの処理を記述することで、クラスの扱いに慣れてもらう。
直交座標系
#include <stdio.h> #include <math.h> // 直交座標系の複素数クラス class Complex { private: double re ; // 実部 double im ; // 虚部 public: void print() { printf( "%lf + j%lf¥n" , re , im ) ; } Complex( double r , double i ) { re = r ; im = i ; } Complex() { // デフォルトコンストラクタ re = im = 0.0 ; } void add( Complex z ) { // 加算は、直交座標系だと極めてシンプル re = re + z.re ; im = im + z.im ; } void mul( Complex z ) { // 乗算は、直交座標系だと、ちょっと煩雑 double r = re * z.re - im * z.im ; double i = re * z.im + im * z.re ; re = r ; im = i ; } double get_re() { return re ; } double get_im() { return im ; } double get_abs() { // 絶対値 return sqrt( re*re + im*im ) ; } double get_arg() { // 偏角 return atan2( im , re ) ; } } ; // ←何度も繰り返すけど、ここのセミコロン忘れないでね int main() { // 複素数を作る Complex a( 1.0 , 2.0 ) ; Complex b( 2.0 , 3.0 ) ; // 複素数の計算 a.print() ; a.add( b ) ; a.print() ; a.mul( b ) ; a.print() ; return 0 ; }
極座標系
上記の直交座標系の Complex クラスは、加減算の関数は単純だけど、乗除算の関数を書く時には面倒になってくる。この場合、極座標系でプログラムを書いたほうが判りやすいかもしれない。
// 局座標系の複素数クラス class Complex { private: double r ; // 絶対値 r double th ; // 偏角 θ public: void print() { printf( "%lf ∠ %lf¥n" , r , th / 3.14159265 * 180.0 ) ; } Complex() { r = th = 0.0 ; } // 表面的には、同じ使い方ができるように // 直交座標系でのコンストラクタ Complex( double x , double y ) { r = sqrt( x*x + y*y ) ; th = atan2( y , x ) ; // 象限を考慮したatan() } // 極座標系だと、わかりやすい処理 void mul( Complex z ) { // 極座標系での乗算は r = r * z.r ; // 絶対値の積 th = th + z.th ; // 偏角の和 } // 反対に、加算は面倒な処理になってしまう。 void add( Complex z ) { ; // 自分で考えて } // double get_abs() { return r ; } double get_arg() { return th ; } double get_re() { return r * cos( th ) ; } double get_im() { return r * sin( th ) ; } } ; // ←しつこく繰り返すけど、セミコロン忘れないでね(^_^;
このように、プログラムを開発していると、当初は直交座標系でプログラムを記述していたが、途中で極座標系の方がプログラムが書きやすいという局面となるかもしれない。しかし、オブジェクト指向による隠蔽化を正しく行っていれば、利用者に影響なく「データ構造」や「その手続き(メソッド)」を書換えることも可能となる。
このように、プログラムをさらに良いものとなるべく書換えることは、オブジェクト指向ではリファクタリングと呼ぶ。
正しくクラスを作っていれば、クラス利用者への影響が最小にしながらリファクタリングが可能となる。
メソッドのプロトタイプ宣言
class 構文では、{} の中に、要素の定義や、メソッドの記述を行うと説明してきたが、メソッド内の処理が長い場合もある。
この時に、すべてを {} の中に書こうとすると、全体像が見渡せない。こういう時には、以下のように、メソッドのプロトタイプ宣言と、メソッドの実体の記述を別に記載する。
class Complex { private: double re , im ; public: Complex( double r , double i ) ; // メソッドのプロトタイプ宣言 void print() ; } ; // メソッドの実体 Complex::Complex( double r , double i ) { re = r ; im = i ; } void Complex::print() { printf( "%lf + j %lf" , re , im ) ; }
ゲッター/セッター (経験者向け解説)
それぞれのクラス宣言では、get_re() , get_im() , get_abs() , get_arg() というメソッドを記載した。このように記述しておくと、クラス外で re , im といったメンバを public 指定をせずに、リファクタリングしやすいクラスにすることができる。(re, im を public にしてしまうと、クラス外でオブジェクトへの代入が可能となる。)
PHPなどの private や public の機能のないオブジェクト指向言語では、get_xx() といった要素の参照しかできないメソッドを作ったうえで、クラス外でメンバ参照をしないというマナーを徹底させることで、public 機能の代用し、隠蔽化を徹底させることも多い。
この場合、参照専用の get_xx() と同じように、要素に値を設定するためのメソッド set_xx( 値… ) を作るとプログラムの意味が分かりやすくなる。こういったクラスの参照や代入のメソッドは、getter(ゲッター),setter(セッター)と呼ぶ。
ゲッターやセッターメソッドでは、要素を参照(あるいは代入)するだけといった極めて単純な関数を作ることになる。この場合、関数呼び出しの処理時間が無駄になる。この対処として、C++ には inline 関数機能がある。関数(メソッド)の前に、inline を指定すると、コンパイラは関数呼び出し用の命令を生成せず、それと同じ処理となる命令を埋め込んでくれる。(開いたサブルーチン)
class Complex { private: double re , im ; public: : inline void get_re() { return re ; } } ;
const 指定 (経験者向け解説)
C++ では、間違って値を書き換えるような処理を書けないようにするための、const 指定の機能がある。
void foo( const int x ) { x++ ; // 定数を書き換えることはできない。 printf( "%d\n" , x ) ; } int main() { const double pi = 3.141592 ; // C言語で #define PI 3.141592 と同等 int a = 123 ; foo( a ) ; return 0 ; }
前に説明した、getter メソッドは要素を参照するだけで、オブジェクトの中身が変化しない。逆に言えば、getter のメソッド内にはオブジェクトに副作用のある処理を書いてはいけない。こういった用途に、オブジェクトを変化させないメソッド宣言がある。先の、get_re() は、
class ... { : inline double get_re() const { re = 0 ; // 文法エラー return re ; } } ;
高専ワイヤレスIoT技術実証コンテスト
総務省主催の、地域における若手人材を活用した電波有効利用に資するIoT技術実証の円滑な実施のため、有効策を取りまとめていくことを目的とした事業の一環としてのコンテストが開催されます。
全国の高等専門学校(学生)を対象に、第5世代移動通信システム(5G)の特性を生かした技術及びワイヤレスIoT技術を活用することにより、地域における諸課題について、様々な分野や業種、自治体、地域等を巻き込んだ解決、あるいは新たなサービスの実現に繋がるようなアイデアを公募します。
授業アンケート結果(ぷちブルーな気分)
情報ネットワーク基礎(3EI/後期)
楽しんで受講してくれた人からの意見があり、ポイントでも85ポイントと高評価であった。内容理解やシラバスについてポイントが若干低いようであるが、誤差の範疇と思われる。理解把握のポイントが最も低く、理解度確認のための質問などをもう少し増やしても良かったかと思う。
情報制御基礎(3年学際科目/前期)
学際科目ということで、初めて実施した科目であり、他学科からも受講生がある内容で、ポイントも70ポイントと低い評価であった。
プログラムを授業でやっていない学科の学生から、内容が理解できないとの意見が多かった。今年度は、他学科の学生にもわかるように、プログラムの説明を増やしたり、プログラムよりも基本的な内容を増やしたいと考えている。
情報構造論(4EI/通年)
意見の欄には、例年になく辛辣な意見もあった。他の同クラスのアンケートでも、全般的に厳しい意見が多くみられ、ポイントは74.8と例年よりも低くいが、このクラスのオフセットとも考えられる。
昨年から講義資料のWeb掲載などを行い、それを使った授業を中心としているが、ノート作成ができていない学生から、ノートをとる時間を十分にとってほしいとの意見があった。もう少し、授業の時間の作り方などを考えたいが、一方で不まじめな学生がノートもも一切とらないで受講する姿は、理解する意欲に欠けていることもあり、どのような対処とすべきか、時間をかけて考えていきたい。
データベース(5EI/後期)
ポイントでは78.6と、若干低めの評価であった。演習量や試験についての評価が他に比べて若干低く、意見でも図や表といった具体例を交えた例での説明を増やしたほうが理解が進むとの建設的な意見もあった。資料などもWebでの公開などを進めているが、今後も実例などを増やし解りやすい資料を目指したい。
オブジェクト指向プログラミング(PS2/前期)
他学科出身の受講者も含まれるため、例年進度に注意しながら授業を進めているが、ポイントでは80ポイントで、例年並みの評価であった。
もう少し、演習などをタイムリーに行いながら授業を進めたいと考えているが、演習環境などの準備も必要で自主学習などの課題を検討したいと思う。
予備実験2 パズル問題
プログラミングコンテストの競技部門では、パズルのような組み合わせ問題が 出題されることが多い。そこで、この予備実験では、きわめて単純なパズル問題(組み合わせ問題) のプログラムについて扱う。
組み合わせ問題の基礎
簡単な問題として、「100未満の整数の値を3つ選び、その値を辺の長さとした場合、 直角三角形となるものをすべて表示する。」について考える。
一番簡単な方法は、以下となるであろう。
#include <stdio.h> #include <math.h> #include <time.h> // 整数比の直角三角形の一覧を求める。 void integer_triangle( int n ) { for( int a = 1 ; a < n ; a++ ) { for( int b = 1 ; b < n ; b++ ) { // 一番ダサい方法 for( int c = 1 ; c < n ; c++ ) { if ( a*a + b*b == c*c ) { printf( "%d %d %d\n" , a , b , c ) ; } } } } } int main() { integer_triangle( 100 ) ; return 0 ; }
しかしこのプログラムの欠点としては、100×100×100回のループで無駄な処理が多い。
ループ回数を減らすだけなら、最も内側の処理を、計算で整数値か確認すればいい。
void integer_triangle( int n ) { for( int a = 1 ; a < n ; a++ ) { for( int b = 1 ; b < n ; b++ ) { // ココも改良できるよね? int d = a*a + b*b ; int c = (int)sqrt( d ) ; // 斜辺Cの整数値を求め、改めて確認する。 if ( c*c == d ) { printf( "%d %d %d\n" , a , b , c ) ; } } } }
(1) 計算誤差の問題を考えてみよう。
たとえば、3:4:5の直角三角形で、3*3+4*4 = 25 だが、sqrt(25)は実数で計算するから、 計算誤差で4.99999で求まったらどうなるだろうか?
1~100までの数値で、”int a = sqrt( (double)(i*i) ) ;” を計算してみて、 異なる値が求まることはあるか? 多少の計算誤差があっても正しく処理が行われるにはどうすればいいか、考えてみよう。
(2) 無駄な答えについて考えてみよう。
このプログラムの答えでは、簡単な整数比の答えの「整数倍の答え」も表示されてしまう。 たとえば、(3:4:5)の答えのほかに、(6:8:10)も表示される。 こういった答えを表示しないようにするにはどうすればよいか?
また、この2つのプログラムの処理時間を実際に比べてみる。
int main() { time_t start , end ; // time() 関数は、秒数しか求まらないので、 // あえて処理を1000回繰り返し、数秒かかる処理にする。 start = time( NULL ) ; for( int i = 0 ; i < 1000 ; i++ ) { // ただし、関数内のprintfをコメントアウトしておくこと integer_triangle( 100 ) ; } end = time( NULL ) ; printf( "%lf\n" , difftime( end , start ) ) ; return 0 ; }
再帰プログラミング
組み合わせ問題では、forループの多重の入れ子で問題を解けない場合が多い。 (書けないことはないけど無駄なループで処理が遅くなるか、入れ子段数が可変にできない。)
こういった場合には、再帰プログラミングがよく利用される。 もっとも簡単な再帰の例として、階乗のプログラムを考える。 通常であれば、以下のような for ループで記述することになるだろう。
// 階乗の計算 int fact( int x ) { // ループ int f = 1 ; for( int i = 2 ; i <= x ; i++ ) f = f * i ; return f ; }
再帰呼び出しでは、関数の処理の中に、自分自身の関数呼び出しが含まれる。 また、無限に自分自身を呼び出したら処理が止まらないので、 問題を一つ小さくして、これ以上小さくできないときは処理を止めるように記述する。
int fact( int x ) { // 再帰呼び出し if ( x <= 1 ) return 1 ; else return x * fact( x - 1 ) ; }
ここ以降は、指定長さを指定辺の組み合わせで作ると、Flood-fill の選択とする。
指定長を指定辺の組み合わせで作る
再帰を使った簡単なパズル問題として、以下のプログラムを作成したい。
配列の中に、複数の辺の長さが入っている。これを組み合わせて指定した長さを作れ。 使用する辺はできるだけ少ない方がよい。
int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
(例) 辺の長さ10を作るには、(5,4,1)とか(7,3)などが考えられる。
これは、ナップサック問題の基本問題で、容量の決まったナップサックに最大量入れる組合せを求めるのと同じである。
このプログラムを解くには…
10 を [4,5,2,1,3,7] で作るには... (0) 6=10-4 を [5,2,1,3,7]で作る。 (1) 5=10-5 を [4,2,1,3,7]で作る。 (2) 8=10-2 を [5,4,1,3,7]で作る。 (3) 9=10-1 を [5,2,4,3,7]で作る。 (4) 7=10-3 を [5,2,1,4,7]で作る。 (5) 3=10-7 を [5,2,1,3,4]で作る。
そこで、ここまでの考えを、以下のようなプログラムで記述してみる。
// 指定されたデータを入れ替える。 void swap( int*a , int*b ) { int x = *a ; *a = *b ; *b = x ; } void check( int array[] , int size , int len , int n ) { // array[] 配列 // size 配列サイズ // len 作りたい長さ // n 使った個数 for( int i = n ; i < size ; i++ ) { // i番目を先頭に... swap( &array[ n ] , &array[ i ] ) ; printf( "check( array , %d , %d , %d )\n" , size , len - array[ n ] , n+1 ) ; // 最初のswapでの変更を元に戻す。 swap( &array[ i ] , &array[ n ] ) ; } } int main() { int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ; check( a , 6 , 10 , 0 ) ; }
(1) これを再帰呼び出しにしてみよう。どう書けばいい?
void check( int array[] , int size , int len , int n ) { // array[] 配列 // size 配列サイズ // len 作りたい長さ // n 使った個数 if ( len < 0 ) { // 指定した丁度の長さを作れなかった。 ; } else if ( len == 0 ) { // 指定した長さを作れたので答えを表示。 for( int i = 0 ; i < n ; i++ ) { printf( "%d " , array[ i ] ) ; } printf( "\n" ) ; } else { // 問題を一つ小さくして再帰。 for( int i = n ; i < size ; i++ ) { swap( &array[ n ] , &array[ i ] ) ; printf( "check( array , %d , %d , %d )\n" , size , len - array[ n ] , n+1 ) ; check( array , size , len - array[ n ] , n + 1 ) ; swap( &array[ i ] , &array[ n ] ) ; } } }
(2) 少ない組み合わせの方がポイントが高い場合には、プログラムをどう変更する?
(3) 答えが1つだけで良い場合は、プログラムをどう変更する?
(4) このプログラムでは、冗長な答えがあるか?ないか?検討せよ。
(5) 前設問の整数比直角三角形のプログラムで、冗長な答えを削除するプログラムを作成せよ。
# ただし、(2)〜(5)は、演習の実験の時間内でできる範囲とする。
Flood fill アルゴリズム
前の問題は、今年度のプログラミングコンテストの課題のパズルとは、方向性が違うので、今年度のプロコンの競技部門に近いパズルネタで演習。(Wikipedia Flood-fill参照)
以下の image のような2次元配列が与えられたら、指定座標(x,y)を中心に周囲を塗りつぶす処理を作成せよ。
include <stdio.h> // *は壁 SPCは白 この領域の指定位置を#で塗りつぶす。 char image1[10][10] = { // (4,4)始点で塗りつぶし後 "*********" , // ********* "* * *" , // * *###* "* * *" , // * *###* "* * *" , // * *####* "*** ***" , // ***###*** "* * *" , // *####* * "* * *" , // *###* * "* * *" , // *###* * "*********" , // ********* } ; char image2[10][10] = { // 応用問題用の画像例 "*********" , // * のような隙間は通り抜けられる "* * *" , // * ようにするにはどうすればいい? "* ** *" , // ** "* ** *" , // ** これは通り抜けられない "*** ***" , // ** "* * *" , "* * *" , "* * *" , "*********" , } ; // 盤面を表示 void print_image( char image[10][10] ) { for( int y = 0 ; y < 9 ; y++ ) { for( int x = 0 ; x < 9 ; x++ ) { printf( "%c" , image[y][x] ) ; } printf( "\n" ) ; } } // 再帰呼び出しを使った flud_fill アルゴリズム void flood_fill( char image[10][10] , int x , int y , char fill ) { // 指定座標が空白なら if ( image[y][x] == ' ' ) { // その座標を埋める image[y][x] = fill ; ////////////////////////////////////// // ここに周囲をflud_fillする処理を書く // ////////////////////////////////////// } } int main() { print_image( image1 ) ; flood_fill( image1 , 4 , 4 , '#' ) ; print_image( image1 ) ; return 0 ; }
応用問題
Wikipediaのflood-fill のプログラムの説明のアルゴリズムでは、左図黒のような斜めに並んだブロックは、境界として通り抜けられないようにつくられている。
そこで、斜めに並んだブロックは通り抜けられるルールとした場合のプログラムを記述せよ。
プログラムと数値型
コンピュータの中では、2進数で値を表現するが、組み込み系のような小さいコンピュータでは、たくさんの桁を必要とする情報を扱うことが苦手である。そこで、C言語で数値を扱う型と、その型で扱える数値の範囲や問題点を説明する。
補足資料:プログラミングの基礎として、C言語の基礎を示す。
数値を扱う型
C言語では、データを覚える型を大きく2つに分けると、整数型(int)と実数型(float)に分けられる。
整数型(int)
整数型も正の値しか覚えられない符号無し型(unsigned int)と、符号付き型(signed int)に分けられる。さらに、その値を8bitで覚える文字型(char)、16bitで覚える short int型、32bitで覚える int 型、64bitで覚える long int 型(※C言語では long int で宣言すると32bitの場合も多いので要注意)がある。
精度 | 符号あり | 符号なし |
8bit | char | unsigned char |
16bit | short int | unsigned short int |
32bit | int | unsigned int |
64bit | long int※ | unsigned long int※ |
符号付きのデータは、負の数は2の補数によって保存する。この場合2進数の最上位bitは、負の数であれば必ず1となる。
整数型で扱える数
例えば、2進数3桁であれば、000,001,010,011,100,101,110,111 で、10進数であれば 0~7 の8通りの値が扱える。
(例) 符号なしの1byte(8bit)であれば、いくつの数を扱えるであろうか?
一般的に N bit であれば、0~(2N-1) までの値が扱える。
bit数 | 型 | 符号なし | |
8 | unsigned char | 0~28-1 | 0~255 |
16 | unsigned short int | 0~216-1 | 0~65535 |
32 | unsigned int | 0~232-1 | 0~4294967295 |
符号付きであれば、2の補数表現で最上位bitが0であれば正の数、1であれば負の数を表す。このため、N bit の符号つき整数は、-2N-1から2N-1-1の範囲の値を覚えられる。
bit数 | 型 | 符号あり | |
8 | char | -27~27-1 | -128~127 |
16 | short int | -215~215-1 | -32768~32767 |
32 | int | -231~231-1 | -2147483648~2147483647 |
数値の範囲の問題で動かないプログラム
この話だけだと、扱える数値の上限について実感がわかないかもしれないので、以下のプログラムをみてみよう。
組み込み系のコンピュータでは、int 型でも、一度に計算できるbit数が少ない。例えば、int型が16bitコンピュータでは、以下のプログラムは期待した値が計算できない。以下の例では、16bit int型として short int で示す。
// コード1 #include <stdio.h> #include <math.h> int main() { // 原点から座標(x,y)までの距離を求める short int x = 200 ; short int y = 200 ; short int r2 = x*x + y*y ; // (x,y)までの距離の2乗 short int r = sqrt( r2 ) ; // sqrt() 平方根 printf( "%d\n" , r ) ; // 何が求まるか? return 0 ; // (例) 282ではなく、120が表示された。 }
コンピュータで一定時間かかる処理を考えてみる。
// コード2.1 // 1 [msec] かかる処理が以下のように書いてあったとする。 short int i ; for( i = 0 ; i < 1000 ; i++ ) NOP() ; // NOP() = 約1μsecかかる処理とする。 // コード2.2 // 0.5 [sec]かかる処理を以下のようにかいた。 short int i ; for( i = 0 ; i < 500000 ; i++ ) NOP() ; // でもこの処理は16bitコンピュータでは、1μsecもかからずに終了する。なぜか?
上記の例は、性能の低い16bit コンピュータの問題で、最近は32bit 整数型のコンピュータが普通だし、特に問題ないと思うかもしれない。でも、32bit でも扱える数の範囲で動かなくなるプログラムを示す。
OS(unix) では、1970年1月1日からの経過秒数で時間を扱う。ここで、以下のプログラムは、正しい値が計算できない有名な例である。(2004年1月11日にATMが動かなくなるトラブルの原因だった)
// コード3.1 int t1 = 1554735600 ; // 2019年4月09日,00:00 int t2 = 1555340400 ; // 2019年4月16日,00:00 // この2日の真ん中の日を求める。 // 以下のプログラムは、正しい 2019年4月12日12:00 が求まらない。なぜか? int t_mid = (t1 + t2) / 2; // (例) 1951年03月25日 08:45 になった。 // コード3.2 // 以下のプログラムは正しく動く。 // time_t 型(時間処理用の64bit整数) time_t t1 = 1554735600 ; // 2019年4月09日,00:00 time_t t2 = 1555340400 ; // 2019年4月16日,00:00 // たとえ32bitでも溢れない式 time_t t_mid = t1 + (t2 - t1) / 2 ;
コンピュータと2進数
3年の情報制御基礎の授業の一回目。この授業では、情報系以外の学生も受講する。昨年度は、プログラムも作る話から、プログラムの基礎の話もしたけど、他学科からの学生さんには難しい所もあったので、共通的な話題を増やす予定。
出席確認は、右側のQRコードを撮影するか、QRコードをクリックして、Microsoft Forms で出席を報告してください。
もし、Office365にLoginできない場合は、直接出席を伝えて下さい。
情報制御基礎のシラバス
情報制御基礎では、ここに上げたシラバスに沿って授業を行う。
基本的に、センサーから読み取ったデータを使って動くシステムを作る場合の、知識ということでアナログ量・デジタル量の話から、移動平均やデータ差分といった数値処理や、そこで求まった値を制御に用いるための基礎的な話を行う。
コンピュータと組み込み系
最近では、コンピュータといっても様々な所で使われている。(1)科学技術計算用の大型コンピュータやインターネットの処理を行うサーバ群、(2)デスクトップパソコン、(3)タブレットPCやスマートフォンのような端末、(4)電化製品の中に収まるようなワンチップコンピュータなどがある。

ワンチップコンピュータ
身近で使われている情報制御という点では、(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進数が元の値を表していることを確認すること。
小数点以下は、最大7桁まで求めれば良い。
(2) 自分の誕生日の日と、自分の学籍番号の下2桁の値を加えた値について、8bitの2進数で表わせ。(2月7日生まれの出席番号13番なら7+13=21)
その後、8bitの2進数として、2の補数を求めよ。
構造体でオブジェクト指向の最初の一歩
構造体でオブジェクト指向もどき
例えば、名前と年齢の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者とデータ利用者で分けて 仕事ができることを説明。
// この部分はデータ構造の設計者が書く // データ構造を記述 struct Person { char name[10] ; int age ; } ; // データに対する処理を記述 void setPerson( struct Person* p , char s[] , int a ) { // ポインタの参照で表記 strcpy( (*p).name , s ) ; (*p).age = a ; } void printPerson( struct Person* p ) { // アロー演算子で表記 "(*p).name" は "p->name" で書ける printf( "%s %d¥n" , p->name , p->age ) ; } // この部分は、データ利用者が書く int main() { // Personの中身を知らなくてもいいから配列を定義(データ隠蔽) struct Person saitoh ; setPerson( &saitoh , "saitoh" , 55 ) ; struct Person table[ 10 ] ; // 初期化は記述を省略 for( int i = 0 ; i < 10 ; i++ ) { // 出力する...という雰囲気で書ける(手続き隠蔽) printPerson( &table[i] ) ; } return 0 ; }
このプログラムの書き方では、mainの中を読むだけもで、 データ初期化とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、setPerson()や、printPerson()という関数の中身についても、 初期化・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。
C++のクラスで表現
上記のプログラムをそのままC++に書き直すと以下のようになる。
#include <stdio.h> #include <string.h> // この部分はクラス設計者が書く class Person { private: // クラス外からアクセスできない部分 // データ構造を記述 char name[10] ; // メンバーの宣言 int age ; public: // クラス外から使える部分 // データに対する処理を記述 void set( char s[] , int a ) { // メソッドの宣言 // pのように対象のオブジェクトを明記する必要はない。 strcpy( name , s ) ; age = a ; } void print() { printf( "%s %d¥n" , name , age ) ; } } ; // ← 注意ここのセミコロンを書き忘れないこと。 // この部分はクラス利用者が書く int main() { Person saitoh ; saitoh.set( "saitoh" , 55 ) ; saitoh.print() ; // 文法エラーの例 printf( "%d¥n" , saitoh.age ) ; // phoneはprivateなので参照できない。 return 0 ; }
用語の解説:C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。
引数渡しについて
オブジェクト指向の授業では他学科出身の人も多いので、引数渡しの理解が浅いことから、別途説明を行う。
値渡し、ポインタ渡し、参照渡し
構造体の使い方の話では、関数との構造体のデータ渡しでポインタなどが出てくるので、 値渡し・ポインタ渡し・参照渡しの説明。(参照渡しはC++で導入された考え方)
値渡し
C言語の基本は、値渡し。呼び出し側の実引数は、関数側の仮引数に値がコピーされる。 このため、呼び出し側の変数(下の例ではa)の中身は変化しない。 よって、関数の呼び出しで呼び出し側の変数が勝手に中身が変わらないので、予想外の変数の中身の変化が無く分かりやすい。
// 値渡し(call by value)の例 void foo( int x ) { x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124が表示 foo( a ) ; // 124が表示 }
ポインタ渡し
しかし、上の例では、foo()の呼び出しで、変数aの中身が変化してくれたほうが都合が良い場合もある。 この場合は、C言語ではポインタを使って記述する。 このように、関数を呼び出して、手元の変数が変化することは、副作用と呼ばれる。 副作用の多いプログラムは、変数の値の管理がわかりにくくなるので、副作用は最小限に記述すべき。
// ポインタ渡し(call by pointer)の例 void foo( int *px ) { (*px)++ ; printf( "%d¥n" , (*px) ) ; } void main() { int a = 123 ; foo( &a ) ; // 124が表示 foo( &a ) ; // 125が表示 }
参照渡し
しかし、ポインタを多用すると、ポインタを動かしてトラブルも増えることから、ポインタはあまり使わない方が良い。 そこで、C++では参照型というものがでてきた。
// 参照型(call by reference)の場合 void foo( int &x ) { x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124が表示 foo( a ) ; // 125が表示 }
参照型は、ポインタを使っていないように見えるけれども、機械語レベルでみればポインタ渡しの命令を自動的に生成してくれるだけ。