2017年上海交大考研机试第三题 Fibonacci Representation
思路:1.运用了一个数学性质,即Fibonacci的前k项等于第k+2项减去2,发现不了这个性质,也可用循环将前k项求出来。
2.运用的大体思想是递归解法
构造出口条件:
1、刚好减得尽,则方法数多1
2、前面index项无论如何都不能等于大于当前数,则方法数为0
#include<cstdlib>
#include<string.h>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=110000000;
int F[maxn],n;
void Fibonacci(){//求Fibonacci数
F[1]=1,F[2]=2;
for(int i=3;i<maxn;i++){
F[i]=F[i-1]+F[i-2];
}
}
int dp(int n,int index){
if(n==0)return 1;//刚好减得尽,则方法数多一
if(F[index+2]-2<n)return 0;//前面几项全部加起来也无法等于n时,则方法数为0
for(int i=index;i>0;i--){
while(F[i]>n)i--;//当前的Fibonacci数大于n时,执行此操作
//分两种情况,一是不选择小于n的最大Fibonacci数,二是选择小于n的最大Fibonacci数
return dp(n,i-1)+dp(n-F[i],i-1);
}
}
int main(){
int i=maxn;
scanf("%d",&n);
Fibonacci();
for(i=0;i<maxn-1;i++){//寻找小于n的最大Fibonacci数
if(F[i]>n)break;
}
i--;
printf("%d\n",dp(n,i));
return 0;
}