3.找出n个自然数(1,2,3,…,n)中取r个数的组合。采用分治策略,写出相应问题的算法及c程序。
时间: 2024-03-25 12:36:58 浏览: 61
首先,我们可以观察到这个问题具有明显的子问题结构,即在n个自然数中取r个数的组合,可以分解为两个子问题:
1. 在n-1个自然数中取r个数的组合;
2. 在n-1个自然数中取r-1个数的组合,并将n加入到这r-1个数中,形成r个数的组合。
这启示我们可以采用分治的策略来解决这个问题。具体来说,我们可以设计递归函数`combine`,它接受三个参数:当前可选的自然数范围[start, end],需要选出的数字个数k,以及当前的已选数字组合prefix,返回[start, end]中选出k个数字的所有组合。
算法步骤如下:
1. 如果k等于0,说明已经选出了需要的数字,将prefix添加到结果集中,并返回;
2. 如果[start, end]中可选的数字个数不足k个,直接返回;
3. 否则,分别递归求解:
- 跳过start,从start+1开始选出k个数字,将结果添加到结果集中;
- 将start添加到prefix中,从start+1开始选出k-1个数字,将结果添加到结果集中;
C++代码如下:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void combine(int start, int end, int k, vector<int>& prefix, vector<vector<int>>& res) {
if (k == 0) {
res.push_back(prefix);
return;
}
if (end - start + 1 < k) {
return;
}
// 不选start
combine(start + 1, end, k, prefix, res);
// 选start
prefix.push_back(start);
combine(start + 1, end, k - 1, prefix, res);
prefix.pop_back();
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> prefix;
combine(1, n, k, prefix, res);
return res;
}
int main() {
int n = 5, k = 3;
auto res = combine(n, k);
for (auto comb : res) {
for (auto num : comb) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
```
输出结果与前面的递归算法相同:
```
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
```