Fibonacci
Time Limit: 2000MS Memory limit: 131072K
题目描述
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.
输入
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<=109).
输出
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.
order. If there are multiple ways, you can output any of them.
示例输入
4
5
6
7
100
示例输出
5=5
6=1+5
7=2+5
100=3+8+89
来源
“浪潮杯”山东省第七届ACM大学生程序设计竞赛
题意
这道题的题意也很简单,就是给你一个数,让你输出这个数字是用那些斐波那契数的和所组成的,N的范围到10^9,也就是第45个斐波那契数左右吧!
打表求得前45个斐波那契数,然后,然后不难发现这些数字的组合有一个规律,比如100,比他小的第一个斐波那契数是89,然后100-89=11,比11小的第一个斐波那契数是8,就这样,总会找出一些斐波那契数的和与原数相等,保存在数组中,输出~
为什么每次比赛结束之后才会发现题目原来这么简单,
AC代码:
#include<stdio.h> #include<iostream> #include<math.h> #include<string.h> using namespace std; int a[46]= {1,1}; int b[46]; void init() { for(int i=2; i<46; i++) a[i]=a[i-1]+a[i-2]; } int find(int n) { for(int i=1; i<46; i++) if(a[i]>n)return a[i-1]; return 0; } int main() { init(); int N; cin>>N; while(N--) { int n; cin>>n; int s=0,j=0; memset(b,0,sizeof(b)); while(s!=n) { int d=find(n-s); b[j++]=d; s+=find(n-s); } printf("%d=%d",n,b[--j]); for(--j; j>=0; j--) printf("+%d",b[j]); printf("\n"); } }