データ構造とアルゴリズム論 第６章 探索のアルゴリズム データ構造とアルゴリズム論 第６章　探索のアルゴリズム 平成28年6月10日 森田　彦

理解度チェック１（問題１） 空欄①～③には以下のどの順で数字が並びますか？適切な並びを選択して下さい。 １．4 3 8　　　２． 4 8 3 ３． 3 4 8 ４．3 8 4 　　 ５． 8 3 4

理解度チェック１ 解答 空欄①～③に入る適切な並びは？ １．4 3 8 ２． 4 8 3 ３． 3 4 8 ４．3 8 4 ５． 8 3 4 理解度チェック１　解答 空欄①～③に入る適切な並びは？ １．4 3 8　　　２． 4 8 3 ３． 3 4 8 ４．3 8 4 　　 ５． 8 3 4 A 1 2 3 ４ ３ ８ １ A[1]とA[2]を比較し、A[1]＜A[2]なので交換する。 ４ ① ② ③ １ ８ ３

理解度チェック２（問題２） 空欄①～⑤には以下のどの順で数字が並びますか？適切な並びを選択して下さい。 １．12 10 7 5 9 １．12 10 7 5 9　　　 ２．12 10 7 9 5 ３．12 10 9 5 7 ４．12 10 9 7 9

理解度チェック２ 解答 i=0 i=1 i=2 空欄①～⑤に入る適切な並びは？ １．12 10 7 5 9 ２． 12 10 7 9 5 理解度チェック２　解答 空欄①～⑤に入る適切な並びは？ １．12 10 7 5 9　　　２． 12 10 7 9 5 ３．12 10 9 5 7 ４． 12 10 9 7 9 A 1 2 3 4 10 12 7 5 9 i=0 10 12 7 5 9 12 10 10 12 10 i=1 12 10 7 5 9 10 10 i=2 12 10 7 5 9 9 7 7 9

理解度チェック３（問題３） 空欄①に入る最も適切な数値は次のいずれですか？ １．2　　　２． 3 ３．4 ４．5 ５． 6

理解度チェック３ 解答 １．2 ２． 3 ３．4 ４．5 ５． 6 iの初期値は、整列済み配列の末端の要素番号。 理解度チェック３　解答 空欄①に入る最も適切な数値は次のいずれですか？ １．2　　　２． 3 ３．4 ４．5 ５． 6 iの初期値は、整列済み配列の末端の要素番号。 今の場合、A[3]までが整列済み。 したがって、答は３。

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

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

6-1 線形探索 端から順番に探索する方法 ３を発見！ 例：カードの中から数字の３を探す。 ５ １ ３ 6-1　線形探索 端から順番に探索する方法　 例：カードの中から数字の３を探す。 ５ １ ３ ３を発見！ 流れ図で表すと・・・　→　p.98参照

最大（2n+1）回の比較が必要 → 改良の余地は？ → 番兵法へ（p.99） ＜線形探索のアルゴリズム＞ 開始 A[1]～A[n]にデータ保管済み Noの入力 探したい数字を入力 データの終端のチェック i ← 1 毎回必要？ No i≦n Yes ’ありませんでした。’ Yes A[i] ＝No No i,’番目にありました。’ i ← i+1 次をめくる 終了 最大（2n+1）回の比較が必要　→　改良の余地は？　→　番兵法へ（p.99）

最大比較回数が減った！ ＜番兵法のアルゴリズム＞ 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,’番目にありました。’ 終了 最大比較回数が減った！

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

2分探索法 6-2 2分探索 線形探索では、データ数に比例して（データ照合のための）比較回数が増大。 データ数が10倍→計算時間も10倍 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[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倍になっても比較回数は１回増えるだけ！ 流れ図の確認→p.107 →　【基礎課題6-5】で確認 プログラムは【基礎課題6-6】で作成

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

6-4 応用課題 線形探索の応用→【応用課題6-A】 ２分探索の応用→【応用課題6-B】 6-4　応用課題 線形探索の応用→【応用課題6-A】 ２分探索の応用→【応用課題6-B】 【応用課題6-B】のプログラムを作成する事ができれば、本章の理解度はOKです。

今後の予定 6/17 第７章 再帰処理 6/24 第８章 連結リスト 7/ 1 第９章 木構造 7/ 8 第１０章 スタックとキュー 6/17　第７章　再帰処理 6/24 第８章　連結リスト 7/ 1 第９章　木構造 7/ 8 第１０章　スタックとキュー 7/15　第２回テスト &　課題チェック 7/22　課題最終チェック（力試しの課題を含む）

学習に当たって これまでの基礎課題を全て終了した学生は【応用課題6-A】および【応用課題6-B】のチェックを終了すれば演習を終えても結構です。