情報処理Ⅱ ２００５年１２月９日（金）

第１回レポートについて 解説（PDF）を作って，授業ページからリンクしました． 以下の人は，見ておいてください． 課題は公開しません． 問２で小数点以下３１桁まで解答してくれた人 問４の出題意図がよく分からなかった人 実はプログラムにバグがあるんじゃないかと思った人 期末試験でちょっとでもいい点をとりたい人

前回学んだこと 関数を自分で定義し，変数の利用方法・範囲を明示的に制限することで，適切な機能分割を図る． 関数を自分で定義することができる．関数を呼び出すとき，引数は値渡しで授受される． 「変数の定義」と「オブジェクトの生成」は別． オブジェクトの生成・破棄のタイミングに注意する．

本日学ぶこと 関数の補足 並べ替え問題 再帰(recursion)

補足１：引数の授受 Cの関数呼び出しでは必ず値渡し(call by value)になる． 値渡し: 実引数のコピーが仮引数に格納される．その後，仮引数の値を変更しても，実引数の値には影響しない． 参照渡し(call by reference)をしたければ，ポインタ値を引数とすればよい． 参照渡し: 仮引数の値を変更すれば，実引数の値もそれに変わる．Cではこの意味での参照渡しをすることができないが，ポインタ値を渡すことで，その参照先の値を変えることができる． 実引数を，配列変数の名前，または変数の前に「&」をつけたものにする． 仮引数はポインタ変数にする．

補足２：ポインタ値の値渡し 関数： 呼び出し側： message wakayama 'W' 'a' 'k' 'a' 'y' 'a' 'm' void print_message(char *message) { printf("%s\n", message); } 呼び出し側： char wakayama[] = "wakayama"; print_message(wakayama); 実引数の値（ポインタ値）は変更不可． 参照先（文字列 "Wakayama"の 中身)は変更可． 関数print_messageの中 message wakayama 'W' 'a' 'k' 'a' 'y' 'a' 'm' 'a' '\0'

補足３：複数の値を返すには ポインタ値を渡して，関数の中で参照先の値を変更する． 例 x y void swapint(int *x, int *y) { int tmp = *x; *x = *y; *y = tmp; } int a = 3; b = 5; swapint(&a, &b); a=3 b=5 swapint x y tmp a=5 b=3

並べ替え問題 処理対象：intの１次元配列 並べ替えは「ソート(sort)」，「ソーティング(sorting)」，「整列」とも呼ばれる． ４ 処理前： ４ ２ ５ １ ６ ８ ３ ７ 処理後： １ ７ ８ ６ ５ ４ ３ ２

ソートとは データを，何らかの基準で順番に並べること． 例 試験の点数順に学生番号を出力する 時系列で出力される情報を，キーワードごとに並べる 学生番号：0003 氏名：さしすせそ 情処Ⅰの点数：90 情処Ⅱの点数：0 修得単位数： 24 学生番号：0002 氏名：かきくけこ 情処Ⅰの点数：60 情処Ⅱの点数：99 修得単位数： 48 学生番号：0002 氏名：かきくけこ 情処Ⅰの点数：60 情処Ⅱの点数：99 修得単位数： 48 学生番号：0001 氏名：あいうえお 情処Ⅰの点数：80 情処Ⅱの点数：75 修得単位数： 52 学生番号：0001 氏名：あいうえお 情処Ⅰの点数：80 情処Ⅱの点数：75 修得単位数： 52 学生番号：0003 氏名：さしすせそ 情処Ⅰの点数：90 情処Ⅱの点数：0 修得単位数： 24 学生番号で昇順ソート 情処Ⅰの点数で降順ソート （ソートの）「キー」という

並べ替え問題：定義する関数 int get_array_length(int *array); 配列の要素数を求める． × sizeof(array)/sizeof(array[0]) void print_array(const char *message, int *array); メッセージと，配列の各値を出力する． void sort_by_selection(int *array); 選択法を用いて並べ替える． 配列の中身を書き換える．

関数の呼び出し関係 main print_array sort_by_selection get_array_length

再帰呼び出しとは 関数の内部で自分自身を呼び出すことを，再帰呼び出し(recursive call)という． 用途 注意点 再帰的（帰納的，循環的）な定義 バックトラック(backtrack) 分割統治法(divide-and-conquer) 注意点 無限ループにならないようにする． 再帰を使わないほうがよいこともある．

カウントダウンするプログラム 自作関数countdownの定義の中で，countdownを呼び出している．

カウントアップするプログラム 出力の位置を変えると，カウントアップになる． カウントアップ，カウントダウンともに，再帰呼び出しなしの プログラムのほうが，効率はよい． なぜ再帰呼び出しは効率が悪いか？ …関数呼び出しのコスト（オーバーヘッド）があるから．

なぜ再帰呼び出しが可能なのか？ 同一の変数名x に対して複数の このようなデータ 構造を，「スタック」 オブジェクトが という． 生成される． このようなデータ 構造を，「スタック」 という． countdown x = 0 countdown x = 1 countdownの再帰呼び出しを終えたときの戻り先 countdownの呼び出し（関数処理）を終えたときの戻り先 countdown関数処理時に 生成されるオブジェクト main x = 2 main関数処理時に 生成されるオブジェクト num = 2

再帰的な定義の例 階乗 フィボナッチ数列 再帰呼び出しを用いれば，シンプルに書ける． しかしこれらも，whileループのほうが効率がよい． 0! = 1, 1! = 1 n! = n×(n-1)!　(n≧2) フィボナッチ数列 a1 = 1, a2 = 1 an = an-1 + an-2 　(n≧3) 再帰呼び出しを用いれば，シンプルに書ける． しかしこれらも，whileループのほうが効率がよい．

分割統治法 対象領域を細分化して求め（分割），全体として正しい解になる（統治）ようにする． 例: クイックソート ４ ７ ３ ８ ６ １ ２ ５ ２ ８ ５ ７ ６ １ ３ ４ 「４より小」と 「４より大」に 分ける． １ ８ ７ ６ ５ ４ ３ ２ １ ２ ３ ４ ５ ６ ７ ８

クイックソートの関数呼び出し 配列領域，開始位置，終了位置を引数とする． ４ ７ ３ ８ ６ １ ２ ５ ２ ３ １ ４ ６ ７ ８ ５ １

関数の呼び出し関係 (quicksort.c) main get_array_length quicksort print_array 再帰！

まとめ 再帰呼び出しを用いて関数を定義すると，プログラムがすっきり書けることがある． 一般に，再帰を用いないほうが効率的である． 再帰的に定義された問題に適用すると，効果的． 一般に，再帰を用いないほうが効率的である． 関数内のauto変数は，関数呼び出しごとに生成される．

今後の予定 第１０回：１２月１６日（金） 第１１回：１２月２２日（木） １６：３０～１８：００ 第１２回：１月１３日（金） 第１１回：１２月２２日（木）　１６：３０～１８：００ （１２月２３日（金）は祝日） 第１２回：１月１３日（金） 第１３回：１月１９日（木）　１６：３０～１８：００　（？） 第１４回：１月２０日（金） （１月２７日（金）は村川出張のため休講） （試験持込用の書籍を購入しておく？） 試験：２月３日（金）