情報処理Ⅱ
２００５年１２月２２日（木）
本日学ぶこと：プログラミングの例題２つ
暗号化問題
学ぶこと：配列と写像，static変数
ぷよ連結問題
学ぶこと：列挙型，再帰とトラックバック，多次元配列を引数と
する関数
Wagahai Ha Nekodearu
Zdjdkdl Kd Qhnrghdux
2
暗号化問題
仕様
入力文にあるすべての'A'をα，すべての'B'をβ，…に置き換
えて出力する．（単一換字暗号という．）
文字は，char型の任意の値とする．ただし'\0'を除く（'\0'
は必ず'\0'に置き換える，と考えてもよい）．
どの文字をどの文字に置き換えるかは，プログラムの中で指
定する．
簡単な操作で，復号できるようにする．
Wagahai Ha Nekodearu
•
暗号化
•
復号
Zdjdkdl Kd Qhnrghdux
3
暗号化問題
（まずい）方針
'A'をα，'B'をβ，…に置き換えるのを
switch～caseで行う．
• プログラムが無駄に長くなる．
• 柔軟性に欠ける．
char encrypt_char(char c)
{
switch (c) {
case 'A':
return 'D';
case 'B':
return 'E';
...
}
}
4
変換前 変換後
暗号化問題
方針
暗号化のための変換表（暗号化表）を，
配列で保持する．
• char encrypt_table[256];
'A'
'D'
'B'
'E'
...
...
encrypt_table['A']の値
encrypt_
table
… 'D'
+0
'E'
+'A'
+1
'F'
'G' …
+'C'
+'B'
+'D'
+255
5
暗号化問題
方針（続き）
暗号化は，写像を用いる．
• 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
6
暗号化問題
方針（続き）
fが恒等写像
であるとは，
f(x)=x
定義する関数
• 変換表を恒等写像にする．
• 暗号化表を設定する．
• 暗号化表を用いて，復号表を設定する．
• 変換表を用いて，文字列を暗号化もしくは復号する．
暗号化と復号はどう区別する？
• 暗号化：./encrypt Wakagai Ha Nekodearu
• 復号： ./encrypt -d Zdjdkdl Kd Qhnrghdux
「コマンドラインオプション」
と呼ばれる
7
定義する関数（１）
void reset_table(char *table);
変換表を恒等写像にする．
encrypt_
table
?
0
table
+0
関数内の
ローカル変数
（関数が終了すると，
破棄される）
?
1
… 'A'
?
'B'
?
+'A'
+1
'C'
? … 255
?
+'C'
+'B'
+255
8
定義する関数（２）
void set_encrypt_table(char *table, const
char *from, const char *to);
二つの文字列を用いて，暗号化表を設定する．
encrypt_
table
… 'D'
table
+'A'
'E'
'F'
…
+'C'
+'B'
from
to
'A' 'B' 'C' … '\0'
'D' 'E' 'F' … '\0'
9
定義する関数（３）
void set_decrypt_table(char *table, const
char *encrypt_table);
暗号化表を用いて，復号表を設定する．
decrypt_
table
table
…
+0
'A' …
+'A'
+1
encrypt_
table
encrypt_
table
+'C'
+'B'
… 'D'
+0
+1
+'A'
+'D'
+255
…
+'B'
+'C'
+'D'
+255
10
定義する関数（４）
char *encrypt(const char *text, const
char *table);
変換表を用いて，文字列を暗号化もしくは復号する．
「暗号化」と「復号」の処理を共通化している！
戻り値は，変換された文字列で，static変数result（のポ
インタ値）となる．
text
table
result
戻り値
'W' 'a' 'g' 'a' 'h' 'a' 'i' '\0'
… 'D' 'E' 'F' 'G' …
'Z' 'd' 'j' 'd' 'k' 'd' 'l' '\0'
static領域（関数が終了しても，破棄されない）
11
暗号化プログラムの補足
関数set_encrypt_tableの仮引数from, toは
const char *型である．このとき
○ from++; to++;
× (*from)++;
• fromの参照先(const char型の値)を変更しようとして
いる．
暗号化のように，関数開始時点で長さがわからない文字列
を入力にとり，それと同じ長さの暗号文を返すときは，生成す
る暗号文が配列領域をはみ出さないように配慮する．
encrypt.cでは，100文字を越える入力は，そこから無視し
ている．
12
ぷよ連結問題
「ぷよ」が配置された２次元空間（フィールド）と，その中の座
標を入力に取り，そこと連結する「ぷよ」の個数を求めよ．
13
フィールドの表現（１）
フィールドは２次元 ⇒２次元配列を使用
色は赤・青・黄と空白 ⇒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,
};
空白…0
…1
…2
…3
14
フィールドの表現（２）
しかし…
マスに入る値はいろいろあるのでは？
色の番号（数値）は重要か？
マスに入る値を列挙型で表現する．
enum puyo {
P_EMPTY, P_RED, P_BLUE, P_YELLOW,
P_GREEN, P_PURPLE, P_OJAMA, P_MAX
};
7
enum puyo型の値（もしくは整数値）が色ぷよか否かは，自作
関数is_coloredで判定する．
•
•
15
ぷよ連結問題・再帰版（１）
考え方
着目する地点の上下左右に探索を
広げる．
連結するぷよの個数は，
1
+ 「上に伸ばして連結する個数」
+ 「下に伸ばして連結する個数」
+ 「左に伸ばして連結する個数」
+ 「右に伸ばして連結する個数」
探索済の情報を格納しておく．
• フィールドの値の最上位ビットで
• 無限ループ回避のため
0 0 0 0 0 0 1 1
探索済？
ぷよの種類
16
ぷよ連結問題・再帰版（２）
２次元フィールドfieldと，その中の座標(x,y)を入力に取
り，そこと色ぷよcolorで連結するぷよの個数
calc_puyo(field, x, y, color)は，
座標がフィールド外なら，0
自作関数
色ぷよでないか，色がcolorと異なっていれば，0
is_connected
探索済なら，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)
17
バックトラック
後戻り法ともいう．
木など，枝分かれする対象をすべて探索するのに有用．
再帰呼び出しを使用し，戻る地点の情報をスタックに乗せる．
「
」が
戻る地点の情報
18
ぷよ連結問題とバックトラック
19
再帰は効率的？
6×6のフィールドで全部同じ色ぷよのとき，calc_puyoは
合計36回呼び出される．
•
や
などの総数
最大36段の深さ(level)の呼び出しになる．
• 図で表示される
や
などの最大の個数
20
多次元配列を引数とする関数
（１次元）配列を引数とする関数
char a[] = "wakayama";
len = strlen(a);
int strlen(char *s);
多次元配列を引数とする関数
aは
char [9]型の
配列変数
実引数のaは
char *型の
ポインタ値
仮引数のsは
char *型の
ポインタ変数
char field[6][6];
color = get_puyo(field, 0, 0);
int get_puyo(char field[][6], int x, int y);
fieldは
char [6][6]型の
配列変数
実引数の
fieldは
char (*)[6]型
のポインタ値
仮引数のfieldは
char [ ][6]型
（char (*)[6]型）の
ポインタ変数
関数の仮引数が配列の形に見えても，それはポインタである．
21
仮引数と実引数が同じ名前でいいの？
言語規格上，問題ない．
実用上も便利．
仮引数と実引数の有効範囲が違うから
大きな長さの関数を分割したいとき，変数名を共通化すればい
いから
デメリット：変数名を一括して置換したときに，置換すべきで
ないものを置換してしまうかも
22
© Copyright 2024 ExpyDoc
