1317:【例5.2】组合的输出

2023-12-28 20:55:43

1317:【例5.2】组合的输出

时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
排列与组合是常用的数学方法,其中组合就是从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
思路:

  • 这是一个排列问题,排列n个数,要求就是按字典序排列,最简单的就是用循环遍历即可,但是由于r是未知,不能确定循环次数,且题目要求用递归
  • 遍历过程是一个深度优先搜索,确定第一层(第一个数)后立即确定下一层(下一个数),直到确定叶节点(最后有一个数),由于寻找叶节点这个过程都是一致,所以利用递归+循环遍历即可实现,递归实现上一层和下一层的搜索(例如: 12 4 ,1 2 5同层遍历完后也是靠递归回到第二层,然后再循环遍历得到1 3 4 ,1 3 5),循环遍历则实现同一层的搜索(例如:1 2 3 ,1 2 4 ,1 2 5即通过递归是的循环遍历实现)
  • 由于搜索过程中遍历时可以从上一层得到的数开始遍历,所以可以不需要一个标记数组去标记已经排列过的数
  • 排列的过程是一个树状,不需要考虑如何储存,只需要每次排列的数放到数组a[i]即可,每次递归回到上一层会再赋值,所以不需要考虑数据还原
#include<bits/stdc++.h>
using namespace std;
int n;
int r;
int a[22]={0};//将遍历得到的排列放进数组储存
void dfs(int l); //l表示遍历的深度 ,遍历到第几层即表示求排列的第n个数 
int main(){
	cin>>n;
	cin>>r;
	dfs(1);//从第一个第一层开始遍历 
	return 0;
}
void dfs(int l){
	//判断是否遍历完一次 
	if(l==r+1){
		for(int i=1;i<=l-1;i++){
			printf("%3d",a[i]);
		}
		cout<<endl;
		return ;//返回到上一层 
	}else{
		//直接从上一个得到的数开始遍历,实现按照字典序排列,如果是全排列则需要一个数组来标记是否遍历过,并在遍历后取消标记 
		for(int i=a[l-1]+1;i<=n;i++){   
			a[l]=i;  //遍历第几层即得到第几个数,所以是a[l] 
			//继续遍历得到下一位
			dfs(l+1); //由于遍历得到一串数后输出,会返回到上一层,继续往下遍历,这是递归+遍历,所以不用单独考虑遍历到 
		}
	}
	
}

文章来源:https://blog.csdn.net/m0_46183615/article/details/135276445
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。