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