腾讯建站官网,怎么用wordpress建电商网站吗,网络营销企业推广策划,如何构成网站1317#xff1a;【例5.2】组合的输出
时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 排列与组合是常用的数学方法#xff0c;其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)#xff0c;我们可以简单地将n个元素理解为自然数1#xff0c;2#xff0c;…#…1317【例5.2】组合的输出
时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 排列与组合是常用的数学方法其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)我们可以简单地将n个元素理解为自然数12…n从中任取r个数。现要求你用递归的方法输出所有组合。
例如n5r3所有组合为
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(1n211≤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]即可每次递归回到上一层会再赋值所以不需要考虑数据还原
#includebits/stdc.h
using namespace std;
int n;
int r;
int a[22]{0};//将遍历得到的排列放进数组储存
void dfs(int l); //l表示遍历的深度 遍历到第几层即表示求排列的第n个数
int main(){cinn;cinr;dfs(1);//从第一个第一层开始遍历 return 0;
}
void dfs(int l){//判断是否遍历完一次 if(lr1){for(int i1;il-1;i){printf(%3d,a[i]);}coutendl;return ;//返回到上一层 }else{//直接从上一个得到的数开始遍历实现按照字典序排列如果是全排列则需要一个数组来标记是否遍历过并在遍历后取消标记 for(int ia[l-1]1;in;i){ a[l]i; //遍历第几层即得到第几个数所以是a[l] //继续遍历得到下一位dfs(l1); //由于遍历得到一串数后输出会返回到上一层继续往下遍历这是递归遍历所以不用单独考虑遍历到 }}}
