题目相关

题目描述

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且 r ≤n)，我们可以简单地将n个元素理解为自然数1,2,…,n从中任取r个数。

现要求你输出所有组合。

例如n=5,r=3所有组合为：

12 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,0≤r≤n)。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

**注意哦!输出时，每个数字需要3个场宽，pascal可以这样：

write(ans:3);

输入输出样例

输入

5 3

输出

题目链接

P1157 组合的输出 - 洛谷

分析

阅读完题目，发现本题就是让我们从 1 ~ n个数中选出r个数，输出所有的组合，并且部分顺序。且对输出做出了一定的要求，元素要从小到大排列，且占三个场宽。

占三个场宽可以使用printf来实现，注意加上头文件cstdio

printf("%3d",x);//输出元素占3个场宽

选择的过程和全排列问题有些类似。每次都是从一堆数字中选一个出来加入组合，等挑完r个元素后，就输出。过程中要注意一点，他需要从小到大排列。那么我们可以使得挑选的数字比前一个选的大，这样就可以了。而不是说，选出所有的数字之后再去筛选，这样反而麻烦很多。

for(int i=ranks[pre]+1;i<=n;i++){//遍历比前一个元素大的数字

	ranks[pre+1]=i;//存到组合序列中

    ...

}

代码实现

#include <iostream>

#include <cstdio>

using namespace std;

int n,r;

int ranks[25]={0};//存放选好的r个数字 

void dfs(int sel){

	//已选好sel个数字

	if(sel==r){

		for(int i=1;i<=r;i++){

			printf("%3d",ranks[i]);

		}

		cout<<endl;

	}else{//还未挑选好

		//挑选第sel+1个数字

		//其中的元素按由小到大的顺序排列

		// 我的第sel+1个数字> 第sel个 ranks[sel]

		for(int i=ranks[sel]+1;i<=n;i++){//第sel+1 个数字可能的值

			//挑选i 存放进ranks数组中

			//第sel+1 个  => ranks[sel]

			ranks[sel+1]=i;

			//已经选好了sel+1个数字

			//递归调用 ，继续寻找下一个

			dfs(sel+1);

		}

	}

}

int main() {

	cin>>n>>r;

	dfs(0);

	return 0;

}

巴特西

【递归】P1157组合的输出