派生と継承
前回の派生と継承のイメージを改めて記載する。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) : age( x ) { strcpy( name , s ) ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } void print() { Person::print() ; // 基底クラスPersonで名前と年齢を表示 printf( "- %s %d\n" , dep , grade ) ; } } ; void main() { Person saitoh( "t-saitoh" , 55 ) ; Student yama( "yamada" , 21 , "ES" , 1 ) ; Student nomu( "nomura" , 22 , "PS" , 2 ) ; saitoh.print() ; // 表示 t-saitoh 55 yama.print() ; // 表示 yamada 21 // - ES 1 nomu.print() ; // 表示 nomura 22 } // - PS 2
このような処理でのデータ構造は、次のようなイメージで表される。
派生クラスでの問題提起
基底クラスのオブジェクトと、派生クラスのオブジェクトを混在してプログラムを記述したらどうなるであろうか?
上記の例では、Person オブジェクトと、Student オブジェクトがあったが、それをひとまとめで扱いたいこともある。
以下の処理では、Person型の saitoh と、Student 型の yama, nomu を、一つの table[] にまとめている。
void main() { Person saitoh( "t-saitoh" , 55 ) ; Student yama( "yamada" , 21 , "ES" , 1 ) ; Student nomu( "nomura" , 22 , "PS" , 2 ) ; Person* table[3] = { &saitoh , &yama , &nomu , } ; for( int i = 0 ; i < 3 ; i++ ) { table[ i ]->print() ; } }
C++では、Personへのポインタの配列に代入する時、Student型ポインタは、その基底クラスへのポインタとしても扱える。ただし、このように記述すると、table[] には、Person クラスのデータして扱われる。
このため、このプログラムを動かすと、以下のように、名前と年齢だけが3人分表示される。
t-saitoh 55 yamada 21 nomura 22
派生した型に応じた処理
上記のプログラムでは、 Person* table[] に、Person*型,Student*型を混在して保存をした。しかし、Person*として呼び出されると、yama のデータを表示しても、所属・学年は表示されない。上記のプログラムで、所属と名前を表示することはできないのだろうか?
// 混在したPersonを表示 for( int i = 0 ; i < 3 ; i++ ) table[i]->print() ; // Student は、所属と名前を表示して欲しい t-saitoh 55 yamada 21 - ES 1 nomura 22 - PS 2
上記のプログラムでは、Person型では、後でStudent型と区別ができないと困るので、Person型に、Person型(=0)なのか、Student型(=1)なのか区別するための type という要素を追加し、type=1ならば、Student型として扱うようにしてみた。
// 基底クラス class Person { private: int type ; // 型識別情報 char name[ 20 ] ; int age ; public: Person( int tp , const char s[] , int x ) : type( tp ) , age( x ) { strcpy( name , s ) ; } int type_person() { return type ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( int tp , const char s[] , int x , const char d[] , int g ) : Person( tp , s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } void print() { Person::print() ; // 基底クラスPersonで名前と年齢を表示 printf( "- %s %d\n" , dep , grade ) ; } } ; void main() { // type=0 は Person 型、type=1は Student 型 Person saitoh( 0 , "t-saitoh" , 55 ) ; Student yama( 1 , "yamada" , 21 , "ES" , 1 ) ; Student nomu( 1 , "nomura" , 22 , "PS" , 2 ) ; Person* table[3] = { &saitoh , &yama , &nomu , } ; for( int i = 0 ; i < 3 ; i++ ) { switch( table[i]->type_person() ) { case 0 : table[i]->print() ; break ; case 1 : // 強制的にStudent*型として print() を呼び出す。 // 最近のC++なら、(static_cast<Student*>(table[i]))->>print() ; ((Student*)table[i])->print() ; break ; } } }
しかし、このプログラムでは、プログラマーがこのデータは、Personなので type=0 で初期化とか、Studentなので type=1 で初期化といったことを記述する必要がある。また、型情報(type)に応じて、その型にふさわしい処理を呼び出すための switch 文が必要になる。
もし、派生したクラスの種類がいくつもあるのなら、型情報の代入は注意深く書かないとバグの元になるし、型に応じた分岐は巨大なものになるだろう。実際、オブジェクト指向プログラミングが普及する前の初期の GUI プログラミングでは、巨大な switch 文が問題となっていた。
仮想関数
上記の、型情報の埋め込みと巨大なswitch文の問題の解決策として、C++では仮想関数(Virtual Function)が使える。
型に応じて異なる処理をしたい関数があったら、その関数の前に virtual と書くだけで良い。このような関数を、仮想関数と呼ぶ。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) : age( x ) { strcpy( name , s ) ; } virtual void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } virtual void print() { Person::print() ; // 基底クラスPersonで名前と年齢を表示 printf( "- %s %d\n" , dep , grade ) ; } } ; void main() { // type=0 は Person 型、type=1は Student 型 Person saitoh( "t-saitoh" , 55 ) ; Student yama( "yamada" , 21 , "ES" , 1 ) ; Student nomu( "nomura" , 22 , "PS" , 2 ) ; Person* table[3] = { &saitoh , &yama , &nomu , } ; for( int i = 0 ; i < 3 ; i++ ) { table[i]->print() ; } }
クラスの中に仮想関数が使われると、C++ では、プログラム上で見えないが、何らかの型情報をオブジェクトの中に保存してくれる。
また、仮想関数が呼び出されると、その型情報を元に、ふさわしい関数を自動的に呼び出してくれる。このため、プログラムも table[i]->print() といった極めて簡単に記述できるようになる。
関数ポインタ
仮想関数の仕組みを実現するためには、関数ポインタが使われる。
以下の例では、返り値=int,引数(int,int)の関数( int(*)(int,int) )へのポインタfpに、最初はaddが代入され、(*fp)(3,4) により、7が求まる。
int add( int a , int b ) { return a + b ; } int mul( int a , int b ) { return a * b ; } void main() { int (*fp)( int , int ) ; fp = add ; printf( "%d\n" , (*fp)( 3 , 4 ) ) ; // 3+4=7 fp = mul ; printf( "%d\n" , (*fp)( 3 , 4 ) ) ; // 3*4=12 int (*ftable[2])( int , int ) = { add , mul , } ; for( int i = 0 ; i < 2 ; i++ ) printf( "%d\n" , (*ftable[i])( 3 , 4 ) ) ; }仮想関数を使うクラスが宣言されると、一般的にそのコンストラクタでは、各クラス毎の仮想関数へのポインタのテーブルが型情報として保存されるのが一般的。仮想関数の呼び出しでは、仮想関数へのポインタを使って処理を呼び出す。このため効率よく仮想関数を動かすことができる。
効率のよいメモリ使用と動的メモリ確保
次にメモリの利用効率の話について解説する。
配列宣言でサイズは定数
C言語では、配列宣言を行う時は、配列サイズに変数を使うことはできない。
最近のC(C99)では、実は下記のようなものは、裏で後述のalloca()を使って動いたりする。(^_^;
void foo( int size ) { int array[ size ] ; // エラー for( int i = 0 ; i < size ; i++ ) array[ i ] = i*i ; } void main() { foo( 3 ) ; foo( 4 ) ; }
メモリ利用の効率
配列サイズには、定数式しか使えないので、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。
#define MEMBER_SIZE 50 #define NAME_LENGTH 20 char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;
しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。(“t-saitoh”くんは配列サイズ9byte、”寿限無”くんは配列220byte といった使い方はできない) また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 10000人分を用意する必要がある。 ただし、10000人の”寿限無”ありを考慮して、5Mbyte の配列を準備したのに、与えられたデータ量が100件で終わってしまうなら、その際のメモリの利用効率は極めて低い。
このため、最も簡単な方法は、以下のように巨大な文字配列に先頭から名前を入れていき、 文字ポインタ配列に、各名前の先頭の場所を入れる方式であれば、 途中に寿限無がいたとしても、問題はない。
char array[2000] = "ayuka¥0mitsuki¥0t-saitoh¥0tomoko¥0....." ; char *name[ 50 ] = { array+0 , array+6 , array+14 , array+23 , ... } ;
この方式であれば、2000byte + 4byte(32bitポインタ)×50 のメモリがあれば、 無駄なメモリ空間も必要最低限とすることができる。
参考:
寿限無(文字数:全角103文字)
さる御方、ビチクソ丸(文字数:全角210文字)
引用Wikipedia
大きな配列を少しづつ貸し出す処理
// 巨大な配列 char str[ 10000 ] ; // 使用領域の末尾(初期値は巨大配列の先頭) char* sp = str ; // 文字列を保存する関数 char* entry( char* s ) { char* ret = sp ; strcpy( sp , s ) ; sp += strlen( s ) + 1 ; return ret ; } int main() { char* names[ 10 ] ; names[ 0 ] = entry( "saitoh" ) ; names[ 1 ] = entry( "jugemu-jugemu-gokono-surikire..." ) ; return 0 ; } // str[] s a i t o h ¥0 t o m o k o ¥0 // ↑ ↑ // names[0] names[1]
このプログラムでは、貸し出す度に、sp のポインタを後ろに移動していく。
スタック
この貸し出す度に、末尾の場所をずらす方式にスタックがある。
int stack[ 100 ] ; int* sp = stack ; void push( int x ) { *sp = x ; // 1行で書くなら sp++ ; // *sp++ = x ; } int pop() { sp-- ; return *sp ; // return *(--sp) ; } int main() { push( 1 ) ; push( 2 ) ; push( 3 ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; return 0 ; }
スタックは、最後に保存したデータを最初に取り出せる(Last In First Out)から、LIFO とも呼ばれる。
このデータ管理方法は、最後に呼び出した関数が最初に終了することから、関数の戻り番地の保存や、最後に確保した局所変数が最初に不要となることから、局所変数の管理に利用されている。
alloca() 関数
局所変数と同じスタック上に、一時的にデータを保存する配列を作り、関数が終わると不要になる場合には、alloca() 関数が便利である。alloca の引数には、必要なメモリの byte 数を指定する。100個の整数データを保存するのであれば、int が 32bit の 4byte であれば 400byte を指定する。ただし、int 型は16bitコンピュータなら2byteかもしれないし、64bitコンピュータなら、8byte かもしれないので、sizeof() 演算子を使い、100 * sizeof( int ) と書くべきである。
#include <alloca.h> void foo( int size ) { int* p ; // p = (int*)alloca( sizeof( int ) * size ) ; for( int i = 0 ; i < size ; i++ ) p[ i ] = i*i ; } void main() { foo( 3 ) ; foo( 4 ) ; }
alloca() は、指定された byte 数のデータ領域の先頭ポインタを返すが、その領域を 文字を保存するために使うか、int を保存するために使うかは alloca() では解らない。alloca() の返り値は、使う用途に応じて型キャストが必要である。文字を保存するなら、(char*)alloca(…) 、 intを保存するなら (int*)alloca(…) のように使う。
ただし、関数内で alloca で確保したメモリは、その関数が終了すると、その領域は使えなくなる。このため、最後に alloca で確保したメモリが、最初に不要となる…ような使い方でしか使えない。
ポインタの加算と配列アドレス
ポインタの加算と配列アドレス
ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。
// ポインタ加算の例 int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ; void main() { int* p ; // p∇ p = &a[2] ; // a[] : 11,22,33,44,55 // -2 +0 +1 printf( "%d¥n" , *p ) ; // 33 p[0] printf( "%d¥n" , *(p+1) ) ; // 44 p[1] printf( "%d¥n" , *(p-2) ) ; // 11 p[-2] p = a ; // p∇ printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55 p++ ; // → p∇ printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55 p += 2 ; // → → p∇ printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55 }
ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。
*(p + 整数式) と p[ 整数式 ] は同じ意味
特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。
構造体とポインタ
構造体を関数に渡して処理を行う例を示す。
struct Person { char name[ 10 ] ; int age ; } ; struct Person table[3] = { { "t-saitoh" , 55 } , { "tomoko" , 44 } , { "mitsuki" , 19 } , } ; void print_Person( struct Person* p ) { printf( "%s %d\n" , (*p).name , // * と . では . の方が優先順位が高い // p->name と簡単に書ける。 p->age ) ; // (*p).age の簡単な書き方 } void main() { for( int i = 0 ; i < 3 ; i++ ) { print_Person( &(table[i]) ) ; // print_Person( table + i ) ; でも良い } }
構造体へのポインタの中の要素を参照する時には、アロー演算子 -> を使う。
C言語の制御構文の基礎(part2)
制御構文とフローチャート
構文の入れ子
文と複文
C言語の文法で、{,} は複数の処理をまとめる複文とよばれる。
これに対して、a = 123 ; といったセミコロンで終わる「処理 ;」は単文という。
制御構文は、「if ( 条件) 文」で文となる。このため、文が単文であれば、{,} は不要である。
if ( 条件 ) { a = 123 ; } if ( 条件 ) a = 123 ; // 中括弧は不要
同じように、「while(条件) 文」、「for(A,B,C) 文」、「do 文 while(条件) ;」も、それぞれ文を構成する。
{,} の複文は、{ 文 文 文… } のように、一連の文を実行し、それを1つの文として扱うための機能である。
文と処理順序の理解(レポート2-1)
プログラムの制御構造の確認として、以下のレポートを次回講義までに提出せよ。
以下の3つ(No.1,No.2,No.3)の問題から、
M科,C科,B科の学生は(自分の出席番号 % 2)+1 の問題、E科,EI科の学生は、(自分の出席番号 % 3)+1について、プログラムのフローチャートを描き、その実行順序を20ステップめまで答えよ。
レポートには、
- 元プログラム
- フローチャート
- 実行順序
- 変数の変化がわかる内容
- (できれば、実際にプログラムを動かし、正しいことを検証)
を明記すること。
No.1
No.2
No.3
Excel で計算式の基礎(part1)
情報制御基礎では、プログラムで計算する所を、Excel のような表計算ソフトを用いて検証してもらったりする予定なので、Excel で計算式を使う方法を説明する。
セルの場所と簡単な式
簡単な、品名・単価・個数・価格の表を考える。以下の表のように、列の名前と、品名・単価・個数まで入力した後、単価と個数をかけた価格を求めるとする。
Excel では、表の列には左から、A,B,C,D… , 表の行には上から1,2,3,4,5 と番号が振られていて、特定の列・特定の行のデータを表す時には、列行を組み合わせ、A1に品名、B3に¥80、C5に4 が入っている。
例えば、D2 に、ノート単価120円、ノート個数3個をかけた値を入れたい場合は、D2の場所に、
=B2*C2
を書き込めば、その場所には360が表示される。
D3には、”=B3*C3″を入力すれば、160 が表示される。しかし、この様な式を何度も入力するのは面倒である。
この場合、セル・カーソルを、D2 に合わせ、[右ボタン]-[コピー]を行い、D3 で[右ボタン]-[貼り付けオプション]-[貼り付け]を行えば、”=B3*C3″が入力される。
ここで注意しないといけないのが、式を張り付ける場合には、貼り付け先のセルの場所が一つ下の行なので、行番号を表す2の部分が1つ下の行番号3に書き換えられて、貼り付けが行われる。(相対参照)
関数式
例えば、下左図のような、数字とその平方根の表を作る場合、A2 に 1、B2に =sqrt( A2 ) を入力、A3 に =A2+1 を入力したあと、B2の式をB3にコピー&ペーストし、A3,B3 を A4~A6にペーストすればいい。
B2に入力したような、sqrt( A2 ) のようなものは、関数式と呼ばれる。
また、A3,B3 といった複数の行・列をまとめた範囲を示す時は、A3:B3 といった表記方法であらわす。
絶対参照と相対参照
最初の例に戻って、単価と個数の積で今度は税率を加えて計算する例を考える。また、税率は後で変化するかもしれないので、B1 のセルに税率を記入しておく場合を考える。
この場合、D3 には、” =B3*C3*(1+B1) ” を入力すればいい。
ただ、このように式を入力すると、D3 の計算式を、D4,D5,D6 にコピーすると、セル D4 には =B4*C4*(1+B2) が入力されてしまい、B2 には単価という文字が記載されているため、正しい結果が求まらない。
こういった場合には、絶対参照を用いる。D3 に記入する式を
=B3*C3*(1+$B$2)
とし、この D3 の式を D4 にコピー&ペーストすると、列記号、行番号の前に$がついた部分の式は、貼り付け場所に応じて変化しない。
このような、$B$2 といったセルの参照は、絶対参照と呼ぶ。これに対し、B2 といったセル参照は、貼り付け場所に応じて書き換えられるので、相対参照と呼ぶ。
絶対参照と相対参照が混ざった、$B2, B$2 といった書き方もある。
式の入力時にF4ボタンを押す度に、B2→$B$2→B$2→$B2→B2 と変化する
$B2 は、式をコピーすると列部分はBのまま、行部分は場所に合わせて変化する。
B$2 は、式をコピーすると列部分は場所に合わせて変化し、行部分は2のままとなる。
レポート課題(2-2)
Excel で、xを0〜180度まで変化させたときのsin(x),位相をyとした時のsin(x+y)の値の表を作り、グラフ機能で表示せよ。
レポートには、セルにどのような式を入力したかの説明と、結果のグラフ(解りやすいように表示を工夫すること)をつけること。
派生と継承
隠ぺい化の次のステップとして、派生・継承を説明する。
派生を使わずに書くと…
元となるデータ構造(例えばPersonが名前と年齢)でプログラムを作っていて、 途中でその特殊パターンとして、所属と学年を加えた学生(Student)という データ構造を作るとする。
// 元となる構造体(Person) struct Person { char name[ 20 ] ; // 名前 int age ; // 年齢 } ; // 初期化関数 void set_Person( struct Person* p , char s[] , int x ) { strcpy( p->name , s ) ; p->age = x ; } // 表示関数 void print_Person( struct Person* p ) { printf( "%s %d\n" , p->name , p->age ) ; } void main() { struct Person saitoh ; set_Person( &saitoh , "t-saitoh" , 50 ) ; print_Person( &saitoh ) ; }
パターン1(そのまんま…)
上記のPersonに、所属と学年を加えるのであれば、以下の方法がある。 しかし以下パターン1は、要素名がname,ageという共通な部分があるようにみえるが、 プログラム上は、PersonとPersonStudent1は、まるっきり関係のない別の型にすぎない。
このため、元データと共通部分があっても、同じ処理を改めて書き直しになる。
// 元のデータに追加要素(パターン1) struct PersonStudent1 { // Personと同じ部分 char name[ 20 ] ; // 名前 int age ; // 年齢 // 追加部分 char dep[ 20 ] ; // 所属 int grade ; // 学年 } ; void set_PersonStudent1( struct PersonStudent1* p , char s[] , int x , char d[] , int g ) { // set_Personと同じ処理を書いている。 strcpy( p->name , s ) ; p->age = x ; // 追加された処理 strcpy( p->dep , d ) ; p->grade = g ; } // 名前と年齢だけ表示 void print_PersonStudent1( struct PersonStudent1* p ) { // print_Personと同じ処理を書いている。 printf( "%s %d\n" , p->name , p->age ) ; } void main() { struct PersonStudent1 yama1 ; set_PersonStudent1( &yama1 , "yama" , 22 , "PS" , 2 ) ; print_PersonStudent1( &yama1 ) ; }
パターン2(元データの処理を少し使って…)
パターン1では、同じような処理を何度も書くことになり、面倒なので、 元データ用の関数をうまく使うように書いてみる。
// 元のデータに追加要素(パターン2) struct PersonStudent2 { // 元のデータPerson struct Person person ; // 追加部分 char dep[ 20 ] ; int grade ; } ; void set_PersonStudent2( struct PersonStudent2* p , char s[] , int x , char d[] , int g ) { // Personの関数を部分的に使う set_Person( &(p->person) , s , x ) ; // 追加分はしかたない strcpy( p->dep , d ) ; p->grade = g ; } void print_PersonStudent2( struct PersonStudent2* p ) { // Personの関数を使う。 print_Person( &p->person ) ; } void main() { struct PersonStudent2 yama2 ; set_PersonStudent2( &yama2 , "yama" , 22 , "PS" , 2 ) ; print_PersonStudent2( &yama2 ) ; }
このパターン2であれば、元データ Person の処理をうまく使っているので、 プログラムの記述量を減らすことはできるようになった。
しかし、print_PersonStudent2() のような処理は、元データ構造が同じなのに、 いちいちプログラムを記述するのは面倒ではないか?
そこで、元データの処理を拡張し、処理の流用ができないであろうか?
基底クラスから派生クラスを作る
オブジェクト指向では、元データ(基底クラス)に新たな要素を加えたクラス(派生クラス)を 作ることを「派生」と呼ぶ。派生クラスを定義するときは、クラス名の後ろに、 「:」「public/protected/private」基底クラス名を書く。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) : age( x ) { strcpy( name , s ) ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: // 追加部分 char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } } ; void main() { Person saitoh( "t-saitoh" , 50 ) ; saitoh.print() ; Student yama( "yama" , 22 , "PS" , 2 ) ; yama.print() ; }
ここで注目すべき点は、main()の中で、Studentクラス”yama”に対し、yama.print() を呼び出しているが、パターン2であれば、print_PersonStudent2()に相当するプログラムを 記述していない。 しかし、この派生を使うと Person の print() が自動的に流用することができる。 これは、基底クラスのメソッドを「継承」しているから、 このように書け、名前と年齢「yama 22」が表示される。
さらに、Student の中に、以下のような Student 専用の新しい print()を記述してもよい。
class Student ...略... { ...略... // Student クラス専用の print() void print() { // 親クラス Person の print() を呼び出す Person::print() ; // Student クラス用の処理 printf( "%s %d\n" , dep , grade ) ; } } ; void main() { ...略... Student yama( "yama" , 22 , "PS" , 2 ) ; yama.print() ; }
この場合は、継承ではなく機能が上書き(オーバーライト)されるので、 「yama 22 / PS 2」が表示される。
派生クラスを作る際の後ろに記述した、public は、他にも protected , private を 記述できる。
public だれもがアクセス可能。 protected であれば、派生クラスからアクセスが可能。 派生クラスであれば、通常は protected で使うのが一般的。 private 派生クラスでもアクセス不可。
仮想関数への伏線
上記のような派生したプログラムを記述した場合、以下のようなプログラムでは何が起こるであろうか?
class Student ... { : void print() { Person::print() ; // 名前と年齢を表示 printf( " %s %d¥n" , dep , grade ) ; // 所属と学年を表示 } } ; void main() { Person saitoh( "t-saitoh" , 55 ) ; saitoh.print() ; // t-saitoh 55 名前と年齢を表示 Student mitsu( "mitsuki" , 19 , "E" , 4 ) ; Student ayuka( "ayuka" , 17 , "EI" , 2 ) ; mitsu.print() ; // mitsuki 19 / E 4 名前,年齢,所属,学年を表示 ayuka.print() ; // ayuka 17 / EI 2 名前,年齢,所属,学年を表示 Person* family[] = { &saitoh , &mitsu , &ayuka , // 配列の中に、Personへのポインタと } ; // Studentへのポインタが混在している // 派生クラスのポインタは、 // 基底クラスのポインタとしても扱える for( int i = 0 ; i < 3 ; i++ ) family[ i ]->print() ; // t-saitoh 53/mitsuki 18/ayuka 16 } // が表示される。
ソートアルゴリズム
前回の授業のハノイの塔は、単純な再帰方程式で処理時間のオーダーが巨大となる一例として示した。そこで、プログラムの中でよく利用されるデータの並び替え(ソート)で処理時間の分析を行ってみる。
様々なソートアルゴリズム
データの有名な並び替えアルゴリズムとその処理時間のオーダーを示す。
- バブルソート O(N2)
- 選択法 O(N2/2)
- クイックソート O( N log N )
- マージソート O( N log N )
マージソートの分析
マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。
このことから、再帰方程式は、以下のようになる。
この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。
:
よって、
選択法とクイックソートの処理時間の比較
データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。
- データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
- データ件数何件以上なら、クイックソートの方が高速になるか答えよ。
設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。
実数型と取り扱いの注意
実数型(float / double)
実数型は、単精度実数(float型)と、倍精度実数(double型)があり、それぞれ32bit,64bitでデータを扱う。
単精度型(float)では、符号1bit,指数部8bit,仮数部23bitで値を覚え、数値としては、以下の値を意味する。(精度が低いので普通のコンピュータではあまり使われることはない)
符号✕ 1.仮数部 ✕ 2指数部-127
倍精度型(double)では、符号1bit,指数部11bit,仮数部52bitで値を覚え、数値としては、以下の意味を持つ。
符号✕ 1.仮数部 ✕ 2指数部-1023
倍精度型を使えば、正しく計算できるようになるかもしれないが、実数型はただの加算でも仮数部の小数点の位置を合わせたりする処理が必要で、浮動小数点専用の計算機能を持っていないような、ワンチップコンピュータでは整数型にくらべると10倍以上遅い場合もある。
実数の注意点
C言語でプログラムを作成していて、簡単な数値計算のプログラムでも動かないと悩んだことはないだろうか?解らなくて友達のプログラムを真似したら動いたけど、なぜ自分のプログラムは動かなかったのか深く考えたことはあるだろうか?
単純な合計と平均
整数を入力し、最後に合計と平均を出力するプログラムを以下に示す。
しかし、C言語でこのプログラムを動かすと、10,10,20,-1 と入力すると、合計(sum)40,件数(cnt)3で、平均は13と表示され、13.33333 とはならない。
小数点以下も正しく表示するには、どうすればいいだろうか?
ただし、変数の型宣言を “double data,sum,cnt ;” に変更しないものとする。
// 入力値の合計と平均を求める。 #include <stdio.h> int main() { int data ; int sum = 0 ; int cnt = 0 ; for(;;) { printf( "数字を入力せよ。-1で終了¥n" ) ; scanf( "%d" , &data ) ; if ( data < 0 ) break ; cnt = cnt + 1 ; sum = sum + data ; } printf( "合計 %d¥n" , sum ) ; printf( "平均 %d¥n" , sum / cnt ) ; }
C言語では、int型のsum / int型のcnt の計算は、int 型で計算を行う。このため、割り算だけ実数で行いたい場合は、以下のように書かないといけない。
printf( "平均 %lf¥n" , (double)sum / (double)cnt ) ;
// (double)式 は、sum を一時的に実数型にするための型キャスト
まずは動く例
以下のプログラムは、見れば判るけど、th を 0度〜360度まで5度刻みで変化させながら、y = sin(th) の値を表示するプログラム。
// sin の値を出力 #include <stdio.h> #include <math.h> int main() { double th , y ; for( th = 0.0 ; th <= 360.0 ; th += 5.0 ) { y = sin( th / 180.0 * 3.1415926535 ) ; printf( "%lf %lf¥n" , th , y ) ; } return 0 ; }
動かないプログラム
では、以下のプログラムはどうだろうか?
// case-1 ---- プログラムが止まらない #define PI 3.1415926535 int main() { double th , y ; // 0〜πまで100分割でsinを求める for( th = 0.0 ; th != PI ; th += PI / 100.0 ) { y = sin( th ) ; printf( "%lf %lf¥n" , th , y ) ; } return 0 ; }
// case-2 ---- y の値が全てゼロ int main() { int th ; double y ; for( th = 0 ; th <= 360 ; th += 5 ) { y = sin( th / 180 * 3.1415926535 ) ; printf( "%d %lf¥n" , th , y ) ; } return 0 ; }
どちらも、何気なく読んでいると、動かない理由が判らないと思う。そして、元のプログラムと見比べながら、case-1 では、「!=」を「<=」に書き換えたり、case-2 では、「int th ;」を「double th ;」に書き換えたら動き出す。
では何が悪かったのか…
回答編
C言語の基礎(part1)
学際科目の情報制御基礎において、学科間でプログラミングの初歩の理解差があるので、簡単なC言語プログラミングの基礎の説明。
Hello World
“Hello World”と表示するだけのC言語プログラムは以下のようになる。
// コメントの書き方1 // "//"で始まる行は、プログラムの説明(コメント) /* コメントの書き方2 */ // "/*"から"*/"で囲まれる範囲もコメント #include <stdio.h> // #で始まる行はプリプロセッサ行 // stdio.h には、入出力関数の説明が書いてある int main() { // 一連の処理の塊を関数と呼ぶ。 // C言語では main() 関数を最初に実行する。 printf( "Hello World\n" ) ; // printf() は、以下の物を表示する関数。 // "\n"は、文字を出力して改行するための特殊文字 return 0 ; // main() 関数が、正常終了したことを意味する } // 0 を返り値として返す。
“#include <>”のプリプロセッサ行は、最初のうちは解りにくいので、これを書かないとダメ…と思っていればいい。
#include <stdio.h> は、別ファイル(ヘッダファイル) stdio.h に記載されているプログラムを読み込む機能。
stdio.h には、printf() とか scanf() とかの関数や定数などの情報が記載されている。
C言語の基本的な命令(文)は、”;”で終わる。(単文)
複数の処理をまとめる場合には、”{“から”}”の中に、複数の文を書き並べる。(複文)
関数とは、複数の処理をひとまとめにした、処理の「かたまり」と思えばいい。
関数の型 関数名( 仮引数 ... ) { 処理1 ... ; 処理2 ... ; }printf() の 文字列中の”\n”(あるいは”¥n”)は、改行を意味する。
「\:バックスラッシュ」は、日本語環境では「¥:円記号」で入力・表示することが多い。
変数と代入
#include <stdio.h> #include <math.h> // 数学関数を使う 平方根 sqrt() を使っている int main() { // 変数の宣言 int i ; // 符号付き32bit変数 i の宣言 int a = 123 , j ; // a を 123 で初期化 , j も整数型 float x ; // 単精度実数の x を宣言 double y = 1.234 , z ; // 倍精度実数の y を宣言し 1.234 で初期化, // z も倍精度実数 // 変数への代入 i = 1 ; // i に 1 を代入 i = 12 + 2 * a ; // 12+2*a を代入 a は123なので、 // iには、258 が入る。 x = sqrt( 2.0 ) ; // x に 2.0 の平方根(1.4142)を代入 z = y * 2.0 + x * 3.0 ; // y*2+x*3をzに代入 // 変数の内容の表示 printf( "%d\n" , i ) ; // 整数型(%d)で、 i の値を表示 printf( "%f\n" , x ) ; // 単精度実数(%f) で、x の値を表示 printf( "%lf\n" , z ) ; // 倍精度実数(%lf)で、z の値を表示 printf( "iの値は%d,xの値は%lfです。\n" , i , x ) ; return 0 ; // 正常終了 0 を返す }
変数(計算結果を格納する入れ物)を使う場合は、変数を宣言する。
変数名には、何が入っているのか理解しやすいように、名前をつければいい。(英字で始まり、英数字が続くもの,_が入ってもいい)
変数に値を記憶する時は、”変数名=式 ;”の様に書くと、代入演算子”=” の右辺を計算し、その計算結果が左辺の変数に保存される。
変数の内容を表示する時には、printf() の文字列の中に、%d,%f,%lf などの表示したい式の型に応じたものを書いておく。
式の値が、その %.. の部分に書き込まれて、出力される。
繰り返しの制御命令
最も基礎的な繰り返し命令として、for() 文を説明。
#include <stdio.h> int main() { int i ; for( i = 1 ; i <= 10 ; i++ ) { // iを1から10まで変化させる。 printf( "%d %d\n" , i , i*i ) ; // i と iの二乗を表示 } return 0 ; }
for文の意味を説明するために、対応するフローチャートを示す。
先のプログラムをフローチャートで示し、その命令の実行順序と、その変数の変化を下図に示す。
理解度確認
以下のプログラムの実行順序と、最終結果で表示される内容を答えよ。
ポインタを使った処理
この後の授業で、ポインタを使ったプログラムが増えるので、ポインタの理解の確認
ポインタと引数
値渡し
// 値渡しのプログラム void foo( int x ) { // x は局所変数(仮引数は呼出時に // 対応する実引数で初期化される。 x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 // 処理後も main::a は 123 のまま。 foo( a ) ; // 124 }
このプログラムでは、aの値は変化せずに、124,124 が表示される。
でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか?
// 大域変数を使う場合 int x ; void foo() { x++ ; printf( "%d¥n" , x ) ; } void main() { x = 123 ; foo() ; // 124 foo() ; // 125 }
しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。
// 大域変数が原因で予想外の挙動をしめす簡単な例 int i ; void foo() { for( i = 0 ; i < 2 ; i++ ) printf( "A" ) ; } void main() { for( i = 0 ; i < 3 ; i++ ) // このプログラムでは、AA AA AA と foo() ; // 表示されない。 }
静的局所変数
大域変数を使わない方法としては、静的局所変数( static )を使う方法もある。
// 静的局所変数を使う場合 void foo() { static int x = 123 ; // x は foo の内部でのみ使用可 // x はプログラム起動時に作られ 123 で初期化される。 x++ ; printf( "%d¥n" , x ) ; } void main() { foo() ; // 124 foo() ; // 125 // ここで x = 321 といった代入はできない }
静的局所変数は、変数の寿命が大域変数と同じように、プログラム起動から終了までの間だが、参照できるスコープは所属するブロック内に限られる。
ポインタ渡し
C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。
// ポインタ渡しのプログラム void foo( int* p ) { // p はポインタ (*p)++ ; printf( "%d¥n" , *p ) ; } void main() { int a = 123 ; foo( &a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( &a ) ; // 124 } // さらに125と増える。
ポインタを利用して引数に副作用を与える方法は、ポインタを正しく理解していないプログラマーでは、危険な操作となる。C++では、ポインタ渡しを使わないようにするために、参照渡しを利用する。
参照渡し
// ポインタ渡しのプログラム void foo( int& x ) { // xは参照 x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( a ) ; // 124 } // さらに125と増える。
ポインタ渡しを使う処理
// ポインタ渡しのプログラム void swap( int* pa , int* pb ) { int t = *pa ; *pa = *pb ; *pb = t ; } void main() { int a = 123 ; int b = 111 ; swap( &a , &b ) ; printf( "%d %d¥n" , a , b ) ; }