情報処理Ⅱ 第１１回 2004年12月21日（火）

本日学ぶこと：プログラミングの例題３つ 行列式の計算 「ぷよ連結問題」の再帰的解法 「ぷよ連結問題」の非再帰的解法 学ぶこと：配列を含む構造体の利用，再帰呼び出し 「ぷよ連結問題」の再帰的解法 学ぶこと：列挙型の利用，多次元配列を引数とする関数 「ぷよ連結問題」の非再帰的解法 学ぶこと：構造体の利用，配列の写像化 1 2 3 4 5 6 7 8 9 = 0

なぜ行列式を必要とするのか？ 行列や線形代数は，工学の多くの分野の基礎となる． n行n列の行列Aに関する等価な命題 以下では，行数=列数 行列Aによる線形写像（一次変換）は，n次元の空間全体をそれ自身に移す（全単射となる） 行列式|A|≠0 ⇒プログラミングできるのでは？ 以下では，行数=列数 「n次の正方行列(square matrix)」を扱う． nは処理の中で変わり得る．

どのようにして行列式を求めるか？ n=1のときは，成分の値が行列式 n=2, 3のときは「たすきがけ」で求められる． 順列と符号から求める． 行列の基本操作で求める． 余因子から求める．⇒採用！ 1 2 3 5 6 = -3 5 = 5 4 5 6 = 5 8 9 7 8 9

余因子を用いた行列式の求め方 = × + (-1) × × … + + (-1)n-1 × × … … … n次の行列式は， 積と和で求められる． ⇒ 再帰的な定義！ … 符号 各行の1列目の 要素 各行と1列目を 除いた行列の行列式

sqmatrix.cで定義した構造体とその利用方法 最大で n=5 までの次数の行列を格納できる…非効率な上，柔軟性に欠ける 「オブジェクト」と「それを指すポインタ」を定義するのは面倒だ．なんとかできないか… typedef struct sqmatrix { 　int size; 　double element[5][5]; 　} sqmatrix; matrix m, *pm = &m; element [0][0] [0][1] [0][2] [0][3] [0][4] [1][0] [1][1] [1][2] [1][3] [1][4] [2][0] [2][1] [2][2] [2][3] [2][4] [3][0] [3][1] [3][2] [3][3] [3][4] [4][0] [4][1] [4][2] [4][3] [4][4] ２次元の添字は 先に y 座標 後に x 座標 ～列目 (x座標) ～行目 (y座標)

sqmatrix.cで定義した関数（１） sqmatrix *init_sqmatrix(sqmatrix *pm, int size) 行列の次数を指定し，各成分の値を0にする． sqmatrix *set_row(sqmatrix *pm, int y, double *vector) 行列の特定の行の値（行ベクトル）を設定する． void print_sqmatrix(sqmatrix *pm, double *det) 行列の内容を出力する． detがNULLでなければ，行列式の値として*detも出力する． 「init」は 「initialize」の略

