Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の5_A問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#5「分割統治法」では、部分的な小さな問題を解くことによって、与えられた元の問題を解く手法を紹介します。
問題（5_A: Exhaustive Search）
問題はリンク先をご覧ください。
AOJ ALDS1 5_A問題: Exhaustive Search
再帰関数を使う全探索について学びます。
再帰関数を使う全探索について
この問題は、数列の長さとなる $n$ 重ループを書けば解くことができます。再帰関数を使えば、回数が決まっていないループ相当の処理を実現することができます。
C++ プログラム例（ALDS1 5_A）
再帰関数 rec は、以下のように実装します（8ー18行目）。
- 数列をどこまで処理したかを表す i と、総和の残り remain を引数とします。総和が m になる組み合わせがあれば true を返します。そうでなければ false を返します。
- 引数 remain が 0 になれば、総和となる組み合わせが見つかったことを表します（10、11行目）。
- すべて調べて総和となる組み合わせがなければ false を返します（13、14行目）。
- 再帰的に関数を呼び出して、a[i] を選択する場合と選択しない場合を調べます（17行目）。
関数 rec の戻り値によって、”yes” または “no” を出力します。以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> a;
bool rec(int i, int remain)
{
if (remain == 0) {
return true;
}
if (i == n) {
return false;
}
return rec(i + 1, remain) || rec(i + 1, remain - a[i]);
}
int main()
{
cin >> n;
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int m;
cin >> m;
if (rec(0, m)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
return 0;
}上のプログラムでは、$n$ 重ループの替わりに再帰関数を使って解答を求めました。
$2^n$ 通りのループを行う bit全探索という手法があります。bit全探索については、この記事で説明しています。bit全探索で総和となる値をすべて set コンテナ sum に格納します。読みだした値が sum に含まれているか判定して、結果を出力します。
以下が、bit全探索を使ったプログラムとなります。キーとなるコードの背景行を変えています。
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef unsigned int uint;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
set<int> sum;
for (uint bit = 0; bit < (1ULL << n); ++bit) {
int t = 0;
for (uint i = 0; i < n; ++i) {
if ((bit & (1ULL << i)) != 0) {
t += a[i];
}
}
sum.insert(t);
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int m;
cin >> m;
if (sum.find(m) != sum.end()) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
return 0;
}上記プログラムはどちらも、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
トピック#5では、再帰関数を使って、部分的な小さな問題に分解して解く手法を紹介します。
引き続き、ALDS1 の問題を紹介していきます。
