A27450. 组合的输出
填空题
较易
知识点
题目描述
组合的输出
题目描述
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你用递归的方法输出所有组合。
例如n＝5，r＝3，所有组合为：
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
输入
一行两个自然数n、r(1<n<21，1≤r≤n)。
输出
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
输入样例
5 3输出样例
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参考答案
#include<bits/stdc++.h>
using namespace std;
int nums[25];//记录要输出哪些数，记录在num[1],num[2]...,num[r]
int n, r;//从n个元素中抽出r个元素
void dfs(int k, int st)//k:要确定升序排列中的第几个数，要填入的数字大于等于st
{
if(k > r)//如果已经填充了r个数字，再看第r+1个数字
{//输出存在num中的排列数
for(int j = 1; j <= r; ++j)
cout << setw(3) << nums[j];
cout << endl;
return;
}
for(int i = st; i <= n; ++i)
{
nums[k] = i;//添加数字
dfs(k+1, i+1);
}
}
int main()
{
cin >> n >> r;
dfs(1, 1);
return 0;
}答案解析
#include <bits/stdc++.h>
using namespace std;
int a[21]={0},n,r;
bool b[21]={0};
void s(int t){
for(int i=a[t-1]+1;i<=n;i++){
if(!b[i]){
b[i]=1;
a[t]=i;
if(t==r){
for(int i=1;i<=r;i++)
cout<<setw(3)<<a[i];
cout<<endl;
}
else s(t+1);
b[i]=0;
}
}
}
int main(){
cin>>n>>r;
s(1);
return 0;
}
上一题
下一题