题目链接:http://poj.org/problem?id=2248
分析
当搜索树的分支随深度增大得很快的时候,最适合用迭代加深。
设置一个dep限制搜索深度,一旦到达dep立刻回溯。
dep逐渐增大,逼近答案。尽管每次都会重复搜索部分分支,因为最终的dep比较小,影响不大。
这题每多一层会多很多节点,但是答案的深度比较浅,很适合用迭代加深。
代码
#include <iostream>
using namespace std;
typedef long long ll;
#define maxn 2000006
#define fi first
#define se second
#define pb push_back
int n,dep;
int a[105];
bool dfs(int d)
{
if(d > dep)
{
if(a[dep] == n) return 1;
return 0;
}
bool vis[105] = {0};
for(int i=d-1;i>=1;i--)
{
for(int j=d-1;j>=1;j--)
{
if(a[i] + a[j] <= a[d - 1]) break;
if(a[i] + a[j] <= n && !vis[a[i] + a[j]])
{
a[d] = a[i] + a[j];
vis[a[d]] = 1;
if(dfs(d + 1)) return 1;
}
}
}
return 0;
}
int main()
{
int T = 1;
//scanf("%d",&T);
while(T--)
{
while(~scanf("%d",&n))
{
if(n == 0) break;
dep = 1;
a[1] = 1;
while(!dfs(2))
{
dep++;
}
for(int i=1;i<=dep;i++) printf("%d ",a[i]);
printf("\n");
}
}
return 0;
}