首页 > 代码库 > 洛谷P1755 斐波那契的拆分

洛谷P1755 斐波那契的拆分

2024-08-19 07:34:45   216人阅读

题目背景

无

题目描述

已知任意一个正整数都可以拆分为若干个斐波纳契数，现在，让你求出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 }

 

洛谷P1755 斐波那契的拆分


联系
我们