锐客网

  1. 首页 > it技术 > >

简单谈谈实现递归暴力枚举

简单谈一谈如何用递归实现暴力枚举。
下面先看到一个例子。
袋子里有2红3绿5黄球，随机从中摸出8个，打印显示所有组合。
暴力枚举，其实就是实现一颗搜索树。
那很显然这颗搜索树的层数是8层，因为只要摸8个就行了。每个节点拓展出去的儿子节点很显然是10个，因为每次都有10种选择。
那很显然。8层是递归出口。10个是每层要枚举的分支。所以可以写出如下代码。

char s[]="gggrryyyyy"; //存放颜色数据 char ans[10]; //存放当前方案 void dfs(int d) { if(d==8) { for(int i=0; i

但是这并不符合题目的要求。因为这样写，就有可能同个字符被取了多次，而很显然每个字符只能被取一次。好的，可以修改代码，得到如下代码。
int vis[15]; char s[]="gggrryyyyy"; //存放颜色数据 char ans[10]; //存放当前方案 void dfs(int d) { if(d==8) { for(int i=0; i

这样，加个标记数据，就可以保证在某个方案里，一个字符只能被取一次。但是，发现，这个方法还是不行，因为一个节点发射出去的儿子节点，最多只能是3个(“r”,”g”,”y”),而不能是(“r”,”r”,”g”,”g”“y”…)，否则同种方案会被计算多次。那也就是说，在每一层搜索的时候，搜过的字符就不能再搜了。由于字符数组是有序的，所以用如下代码就可以实现上述功能。
int vis[15]; char s[]="gggrryyyyy"; //存放颜色数据 char ans[10]; //存放当前方案 void dfs(int d) { if(d==8) { for(int i=0; i

好了，现在已经快实现了，就差最后一步了。现在有个问题就是。可能会搜出”gggrryyy”,”gggryyyr”,那由于取得是组合，所以这两种也应该算同种方案。那如何解决这个问题呢？其实很简单，只要保证有序地取，就不会重复，因为不同排列的同种组合排好序是一样的，比如这次搜索，把s第i个儿子给了ans[d]，那么下一次搜索，枚举儿子分支的时候就从i+1开始。这样搜出来的绝对是有序的，就不会出现无序的情况。
代码如下：
char s[]="gggrryyyyy"; int vis[15]; char ans[10]; void dfs(int d,int last) { if(d==8) { for(int i=0; i<8; i++) cout

主函数里直接dfs(0,0); 就可以了。
这样，这个问题就解决了。
下面再看到一个问题。
输入n（1-10之间数字），将数字分解显示，如6可以显示为6，5+1，4+2，4+1+1…..
同样，在写代码之前，脑袋里要有一颗搜索树。
但是，这里递归层数就不那么明确了。那可以用一个状态sum来确定递归出口。可以写出代码。
void dfs(int sum) { if(sum==0) { 输出一组解 return ; } for(int i=sum; i>0; i--) { 取一个加数为i dfs(sum-i); } }

很容易发现，怎么输出解啊。我怎么知道加数有多少个呀？
简单，再加个形参记录层数就可以了，刚好第d层可以放第d个加数。
可以写出代码。
void dfs(int d,int sum) { if(sum==0) { for(int i=0; i0; i--) { ans[d]=i; dfs(d+1,sum-i); } }

紧接着，你会发现你输出了”4+2”，又输出了”2+4”
这其实跟上面的不同排列相同组合是同一种情况，同样可以用上面的思路解决，只要让后面的数比前一个取的数小于等于就可以了。可以写出代码。
void dfs(int d,int sum,int pre) { if(sum==0) { for(int i=0; i0; i--) { ans[d]=i; if(i<=pre) dfs(d+1,sum-i,i); } }

完美解决问题。
那现在这个问题会解决了吗？
用递归实现，输出用1分、2分和5分的硬币凑成1元，一共有多少种方法。
不确定层数，又是组合问题，所以可以先定个sum的状态，然后下一次取一定要大于等于上一次所取的，避免方案重复。
最后附上这三道题的完整代码。
摸球
#include #include #include #include #define LL long long using namespace std; char s[]="gggrryyyyy"; int vis[15]; char ans[10]; void dfs(int d,int last) { if(d==8) { for(int i=0; i<8; i++) cout

n的所有和
#include #include #include #include #define LL long long using namespace std; int ans[10]; void dfs(int d,int sum,int pre) { if(sum==0) { for(int i=0; i0; i--) { ans[d]=i; if(i<=pre) dfs(d+1,sum-i,i); } } using namespace std; int main() { freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); int n; while(cin>>n) dfs(0,n,n); return 0; }

【简单谈谈实现递归暴力枚举】凑硬币
#include #include #include #include #define LL long longusing namespace std; int ans=0; int a[105]={5,2,1}; void dfs(int cur,int last) { if(cur==0) { ans++; return ; } for(int i=last; i<3; i++) if(cur>=a[i]) dfs(cur-a[i],i); } int main() { //freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); int n; for(int i=100; i<=100; i++) { ans=0; dfs(i,0); printf("%d\n",ans); } return 0; }

    推荐阅读


    上一篇：回首2018|回首2018,拥抱2019

    下一篇：本博客已搬家