情報処理Ⅱ 第９回 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 定義する関数（１） void reset_table(char *table) 変換テーブルを恒等写像にする（変換のリセット）． encrypt_ table ? 0 table +0 関数内の ローカル変数 （関数が終了すると， 破棄される） ? 1 … 'A' ? 'B' ? +'A' +1 'C' ? … 255 ? +'C' +'B' +255 6 定義する関数（２） 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 定義する関数（３） 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 定義する関数（４） 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 分割統治法 対象領域を細分化して求め（分割），全体として正しい解にな る（統治）ようにする． 例: クイックソート 「４より小」と 「４より大」に 分ける． ４ ７ ３ ８ ６ １ ２ ５ ２ ３ １ ４ ６ ７ ８ ５ １ ２ ３ ４ ５ ６ ８ ７ １ ２ ３ ４ ５ ６ ７ ８ 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＞3なので， 赤矢印を進めてから交 換し，青矢印を進める． ４ ３ ７ ８ ６ １ ２ ５ ４ ３ ７ ８ ６ １ ２ ５ 4＞1なので， 交換が発生する． ４ ３ １ ８ ６ ７ ２ ５ 21 クイックソートの考え方 ４ ３ １ ８ ６ ７ ２ ５ p= 基準値 ＜p≦ 基準値未満 ＜p＜ 基準値以上 p= 走査の位置 ＜p≦ 未調査 pは，配列中の要素を指す 整数値またはポインタ値 22 クイックソートの考え方 ４ ３ １ ８ ６ ７ ２ ５ 4＞2なので， 交換が発生する． ４ ３ １ ２ ６ ７ ８ ５ 配列の走査は終了． 緑矢印と赤矢印の値を 交換しておく． ２ ３ １ ４ ６ ７ ８ ５ ２ ３ １ ４ ６ ７ ８ ５ 赤矢印の左と右で別々 にソートする．ここで再 帰呼び出しを使用する． １ ２ ３ ４ ５ ６ ７ ８ 23 まとめ 再帰呼び出しを用いて関数を定義すると，プログラムがすっ きり書けることがある． 再帰的に定義された問題に適用すると，効果的． 一般に，再帰を用いないほうが効率的である． 関数内のauto変数は，関数呼び出しごとに生成される点に注 意． 24
© Copyright 2024 ExpyDoc
