Addition Chains ZOJ - 1937（深搜 迭代 剪枝）

本文主要是介绍Addition Chains ZOJ - 1937（深搜 迭代 剪枝），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Sample Input
5
7
12
15
77
0

Sample Output
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77
题意
给你一个n,找从 0 到 n 的最短序列，满足每一个 a[k] 都存在a[k]=a[i]+a[j]。且第一项目为1，最后一项为n。
思路
用深搜加迭代，注意剪枝。

#include<stdio.h>
using namespace std;
int n,f,a[110];
bool dfs(int aa,int bb)
{if(aa==f){if(a[aa-1]==n)return 1;return 0;}for(int i=0; i<=aa-1; i++)for(int j=i; j<=aa-1; j++){if(a[i]+a[j]>n)break;if(a[i]+a[j]>bb){a[aa]=a[i]+a[j];if(dfs(aa+1,a[aa]))return 1;}}return 0;
}
int main()
{int i;a[0]=1;while(scanf("%d",&n)&&n){for(i=1;; i++){f=i;if(dfs(1,1)){for(int j=0; j<=i-1; j++)printf("%d ",a[j]);printf("\n");break;}}}return 0;
}

这篇关于Addition Chains ZOJ - 1937（深搜 迭代 剪枝）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---