Description
Fibonacci numbers are well-known as follow:
Now given an integer N, please find out whether N can be represented as the sum of several Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.
Input
Multiple test cases, the first line is an integer T (T<=10000), indicating the number of test cases.
Each test case is a line with an integer N (1<=N<=1000000000).
Output
One line per case. If the answer don’t exist, output “-1” (without quotes). Otherwise, your answer should be formatted as “N=f1+f2+…+fn”. N indicates the given number and f1, f2, … , fn indicating the Fibonacci numbers in ascending order. If there are multiple ways, you can output any of them.
Sample Input
4
5
6
7
100
Sample Output
5=5
6=1+5
7=2+5
100=3+8+89
Source
Unknown
#include <cstdio>
#include <iostream>
#include <cmath>
#include <
string>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
const int inf =
0x3f3f3f3f;
const int maxn =
1e6;
ll number[10000+
8], sum[
10000+
8];
int t;
ll n;
void init()
{
for(
int i =
1; i<
46; i++)
//虽然n<=1000000000，看起来数据很大，实际上在斐波那契数列里面，下标最大也不过是45而已
{
if(i ==
1)number[i] =
1;
else if(i ==
2)number[i] =
2;
else number[i] = number[i-
1]+number[i-
2];
}
}
int main()
{
while(~scanf(
"%d", &
t))
{
while(t--
)
{
init();
int miao =
0;
scanf("%d", &
n);
int ying = n, flag =
0;
for(
int i =
45; i>
0; i--
)
{
if(ying>=
number[i])
{
sum[miao++] =
number[i];
ying -=
number[i];
if(ying <=
0)
break;
}
}
printf("%d=", n);
for(
int i = miao-
1; i>=
0; i--
)
{
if(flag)printf(
"+");
flag =
1;
printf("%d", sum[i]);
}
printf("\n");
}
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/10549023.html
相关资源：JAVA上百实例源码以及开源项目
