アルゴリズムとデータ構造(05/06/07)

• 第6回(2005/6/7)
  • 41ページ
    • 問題9
    • 問題10
  • 42ページ
  • 43ページ
  • 44、45ページ
  • 46ページ
  • 47ページ(二分探索法)
  • 48ページ
  • 49ページ
  • 50ページ

第6回(2005/6/7)

配列の処理は反復(ループ)を使う。

 41ページ

問題9

1. 最大値を記憶する変数(max)を用意し、初期値は配列の先頭要素(h[1])にする
2. ループを使い配列要素の2番目から最後までにアクセスできるようにし、次の処理を繰り返す
   1. maxと各配列要素の値を比較し、配列要素の値がmaxより大きければそれを新しいmaxの値とする

問題10

• 問題9と異なるのは最大値の場所を記憶する変数daiがあること。
• 問題9で新しいmaxを設定するときにdaiの値を設定する。

 42ページ

これまでの問題を応用すればよい。

1. 最大値maxと最小値minの初期値は配列要素の先頭の値h[1]にする
2. 合計の初期値も配列の先頭要素にする
3. 配列の2番目の要素から最後の要素までにアクセスできるループを用意し、次の処理を行う。
   1. 最大値検出
   2. 最小値検出
   3. 合計計算
4. 全配列への参照が完了したら、平均を計算する。

 43ページ

配列要素への代入は変数の代入と同じ

 44、45ページ

プログラミング追加分(20050530)を参照

 46ページ

各要素の値と探索キーの値を順に比較し、一致するか否かを調べればよい。

 47ページ(二分探索法)

二分探索法は配列内のデータが昇順にソートされていることを前提にした探索法です。名前が示すように探索する範囲を二分(半分)にし、対象とするデータの個数を減らしていきます。

手順は次の通り。

1. 探索対象範囲の先頭の要素番号をs、最後の要素番号をeとする。ここでは0→s、8→eとなる。
2. 探索対象範囲の中間点の要素番号をmとする。その値は(s + e) / 2 → mとする。
3. もし、s > eならば、探索対象の値は存在せず、探索終了。
4. もし、TK = H[m]なら見つかったときの処理を実施する。
5. もし、TK > H[m]ならm+1→sにする。
6. もし、TK < H[m]ならm-1→eにする。
7. 2に戻る。

 48ページ

キーと一致する科目コードを探し、その要素番号を使って科目名を表示する。

 49ページ

48ページの問題を応用する。

• 二重ループを使う
  • キーを取り出すループ
  • 科目表からキーと一致する科目コードを検索するループ

1. 科目コードを検索する。
2. 一致した場所(要素番号)から科目名を取り出し、結果を格納する配列要素へ代入する。

 50ページ

49ページの変形

アルゴリズムとデータ構造(H17)