小明非常喜歡 F i b o n a c c i Fibonacci Fibonacci數(shù)列，數(shù)列為 f 1 = 1 , f 2 = 2 , f n = f n ? 1 + f n ? 2 f_1=1,f_2=2,f_n=f_n{?}_1+f_n?_2 f1?=1,f2?=2,fn?=fn??1?+fn??2?。 小明想知道對于一個(gè)整數(shù) n n n，使得 n = f i + f j + f k n=f_i+f_j+f_k n=fi?+fj?+fk?的組合有多少種？ 比如 5 = 1 + 1 + 3 5=1+1+3 5=1+1+3 或者 5 = 1 + 2 + 2 5=1+2+2 5=1+2+2,有2種。注意 1 + 2 + 2 1+2+2 1+2+2 和 2 + 1 + 2 2+1+2 2+1+2 被認(rèn)為是同一種。
第一行是一個(gè)整數(shù)
1
≤
T
≤
1000
)
1≤T≤1000)
1≤T≤1000)，表示樣例的個(gè)數(shù)。
每個(gè)樣例是一個(gè)整數(shù)
n
(
3
≤
n
≤
109
)
n(3≤n≤109)
n(3≤n≤109)。
依次每行輸出一個(gè)樣例的結(jié)果，為一個(gè)整數(shù)。
樣例輸入2
3
5
1
2
重慶分公司
重慶分公司
// 基本思路：
// 1、先將斐波那契數(shù)列制表；
// 2、找出所有相加可以等于n的組合，將他們存入二維數(shù)組，然后排序
// 3、每次數(shù)組有新元素進(jìn)來都將它們與數(shù)組內(nèi)原有的進(jìn)行比較，發(fā)現(xiàn)有重復(fù)這組新元素就跳過，否則就cnt++
#includevoid sort(int num[]){//排序函數(shù)
int i, j;
for(i = 0; i< 2; i++){//選擇排序
for(j = i + 1; j<= 2; j++){if(num[i]< num[j]){int temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
}
int cmp(int a[], int b[]){//比較兩數(shù)組的函數(shù)
int i, flag = 0;
for(i = 0; i<= 2; i++){if (a[i] != b[i]) {flag = 1;
break;
}
}
return flag;
}
int main(){int T;
int n;
scanf("%d", &T);
while (T--){scanf("%d", &n);
int i, j, k, cnt = 0;
int t = 0, u;
int f[45] = {0}, s[1000][3] = {0};
f[1] = f[2] = 1;//這里我是從1開始的
for (i = 3; i< 45; i++){//斐波那契數(shù)列打表，只打到44是因?yàn)榈?4個(gè): 1134903170，第45個(gè): 1836311903，而題目要求n< 10 ^ 9
f[i] = f[i - 1] + f[i - 2];
}
for (i = 1; i< 45; i++){if (f[i] >n) break;
for (j = 1; j< 45; j++){for (k = 1; k< 45; k++){if (f[i] + f[j] + f[k] == n) {t++;
s[t][0] = f[i], s[t][1] = f[j], s[t][2] = f[k];//將f[i], f[j], f[k]存入數(shù)組
sort(s[t]);//排序
for(u = 1; u< t; u++){if (cmp(s[t], s[u]) == 0) goto next;//遇到和之前相同的就跳出
}
cnt++;
next: ;
}
}
}
}
printf("%d\n", cnt);
}
return 0;
} 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
