データ構造とアルゴリズム論 第６章 探索のアルゴ リズム 平成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 線形探索 端から順番に探索する方法 例：カードの中から数字の３を探す。 ５ １ ３ ３を発見！ 流れ図で表すと・・・ → 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) データ数がｎ個の時の、最大比較回数 （データが見つからなかった場合の比較 回数）は？ 線形探索法では、（２ｎ+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倍になっても比較回数は１回増えるだけ！ → 【基礎課題6-5】で確認 流れ図の確認→p.101 プログラムは【基礎課題6-6】で作成 6-3 アルゴリズムの効率 ２分探索法は線形探索法（番兵法）より効率 が良い。 p.104をよく読んで下さい。 【基礎課題6-5】をきちんとやっておくことが必要。 6-4 応用課題 線形探索の応用→【応用課題6-A】 ※ プリントでは【基礎課題6-A】となっているの で「応用課題」に訂正して下さい。 ２分探索の応用→【応用課題6-B】 【応用課題6-B】のプログラムを作成する 事ができれば、本章の理解度はOKです。 今後の予定 12/6 第７章 再帰処理 12/13 第８章 連結リスト 12/20 第９章 木構造 12/27 第２回目テスト 1/10 終章 補足 ＆ 課題最終チェック
© Copyright 2024 ExpyDoc
