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

データ構造とアルゴリズム論
第７章探索のアルゴ
リズム
平成15年11月25日
森田彦
基礎課題提出状況(11/18)
平均提出数=30.4 (全課題数35)
基礎課題提出状況（11/18）
平均提出数=30.4
90
80
度数（人数）
70
60
50
40
30
20
10
0
0～5
6～10
11～15
16～20
21～25
提出数範囲
約6割が31題以上を提出
25～30
31～35
応用課題提出状況（11/18）
平均提出課題数＝8.1
応用課題提出状況（11/18）
平均提出数＝8.1
40
35
度数（人数）
30
25
20
15
10
5
0
0
1～４
5～8
9～12
13～16
提出数範囲
13題以上提出は約22%
17～20
21～24
探索とは？
 あるデータ群から、目的のデータと合致す
るものを探し出す、という処理。→検索と
も言う。
Webページの検索機能の強化→最近急速
に発展
本章では、最も基本的な探索アルゴリズ
ムを学習。
本章（本日）の学習のねらい
① 基本的な探索アルゴリズムを学習し、そ
の処理の流れを理解する。
→ 線形探索、2分探索
② 探索アルゴリズムの効率について考察
する。
③ 探索アルゴリズムを実際のプログラムに
応用する。
7-1 線形探索
 端から順番に探索する方法
例：カードの中から数字の３を探す。
５
１
３
３を発見！
流れ図で表すと・・・ → p.106参照
開始
＜線形探索のアルゴリズム＞
A[1]～A[n]にデータ保管
Noの入力探したい数字を入力
データの終端のチェック
i←1
毎回必要？
i≦n
No
Yes
A[i] ＝No
Yes
’ありませんでした。’
No
i ← i+1
i,’番目にありました。’
終了
最大（2n+1）回の比較が必要 → 改良の余地は？
→ 番兵法へ
＜番兵法のアルゴリズム＞
開始
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,’番目にありました。’
終了
最大比較回数が減った！
【基礎課題7-1】(p.108)
 データ数がｎ個の時の、最大比較回数
は？
線形探索法では、（２ｎ+1）回
番兵法では n+2 回？
流れ図の確認→【基礎課題7-2】、【基礎課題7-3】
線形探索の（練習）プログラム→【基礎課題7-4】
7-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倍になっても比較回数は１回増えるだけ！
→ 【基礎課題7-5】で確認
プログラムは【基礎課題7-6】で作成
データ数が増えると効率が良い → P.118参照
7-4 応用課題
 線形探索の応用→【応用課題7-A】
 ２分探索の応用→【応用課題7-B】
 【応用課題7-B】のプログラムを作成する
事ができれば、本章の理解度はOKです。
第２回目テストのアナウンス
 日時：12/9 13:15～14:15 （13:10までに
着席しておいて下さい）
 実施形態：ペーパーテスト形式（テスト中
はＰＣを使用できません）
 参照等：テキスト、プリント、自作ノート参
照可
 出題範囲：第５章～第８章（12/2学習）まで
 アドバイス：暗記ではなく、処理の流れを
“理解する”事に重点を置いて下さい。

Download Report