xtu oj 1375斐波纳契

题目描述
小明非常喜欢斐波纳契数列,数列为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
 

#include
int main(){
	int f[45]={1,1};
	int i;
	for(i=2;i<45;i++){
		f[i]=f[i-1]+f[i-2];
	}
	for(i=0;i<45;i++){//先写出一个斐波那契数列，在c++中斐波那契数列最多只能有47个，后面的数太大了 
		printf("%d ",f[i]);
	}
	long long num[100000]={0};//定义一个长数组 ，用来存储三个斐波那契额数列相加可能的值 
	int j,k;
	int cnt=0;
	for(i=1;i<45;i++){
		for(j=i;j<45;j++){
			for(k=j;k<45;k++){
				num[cnt]=f[i]+f[k]+f[j];//三个斐波那契数列相加可能的值存入num数组内 
				//printf("%lldn",num[cnt]);
				cnt++;
			}
		}
	}
	printf("%d",cnt);
	long long n;
	int t;
	int cnt1;
	scanf("%d",&t);
	while(t--){
		scanf("%lld",&n);
		cnt1=0;
		for(i=0;i 
思路：挺暴力的，就是把三个斐波那契数列所有可能的值都记录在一个数组之中，并且不是按照类似哈希散列一样，出现过为true，没出现就是false，而是通过cnt计数，因为，后面要判断的是数字有几种组合的形式，而不是能不能这样子组合