深度优先搜索 和问题 简单函数递归 “加 还是不加”

Foj 1106
题目：Sum of Factorials

代码：

#include<cstdio> #include<iostream> #include<stdlib.h> #include<string.h> int n; int store[11]={1,1,2,6,24,120,720,5040,40320,362880}; bool dfs(int i,int sum)//9个节点 每个节点两个状态 {if(i==10)return sum==n;//到底 if(dfs(i+1,sum))return true;//这个节点不加 找到 if(dfs(i+1,sum+store[i]))return true;//这个节点加 找到 return false;//都没找到 } int main() {while(scanf("%d",&n)!=EOF){if(n<0)break;if(n==0){printf("NO\n");continue;}bool t;t=dfs(0,0);if(t)printf("YES\n");else printf("NO\n");}return 0; }

“加或不加”核心部分

int store[11]={1,1,2,6,24,120,720,5040,40320,362880}; bool dfs(int i,int sum)//9个节点 每个节点两个状态 {if(i==10)return sum==n;//到底 if(dfs(i+1,sum))return true;//这个节点不加 找到 if(dfs(i+1,sum+store[i]))return true;//这个节点加 找到 return false;//都没找到 }

dfs一个比较方便的用处，即是可以判断这种类型的题目：部分和问题。
首先第一部分判断是否把所有的节点判断完毕，返回sum==n，如果找到了，返回True，没找到返回False。

第二部分表示：在当前这个节点上，选择不加上该节点所代表的数的值，得到想要的结果，返回True。

第三部分表示：在当前这个节点上，选择加上该节点所代表的数的值，得到想要的结果，返回True。

最后，如果在此时的这个节点，不管这个节点的状态如何，都不会找到想要的值，返回False。

转载于:https://www.cnblogs.com/qq952693358/p/5317597.html

总结

以上是生活随笔为你收集整理的深度优先搜索 和问题 简单函数递归 “加 还是不加”的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。