0

我想检查集合 [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）。我想我在这里做错了什么，但我在我的代码中找不到错误。

4

1 回答 1

0

在check()函数中，您不需要检查dsetsize being 1，因为在从索引到有效大小的for循环中，它在下面得到了注意。i = 0删除以下if语句，该语句应产生有效数字，其总和为 的倍数3：

if (dset.size() == 1) {
    if (dset[0] % 3 == 0) { return false; }
}
于 2019-11-27T11:50:46.920 回答