题目背景
无
题目描述
已知任意一个正整数都可以拆分为若干个斐波纳契数，现在，让你求出n的拆分方法
输入输出格式
输入格式：一个数t，表示有t组数据
接下来t行，每行一个数n（如题）
输出格式：t行，每行一个字符串，表示拆分方法（格式:n=a1+a2+a3+..+an），要求从小到大输出
输入输出样例
输入样例#1：
input1:1
1
input2:1
10
输出样例#1：
output1:1=1
output2:10=2+8
说明
若有多组数据，以个数最小的为准，若仍有多组，输出右边尽量大的一组
对于100%的数据 t<=1000 1<=n<=10^9
小小DFS
1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #define LL long long 8 using namespace std; 9 int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 int T; 16 int n; 17 int a[50]; 18 bool DFS(int pos,int res,bool flag){ 19 if(res==n){return 1;} 20 if(!pos)return 0; 21 for(int i=pos;i;i--){ 22 if(res+a[i]>n)continue; 23 if(DFS(i-1,res+a[i],0)){ 24 if(flag)printf("%d\n",a[i]); 25 else printf("%d+",a[i]); 26 return 1; 27 } 28 } 29 return 0; 30 } 31 int main(){ 32 int i,j; 33 scanf("%d",&T); 34 a[1]=1;a[2]=1; 35 for(i=3;i<46;i++){ 36 a[i]=a[i-1]+a[i-2]; 37 // printf("%d\n",a[i]); 38 } 39 while(T--){ 40 scanf("%d",&n); 41 printf("%d=",n); 42 DFS(45,0,1); 43 } 44 return 0; 45 }