Presentation is loading. Please wait.

Presentation is loading. Please wait.

データ構造とアルゴリズム論 第6章 探索のアルゴリズム

Similar presentations


Presentation on theme: "データ構造とアルゴリズム論 第6章 探索のアルゴリズム"— Presentation transcript:

1 データ構造とアルゴリズム論 第6章 探索のアルゴリズム
データ構造とアルゴリズム論 第6章 探索のアルゴリズム 平成17年11月29日 森田 彦

2 基礎課題提出状況(11/22) 48.5%が全課題を提出 13名 要注意! 昨年よりやや速いペース!

3 応用課題提出状況(11/22) 全課題提出は9名 12題以上提出は66% 昨年とほぼ同じペース。

4 探索とは? あるデータ群から、目的のデータと合致するものを探し出す、という処理。→検索とも言う。
 Webページの検索機能の強化→現在急速に発展 本章では、最も基本的な探索アルゴリズムを学習。

5 本章(本日)の学習のねらい 基本的な探索アルゴリズムを学習し、その処理の流れを理解する。 → 線形探索、2分探索
基本的な探索アルゴリズムを学習し、その処理の流れを理解する。              → 線形探索、2分探索 探索アルゴリズムの効率について考察する。 探索アルゴリズムを実際のプログラムに応用する。

6 6-1 線形探索 端から順番に探索する方法 3を発見! 例:カードの中から数字の3を探す。 5 1 3
6-1 線形探索 端から順番に探索する方法  例:カードの中から数字の3を探す。 3を発見! 流れ図で表すと・・・ → p.92参照

7 最大(2n+1)回の比較が必要 → 改良の余地は? → 番兵法へ(p.93)
<線形探索のアルゴリズム> 開始 A[1]~A[n]にデータ保管済み Noの入力 探したい数字を入力 データの終端のチェック i ← 1 毎回必要? No i≦n Yes ’ありませんでした。’ Yes A[i] =No No i,’番目にありました。’ i ← i+1 終了 最大(2n+1)回の比較が必要 → 改良の余地は? → 番兵法へ(p.93)

8 最大比較回数が減った! <番兵法のアルゴリズム> A[1]~A[n]にデータ保管 最後の1回だけ! 開始 Noの入力 i ← 1
データ終端を見分ける番兵の用意 A[n+1] ← No データの終端のチェック A[i] =No Yes 最後の1回だけ! No i≦n No i ← i+1 Yes ’ありませんでした。’ i,’番目にありました。’ 終了 最大比較回数が減った!

9 【基礎課題6-1】(p.94) データ数がn個の時の、最大比較回数(データが見つからなかった場合の比較回数)は?
 線形探索法では、(2n+1)回  番兵法では    回?  n+2 流れ図の確認→【基礎課題6-2】(ループ端記号の場合) 【基礎課題6-3】(A[0]~A[n-1]の場合) 線形探索の(練習)プログラム→【基礎課題6-4】(p.97)

10 2分探索法 6-2 2分探索 線形探索では、データ数に比例して(データ照合のための)比較回数が増大。 データ数が10倍→計算時間も10倍
6-2 2分探索 線形探索では、データ数に比例して(データ照合のための)比較回数が増大。 データ数が10倍→計算時間も10倍   → 大きなデータ数では、効率が悪い! もっと効率の良い方法は? 2分探索法

11 例:数字「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[9]を比較  ② 「30」と真ん中のA[8]を比較 1 3 7 12 13 14 20 30 41 22 1 3 7 12 13 14 20 30 41 22 1 3 7 12 13 14 20 22 30 41 1 3 7 12 13 14 20 22 30 41 13 22 「30」がA[9]にあることを発見!→ 終了! 探索範囲がA[9]~A[10]に絞られる。 探索範囲がA[6]~A[10]に絞られる。 データ数が2倍になっても比較回数は1回増えるだけ! 流れ図の確認→p.101 → 【基礎課題6-5】で確認 プログラムは【基礎課題6-6】で作成

12 6-3 アルゴリズムの効率 p.104をよく読んで下さい。 2分探索法は線形探索法(番兵法)より効率が良い。
6-3 アルゴリズムの効率  2分探索法は線形探索法(番兵法)より効率が良い。  p.104をよく読んで下さい。 【基礎課題6-5】をきちんとやっておくことが必要。

13 6-4 応用課題 線形探索の応用→【応用課題6-A】 ※ プリントでは【基礎課題6-A】となっているので「応用課題」に訂正して下さい。
6-4 応用課題 線形探索の応用→【応用課題6-A】  ※ プリントでは【基礎課題6-A】となっているので「応用課題」に訂正して下さい。 2分探索の応用→【応用課題6-B】 【応用課題6-B】のプログラムを作成する事ができれば、本章の理解度はOKです。

14 今後の予定 12/6 第7章 再帰処理 12/13 第8章 連結リスト 12/20 第9章 木構造 12/27 第2回目テスト
12/6 第7章 再帰処理 12/13 第8章 連結リスト 12/20 第9章 木構造 12/27 第2回目テスト 1/10 終章 補足 & 課題最終チェック


Download ppt "データ構造とアルゴリズム論 第6章 探索のアルゴリズム"

Similar presentations


Ads by Google