AcWing 170. 加成序列
原题链接
简单
作者:
lqmm1
,
2021-12-05 21:45:27
,
所有人可见
,
阅读 371
/*
迭代加深其实是一种限制深度的搜索
当我们可以确定我们要找的答案深度不高而且一定有答案的时候我们可以用迭代加深
迭代加深的方式很简单
我们枚举限制的深度然后去搜索如果搜到了答案就结束没有得到那么就把深度扩大继续搜索
这样的搜索方式只会增加常数但是可以有效的防止时间复杂度指数级别爆炸
我们这题层数其实就是位数我们可以发现答案的位数一定很小所以这题我们可以用迭代加深来搜索
这题是要我们找一个序列
这个序列满足3个性质
递增的
首位是1末位是n
其次中间每位数都是前面两个值的相加
我们搜索一定是按位搜索
枚举每一位可以放的值放好然后跑到下一位
我们可以在每层开一个数组避免重复搜索一个值
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
using namespace std;
int ans[110];
int n;
bool dfs(int u,int depth)
{
if(u>depth)return false;
if(u==depth&&ans[u]==n)return true;
if(u==depth&&ans[u]!=n)return false;
int st[110]={0};
for(int i=1;i<=u;i++)
{
for(int j=1;j<=u;j++)
{
int t=ans[i]+ans[j];
if(st[t]||t>n||t<ans[u])continue;
st[t]=1;
ans[u+1]=t;
if(dfs(u+1,depth))return true;
}
}
return false;
}
int main()
{
while(cin>>n)
{
if(n==0)break;
ans[1]=1;
int depth=2;
if(n==1)
{
cout << 1<<endl;
continue;
}
while(!dfs(1,depth))depth++;
for(int i=1;i<=depth;i++)
cout << ans[i]<<" ";
cout << endl;
}
return 0;
}