■ 数値N(<=25)を重複しない数値に分割
数値Nを重複しない数値に分割する課題(CodeIQの問題を解くために必要な計算)について考えて
無理やり3パターン作ったのでメモ。
N=3の場合、(1+2),(3)
N=6の場合、(1+2+3),(1+5),(2+4),(6)
■ 何のために作るのか？
全検索アルゴリズムでスタックやキューを使った場合の考え方にも慣れたい。
再起呼び出し以外での実装はどうするのか？を考えたくなった。
■ 実装(C++)
ideone.comで動作確認できます。
□ 1. 総当たり方式（brute_force関数）
まずは難しい事を考えずに総当たり方式を作ってみた。
numの各ビットを下位から1,2,3,...と読み換えて合計値がNなら該当するパターンであると判断する方法。
考えられるパターンを全て探索するので遅いが、全パターン検索できるかは一目瞭然。
int brute_force(int N)
{
int num, i, val;
int count = 0;
for (num = 1; num < (1 << N); num++) {
val = 0;
for (i = 0; i<MAXNUMBER; i++) {
if (num & (1 << i)) { val += (i + 1); }
}
if (val == N) {
count++;
}
}
return count;
}
N=3の場合、0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111 の7パターン(2^3-1)に対しNと等価か調査する。
N=6の場合は、63パターン=(2^6)-1に対し…以下、略…
N=25の場合は、33554431パターン=(2^25-1)に対し…以下、略…
結論：計算数が多すぎて実用にならない(CodeIQの制限時間に引っかかる)
ideone.comは、高速なCPUを使っているようで、凄く速くてビックリしたが...
□ 2. 再起呼び出し方式（recursive関数）
他関数とデータ構造を共通化しようと思って実装したので理解しにくくて申し訳ない感じですが...
int recursive(int N, PartData* prev = NULL)
{
int n;
int num = 0;
PartData pd = { 0, 1 };
if (prev == NULL) { prev = &pd; }
for (n = prev->start; n <= N; n++)
{
PartData nd = *prev;
nd.sum += n;
nd.start = n + 1;
nd.hist[n] = n;
if (nd.sum > N) { return 0; }
if (nd.sum == N)
{
PartDataPrint(&nd);
num++;
return num;
}
else
{
num += recursive(N, &nd);
}
}
return num;
}
目標値Nに対して1から順番に加算していきNより小さければ再起呼び出しをする。
目標値Nより大きければ処理を止めるので無駄がない。
1 + 2 + 3 = 6 : OK
1 + 2 + 4 = 7 : NG
1 + 3 + 4 = 8 : NG
1 + 4 + 5 = 9 : NG
1 + 5 = 6 : OK
2 + 3 + 4 = 9 : NG
2 + 4 = 6 : OK
以下略、、、
3. キューorスタックを利用する方式（stack_or_que関数）
//-----------------------------------------------------------------------------
// スタック or キューを使った実装
//-----------------------------------------------------------------------------
int stack_or_que(int N, int isStack)
{
int i;
int num = 0;
std::stack<PartData> stk;
std::queue<PartData> que;
// 初期値登録
// 合計値 = 0
// ループ開始値 = 1
PartData s = { 0, 1 };
if (isStack) stk.push(s);
else que.push(s);
while ((isStack ? stk.size() : que.size()) > 0)
{
if (isStack) { s = stk.top(); stk.pop(); } // 値を取り出す
else { s = que.front(); que.pop(); } // 値を取り出す
// 目標値に到達していれば表示して次へ
if (s.sum == N)
{
PartDataPrint(&s);
num++;
continue;
}
// s を 1 要素分だけ探索
// "合計値 <= N" の条件に該当するものを登録
for (i = s.start; i <= N; i++)
{
PartData cp = s;
cp.sum += i;
cp.start = i + 1;
cp.hist[i] = i;
if (cp.sum > N)
{
break; // これ以上の探索は無駄なのでbreak
}
// 次に期待できない場合はスルー
if ((cp.sum < N) && (cp.sum + cp.start) > N) {
continue;
}
if (isStack) { stk.push(cp); }
else { que.push(cp); }
}
}
return num;
}
下記の原則で動作する。(理解しにくいなぁ...)
popした値(s.sum)にs.start ～ Nの値を加算し、結果がN以下なら次の候補としてpushする。
1回目のpopで、recursive関数の1階層目のループに相当する処理。
2回目以降のpopでは、recursive関数の2階層目以降のループに相当する処理。
要はpopで取得したデータを見て、次に持ち越すか、破棄するかの2択処理になっている。
1回目pop sum=0, start=1
[0+1] sum=1, start=2 : push (Nより小さいので継続)
[0+2] sum=2, start=3 : push (Nより小さいので継続)
[0+3] sum=3, start=4 : continue (破棄)
[0+4] sum=4, start=5 : continue (破棄)
[0+5] sum=5, start=6 : continue (破棄)
[0+6] sum=6, start=7 : push (Nと等価なのでpop時に表示)
2回目pop sum=1, start=2
[0+1+2] sum=3, start=3 : push (Nより小さいので継続)
[0+1+3] sum=4, start=4 : continue (破棄)
[0+1+4] sum=5, start=5 : continue (破棄)
[0+1+5] sum=6, start=6 : push (Nと等価なのでpop時に表示)
[0+1+6] sum=7, start=7 : break (破棄)
3回目pop sum=2, start=3
[0+2+3] sum=5, start=4 : continue (破棄)
[0+2+4] sum=6, start=5 : push (Nと等価なのでpop時に表示)
[0+2+5] sum=7, start=6 : break (破棄)
4回目pop sum=6, start=7 → 発見
5回目pop sum=3, start=3
[0+1+2+3] sum=6, start=4 : push (Nと等価なのでpop時に表示)
[0+1+2+4] sum=7, start=5 : break
6回目pop sum=6, start=6 → 発見
7回目pop sum=6, start=5 → 発見
8回目pop sum=6, start=4 → 発見
■結論
再起呼び出しが一番わかりやすい実装に見えるが、実装は出来た。
もうちょっと、マシな実装があるような気がするのだが・・・