xtu oj 1375 Fabonacci

题目描述

小明非常喜欢Fibonacci数列，数列为?f1=1,f2=2,fn=fn?1+fn?2。 小明想知道对于一个整数n，使得n=fi+fj+fk的组合有多少种？ 比如5=1+1+3?或者?5=1+2+2,有2种。注意?1+2+2?和?2+1+2?被认为是同一种。

输入

第一行是一个整数T(1≤T≤1000)，表示样例的个数。

每个样例是一个整数n(3≤n≤109)。

输出

依次每行输出一个样例的结果，为一个整数。

样例输入

2
3
5

样例输出

1
2

AC代码

#include<stdio.h>?
#define?N?100000
int?f[N]={};
void?init(){
????f[0]=1,f[1]=1;
????int?i;
????for(i=2;i<45;i++){
????????f[i]=f[i-1]+f[i-2];
????}
}
int?main(){
????int?T;
????scanf("%d",&T);
????init();
????while(T--){
????????int?i,j,k;
????????int?n,cnt=0;
????????scanf("%d",&n);
????????for(i=1;i<45;i++){
????????????for(j=i;j<45;j++){
????????????????for(k=j;k<45;k++){
????????????????????if(f[i]+f[j]+f[k]==n){
????????????????????????cnt++;
????????????????????}
????????????????}
????????????}
????????}
????????printf("%d\n",cnt);
????}
}