データ構造とアルゴリズム論

データ構造とアルゴリズム論
第6章 探索のアルゴ
リズム
平成17年11月29日
森田 彦
基礎課題提出状況(11/22)
基礎課題提出状況(11/22) 平均=27.6(昨年27.0) [全課題31題]
80
70
度数(人数)
60
50
'04年度
'05年度
40
30
13名 要注意!
20
10
0
6~10
11~15
16~20
21~25
提出数
昨年よりやや速いペース!
26~30
31
48.5
%
が
全
課
題
を
提
出
応用課題提出状況(11/22)
応用課題提出状況(11/22) 平均13.48(昨年13.3)
全課題23題
全
課
題
'04年度 提
'05年度 出
は
60
度数(人数)
50
40
30
20
10
9
0
0
1~5
6~10 11~15 16~20 20~23
提出数
昨年とほぼ同じペース。
12題以上提出は66%
名
探索とは?
 あるデータ群から、目的のデータと合致す
るものを探し出す、という処理。→検索と
も言う。
Webページの検索機能の強化→現在急速
に発展
本章では、最も基本的な探索アルゴリズ
ムを学習。
本章(本日)の学習のねらい
① 基本的な探索アルゴリズムを学習し、そ
の処理の流れを理解する。
→ 線形探索、2分探索
② 探索アルゴリズムの効率について考察
する。
③ 探索アルゴリズムを実際のプログラムに
応用する。
6-1 線形探索
 端から順番に探索する方法
例:カードの中から数字の3を探す。
5
1
3
3を発見!
流れ図で表すと・・・ → p.92参照
開始
<線形探索のアルゴリズム>
A[1]~A[n]にデータ保管済み
Noの入力 探したい数字を入力
データの終端のチェック
i←1
毎回必要?
i≦n
No
Yes
A[i] =No
Yes
’ありませんでした。’
No
i ← i+1
i,’番目にありました。’
終了
最大(2n+1)回の比較が必要 → 改良の余地は?
→ 番兵法へ(p.93)
<番兵法のアルゴリズム>
開始
A[1]~A[n]にデータ保管
Noの入力
i←1
A[n+1] ← No
データ終端を見分ける番兵の用意
データの終端のチェック
A[i] =No
No
i ← i+1
Yes
最後の1回だけ!
i≦n
No
Yes
’ありませんでした。’
i,’番目にありました。’
終了
最大比較回数が減った!
【基礎課題6-1】(p.94)
 データ数がn個の時の、最大比較回数
(データが見つからなかった場合の比較
回数)は?
線形探索法では、(2n+1)回
番兵法では n+2 回?
流れ図の確認→【基礎課題6-2】(ループ端記号の場合)
【基礎課題6-3】(A[0]~A[n-1]の場合)
線形探索の(練習)プログラム→【基礎課題6-4】(p.97)
6-2 2分探索
 線形探索では、データ数に比例して(デー
タ照合のための)比較回数が増大。
 データ数が10倍→計算時間も10倍
→ 大きなデータ数では、効率が悪い!
 もっと効率の良い方法は?
2分探索法
例:数字「30」の書かれたカードを探す。
※最初に昇順にソートしておく。
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10]
1
3
7 12 13 14 20 22 30 41
①
② 「30」と真ん中のA[5]を比較
③
「30」と真ん中のA[8]を比較
「30」とA[9]を比較
1
3
7 12 13 14 20 22 30 41
「30」がA[9]にあることを発見!→
探索範囲がA[9]~A[10]に絞られる。
探索範囲がA[6]~A[10]に絞られる。
終了!
データ数が2倍になっても比較回数は1回増えるだけ!
→ 【基礎課題6-5】で確認
流れ図の確認→p.101
プログラムは【基礎課題6-6】で作成
6-3 アルゴリズムの効率
2分探索法は線形探索法(番兵法)より効率
が良い。
p.104をよく読んで下さい。
【基礎課題6-5】をきちんとやっておくことが必要。
6-4 応用課題
 線形探索の応用→【応用課題6-A】
※ プリントでは【基礎課題6-A】となっているの
で「応用課題」に訂正して下さい。
 2分探索の応用→【応用課題6-B】
 【応用課題6-B】のプログラムを作成する
事ができれば、本章の理解度はOKです。
今後の予定
 12/6 第7章 再帰処理
 12/13 第8章 連結リスト
 12/20 第9章 木構造
 12/27 第2回目テスト
 1/10 終章 補足 & 課題最終チェック