＜アルゴリズムの基本⑥＞繰り返し処理（４）「番兵」付き配列データの処理

あらかじめ有効な配列要素の個数Ｎが分かっていない場合のデータ処理については、「番兵」を使う方法が便利です。今回は例として、「番兵」付き配列データの平均値を求めるアルゴリズムについてまとめます。

目的
擬似コード例
Pythonコード例
1. 出力結果
まとめ

目的

個数が分かっていないデータの平均値を求める
前提条件
- あらかじめ有効な配列要素の個数Ｎは不明
- 配列要素の末尾に「番兵」が付与されている。ここでは＂-1＂とおく
- データの要素構成

　（※）番兵(sentinel)とは
　　　　有効データの末尾の次の要素に格納され、データの終了を表す特殊な文字コードのこと

擬似コード例

今回のアルゴリズムの擬似コード例を示します。「番兵」データを’-1’とし、それが出てくるまで配列の要素加算を順次繰り返します。

Procedure AVERAGE(DATA)
    count ← 0
    sum ← 0
    idx ← 0
    while DATA[idx] ≠ -1 do
          sum ← sum + DATA[idx]
          count ← count + 1
          idx ← idx + 1
    end while
    ave = sum / count
    return ave

Pythonコード例

上記アルゴリズムのPythonコード例を示します。

>>> def average(data):
...     count = 0
...     sum_ = 0
...     idx = 0
...     while data[idx] != -1:
...         sum_ += data[idx]
...         count += 1
...         idx += 1
...     average = sum_ / count
...     return average

出力結果

コードはこちらをご参照ください。

>>> data = [1, 58, 60, 73, -1, 0, 0, 0, 0, 0]
>>> average(data)
48.0

まとめ

今回は、有効データの末尾に「番兵」が付与されたデータの平均値を求めるアルゴリズムについてまとめました。「番兵」は今後もちらほら出てくる手法だと思いますので覚えておきたいです。
次回は、繰り返し処理を使った最大値・最小値を求めるアルゴリズムについてまとめる予定です。

（参考文献：杉浦賢、図解でかんたんアルゴリズム　情報処理のかなめとなる考え方が手に取るようにわかる、Softbank Creative）