AOJ ALDS1 4_A（Linear Search）を解く

Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の4_A問題をC++で解いてみました。

ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#4「探索」は、線形探索、二分探索、ハッシュ（辞書）を学びます。

問題（4_A: Linear Search）

問題はリンク先をご覧ください。

AOJ ALDS1 4_A問題: Linear Search

線形探索について学びます。

線形探索について

データの集合から、与えられたキーの位置や存在するか調べることを探索と呼びます。

与えらえた配列に対して、与えられたキーが存在するか、配列の先頭から最後まで調べるアルゴリウムを線形探索と呼びます。問題に紹介されている擬似コードは以下です。

linearSearch()
    for i が 0 から n-1 まで
        if A[i] と key が等しい
            return i
    return NOT_FOUND

線形探索は素朴ですが、分かりやすいアルゴリズムです。

C++ プログラム例（ALDS1 4_A）

二つの配列 s と t を読み込みます。t の要素に対して s に含まれている要素の個数を出力します。s の大きさ n の上限は 10⁴、t の大きさの上限 q は 500 です。

n × q の上限が 5 × 10⁶ であるため、線形探索でも間に合います。線形探索の擬似コードは、key と等しいインデックスを返しています。実装例では、key と一致した要素が含まれているか bool 型を返すように変更しました。

以下が、C++プログラムとなります。

#include <iostream>
#include <vector>
using namespace std;

bool search(vector<int> a, int key)
{
	for (int i = 0; i < a.size(); ++i) {
		if (a[i] == key) {
			return true;
		}
	}

	return false;
}

int main()
{
	int n;
	cin >> n;
	vector<int> s(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}

	int q;
	cin >> q;
	vector<int> t(q);
	for (int i = 0; i < q; ++i) {
		cin >> t[i];
	}

	int result = 0;
	for (int i = 0; i < q; ++i) {
		if (search(s, t[i])) {
			++result;
		}
	}

	cout << result << endl;

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

トピック#4では、線形探索、二分探索、ハッシュを学びます。これらの機能は、標準ライブラリを通して使うことが多いと思います。ただし、それぞれのアルゴリズムを自分で実装することによって、アルゴリズムの理解が深まると考えています。

引き続き、ALDS1 の問題を紹介していきます。