锐客网

  1. 首页 > it技术 > >

算法|寒假作业 DFS

题目：
寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
每个方块代表1~13中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
请填写表示方案数目的整数。
思路：
【其实一开始是没有思路的】，然后呢我看了下网上的解答，全排列暴力解法，跑不动。只有通过dfs,然后呢dfs涉及到递归，我上一篇文章讲的就是递归。
现在对这道题进行分解，编写递归程序，首先要找到递归方程。
这里我们先对DFS进行分解一下
DFS一般的形式为

dfs(deep){ if(找到解或者走不下去）{ return; } 枚举下一种情况 dfs(deep+1)//deep 表示深度

【算法|寒假作业 DFS】通过上面我们很清楚的知道，这里的递归方程其实就是指我们枚举的每种情况，但是我们以什么为标准呢？
我们应该以index，数组的下标，可以这样理解我先传入3个数，如果这三个数不满足“/”这种情况就是走不通的，我们应该退回去【即换一下第三个数—这里涉及到dfs，dfs就是指一条路走到底，如果不同返回到上一个】
现在题目有点清楚了，然后呢我们传入index是不是得判断是否找到解或者走不下去，一开始我们应该先判断是否走不下去，为什么因为我们传入的index是每次加1，也就是说我们可以一个一个的判断，先除法，除法走不下去的往回，除法能走下去的枚举一下下一个等等。
然后我们讨论一下枚举下一个，如果这个数vis[i]没有被访问到，我们在用这个数【这个就是下一个情况】
#include #include using namespace std; int vis[15]={0},a[15]; int ans=0; void dfs(int index){ if(index==4){ if(!(a[1]/a[2]==a[3]&&a[1]%a[2]==0)) return ; } if(index==7){ if(!(a[4]*a[5]==a[6])) return ; } if(index==10){ if(!(a[7]-a[8]==a[9])) return ; } if(index==13){ if(a[10]+a[11]==a[12]) ans++; return ; } for(int i=1; i<=13; i++){ if(!vis[i]){ vis[i]=1; a[index]=i; dfs(index+1); vis[i]=0; }} }int main(){ dfs(1); cout<

    推荐阅读


    上一篇：MPEG|MPEG LA发表声明支持MC-IF专利池培育流程

    下一篇：爱科宣布董事长兼首席执行官继任人选