给几个数(可重复),取其中三个求有几种可能,用c++实现
时间: 2024-10-08 09:23:59 浏览: 14
在C++中,如果你有一个包含重复数字的整数数组,并想要从中选择3个不同的元素(不考虑顺序),可以使用组合数学的概念,即从n个元素中取出k个不同的元素的组合数,可以用公式`C(n, k) = n! / (k!(n-k)!)`来计算,其中`!`表示阶乘。
为了实现这个功能,你可以创建一个函数,利用`std::vector`存储数据,然后遍历所有可能的组合。但由于直接对阶乘做计算可能会导致溢出,所以更常见的是使用动态规划或者库函数如`std::unordered_set`来避免重复计数。
下面是一个简单的示例,假设我们使用了`std::unordered_set`来跟踪已经选择过的数字:
```cpp
#include <iostream>
#include <vector>
#include <unordered_set>
int combinations(const std::vector<int>& nums, int target) {
std::unordered_set<int> selected;
int count = 0;
for (int num : nums) {
if (selected.find(num) == selected.end()) { // 如果没选过
selected.insert(num); // 选中并增加计数
if (selected.size() == target) { // 选够3个
count++;
selected.erase(selected.begin()); // 移除第一个已选的,准备下一次循环
}
}
}
return count;
}
int main() {
std::vector<int> numbers = {1, 1, 2, 3, 4, 4, 5}; // 示例数组
int target = 3; // 选择3个不同元素
int result = combinations(numbers, target);
std::cout << "从给定数组中选取3个不同的数的不同组合方式共有 " << result << "种。\n";
return 0;
}
```
在这个例子中,我们只计算了不重复的选择数目。如果你想包括重复计数的情况,则需要稍微修改一下计数的方式。
阅读全文