情報処理Ⅱ ２００６年１２月８日（金）.

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

1 情報処理Ⅱ ２００６年１２月８日（金）

2 本日学ぶこと 関数の補足 既存のプログラムから関数を「抽出する」方法 再帰(recursion) クイックソート

3 関数の抽出 反復語判定プログラム（第７回）を例として 関数を抽出することで一般に 関数抽出の要点
コード量（プログラムのサイズ，ステップ数）は増える． しかし，それぞれの関数のコード量は減り，関数ごとに役割が明確になるため，読みやすい． 関数抽出の要点 ①関数名，②戻り値の型，③仮引数 の順に決める． 変数の有効範囲に注意する． 変数の除去や複製が必要なこともある． 保守性向上

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

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

6 カウントアップするプログラム 出力の位置を変えると，カウントアップになる．
カウントアップ，カウントダウンともに，再帰呼び出しなしの プログラムのほうが，効率はよい． なぜ再帰呼び出しは効率が悪いか？ …関数呼び出しのコスト（オーバーヘッド）があるから． 業務としてのプログラミングで，再帰呼び出しを使用してはならないと（コーディング規約で）定めていることも 再帰呼び出しはしてはいけないと書いている例: 『組み込みソフトウェア開発向けコーディング作法ガイド』p.49 『ずっと受けたかったソフトウェアエンジニアリングの授業2』pp

7 なぜ再帰呼び出しが可能なのか？ 同一の変数名x に対して複数の このようなデータ 構造を，「スタック」 オブジェクトが という．
生成される． このようなデータ 構造を，「スタック」 という． countdown x = 0 countdown x = 1 countdownの再帰呼び出しを終えたときの戻り先 countdownの呼び出し（関数処理）を終えたときの戻り先 countdown関数処理時に 生成されるオブジェクト main x = 2 Cの規格として「スタック」が必須ということではない． しかし，関数呼び出しの構造(mainから関数Aを呼び出し，関数Aの中で関数Bを呼び出し，関数Bの処理を終えたら， 制御は，mainではなく，「関数Aの中で関数Bを呼び出したところ」に戻らなければならない(そして，関数Aの処理を 終えたら，制御は，mainの中で関数Aを呼び出したところに戻る))を実行時に保持するには，スタックが最も合理的 ということである． main関数処理時に 生成されるオブジェクト num = 2

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

9 再帰的な定義の例（２） 木構造 再帰呼び出しは必要？ トーナメント表の決勝戦から順に見て， 優勝チームの戦績を知る
100万個の記録から，欲しいものを 瞬時に獲得する ホームディレクトリ以下のすべての ファイル名を出力する 再帰呼び出しは必要？ するのが自然な場合と，してはいけない 場合がある 呼び出し方よりもデータ構造のほうが重要 「ホームディレクトリ以下のすべてのファイル名を出力する」には，いちいちプログラムを作らなくても， 「find ~」を実行するだけでいい．

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

11 クイックソートの関数呼び出し 配列領域，開始位置，終了位置を引数とする． ４ ７ ３ ８ ６ １ ２ ５ ２ ３ １ ４ ６ ７ ８ ５ １
詳細は， のpp.21～23を参照のこと． １ ２ ３ ４ ５ ６ ７ ８

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

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

14 情報処理Ⅱ ２００６年１２月８日（金）の２

15 ここで学ぶこと ライブラリ関数の活用 （参考）関数の分類 先人の知恵を活用する．
勉強・授業のためでなければ， ライブラリ関数と同じ名前や機能の関数は自作しない． （参考）関数の分類 自作関数: 自分で定義する．⇒ １２月１日のテーマ ライブラリ関数: 出来合いのもの．printfなど．⇒ ここでのテーマ

16 ライブラリ関数とヘッダファイル 既に定義されている関数や定数を利用するには，あらかじめ，適切なファイル名（ヘッダファイル）を記載しておく．
printf なら #include <stdio.h> CHAR_BIT なら #include <limits.h> ライブラリ関数と，記載すべきヘッダファイル名は，manpage で知ることができる． man 3 printf jman 3 printf JM Project ( ヘッダファイルはコンパイル環境が保有しているが，その所在は，環境による． Vine Linuxのコマンド

17 ヘッダファイルとインクルード ヘッダファイルには，定数，構造体や特殊な型，関数プロトタイプなどが宣言・定義されている．
#include <stdlib.h> とすると，/usr/include/stdlib.h を取り込む（インクルードする）． 慣例として，ファイル名は「.h」で終わらせる． ヘッダファイルの中で，他のヘッダファイルをインクルードすることもよく行われる． ヘッダファイルを自作することもある．そのファイルをインクルードするときは，#include "headerfile.h" のように書く． 「.c」や「.h」などを，Windowsユーザは「拡張子」と呼んでいるが， Unix文化では「サフィックス(suffix)」と呼ばれている．

18 有用なライブラリ関数（１） #include <stdio.h> を必要とするもの
int printf(const char *format, ...); int scanf(const char *format, ...); int putchar(int c); … 1文字出力 int getchar(void); …　1文字入力 int sprintf(char *str, const char *format, ...); … printfと同様に文字列を構成し，結果をstr（の指し示す配列領域）に格納する 可変引数 と呼ばれる 可変引数 と呼ばれる

19 有用なライブラリ関数（２） #include <stdlib.h> を必要とするもの
int atoi(char *s); … 文字列から整数値への変換 void exit(int status); … プログラムの終了 int rand(void); … 乱数生成 #include <string.h> を必要とするもの size_t strlen(char *s); … 文字列の長さ int strcmp(char *s1, char *s2); … 文字列比較 char *strstr(char *s1, char *s2); … 文字列検索 char *strcat(char *dest, char *src); …文字列連結 #include <string.h>を必要とするものについて， strcatのdestを除き，char *型の仮引数には，constがつく．

20 有用なライブラリ関数（３） #include <ctype.h> を必要とするもの
int isdigit(int c); … 文字が数字であるか判定 isalphaは英字判定，isalnumは英数字判定 int tolower(int c); … 大文字を小文字に変換 大文字以外の文字はそのまま 逆はtoupper #include <math.h> を必要とするもの double exp(double x); … eのx乗 double floor(double x); … x以下で最小の整数 最大はceil，四捨五入（丸め）はround コンパイル時，「cc -lm program.c」のようにリンカオプション(linker option)が必要

21 関数名の表記 printf関数，関数printf printf()関数，関数printf() printf(3) この授業で採用している．
関数名であることを明確にする表記法．よく見かける． printf(3) 「printfというライブラリ関数があって，詳細は， man 3 printfを実行すれば得られる」の意味． 「(1)」ならコマンド，「(2)」はシステムコール man printfを実行すると，ライブラリ関数ではなく，コマンドとしてのprintfの使い方が出てくる． 「printfの実引数に3と書く」ではない．