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

时间:2024-07-01 21:06:38

Fibonacci

Time Limit: 2000MS Memory limit: 131072K

题目描述

Fibonacci numbers are well-known as follow:

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

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.

示例输入

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,就这样,总会找出一些斐波那契数的和与原数相等,保存在数组中,输出~
为什么每次比赛结束之后才会发现题目原来这么简单,山东省第七届ACM省赛------Fibonacci

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