博客

一个数=几个数的和

  • Post author:
  • Post category:其他

斐波那契数据众所周知如下：

 

现在给出一个整数N，请找出N是否可以表示为几个斐波那契数的总和，这样总和不包含任何两个连续的斐波那契数。

输入

多个测试用例，第一行是一个整数T（T <= 10000），表示测试用例的数量。

每个测试用例都是一个整数N（1 <= N <= 109）的行。

产量

每箱一行。如果答案不存在，则输出“-1”（不含引号）。否则，您的答案应格式化为“N = f1 + f2 + … + fn”。N表示给定的数字，f1，f2，…，fn表示斐波那契数字，按升序排列。如果有多种方式，您可以输出它们中的任何一种。

 

示例输入

4
五
6
7
100

示例输出

5 = 5
6 = 1 + 5
7 = 2 + 5
100 = 3 + 8 + 89

这道题的题意也很简单，就是给你一个数，让你输出这个数字是用那些斐波那契数的和所组成的，N的范围到10^9，也就是第45个斐波那契数左右吧！
打表求得前45个斐波那契数，然后，然后不难发现这些数字的组合有一个规律，比如100，比他小的第一个斐波那契数是89，然后100-89=11，比11小的第一个斐波那契数是8，就这样，总会找出一些斐波那契数的和与原数相等，保存在数组中，输出～

#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”);

    }

}