2017sjtu-Fibonacci Representation

思路参考：

链接

链接

斐波那契数的重要性质（可以观察得到）：

大体思路：

先用一个数组存储斐波那契数（注意数据范围到1e8），然后求出斐波那契数列中小于n的最大的斐波那契数

利用递归思想，进行深度优先搜索。

ans=取该最大数的可行方案+不取该最大数的可行方案

返回条件： 若n==0，则说明当前方案可行，方案数+1 若f[index+2]-2<n，则说明从1~index的所有斐波那契数的和均小于n，方案数为0；

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N=1e9+10;//数据可能达到1e8，因此开大一点
int f[80];


void Fabonacci()//求斐波那契数
{

   f[0]=1,f[1]=1,f[2]=2;
   for(int i=3;f[i-1]<N;i++)
        f[i]=f[i-1]+f[i-2];

    return ;

}

int dfs(int n,int index)
{
    if(n==0) return 1;//刚好减的尽，则方法数加1
    if(f[index+2]-2<n) return 0;//从1~index的所有斐波那契数的和都小于n，方法数为0


    for(int i=index;i>0;i--){
        while(f[i]>n) i--;//重新找到小于n的最大的斐波那契数的下标
        return dfs(n,i-1)+dfs(n-f[i],i-1);////分两种情况，一是不选择小于n的最大Fibonacci数，二是选择小于n的最大Fibonacci数

    }
}


int main()
{   int n;
    Fabonacci();
    while(cin>>n)
    {   //找到最大的小于等于n的斐波那契数，其在f数组中的下标为i
        int i=1;
        while(f[i]<=n) i++;
        i--;
        cout<<dfs(n,i)<<endl;
    }
    return 0;
}