ホーム » 2018 » 5月 » 10

日別アーカイブ: 2018年5月10日

2018年5月
« 4月    
 12345
6789101112
13141516171819
20212223242526
2728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

複素数とクラス・隠蔽化の演習

コンストラクタやメソッドの書き方

前回のプログラムを、もう少しC++のオブジェクト指向っぽい書き方を導入してみる。この際に、分かりやすく記述するため、行数が長くなってきた時のための処理を考慮して、記述してみる。

#include <stdio.h>
#include <math.h>
class Complex {
private:
   double re ;
   double im ;
public:
   // 絶対座標系でも極座標系でも、実部・虚部・絶対値・偏角を扱うため
   inline double get_re() const { return re ; }
   inline double get_im() const { return im ; }
   inline double get_r()  const { return sqrt( re*re + im*im ) ; }
   inline double get_th() const { return atan2( im , re ) ; }

   // 極座標系なら、以下のような getterメソッド を書いておけば、
   //   座標系を気にせず処理がかける。
   // inline double get_re() const { return r * cos( th ) ; }
   // inline double get_r()  const { return r ; }

   // inline は、開いたサブルーチンで実装してくれるので処理速度が遅くならない
   // foo() const { ... } は、オブジェクトに副作用が無いことを示す。

   // コンストラクタのメンバー変数の初期化の書き方
   // Complex( ... )
   // : 要素1( 値1 ) , 要素2( 値2 ) ...
   // {  その他の初期化
   // }
   Complex()                       // コンストラクタ
   : re( 0.0 ) , im( 0.0 ) {}
   Complex( double r , double i )  // コンストラクタ
   : re( r ) , im( i ) {}

   // メソッドのプロトタイプ宣言
   //  メソッドの中身が長くなる場合は、
   //  名前と引数だけを宣言しておく
   void print() ;
   void add( Complex ) ;
   void mul( Complex ) ;
} ; // ←しつこいけどセミコロン忘れないでね。

// クラス宣言の外にメソッドの定義を書く
//   メソッドの中身の記述 「::」をクラス限定子と呼ぶ
void Complex::print() {
   printf( "%lf + j%lf¥n" , get_re() , get_im() ) ;
}
void Complex::add( Complex z ) {
   re = re + z.re ;
   im = im + z.im ;
}
void Complex::mul( Complex z ) {
   double r = re * z.re - im * z.im ;
   double i = re * z.im + im * z.re ;
   re = r ;
   im = i ;
}

int main() {
   Complex a( 1.0 , 2.0 ) ;
   Complex b( 2.0 , 4.0 ) ;
   a.add( b ) ;
   a.print() ;
   return 0 ;
}

参考資料

レポート1(複素数の加減乗除)

授業中に示した上記のプログラムをベースに、 記載されていない減算・除算のプログラムを作成し、レポートを作成する。 レポートには、下記のものを記載すること。

  • プログラムリスト
  • プログラムへの説明
  • 動作確認の結果
  • プログラムより理解できること。
    実際にプログラムを書いてみて分かった問題点など…

マージソートのオーダー

マージソートの分析

マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。

このことから、再帰方程式は、以下のようになる。

  • Tm(1)=Ta

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。






よって、

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

  1. データ件数 N= 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
  2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。

メモリ利用の効率

次にメモリの利用効率の話について解説する。
例えば、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。

#define MEMBER_SIZE 50
#define NAME_LENGTH 20
char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;

しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。 また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 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