AOJ0030: Sum of Integers
問題
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030&lang=jp
問題概要
0 から 9 までの数字から異なる n 個の数を取り出して和が s となる組み合わせの数を求めよ。
例
n = 3, s = 6 のとき
0 ~ 9 までの数字から異なる3個の数の和が6になる組み合わせは
1 + 2 + 3 = 6
0 + 1 + 5 = 6
0 + 2 + 4 = 6
の3通り
解答例
指針
- 全通りのパターンを試す(全探索)
解説
0 から 9 までの数字から異なるいくつかの数を取り出す組み合わせのパターンは, それぞれの数字について使うか使わないかを考えればよいので全部で 210 通りになります。
例えば {0, 1, 2, 3} から異なるいくつかの数を取り出す組み合わせ(部分集合の数)は
{}
{0} {1} {2} {3}
{0, 1} {0, 2} {0, 3} {1, 2} {1, 3} {2, 3}
{0, 1, 2} {0, 1, 3} {0, 2, 3} {1, 2, 3}
{0, 1, 2, 3}
の 24 通りと確かに2の冪乗の形になることが確認できます。
パターンがたかだか 210 通りであるので全てのパターンを試すことでこの問題を解くことができそうです。
上の例のように状態を列挙する方法はいくつかあります。
深さ優先探索
これは蟻本の序盤(p34)に書かれている方法です。
次のような状態遷移を行い解を求めます。
i 番目の数字を使うなら sum に a[i] を足し使わないなら足さずに次の数を見るようにすると組み合わせの和を全て列挙出来ます。
#include <iostream> using namespace std; int n, s, cnt; int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 数列{a} の i番目までの数で和を作る. // k: 選んだ数の個数. sum: 選んだ数の和 void dfs(int i, int sum, int k) { // n 個の数を選んで和が s になるものをカウント if (k == n && sum == s) { cnt++; } // 終了条件 if (i == 10 || k == n || sum > s) { return; } // a[i]を使う場合 dfs(i + 1, sum + a[i], k + 1); // a[i]を使わない場合 dfs(i + 1, sum, k); } int main() { while (cin >> n >> s) { if (!n && !s) { break; } cnt = 0; dfs(0, 0, 0); cout << cnt << endl; } return 0; }
明示的に stack を使って似たようなことをするプログラムも書いてみました。
#include <iostream> #include <stack> using namespace std; struct sets { int i, sum, k; }; int n, s, cnt; int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; void dfs(int i, int sum, int k) { stack<sets> S; S.push(sets{i, sum, k}); while (!S.empty()) { sets u = S.top(); if (u.k == n && u.sum == s) { cnt++; } if (u.i == 10 && u.k == 0 && u.sum == 0) { break; } if (u.i < 10 && u.k < n) { S.push(sets{u.i + 1, u.sum, u.k}); S.push(sets{u.i + 1, u.sum + a[u.i], u.k + 1}); } else if (u.i == 10) { int tmp = u.k; while (S.top().k == tmp) { S.pop(); } } else { S.pop(); } } } int main() { while (cin >> n >> s) { if (!n && !s) { break; } cnt = 0; dfs(0, 0, 0); cout << cnt << endl; } return 0; }
標準ライブラリ機能による組み合わせの列挙
C++ の std::next_permutation を使えば順列だけでなく組み合わせの全列挙も簡単に出来ます。
末尾の n 個が 1 でその他が 0 の配列を用意して next_permutation に渡してループを回します。
#include <iostream> #include <algorithm> using namespace std; int main() { int n, s, cnt, sum; int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; while (true) { cin >> n >> s; if (!n && !s) { break; } int arr[10] = {0}; for (int i = 0; i < n; i++) { arr[9-i] = 1; } cnt = 0; do { sum = 0; for (int i = 0; i < 10; i++) { if(arr[i]) { sum += a[i]; } } if (sum == s) { cnt++; } } while (next_permutation(arr, arr+10)); cout << cnt << endl; } return 0; }
Python には itertools という便利なものがあり順列や組み合わせを簡単に列挙できます。
#!/usr/bin/env python2 # -*- coding: utf-8 -*- import itertools while True: n, s = map(int, raw_input().split()) if n == 0 and s == 0: break L = [i for i in xrange(10)] cnt = 0 for i in itertools.combinations(L, n): if sum(i) == s: cnt += 1 print cnt
bit による全探索
{0, 1, 2, 3, 4, ... 9} の部分集合の数は全部で 210 です。
0 ~ 210-1 を2進数表記すると 0000000000 ~ 1111111111 になります。 i 番目の bit が立っている場合,数列の i 番目を使うことにすると部分集合を列挙できます。
任意の整数 n の 0-based-index で i 番目の bit が立っているかどうかを判定するには std::bitset の bitset::test を使う方法と n を i bit 右にシフトしたものと 1 との論理積(&)を取る方法があります。
例えば 13(10) の 2 bit目が立っているどうかは 13 >> 2 と 1 の論理積を取ることで判定できます。 論理積が 0 なら bit は立っておらず 1 なら bit は立ってます。
13 = 1101(2)
13 >> 2 = 0011(2)
0011 & 0001 = 1 => 2 bit 目の bit は立っている
#include <iostream> #include <bitset> using namespace std; int main() { int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; int n, s, sum, cnt; while (cin >> n >> s) { if (!n && !s) { break; } cnt = 0; for (int i = 0; i < (1 << 10); i++) { sum = 0; for (int j = 0; j < 10; j++) { // if (bitset<10>(i).test(j)) { if ((i >> j) & 1) { sum += a[j]; } } if (sum == s && bitset<10>(i).count() == n) { cnt++; } } cout << cnt << endl; } return 0; }
参考文献
- 蟻本
