情報処理II

情報処理Ⅱ
２００６年１２月８日（金）
本日学ぶこと

関数の補足



既存のプログラムから関数を「抽出する」方法
再帰(recursion)
クイックソート
2
関数の抽出


反復語判定プログラム（第７回）を例として
関数を抽出することで一般に



コード量（プログラムのサイズ，ステップ数）は増える．
しかし，それぞれの関数のコード量は減り，関数ごとに役割が
明確になるため，読みやすい．
関数抽出の要点



保守性向上
①関数名，②戻り値の型，③仮引数の順に決める．
変数の有効範囲に注意する．
変数の除去や複製が必要なこともある．
3
再帰呼び出しとは


関数の内部で自分自身を呼び出すことを，再帰呼び出し(リ
カーシブコール，recursive call)という．
用途




再帰的（帰納的，循環的）な定義
バックトラック(backtrack)
分割統治法(divide-and-conquer)
注意点


無限ループにならないようにする．
再帰を使わないほうがよいこともある．
4
カウントダウンするプログラム

自作関数countdownの定義の中で，countdownを呼び出
している．
5
カウントアップするプログラム


出力の位置を変えると，カウントアップになる．
カウントアップ，カウントダウンともに，再帰呼び出しなしの
プログラムのほうが，効率はよい．


なぜ再帰呼び出しは効率が悪いか？
…関数呼び出しのコスト（オーバーヘッド）があるから．
業務としてのプログラミングで，再帰呼び出しを使用してはなら
ないと（コーディング規約で）定めていることも
6
なぜ再帰呼び出しが可能なのか？
このようなデータ
構造を，「スタック」
という．
x=0
同一の変数名x
に対して複数の
オブジェクトが
生成される．
countdown
x=1
countdown
countdown関数処理時に
生成されるオブジェクト
x=2
main
main関数処理時に
生成されるオブジェクト
countdownの再帰呼び出
しを終えたときの戻り先
num = 2
countdownの呼び出し（関
数処理）を終えたときの戻
り先
7
再帰的な定義の例（１）

階乗



フィボナッチ数列




0! = 1, 1! = 1
n! = n×(n-1)! (n≧2)
a1 = 1, a2 = 1
an = an-1 + an-2
(n≧3)
再帰呼び出しを用いれば，シンプルに書ける．
しかしこれらも，whileループのほうが効率がよい．
8
再帰的な定義の例（２）

木構造




トーナメント表の決勝戦から順に見て，
優勝チームの戦績を知る
100万個の記録から，欲しいものを
瞬時に獲得する
ホームディレクトリ以下のすべての
ファイル名を出力する
再帰呼び出しは必要？


するのが自然な場合と，してはいけない
場合がある
呼び出し方よりもデータ構造のほうが重要
9
分割統治法


対象領域を細分化（分割）して求め（統治），全体として正し
い解になるようにする．
例: クイックソート
「４より小」と
「４より大」に
分ける．
４７３８６１２５
２３１４６７８５
１２３４５６８７
１２３４５６７８
10
クイックソートの関数呼び出し

配列領域，開始位置，終了位置を引数とする．
４７３８６１２５
２３１４６７８５
１２３４５６８７
１２３４５６７８
11
関数の呼び出し関係
(quicksort.c)
main
swap
get_array_length
quicksort
print_score
再帰！
12
まとめ

再帰呼び出しを用いて関数を定義すると，プログラムがすっ
きり書けることがある．


再帰的に定義された問題に適用すると，効果的．
一般に，再帰を用いないほうが効率的である．

関数内のauto変数は，関数呼び出しごとに生成される．
13
情報処理Ⅱ
２００６年１２月８日（金）の２
ここで学ぶこと

ライブラリ関数の活用



先人の知恵を活用する．
勉強・授業のためでなければ，
ライブラリ関数と同じ名前や機能の関数は自作しない．
（参考）関数の分類


自作関数: 自分で定義する．⇒ １２月１日のテーマ
ライブラリ関数: 出来合いのもの．printfなど．⇒ ここでの
テーマ
15
ライブラリ関数とヘッダファイル

既に定義されている関数や定数を利用するには，あらかじめ，
適切なファイル名（ヘッダファイル）を記載しておく．



printf なら #include <stdio.h>
CHAR_BIT なら #include <limits.h>
ライブラリ関数と，記載すべきヘッダファイル名は，manpage
で知ることができる．




man 3 printf
Vine Linuxのコマンド
jman 3 printf
JM Project (http://www.linux.or.jp/JM/)
ヘッダファイルはコンパイル環境が保有しているが，その所在
は，環境による．
16
ヘッダファイルとインクルード

ヘッダファイルには，定数，構造体や特殊な型，関数プロトタ
イプなどが宣言・定義されている．




#include <stdlib.h> とすると，
/usr/include/stdlib.h を取り込む（インクルードする）．
慣例として，ファイル名は「.h」で終わらせる．
ヘッダファイルの中で，他のヘッダファイルをインクルードする
こともよく行われる．
ヘッダファイルを自作することもある．そのファイルをインクルー
ドするときは，#include "headerfile.h" のように書く．
17
有用なライブラリ関数（１）

#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（の指し示す配列領域）に格納する
18
有用なライブラリ関数（２）

#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); …文字列連結
19
有用なライブラリ関数（３）

#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)が必要
20
関数名の表記

printf関数，関数printf


printf()関数，関数printf()


この授業で採用している．
関数名であることを明確にする表記法．よく見かける．
printf(3)



「printfというライブラリ関数があって，詳細は，
man 3 printfを実行すれば得られる」の意味．
「(1)」ならコマンド，「(2)」はシステムコール
• man printfを実行すると，ライブラリ関数ではなく，コマ
ンドとしてのprintfの使い方が出てくる．
「printfの実引数に3と書く」ではない．
21

Download Report