情報処理Ⅱ ２００５年１２月２２日（木）.

Presentation on theme: "情報処理Ⅱ ２００５年１２月２２日（木）."— Presentation transcript:

1 情報処理Ⅱ ２００５年１２月２２日（木）

2 本日学ぶこと：プログラミングの例題２つ 暗号化問題 ぷよ連結問題 Wagahai Ha Nekodearu
学ぶこと：配列と写像，static変数 ぷよ連結問題 学ぶこと：列挙型，再帰とトラックバック，多次元配列を引数とする関数 Wagahai Ha Nekodearu Zdjdkdl Kd Qhnrghdux

3 暗号化問題 仕様 入力文にあるすべての'A'をα，すべての'B'をβ，…に置き換えて出力する．（単一換字暗号という．）
文字は，char型の任意の値とする．ただし'\0'を除く（'\0'は必ず'\0'に置き換える，と考えてもよい）． どの文字をどの文字に置き換えるかは，プログラムの中で指定する． 簡単な操作で，復号できるようにする． 　Wagahai Ha Nekodearu 　Zdjdkdl Kd Qhnrghdux 暗号化 復号

4 暗号化問題 （まずい）方針 'A'をα，'B'をβ，…に置き換えるのを switch～caseで行う． プログラムが無駄に長くなる．
柔軟性に欠ける． char encrypt_char(char c) { switch (c) { case 'A': return 'D'; case 'B': return 'E'; ... }

5 暗号化問題 encrypt_ table … 'D' 'E' 'F' 'G' … +0 +'A' +'C' +1 +'B' +'D'
... 'E' 'B' 'D' 'A' 変換後 変換前 方針 暗号化のための変換表（暗号化表）を， 配列で保持する． char encrypt_table[256]; encrypt_table['A']の値 encrypt_ table … 'D' 'E' 'F' 'G' … +0 +'A' +'C' +1 +'B' +'D' +255

6 暗号化問題 方針（続き） 暗号化は，写像を用いる．
a = 'A'; のとき，b = encrypt_table[a]; でbの値が'D'となるようにするには，あらかじめencrypt_table['A']の値を'D'としておけばよい． 復号のための変換表（復号表）は，逆写像を用いて求める． char decrypt_table[256]; decrypt_table[encrypt_table['A']] = 'A'; gがfの逆写像 であるとは， g(f(x))=x

7 暗号化問題 方針（続き） 定義する関数 変換表を恒等写像にする． 暗号化表を設定する． 暗号化表を用いて，復号表を設定する．
fが恒等写像 であるとは， f(x)=x 方針（続き） 定義する関数 変換表を恒等写像にする． 暗号化表を設定する． 暗号化表を用いて，復号表を設定する． 変換表を用いて，文字列を暗号化もしくは復号する． 暗号化と復号はどう区別する？ 暗号化：./encrypt Wakagai Ha Nekodearu 復号： ./encrypt -d Zdjdkdl Kd Qhnrghdux 「コマンドラインオプション」と呼ばれる

8 定義する関数（１） void reset_table(char *table); encrypt_ table ? 1 'A' 'B' …
変換表を恒等写像にする． encrypt_ table ? 1 'A' 'B' … 'C' 255 ? … ? ? ? … ? table +0 +'A' +'C' +1 +'B' +255 関数内の ローカル変数 （関数が終了すると，破棄される）

9 定義する関数（２） void set_encrypt_table(char *table, const char *from, const char *to); 二つの文字列を用いて，暗号化表を設定する． encrypt_ table … 'D' +'A' 'E' +'B' 'F' +'C' … table from to 'A' 'B' 'C' … '\0' 'D' 'E' 'F' … '\0'

10 定義する関数（３） void set_decrypt_table(char *table, const char *encrypt_table); 暗号化表を用いて，復号表を設定する． decrypt_ table … 'A' … table +0 +'A' +'C' +1 +'B' +'D' +255 encrypt_ table … 'D' … encrypt_ table +0 +'A' +'C' +1 +'B' +'D' +255

11 定義する関数（４） char *encrypt(const char *text, const char *table);
変換表を用いて，文字列を暗号化もしくは復号する． 「暗号化」と「復号」の処理を共通化している！ 戻り値は，変換された文字列で，static変数result（のポインタ値）となる． text 'W' 'a' 'g' 'a' 'h' 'a' 'i' '\0' table … 'D' 'E' 'F' 'G' … result 'Z' 'd' 'j' 'd' 'k' 'd' 'l' '\0' static領域（関数が終了しても，破棄されない） 戻り値

12 暗号化プログラムの補足 関数set_encrypt_tableの仮引数from, toは const char *型である．このとき
fromの参照先(const char型の値)を変更しようとしている． 暗号化のように，関数開始時点で長さがわからない文字列を入力にとり，それと同じ長さの暗号文を返すときは，生成する暗号文が配列領域をはみ出さないように配慮する． encrypt.cでは，100文字を越える入力は，そこから無視している．

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

14 フィールドの表現（１） フィールドは２次元 ⇒２次元配列を使用 色は赤・青・黄と空白 ⇒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

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

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

17 ぷよ連結問題・再帰版（２） ２次元フィールド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 再帰呼び出し！

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

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

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

21 関数の仮引数が配列の形に見えても，それはポインタである．
多次元配列を引数とする関数 （１次元）配列を引数とする関数 char a[] = "wakayama"; len = strlen(a); int strlen(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は char *型の ポインタ変数 実引数の fieldは char (*)[6]型 のポインタ値 仮引数のfieldは char [ ][6]型 （char (*)[6]型）の ポインタ変数 fieldは char [6][6]型の 配列変数 関数の仮引数が配列の形に見えても，それはポインタである．

22 仮引数と実引数が同じ名前でいいの？ 言語規格上，問題ない． 実用上も便利．
仮引数と実引数の有効範囲が違うから 実用上も便利． 大きな長さの関数を分割したいとき，変数名を共通化すればいいから デメリット：変数名を一括して置換したときに，置換すべきでないものを置換してしまうかも