C语言回溯法 实现组合数 从N个数中选择M个数
2019/7/10 22:33:37
本文主要是介绍C语言回溯法 实现组合数 从N个数中选择M个数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
在平时的算法的题目中,时常会遇到组合数相关的问题,暴力枚举。在N个数中挑选M个数出来。利用for循环也可以处理,但是可拓展性不强,于是写这个模板供以后参考。
两个函数和全局变量可以直接用。
代码:
#include<iostream> #include<cstdio> #define N 10 //被选择的数目 #define M 5 //要选出来的数目 using namespace std; int vis[N+1]; //标志, int ans=0; //含有的组合数 的数量 int num[M+1]; //选出来的数放在num数组里面 void solve() { //在solve函数里面处理 for(int i=1; i<M+1; i++) cout<<num[i]<<" "; cout<<endl; } void dfs(int index) { //挑选的第index+1个数 if(index == M) { solve(); ans++; return ; } for(int i=num[index]+1; i<N+1; i++) { if(!vis[i]) { vis[i] = 1; num[index+1] = i; dfs(index+1); vis[i] = 0; } } } int main() { dfs(0); //回溯开始 cout<<endl<<ans; return 0; }
可以发现利用回溯法挑选的有一个优势在于,输出的数组是经过排序的。
这篇关于C语言回溯法 实现组合数 从N个数中选择M个数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享