首页 > 代码库 > 构造数列 迭代加深dfs
构造数列 迭代加深dfs
[题目描述]
请构造一个尽量短的序列 A，长度为 len，一开始会给你一个正整数 n，
满足以下条件：
A[1]=1
A[len]=n
A[i]>A[i-1] （len>=i>=2）
A[x]=A[i]+A[j] （1<=i，j<x）
[输入文件]
此题有多组数据，每行一个正整数n，
输入以 0 结尾
[输出文件]
每行 len 个正整数，为A 序列
[输入样例1] [输出样例1]
4 1 2 4
0
[输入样例2] [输出样例2]
5 1 2 3 5
77 1 2 4 5 9 18 36 41 77
0
[数据范围]
30%： n<=10
100%： n<=100
100%： 数据组数不超过 10 组
首先说一下什么是迭代加深dfs。
迭代加深dfs其实就是确定搜索的深度，从而避免多余的搜索，节省时间。
然后再来分析这道题。
我们看了题，知道他要我们求的是最小深度，于是我们就可以想到，最快到达目标的方法无疑是每次加深度的时候，当前的数是之前一个数的两倍。
于是，我们就得到了每个要求的目标的最小深度，那就是log（n），然后我们只需要在最小深度之上往上搜。
得到大体的思想之后，我们就需要两个剪枝来优化dfs，然后这题就可以a了。
第一个剪枝：正常剪枝,如果que[x]>n, 那就不往下搜。
第二个剪枝：如果从当前往下一直用最大的数放入数列还达不到n，那也没必要往下搜了。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define ll long long #define il inline #define db double using namespace std; il int gi() { int x=0,y=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) y=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*y; } il ll gl() { ll x=0,y=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) y=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*y; } int n,depth; int num[45]; bool t; void dfs(int x) { // if(depth>7) //// return; // printf("x=%d t=%d depth=%d\n",x,t,depth); // for(int i=1;i<=depth;i++) // printf("%d ",num[i]); // printf("\n"); if(t) return; if(x-1==depth) { if(num[x-1]==n) t=1; return; } for(int i=1;i<x;i++) for(int j=i;j<x;j++) { if(num[i]+num[j]>num[x-1]&&num[i]+num[j]<=n) { int now=num[i]+num[j]; // printf("1=%d\n",now); for(int k=x;k<depth;k++) now*=2; // printf("2=%d\n",now); if(now<n) continue; num[x]=num[i]+num[j]; dfs(x+1); if(t) return; } } } int main() {while(scanf("%d",&n)) { if(!n) return 0; memset(num,0,sizeof(num)); num[1]=1; depth=1; int now=1; while(now<n) { depth++; now*=2; } // printf("depth=%d\n",depth); t=0; while(!t) { dfs(2); depth++; } depth--; printf("%d\n",depth); printf("%d",num[1]); for(int i=2;i<=depth;i++) printf(" %d",num[i]); printf("\n"); } }
构造数列 迭代加深dfs