c++ 组合问题
发布时间:2020-12-16 10:40:28 所属栏目:百科 来源:网络整理
导读:题目描述 组合问题就是从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个元素(不分顺序且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 )。 输出所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,所有的组合也按字典顺序。 样例输入
样例输出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 Source Code#include <stdio.h> #include <iostream> using namespace std; bool used[30]; int ans[30]; int n,r; void dfs(int u) { if(u == r + 1)//注意:是r + 1 不是r //如果满足R个数据,则输出 { for (int i = 1;i <= r;i ++) printf("%d ",ans[i]); printf("n"); return ; } for (int i = ans[u - 1] + 1;i <= n;i ++)//注意:i的起点是ans[u - 1] + 1 如果有n个数字,就循环n次来检查是否被选中 { if(used[i] == 0)//如果没有被选中 { ans[u] = i;//如果没有被选中,就把i放到ans[]中 used[i] = 1;//used[2] = 1表示2这个数已经被选过了 used[3] = 1表示3这个数已经被选过了 dfs(u + 1);//继续选下一个数字 dfs(1):选第1个数 dfs(2):选第2个数 dfs(n + 1):打印,退出 used[i] = 0;//打印完毕,把该数字取消 } } } int main() { memset(used,sizeof(used)); cin >> n; cin >> r; dfs(1);//选择第一个数字 return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |