【4005】组合的输出
输出 组合
2023-09-14 09:03:46 时间
Time Limit: 10 second
Memory Limit: 20 MB
排列与组合是常用的数学方法,其中组合就是从n个数元素中抽出r个元素(不分顺序且,r≤n),我们可以简单地将n个元素理解为自然数1,2......n,从中任取r个数。
现要求你用递归的方法输出所有的组合,以及组合的总数。
Input
输入文件仅一行,输入两个自然数n,r(1≤n≤21,1≤r≤n)。
Output
首先,输出所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列(每个元素用一个空格隔开,每行行末用换行结束)。
最后,输出组合的总数格式为:sum=组合的总数,最后用换行结束。
Sample Input
5 3
Sample Output
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 sum=10
【题解】
同样是深搜,限制条件有:右边的数字大于左边。r个数字的组合。具体的在程序中讲。
【代码】
#include <cstdio> int n,r,number = 0,a[25],sum = 0; void input_data() { scanf("%d %d",&n,&r); //输入数据 } void search(int t) //dfs { if (number == r) return; //如果已经完成搜索 退出 a[++number] = t; //记录当前搜到的数字 并记录 for (int i = t+1;i <= n;i++) // 要求右边的数字大于左边,则从t+1开始枚举 search(i); if (number == r) //如果已经搜完 则输出 sum递增 { for (int i = 1;i <= number-1;i++) printf("%d ",a[i]); printf("%d\n",a[number]); sum++; } number--; //回溯 回到搜索这个数字之前的状态。 } void get_ans() { for (int i = 1;i <= n-r+1;i++) //n-r+1可以直接改成n,dfs中的剪枝可以很快排除不符合的情况 search(i); printf("sum=%d\n",sum); } int main() { input_data(); get_ans(); return 0; }
相关文章
- 高电平输出怎么转低电平输出
- 2022-08-17:以下go语言代码输出什么?A:运行时 panic;B:32;C:编译错误;D:0。package main
- 2022-12-17:订单最多的客户。以下数据,结果输出3。请问sql语句如何写?
- 开关电源中输出电容的ESR会影响负载的动态响应
- 【Android FFMPEG 开发】FFMPEG 音频重采样 ( 初始化音频重采样上下文 SwrContext | 计算音频延迟 | 计算输出样本个数 | 音频重采样 swr_convert )
- printf中用%d输出float或者double详解编程语言
- 解决Oracle异常输出的方法(oracle异常输出)
- MySQL使用格式化输出法解决数据持久化(mysql格式输出)
- 深入理解CXOracle掌握Oracle输出技能(cx oracle 输出)
- PHP输出控制功能在简繁体转换中的应用
- 基于排列与组合输出多少中情况详解
- sql时间格式化输出、Convert函数应用示例
- 用Python输出一个杨辉三角的例子
- thinkphp3.0输出重复两次的解决方法