情報処理Ⅱ
２００５年１２月９日（金）
第１回レポートについて
解説（PDF）を作って，授業ページからリンクしました．
課題は公開しません．
以下の人は，見ておいてください．
問２で小数点以下３１桁まで解答してくれた人
問４の出題意図がよく分からなかった人
実はプログラムにバグがあるんじゃないかと思った人
期末試験でちょっとでもいい点をとりたい人
2
前回学んだこと
関数を自分で定義し，変数の利用方法・範囲を明示的に制
限することで，適切な機能分割を図る．
関数を自分で定義することができる．関数を呼び出すとき，
引数は値渡しで授受される．
「変数の定義」と「オブジェクトの生成」は別．
オブジェクトの生成・破棄のタイミングに注意する．
3
本日学ぶこと
関数の補足
並べ替え問題
再帰(recursion)
4
補足１：引数の授受
Cの関数呼び出しでは必ず値渡し(call by value)にな
る．
値渡し: 実引数のコピーが仮引数に格納される．その後，仮
引数の値を変更しても，実引数の値には影響しない．
参照渡し(call by reference)をしたければ，ポインタ
値を引数とすればよい．
参照渡し: 仮引数の値を変更すれば，実引数の値もそれに変
わる．Cではこの意味での参照渡しをすることができないが，ポ
インタ値を渡すことで，その参照先の値を変えることができる．
実引数を，配列変数の名前，または変
数の前に「&」をつけたものにする．
仮引数はポインタ変数にする．
5
補足２：ポインタ値の値渡し
関数：
void print_message(char *message)
{
printf("%s\n", message);
実引数の値（ポイン
}
呼び出し側：
char wakayama[] = "wakayama";
print_message(wakayama);
message
wakayama
タ値）は変更不可．
参照先（文字列
"Wakayama"の
中身)は変更可．
関数print_messageの中
'W' 'a' 'k' 'a' 'y' 'a' 'm' 'a' '\0'
6
補足３：複数の値を返すには
ポインタ値を渡して，関数の中で参照先の値を変更する．
例
void swapint(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
a=3 b=5
}
swapint
int a = 3; b = 5;
x
y tmp
swapint(&a, &b);
a=5 b=3
7
並べ替え問題
処理対象：intの１次元配列
処理前：
４ ７ ３ ８ ６ １ ２ ５
処理後：
１ ２ ３ ４ ５ ６ ７ ８
並べ替えは「ソート(sort)」，「ソーティング(sorting)」，
「整列」とも呼ばれる．
8
ソートとは
データを，何らかの基準で順番に並べること．
例
試験の点数順に学生番号を出力する
時系列で出力される情報を，キーワードごとに並べる
学生番号：0003
氏名：さしすせそ
学生番号：0002
情処Ⅰの点数：90
氏名：かきくけこ
情処Ⅱの点数：0
学生番号：0001
情処Ⅰの点数：60
修得単位数： 24
氏名：あいうえお
情処Ⅱの点数：99
情処Ⅰの点数：80
修得単位数： 48
情処Ⅱの点数：75
修得単位数： 52
学生番号：0002
氏名：かきくけこ
学生番号：0001
情処Ⅰの点数：60
氏名：あいうえお
情処Ⅱの点数：99
学生番号：0003
情処Ⅰの点数：80
修得単位数： 48
氏名：さしすせそ
情処Ⅱの点数：75
情処Ⅰの点数：90
修得単位数： 52
情処Ⅱの点数：0
修得単位数： 24
学生番号で昇順ソート
（ソートの）「キー」という
情処Ⅰの点数で降順ソート
9
並べ替え問題：定義する関数
int get_array_length(int *array);
void print_array(const char *message,
int *array);
配列の要素数を求める．
× sizeof(array)/sizeof(array[0])
メッセージと，配列の各値を出力する．
void sort_by_selection(int *array);
選択法を用いて並べ替える．
配列の中身を書き換える．
10
関数の呼び出し関係
main
print_array
sort_by_selection
get_array_length
11
再帰呼び出しとは
関数の内部で自分自身を呼び出すことを，再帰呼び出し
(recursive call)という．
用途
再帰的（帰納的，循環的）な定義
バックトラック(backtrack)
分割統治法(divide-and-conquer)
注意点
無限ループにならないようにする．
再帰を使わないほうがよいこともある．
12
カウントダウンするプログラム
自作関数countdownの定義の中で，countdownを呼び出
している．
13
カウントアップするプログラム
出力の位置を変えると，カウントアップになる．
カウントアップ，カウントダウンともに，再帰呼び出しなしの
プログラムのほうが，効率はよい．
なぜ再帰呼び出しは効率が悪いか？
…関数呼び出しのコスト（オーバーヘッド）があるから．
14
なぜ再帰呼び出しが可能なのか？
このようなデータ
構造を，「スタック」
という．
x=0
同一の変数名x
に対して複数の
オブジェクトが
生成される．
countdown
x=1
countdown
countdown関数処理時に
生成されるオブジェクト
x=2
main
main関数処理時に
生成されるオブジェクト
countdownの再帰呼び出
しを終えたときの戻り先
num = 2
countdownの呼び出し（関
数処理）を終えたときの戻
り先
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
クイックソートの関数呼び出し
配列領域，開始位置，終了位置を引数とする．
４ ７ ３ ８ ６ １ ２ ５
２ ３ １ ４ ６ ７ ８ ５
１ ２ ３ ４ ５ ６ ８ ７
１ ２ ３ ４ ５ ６ ７ ８
18
関数の呼び出し関係
(quicksort.c)
main
get_array_length
quicksort
print_array
再帰！
19
まとめ
再帰呼び出しを用いて関数を定義すると，プログラムがすっ
きり書けることがある．
再帰的に定義された問題に適用すると，効果的．
一般に，再帰を用いないほうが効率的である．
関数内のauto変数は，関数呼び出しごとに生成される．
20
今後の予定
第１０回：１２月１６日（金）
第１１回：１２月２２日（木） １６：３０～１８：００
第１２回：１月１３日（金）
第１３回：１月１９日（木） １６：３０～１８：００ （？）
第１４回：１月２０日（金）
（１２月２３日（金）は祝日）
（１月２７日（金）は村川出張のため休講）
（試験持込用の書籍を購入しておく？）
試験：２月３日（金）
21
© Copyright 2024 ExpyDoc
