オブジェクト指向ガイダンス
専攻科２年のオブジェクト指向の最初の講義で、前半ガイダンスで後半、C言語の構造体などの復習。
オブジェクト指向に関連する歴史
簡単にオブジェクト指向プログラミング(Object Oriented Programming – 略してOOP)が出てくるまでの歴史的流れを最初に説明。
最初のプログラム言語のFortran(科学技術計算向け)の頃は、処理を記述するだけだったけど、 COBOL(商用計算向け)ができた頃には、データをひとまとめで扱う「構造体」(C言語ならstruct …}の考えができた。 その後のALGOLの頃には、処理をブロック化して扱うスタイル(C言語なら{ 文 … }の複文で 記述する方法ができて、処理の構造化・データの構造化ができる。これが「構造化プログラミング(structured programming)」 の始まりとなる。
Wikipediaの記事だと、構造化プログラミングは手続きの構造化のことしか書いてないなぁ… 個人的にはOOPの話の一環として話すため、データ構造化も構造化プログラミングの一部としています。
この後、様々なプログラム言語が開発され、C言語などもできてきた。 一方で、シミュレーションのプログラム開発(例simula)では、 シミュレーション対象(object)に対して、命令するスタイルの書き方が生まれ、 データに対して命令するという点で、擬人法のようなイメージで直感的にも分かりやすかった。 これがオブジェクト指向の始まりとなる。
この考え方を導入した言語の1つが Smalltalk であり、この環境では、プログラムのエディタも Smalltalk で記述したりして、オブジェクト指向がGUIのプログラムと親和性が良いことから普及が拡大する。
C言語にこのオブジェクト指向を取り入れて、C++が開発される。さらに、この文法をベースとした、 Javaなどが開発される。最近の新しい言語では、どれもオブジェクト指向の考えが使われている。
構造体の導入
C++でのオブジェクト指向は、構造体の表記がベースになっているので、まずは構造体の説明。
// 構造体の宣言
struct Person {
char name[ 20 ] ; // 要素1
int phone ; // 要素2
} ;
// 構造体変数の宣言
struct Person saitoh ;
struct Person data[ 10 ] ;
// 実際にデータを参照 構造体変数.要素名
strcpy( saitoh.name , "t-saitoh" ) ;
saitoh.phone = 272925 ;
for( int i = 0 ; i < 10 ; i++ ) {
scanf( "%d%s" , data[ i ].name , &(data[ i ].phone) ) ;
}
値渡し、ポインタ渡し、参照渡し
構造体の使い方の話では、関数との構造体のデータ渡しでポインタなどが出てくるので、 値渡し・ポインタ渡し・参照渡しの復習。(参照渡しは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が表示
}
参照型は、ポインタを使っていないように見えるけれども、機械語レベルでみればポインタを使ったものと同じ。
2015年4月5日(第417回)
入学式のため、収録でお送りしました。
- まるよし Train Pops ～ 国語と遊ぼう！ 第97便 「送り仮名」
- 放送・メディア研究会の部活紹介動画
- 新入生に向けてのアドバイス
- 桜の話
担当：松島（４Ｃ・ＭＣ）、田嶋（３Ｃ）、川﨑（２ＥＩ・ＭＩＸ）、植村（２Ｅ）、中村（教員）、西（教員）
創造工学演習・プログラム予備実験(1)
プログラミングコンテストの競技部門では、パズルのような組み合わせ問題が 出題されることが多い。そこで、この予備実験では、きわめて単純なパズル問題(組み合わせ問題) のプログラムについて扱う。
組み合わせ問題の基礎
簡単な問題として、「100未満の整数の値を３つ選び、その値を辺の長さとした場合、 直角三角形となるものをすべて表示する。」について考える。
一番簡単な方法は、以下となるであろう。
#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) 計算誤差の問題を考えてみよう。(問題点を十分に考えたらここをクリック)
(2) 無駄な答えについて考えてみよう。(問題点を十分に考えたらここをクリック)
また、この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 ) ;
}
指定長を指定辺の組み合わせで作る
再帰を使った簡単なパズル問題として、以下のプログラムを作成したい。
配列の中に、複数の辺の長さが入っている。これを組み合わせて指定した長さを作れ。 使用する辺はできるだけ少ない方がよい。
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) これを再帰呼び出しにしてみよう。どう書けばいい？(考えたらここをクリック)