用c语言编写:/组合问题。排列与组合是常用的数学方法,其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n), // 我们可以简单地将n个元素理解为自然数1, 2, …, n,从中任取r个数。现要求你输出所有组合。 // 例如n = 5, r = 3,所有组合为:123, 124, 125, 134, 135, 145, 234, 235, 245, 345 //* 输入: //一行两个自然数n, r(1 < n < 21, 0≤r≤n)。 // * 输出: // 所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,每个元素占三个字符的位置,所有的组合也按字典顺序。
时间: 2023-06-16 09:04:29 浏览: 59
以下是用C语言编写的解决方案:
```c
#include <stdio.h>
int n, r;
int ans[25];
void dfs(int cur, int last) {
if (cur == r + 1) { // 已选出 r 个数
for (int i = 1; i <= r; i++) {
printf("%3d", ans[i]);
}
printf("\n");
return;
}
for (int i = last + 1; i <= n; i++) {
ans[cur] = i;
dfs(cur + 1, i);
}
}
int main() {
scanf("%d%d", &n, &r);
dfs(1, 0);
return 0;
}
```
这里采用深度优先搜索(DFS)的思想,递归地枚举所有可能的组合。具体地,我们维护一个数组 `ans`,表示当前已选出的 r 个数,以及一个指针 `cur`,表示当前已选出了 `cur-1` 个数,还需要选出 `r-cur+1` 个数。在递归的过程中,我们从上一个选出的数的下一个数开始枚举,并将当前枚举的数放入 `ans` 数组中,然后递归地继续选下一个数。当选出了 r 个数时,我们输出当前的组合即可。
需要注意的是,为了保证组合按字典序排列,我们在每个递归层次上,从上一个选出的数的下一个数开始枚举。这样可以保证每个组合的第一个数都是当前已选出的数中最小的一个。