山东省第七届ACM省赛------Fibonacci

山东省第七届ACM省赛------Fibonacci

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.

输入

Each test case is a line with an integer N (1<=N<=109).

输出

示例输入

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#include#include#includeusing 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"); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。