情報処理Ⅱ 第9回 2004年12月7日(火) 暗号化問題 仕様 入力文にあるすべての'A'をα,すべての'B'をβ,…に置き換 えて出力する.(単一換字暗号という.) 文字は,char型の任意の値とする.ただし'\0'を除く('\0' は必ず'\0'に置き換える,と考えてもよい). どの文字をどの文字に置き換えるかは,プログラムの中で指 定する. 簡単な操作で,復号できるようにする. Wagahai Ha Nekodearu • 暗号化 • 復号 Zdjdkdl Kd Qhnrghdux 2 暗号化問題 方針 暗号化のための変換テーブルを,配列で保持する. • char encrypt_table[256]; encrypt_table['A']の値 encrypt_ table … 'D' +0 'E' +'A' +1 'F' 'G' … +'C' +'B' +'D' +255 3 暗号化問題 方針(続き) 暗号化は,写像を用いる. • 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 4 暗号化問題 fが恒等写像 であるとは, f(x)=x 方針(続き) 定義する関数 • 文字列形式の変換テーブルを,配列に変換する. • 復号のためのテーブルの値を設定する. • 変換テーブルを恒等写像にする(変換のリセット). • 変換テーブルを用いて,文字列を暗号化もしくは復号する. 暗号化と復号はどう区別する? • ./encrypt Wakagai Ha Nekodearu • ./encrypt -d Zdjdkdl Kd Qhnrghdux 「コマンドラインオプション」 と呼ばれる 5 定義する関数(1) void reset_table(char *table) 変換テーブルを恒等写像にする(変換のリセット). encrypt_ table ? 0 table +0 関数内の ローカル変数 (関数が終了すると, 破棄される) ? 1 … 'A' ? 'B' ? +'A' +1 'C' ? … 255 ? +'C' +'B' +255 6 定義する関数(2) 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' 7 定義する関数(3) 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 8 定義する関数(4) 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領域(関数が終了しても,破棄されない) 9 暗号化プログラムの補足 関数set_encrypt_tableの仮引数from, toはconst char *型である.このとき ○ from++; to++; × (*from)++; • fromの参照先(const char型の値)を変更しようとして いる. 暗号化のように,関数開始時点で長さがわからない文字列 を入力にとり,それと同じ長さの暗号文を返すときは,生成す る暗号文が配列領域をはみ出さないように配慮する. encrypt.cでは,100文字(ナル文字を加えて101バイト)を 越える入力は,そこから無視している. 10 まとめ 関数を自分で定義することができる.関数を呼び出すとき, 引数は値渡しで授受される. 変数には,型とは別の属性として,記憶域クラスと型修飾子 を指定できる.static変数とauto変数とでは,大きく挙動 が異なる. 「変数の定義」と「オブジェクトの生成」は別. オブジェクトの生成・破棄のタイミングに注意する. 11 次に学ぶこと 再帰(recursion) 用途 再帰的(帰納的,循環的)な定義 バックトラック(backtrack) 分割統治法(divide-and-conquer) 注意点 無限ループにならないようにする. 再帰を使わないほうがよいこともある. 12 再帰呼び出しとは 関数の内部で自分自身を呼び出すことを,再帰呼び出し (recursive call)という. 例:カウントダウンするプログラム 自作関数countdownの定義の中で,countdownを呼び出し ている. 13 なぜ再帰呼び出しが可能なのか? このようなデータ 構造を,「スタック」 という. x=0 同一の変数名x に対して複数の オブジェクトが 生成される. countdown x=1 countdown countdown関数処理時に 生成されるオブジェクト x=2 main main関数処理時に 生成されるオブジェクト countdownの再帰呼び出 しを終えたときの戻り先 num = 2 countdownの呼び出し(関 数処理)を終えたときの戻 り先 14 再帰呼び出しの注意点 出力の位置を変えると,カウントアップになる. カウントアップ,カウントダウンともに,再帰呼び出しなしの プログラムのほうが,効率はよい. なぜ再帰呼び出しは効率が悪いか? …関数呼び出しのコスト(オーバーヘッド)があるから. 15 再帰的な定義の例 階乗 フィボナッチ数列 0! = 1, 1! = 1 n! = n×(n-1)! (n≧2) a1 = 1, a2 = 1 an= an-1 + an-2 (n≧3) 再帰呼び出しを用いれば,シンプルに書ける. しかしこれらも,whileループのほうが効率がよい. 16 分割統治法 対象領域を細分化して求め(分割),全体として正しい解にな る(統治)ようにする. 例: クイックソート 「4より小」と 「4より大」に 分ける. 4 7 3 8 6 1 2 5 2 3 1 4 6 7 8 5 1 2 3 4 5 6 8 7 1 2 3 4 5 6 7 8 17 ソート(sort) データを,何らかの基準で順番に並べること.「整列」ともいう. 例 試験の点数順に学生番号を出力する 時系列で出力される情報を,キーワードごとに並べる ソートの対象と なる個々の情報を 「レコード」という 学生番号:0003 氏名:さしすせそ 学生番号:0002 情処Ⅰの点数:90 氏名:かきくけこ 情処Ⅱの点数:0 学生番号:0001 情処Ⅰの点数:60 修得単位数: 24 氏名:あいうえお 情処Ⅱの点数:99 情処Ⅰの点数:80 修得単位数: 48 情処Ⅱの点数:75 修得単位数: 52 学生番号:0002 氏名:かきくけこ 学生番号:0001 情処Ⅰの点数:60 氏名:あいうえお 情処Ⅱの点数:99 学生番号:0003 情処Ⅰの点数:80 修得単位数: 48 氏名:さしすせそ 情処Ⅱの点数:75 情処Ⅰの点数:90 修得単位数: 52 情処Ⅱの点数:0 修得単位数: 24 学生番号で昇順ソート (ソートの)「キー」という 情処Ⅰの点数で降順ソート 18 ソートをする際の問題点 計算の手間 処理時間(比較回数)が,レコード数の2乗に比例する方法は, 遅い. レコード数nに対して,n log n に比例するだけの比較回数 でソートできる方法が最善である. 重複キー キーが同じでもレコードが異なっていれば,別物として扱わな ければならない. 安定性 19 文字列並べ替え問題 仕様 コマンドライン引数の各語を,昇順にソートして出力する. • Mukashi Mukashi Aru Tokoroni Ojiisanto Obaasanga Sunde Imashita • Aru Imashita Mukashi Mukashi Obaasanga Ojiisanto Sunde Tokoroni キーは,語の先頭文字とする. • "Mukashi" > "Aru" • "Aru" < "Tokoroni" • "Ojiisanto" == "Obaasanga" クイックソートを用いる. 一般には(辞書順), "Ojiisanto" > "Obaasanga" 20 クイックソートの考え方 緑矢印から橙矢印まで をソートしたい. 4 7 3 8 6 1 2 5 4≦7なので,何もせず 青矢印を進める. 4 7 3 8 6 1 2 5 4>3なので, 赤矢印を進めてから交 換し,青矢印を進める. 4 3 7 8 6 1 2 5 4 3 7 8 6 1 2 5 4>1なので, 交換が発生する. 4 3 1 8 6 7 2 5 21 クイックソートの考え方 4 3 1 8 6 7 2 5 p= 基準値 <p≦ 基準値未満 <p< 基準値以上 p= 走査の位置 <p≦ 未調査 pは,配列中の要素を指す 整数値またはポインタ値 22 クイックソートの考え方 4 3 1 8 6 7 2 5 4>2なので, 交換が発生する. 4 3 1 2 6 7 8 5 配列の走査は終了. 緑矢印と赤矢印の値を 交換しておく. 2 3 1 4 6 7 8 5 2 3 1 4 6 7 8 5 赤矢印の左と右で別々 にソートする.ここで再 帰呼び出しを使用する. 1 2 3 4 5 6 7 8 23 まとめ 再帰呼び出しを用いて関数を定義すると,プログラムがすっ きり書けることがある. 再帰的に定義された問題に適用すると,効果的. 一般に,再帰を用いないほうが効率的である. 関数内のauto変数は,関数呼び出しごとに生成される点に注 意. 24
© Copyright 2025 ExpyDoc