我想检查集合 [1, ..., 15] 的子集 S 有多少,因此不可能从 S 中选择两个元素,使得它们的和是 3 的倍数。
检查这一点的算法如下:在 [1, ..., 15] 的子集和长度为 15 的两个字符的字符串之间存在自然双射(假设两个字符是 '0' 和 '1'修正一个约定),其中位置 i 中的字符“0”表示整数 i 不在子集中,而位置 i 中的字符“1”表示整数 i 在子集中。例如,字符串“111001000000000”与子集 {1, 2, 3, 6} 相关联。该子集不满足上述约束。
我编写了一个 C++ 代码来生成所有此类字符串,将它们转换为 1 到 15 之间的整数向量,并检查该集合中的所有对是否存在总和为 3 的倍数的对。
这是代码:
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <vector>
bool check(const std::vector<int>& dset) {
if (dset.size() == 1) {
if (dset[0] % 3 == 0) { return false; }
}
for (size_t i = 0; i < dset.size() - 1; ++i) {
auto a = dset[i];
for (size_t j = i + 1; j < dset.size(); ++j) {
auto b = dset[j];
if ((a + b) % 3 == 0) { return false; }
}
}
return true;
}
int main() {
const int N = 15; // We consider subsets of [1, ..., N].
int approved = 1; // We automatically approve the empty set.
std::bitset<N> set;
for (int n = 1; n < std::pow(2, N); ++n) {
set = std::bitset<N>(n);
std::vector<int> dset(set.count());
size_t j = 0;
for (int i = 1; i <= N; ++i) {
if (set[i - 1]) {
dset[j++] = i;
}
}
// Sweep through all couples in dset.
if (check(dset)) {
++approved;
}
}
std::cout << approved << " out of " << std::pow(2, N) << std::endl;
}
问题是我的代码返回 373,这是错误的答案(正确的应该是 378)。我想我在这里做错了什么,但我在我的代码中找不到错误。