sqmatrix.cで定義した関数（２） sqmatrix *remove_row_column(sqmatrix *pm, int y, int x) 指定された行と列を取り除いた行列にする． pmが参照するsqmatrixオブジェクトが書き換えられる． 次数（行数，列数）は1減る． double calc_determinant(sqmatrix *pm) 行列式を求める． 再帰呼び出しを使用している． 次数の小さい行列は，関数内のローカル変数(auto変数）としてオブジェクトが生成される．

実行して確認 1 2 3 4 5 6 7 8 9 = 0 1 2 3 4 5 6 7 8 = ? 1/2 2/2 3/2 4/2 5/2 6/2 7/2 8/2 0/2 = ?

ぷよ連結問題 ぷよが配置された２次元空間（フィールド）と，その中の座標を入力に取り，そこと連結する「ぷよ」の個数を求めよ．

フィールドの表現（１） フィールドは２次元 ⇒２次元配列を使用 色は赤・青・黄と空白 ⇒char型で表現 ２次元の添字は 先に y 座標 後に x 座標 char field[高さ][幅] = { 0, 0, 3, 0, 0, 0, 3, 3, 2, 1, 0, 1, 1, 3, 2, 2, 2, 2, 1, 1, 2, 3, 3, 2, 1, 2, 2, 3, 1, 3, 2, 2, 1, 3, 3, 3, }; …1 …2 …3 空白…0

フィールドの表現（２） しかし… マスに入る値を列挙型で表現する． マスに入る値はいろいろあるのでは？ 色の番号（数値）は重要か？ enum puyo { P_EMPTY, P_RED, P_BLUE, P_YELLOW, P_GREEN, P_PURPLE, P_OJAMA, P_MAX }; enum puyo型の値（もしくは整数値）が色ぷよか否かは，自作関数is_coloredで判定する． 7

ぷよ連結問題・再帰版（１） 考え方 着目する地点の上下左右に探索を 広げる． 連結するぷよの個数は， 1 + 「上に伸ばして連結する個数」 + 「下に伸ばして連結する個数」 + 「左に伸ばして連結する個数」 + 「右に伸ばして連結する個数」 探索済の情報を格納しておく． フィールドの値の最上位ビットで 無限ループ回避のため 1 探索済？ ぷよの種類

ぷよ連結問題・再帰版（２） ２次元フィールドfieldと，その中の座標(x,y)を入力に取り，そこと色ぷよcolorで連結するぷよの個数calc_puyo(field, x, y, color)は， 座標がフィールド外なら，0 色ぷよでないか，色がcolorと異なっていれば，0 探索済なら，0 以上のいずれでもないなら，そこを探索済とした上で， 1 + calc_puyo(field, x, y-1, color) + calc_puyo(field, x, y+1, color) + calc_puyo(field, x-1, y, color) + calc_puyo(field, x+1, y, color) 自作関数 is_connected 再帰呼び出し！

バックトラック 後戻り法ともいう． 木など，枝分かれする対象をすべて探索するのに有用． 再帰呼び出しを使用し，戻る地点の情報をスタックに乗せる． 」が 戻る地点の情報 「

ぷよ連結問題とバックトラック

再帰は効率的？ 6×6のフィールドで全部同じ色ぷよのとき，calc_puyoは 合計36回呼び出される． や などのトータル個数 　　　　や　　　などのトータル個数 最大36段の深さ(level)の呼び出しになる． 図で表示される　　　　や　　　などの最大の個数

関数の仮引数が配列の形に見えても，それはポインタである． 多次元配列を引数とする関数 （１次元）配列を引数とする関数 char a[] = "wakayama"; len = strlen(a); int strlen(const char *s) 多次元配列を引数とする関数 char field[6][6]; color = get_puyo(field, 0, 0); int get_puyo(char field[][6], int x, int y) aは char [9]型の 配列変数 実引数のaは char *型の ポインタ値 仮引数のsは const char *型の ポインタ変数 fieldは char [6][6]型の 配列変数 実引数の fieldは char (*)[6]型 のポインタ値 仮引数のfieldは char [][6]型 （char (*)[6]型）の ポインタ変数 関数の仮引数が配列の形に見えても，それはポインタである．

名前重要（１） 「名前」とは，プログラムで使用できる識別子やラベルのこと． なぜ名前重要？ 規格として使用できる文字や重複宣言できる条件が決まっているが，それと別に（読みやすさの観点で）気を配りたい． なぜ名前重要？ 他の人が読みやすくなる． 明日の自分も「他の人」． 効率よくプログラムを書ける． タイプ数を減らすために１～２文字の変数ばかりにしてみても，バグが入りやすく，結局効率は悪くなる． sqmatrix color get_puyo calc_determinant is_colored P_RED

名前重要（２） 識別子やラベルの名称には一貫性を持たせる． 略語も適度に取り入れる． 関数 print_sqmatrix, calc_puyo, is_colored gethostbyname, isdigit 変数 ローカル変数は短く 広い範囲で用いられるものは長く，もしくはわかりやすく 略語も適度に取り入れる． まずは適当な名前をつけ，あとでテキストエディタの一括置換機能で修正していくのもよい． 置換すべきでないものを置換しないように 「動詞_名詞(_修飾語)」 が基本

ぷよ連結問題・非再帰版（１） データ構造を改善しておきたい． 構造体で定義する． 「一つの２次元配列」のみでは 得点や連鎖数などが保存できない． 関数の仮引数が長くなってしまう． 構造体で定義する． 構造体のポインタ渡しで値を参照・書き換えしてもらう．

ぷよ連結問題・非再帰版（２） 考え方 それぞれのマスに領域番号をつける． 連結していれば同じ領域番号になるよう，フィールドを何度も調査して値を変えていく． 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3 7 9 10 12 13 22 29 33

ぷよ連結問題・非再帰版（３） 毎回フィールドを全部調査するのは手間がかかる． ⇒最初に領域番号を簡単に設定し，あとで調整する． ２値画像の連結領域解析の手法を利用 領域番号の求め方 3 8 ? 3 8 9 着目するマスの 上と左の色・領域番号 を見て値を決める． 16 22 ? 16 22 20 21 26 ? 20 21 26 21 26 =

ppb->parentregion[26] = 21 領域番号間の関係 各領域番号について，それよりも小さい領域番号と同じ領域にするための情報を，配列で保持する． そのような領域がなければ，値は-1とする． 要素数は？ ⇒マスの個数を用意しておく． この配列は，領域番号から領域番号への 写像となる． 21 26 = ppb->parentregion[26] = 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 すべてのマスが異なる領域になる例

配列の写像化（１） 簡易設定が終わった ところ 同一視できる 領域番号 領域番号 個数 ppb->region count[ ] ppb->parent region[ ] 1 1 -1 1 2 3 4 5 6 7 8 9 10 11 12 3 2 -1 8 3 -1 1 4 -1 1 5 -1 4 6 -1 6 7 -1 2 8 3 1 9 -1 1 10 7 1 11 8 1 12 -1

配列の写像化（２） 最終状態 同一視できる 領域番号 領域番号 個数 ppb->region count[ ] ppb->parent region[ ] 1 1 -1 1 2 3 4 5 6 7 9 12 3 2 -1 11 3 -1 1 4 -1 1 5 -1 4 6 -1 7 7 -1 8 3 1 9 -1 10 7 11 3 1 12 -1

関数定義の注意点 関数init_fieldは，フィールド構造体を生成し，そのポインタを返す．このオブジェクトは 『「オブジェクト」と「それを指すポインタ」を定義するのは面倒だ．なんとかできないか…』の解答 関数init_fieldは，フィールド構造体を生成し，そのポインタを返す．このオブジェクトは ライブラリ関数mallocを使用して，実行時に生成している． 生成時の値は不定． auto変数の領域（スタック）やstatic領域とは別の（「ヒープ」と呼ばれる）領域で確保される． ブロックを抜けたり関数を終了したりしても破棄されない．プログラム終了時か，ライブラリ関数のfreeを呼び出したときに破棄される． puyoboard オブジェクト ヒープ スタック static領域 ppb

まとめ プログラムを作るときは まずデータ構造（配列，構造体，列挙型など）を検討し， 次に目的ごとに処理（関数）を定める． 再帰呼び出しを使用できるか，使用してよいか検討する． 「一つの問題に一つの解法」ではないことに留意する．

今後の日程 １月１８日，２５日，２月１日は通常通り授業 ２月８日に試験 毎回小テストを実施．出題範囲は，授業で話した内容全部 ２月１日は，おさらい問題を実施 ２月８日に試験 ７５点満点 自筆ノート１冊と，Ｃ言語の教科書のみ持込可