C++程序实现列出所有组合 |21xrx.com

C++程序实现列出所有组合

2023-07-03 07:44:48 深夜i -- --

C++ 程序实现列出所有组合递归算法

组合是数学中一个重要的概念，指从一组元素中选出若干元素的不同方式，且不考虑元素的顺序，不含重复元素。例如，从1、2、3中选出两个元素的组合有{(1,2),(1,3),(2,3)}，其中没有重复元素，也不考虑元素的顺序。

C++程序可以用来列出所有组合，并检查其中是否存在特定的组合。下面是一个简单的C++程序，用于列出给定列表中所有可能的组合。

#include

using namespace std;

vector > combinations;

void getCombinations(vector & nums, int pos, vector & comb) {

if (comb.size() == nums.size() / 2) {

combinations.push_back(comb);

return;

}

for (int i = pos; i < nums.size(); ++i) {

comb.push_back(nums[i]);

getCombinations(nums, i + 1, comb);

comb.pop_back();

}

int main() {

vector nums = 1;

vector comb;

getCombinations(nums, 0, comb);

for (int i = 0; i < combinations.size(); ++i) {

cout << "{";

for (int j = 0; j < combinations[i].size(); ++j) {

cout << combinations[i][j];

if (j != combinations[i].size() - 1) cout << ",";

}

cout << "}" << endl;

}

return 0;

}

在该程序中，使用了递归函数getCombinations来生成所有组合。其中，pos参数指示从哪个位置开始构建组合，comb参数存储当前组合，combinations是用于存储所有组合的变量。当成功构建一个组合时，将其添加到combinations中。

主函数中定义了一个待求解的列表nums和一个空的组合comb，调用getCombinations来生成所有组合，最后遍历combinations并输出每一个组合。

C++程序还可以用于检查是否存在特定的组合。如果要查找[(1,2),(3,4)]是否存在于上述列表中，可以改写getCombinations如下：

bool contains(vector & a, vector & b) {

if (a.size() != b.size()) return false;

for (int i = 0; i < a.size(); ++i)

if (a[i] != b[i]) return false;

return true;

}

bool hasCombination(vector & nums, vector & comb) {

for (int i = 0; i < comb.size(); ++i) {

bool found = false;

for (int j = 0; j < nums.size(); ++j)

if (comb[i] == nums[j]) found = true;

if (!found) return false;

}

vector > combinations;

getCombinations(nums, 0, comb);

for (int i = 0; i < combinations.size(); ++i)

if (contains(combinations[i], comb)) return true;

return false;

}

如果hasCombination(nums, 3)返回true，则[(1,2),(3,4)]存在于列表中。函数contains用于比较两个组合是否相等。

以上是关于使用C++程序实现列出所有组合的简单介绍和示例，希望能对读者有所帮助。

上一篇: idea打包java可执行jar包

下一篇: C++ cout重定向方法介绍

评论区

()

相似文章