Comments
Description
Transcript
プログラミング言語I 第14回 オブジェクト指向 要求 問題の分析 スタックを
要求
四則演算を正しく扱う電卓が欲しい。
100円ショップで売っている電卓
1 + 2 × 3 =
9になる
でも本当は 7 でなければならない
プログラミング言語I 第14回
オブジェクト指向
1 + 2 × 3 = 7 になる電卓が欲しい
埼玉大学工学部
電気電子システム工学科
伊藤 和人
Copyright © 2008 Kazuhito Ito
問題の分析
スタックを利用
間違いの原因は、加算と乗算の優先順位を
考慮していないこと
スタック = 本を積み重ねたもの
1 + 2 × 3
複数の演算子を比較し、優先順位に
したがって演算を実行する
後入れ、先出しのデータ管理方式
Last-In, First-Out (LIFO)
過去に入力した演算子を記憶する必要あり
Copyright © 2008 Kazuhito Ito
Copyright © 2008 Kazuhito Ito
スタックを用いた演算実行
スタックの実現
計算例 1 + 1 2 ×2 3 =
数値のスタックを用意
1
2
1
(なし)
1
+1
2
1
+1
×2
3
=
2
1
3
2
1
+1 ×2
6
1
+1
+1 ×2
+1
入力
数値スタック
直前演算子
Copyright © 2008 Kazuhito Ito
配列によってスタックを表す
データを積む位置、取り出す位置
・・・ 常にスタックの頂上
スタックの頂上を表す変数=スタックポインタ
例 int stack[100];
int sp=99;
スタックポインタ
大域変数として用意
答え
7
スタック本体
スタックは上位(大きな添え字)から
下位(小さな添え字)に向かってデータを積む
Copyright © 2008 Kazuhito Ito
スタックの操作
データをスタックに積む
push操作
void push( int v )
{
sp位置にデータを
stack[sp--] = v;
入れて、spを減少
}
スタックからデータを取り出す
pop操作
int pop( void )
spを増加し、
{
sp位置の
return stack[++sp];
データを読出し
}
Copyright © 2008 Kazuhito Ito
電卓プログラム例1(続き)
void execute( char op ){
int n1, n2;
n2 = pop();
n1, n2の順序に注意
n1 = pop();
switch( op ){
case '+': n1 = n1+n2; break;
case '-': n1 = n1-n2; break;
case '*': n1 = n1*n2; break;
case '/': n1 = n1/n2; break;
}
push( n1 );
}
スタック先頭の2つの数値を取り出し、
演算結果をスタックに積む
Copyright © 2008 Kazuhito Ito
演算子のスタックを利用
if( type == OPERATOR ){
演算子スタックが空でない
while( ! empty() ){
if( op == '+' || op == '-' ){ スタック上演算の
op1 = pop();
優先順位はop以上
execute( op1 );
}else if( op == '*' || op == '/' ){
op1 = pop();
if( op1 == '*' || op1 == '/' || op1 == '^' ){
execute( op1 );
演算op1の優先順位が
}else{
演算op以上なので
push( op1 );
break;
演算op1を実行
}
}
演算opの優先順位が高い
}
のでop1をスタックに戻す
push( op );
}
演算opをスタックに積む
Copyright © 2008 Kazuhito Ito
電卓プログラム例1
入力データ読み取り
int type, value;
char op, op1=' ', op2 =' ';
数値、演算子、‘=’
while( 1 ){
InputData( &type, &op, &value );
if( type == VALUE ) push( value );
演算子を else if( type == OPERATOR ){
if( op2 != ' ' ){ execute( op2 ); op2 = ' '; }
保留
if( op1 == ' ' ) op1 = op;
優先順位に従い
else if( op1 == '*' || op1 == '/' ){
先の演算を実行
execute(
op1
);
op1
=
op;
優先順位に
}else{ /* (op1 == '+' || op1 == '-') */
従い演算を
if( op == '*' || op == '/' ) op2 = op;
保留
else{ execute( op1 ); op1 = op; }
}
}else{
/* type == EQUAL */
if( op2 != ' ' ){ execute( op2 ); op2 = ' '; }
if( op1 != ' ' ){ execute( op1 ); op1 = ' '; }
}
Copyright © 2008}Kazuhito Ito
電卓プログラムを拡張する
加算・減算と乗算・除算の2種類の優先順位
⇒ op1, op2の2つの変数によって優先順位
を実現可能
⇒ ただし、面倒な場合分けが必要
例えば、べき乗(xy)を組み込む
優先順位は3種類
⇒ さらに場合分けが複雑に
演算子についてもスタックを利用することで
場合分けを簡単に
Copyright © 2008 Kazuhito Ito
問題点
数値のスタックと演算子のスタック
2つのスタックを区別する必要あり
スタックを引数に取る方法 ⇒ 型の問題あり
push( stk_data, value ) push( stk_op, op )
pop( stk_data )
pop( stk_op )
専用の関数を用いる方法 ⇒ 効率が悪い
push_data( value ) push_op( op )
pop_data()
pop_op()
あくまでも関数(手続き)が主体
であることに原因がある
Copyright © 2008 Kazuhito Ito
同じ型の
スタックが
2個ある
場合など
オブジェクト指向
数値スタック、演算子スタックがあり、
スタックに対してpush操作やpop操作を行う
data_stack.push( value ) op_stack.push( op )
data_stack.pop()
op_stack.pop()
クラス
class CValueStack
{
public:
CValueStack();
virtual ~CValueStack();
数値スタック
演算子スタック
オブジェクト(スタック)が主体
この考え方をオブジェクト指向という
Copyright © 2008 Kazuhito Ito
クラス(続き)
各メンバ関数の定義
CValueStack::CValueStack()
コンストラクタ
{
sp = 99;
スタックポインタを初期化
}
CValueStack::~CValueStack()
デストラクタ
{
この場合何もしない
}
void CValueStack::push( int v )
Push操作
{
stack[sp--] = v;
}
int CValueStack::pop( void )
Pop操作
{
return stack[++sp];
}
Copyright © 2008 Kazuhito Ito
クラスを用いる利点
オブジェクト指向の考えを実現する
例: スタックオブジェクトが存在し、スタックに
対してpushやpopといった操作を指示する
オブジェクトの型を定義するもの
例: スタックについて、利用者はデータの読み
書きはpush(), pop()といった関数を使用する
ことだけを知っていればよい。push(), pop()
が実際にはどのようなプログラムになっている
か、知らなくてよい。
プログラムの再利用が容易になる
スタックを利用したいプログラムに、スタックの
クラスを単純にコピーすればよい
Copyright © 2008 Kazuhito Ito
コンストラクタ および
デストラクタ
メソッド
void push( int v );
(スタック操作関数)
int pop( void );
int empty( void ){ return sp==99; }
private:
int stack[100];
int sp;
};
Copyright © 2008 Kazuhito Ito
インライン記述
データ
(記憶領域とスタックポインタ)
インスタンスを作る
クラスからインスタンス(オブジェクト)を作る
CValueStack data_stack;
COpStack op_stack;
int n;
data_stack.push( 100 );
data_stack.push( -200 );
op_stack.push( '+' );
n = data_stack.pop();
インスタンス作成
インスタンスに対して
Push操作
Pop操作
Copyright © 2008 Kazuhito Ito
オブジェクト指向の本当の意味
与えられた要求を実現するプログラムを開
発する際に、要求を分析し、プログラムの
構造を設計するための考え方
操作だけを公開し、中身(実装)は隠す
データと操作(メソッド)
が一体化されている
要求を分析し、本質を抽出
オブジェクトの振る舞い、オブジェクト間関係
計算機プログラムとして表現できるように
単純化する
この作業を「モデリング」という
Copyright © 2008 Kazuhito Ito
(オブジェクト指向モデリング)
モデリング例: 数独
クラスを整理
数独のルール
要求
出典: 朝日新聞
縦列(9マスの列が9つあります)、横列(9マス
の列が9つあります)のそれぞれに1から9まで
の数字が1つずつ入ります
太い線で囲まれた3×3のブロック(それぞれ9
マスあるブロックが9つあります)にも、1から9
までの数字が1つずつ入ります
オブジェクトを抽出
マス(9×9個)
列(9個)
ブロック(9個)
ボード(1個)
行(横列)(9個)
ボックス
CBox
列
CColumn
ボード
CBoard
行
CRow
クラス間の関係を分析
1
1
1
81
1
9
Copyright © 2008 Kazuhito Ito
9個のマスの集め方が異なるだけで、責務は同じ
責務に注目して、クラスCGroupへ抽象化する
1
81
1
CPlace
9
*
Copyright © 2008 Kazuhito Ito
CPlace
9 1
縦列に1から9までの数字が1つずつ入ります
横列に1から9までの数字が1つずつ入ります
ブロックに1から9までの数字が1つずつ入ります
CBoard
マス
CBox
クラスの役割分担(責務)を分析
各オブジェクトを抽象化するクラスを作る
CBoard
Copyright © 2008 Kazuhito Ito
1
CGroup
クラスの定義: CPlace
オブジェクトが
作られるときに
1度だけ実行する
CPlace::CPlace() コンストラクタ
{
int v;
for( v=1 ; v<=9 ; v++ ) aValue[v] = 1;
bFixed = 0;
初期化を行う
}
int CPlace::IsFixed( void )
マスの値が決定して
{
if( bFixed ) return nValue; いれば、その値
未定ならば-1を返す
else
return -1;
}
void CPlace::ExcludeValue( int v )
{
マスの値が未定なら
if( ! bFixed ) aValue[v] = 0;
値vを除外する
} Kazuhito Ito
Copyright © 2008
9
1
CColumn
9
CPlace
9
9
1
CRow
クラスの定義: CPlace
class CPlace
クラスCPlace (マスを表す)
{
public:
コンストラクタ および
CPlace();
デストラクタ
virtual ~CPlace();
void FixValue( void );
メソッド
int IsFixed( void );
int IsValueAllowd( int v ){ return aValue[v]; }
void ExcludeValue( int v );
private:
int bFixed;
int aValue[10];
int nValue;
Copyright © 2008};
Kazuhito Ito
データ
クラスの定義: CPlace
void CPlace::Fix( void ) 唯一可能な値に決定する
{
int v, v0;
int nCount = 0;
for( v=1 ; v<=9 ; v++ ){ このマスに許される
値を数える
if( aValue[v] ){
nCount++; v0 = v;
}
許される値が1つのみ
if( nCount == 1 ){
ならば、その値に決定
bFixed = 1;
for( v=0 ; v<9 ; v++ ) aValue[v] = 0;
aValue[v0] = 1;
nValue = v0;
}
マス(オブジェクト)に対して値を決定する
}
Copyright © 2008 Kazuhito Ito
⇒ 値決定はマスの操作として定義する
クラスの定義: CGroup
class CGroup
{
public:
CGroup();
virtual ~CGroup();
クラスの定義: CGroup
クラスCGroup
(列、行、ボックスを表す)
コンストラクタ および
デストラクタ
メソッド
void SetPlace( int k, CPlace *p );
void L1Infer( void );
レベル1の推論
void Fix( void );
値を決定できる
private:
CPlace *place[9];
};
マスを選ぶ
データ
⇒ グループを構成する
9個のマス
グループを構成する9個のマスを登録するためのメソッド
Copyright © 2008 Kazuhito Ito
CPlaceとCGroupの関係より
行、列、ボックスからグループへ抽象化
(共通化)
class CBoard
{
public:
CBoard();
virtual ~CBoard();
必ずCPlaceのメソッド(インターフェース)を経由
CPlace内の変数bFixed、配列aValueなどは意識
隠蔽(カプセル化)
しない
クラスの役割分担(責務)が明確になる
クラス単位でプログラムの再利用が容易になる
Copyright © 2008 Kazuhito Ito
クラスの定義: CBoard
void CBoard::Initialize() グループとマスの関係を
設定する
{
int i,j,bx,by;
列と行の
for( i=0 ; i<9 ; i++ )
グループを設定
for( j=0 ; j<9 ; j++ ){
column[i].SetPlace( j, &(place[i][j]) );
row[j].SetPlace( i, &(place[i][j]) );
}
for( bx=0 ; bx<3 ; bx++ )
ボックスの
for( by=0 ; by<3 ; by++ ) グループを設定
for( i=0 ; i<3 ; i++ )
for( j=0 ; j<3 ; j++ )
box[bx][by].SetPlace( j*3+i,
&(place[bx*3+i][by*3+j]) );
}
Copyright © 2008 Kazuhito Ito
クラスCBoard
コンストラクタ および
デストラクタ
void Initialize( void );
メソッド
void L1Infer( void );
/* その他のメソッド(省略) */
CGroupでは、CPlaceの実装を知らなくてよい
単に9個のマス間の関係のみを考慮
行、列、ボックスの区別は必要ない
Copyright © 2008 Kazuhito Ito
クラスの定義: CBoard
クラスを用いる利点
void CGroup::L1Infer()
レベル1の推論
{
int k, v;
値vに決定した
for( v=1 ; v<=9 ; v++ ){
マスが存在する
for( k=0 ; k<9 ; k++ ){
if( place[k]->IsFixed() == v ) break;
}
if( k<9 ){
for( k=0 ; k<9 ; k++ )
place[k]->ExcludeValue( v );
}
他の8個のマスでは値vを除外する
}
}
private:
CPlace place[9][9];
CGroup column[9];
CGroup row[9];
CGroup box[3][3];
Copyright © 2008};
Kazuhito Ito
データ
⇒ 81個のマス
9個の列
9個の行
9個のボックス
レベル2の推論を組み込む
「ここ」に入りえない値を除外する
②このボックス
では値5は
3 2
ここに入る
1 8 6
4
5
1 9
7 2
①ここが5に
決まった
③このボックスでは
値5はこれらのマスには入らない
ボックスについてレベル2の推論をするための
機能が必要
グループとしてのボックスに、機能を追加する
Copyright © 2008 Kazuhito Ito
機能を追加したクラスCBox追加
クラスの定義: CBox
クラスCGroupを継承するクラスCBoxを定義
CBoard
1
81
1
CPlace
9
*
一般
1
CGroup
継承
特殊
CBox
クラスCGroupの機能を引き継ぎ、さらに
機能を追加したクラスCBoxを定義する
Copyright © 2008 Kazuhito Ito
クラスの定義を修正
class CBoard
{
public:
CBoard();
virtual ~ CBoard();
void Initialize( void );
void L1Infer( void );
void L2Infer( void );
レベル2推論の
/* その他のメソッド(省略) */ メソッドを追加
private:
CPlace place[9][9];
CGroup column[9];
CGroup row[9];
CBox box[3][3];
ボックスをクラスCBoxに変更
Copyright © 2008};
Kazuhito Ito
クラスCBoardの関数L2Infer
void CBoard::L2Infer( void )
レベル2の推論
{
int bx, by, bx0, by0;
CBoxのメソッドを
int i, j, v;
for( v=1 ; v<=9 ; v++ ){
利用
/* 行方向の推論 */
for( by=0 ; by<3 ; by++ )
for( bx=0 ; bx<3 ; bx++ ){
ボックス(bx,by)では i = box[bx][by].OnlyRow( v );
if( i >= 0 )
値vはi行のみ可能
for( bx0=0 ; bx0<3 ; bx0++ ){
if( bx0 == bx ) continue;
他のボックスでは
box[bx0][by].ExcludeRow( i, v );
i行に値vは入らない
}
}
/* 列方向の推論 */ (省略)
}
Copyright © 2008}Kazuhito Ito
class CBox : public CGroup
{
public:
CBox();
virtual ~CBox();
継承を表す部分
public:
void ExcludeColumn( int i, int v );
void ExcludeRow( int j, int v );
int OnlyColumn( int v );
int OnlyRow( int v );
};
レベル2の
推論用に
追加する
メソッド
CGroupのSetPlace, L1Inferなども利用可
Copyright © 2008 Kazuhito Ito
クラスCBoardの関数Initialize
void CBoard::Initialize()
{
int i,j,bx,by;
列と行の
for( i=0 ; i<9 ; i++ )
グループを設定
for( j=0 ; j<9 ; j++ ){
column[i].SetPlace( j, &(place[i][j]) );
row[j].SetPlace( i, &(place[i][j]) );
}
for( bx=0 ; bx<3 ; bx++ )
ボックスの
for( by=0 ; by<3 ; by++ ) グループを設定
for( i=0 ; i<3 ; i++ )
boxには
for( j=0 ; j<3 ; j++ )
関数SetPlaceが
box[bx][by].SetPlace( j*3+i,
あり、利用可能
&(place[bx*3+i][by*3+j]) );
}
Copyright © 2008 Kazuhito Ito
全く変更不要
まとめ1
オブジェクト指向を紹介
プログラム開発の際に、モデリング(要求分析、
プログラム構成設計)を行うための手法
モデリングを行うことで、バグを少なくし、
プログラム開発効率を向上する
要求とプログラムの動作条件の洗い出し
(異常入力が与えられたときの振る舞いなど)
プログラム全体の構成を概観することで、
無駄な部分、無理のある部分を特定し、改善
する
Copyright © 2008 Kazuhito Ito
まとめ2
オブジェクト指向プログラミング言語(C++)
を利用することで、モデルからプログラム
への移行が容易になる
C言語に比べてC++言語は便利な機能が
あるが、本来はオブジェクト指向の考え方
と合わせて初めて真価を発揮する
だからといってしり込みすることなく、便利なと
ころはドシドシ利用すればいい
Copyright © 2008 Kazuhito Ito
プログラミング言語Iのまとめ
プログラミングによって、今まで世界中のど
こにもないものを作り出すことが可能
プログラミングには、創造性、緻密さ、想像
力、知識が要求される
「習うより慣れろ」とにかくプログラムを作っ
てみるのが習得の条件
プログラムが複雑になると予想したら、い
きなりプログラムを書かずに、まずは分析
と設計(場合によってはオブジェクト指向を
導入)
今はC言語(C++言語)を習得するのがベ
スト
Copyright © 2008 Kazuhito Ito