XTU OJ 1375 Fibonacci 題目描述

小明非常喜歡 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?。 小明想知道對(duì)于一個(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)為是同一種。

創(chuàng)新互聯(lián)是一家從事企業(yè)網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、行業(yè)門(mén)戶網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)制作的專(zhuān)業(yè)網(wǎng)站建設(shè)公司，擁有經(jīng)驗(yàn)豐富的網(wǎng)站建設(shè)工程師和網(wǎng)頁(yè)設(shè)計(jì)人員，具備各種規(guī)模與類(lèi)型網(wǎng)站建設(shè)的實(shí)力，在網(wǎng)站建設(shè)領(lǐng)域樹(shù)立了自己獨(dú)特的設(shè)計(jì)風(fēng)格。自公司成立以來(lái)曾獨(dú)立設(shè)計(jì)制作的站點(diǎ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

題解：換了一個(gè)思路來(lái)寫(xiě)，思路就都寫(xiě)在代碼注釋里了

// 基本思路：
// 1、先將斐波那契數(shù)列制表；
// 2、找出所有相加可以等于n的組合，將他們存入二維數(shù)組，然后排序
// 3、每次數(shù)組有新元素進(jìn)來(lái)都將它們與數(shù)組內(nèi)原有的進(jìn)行比較，發(fā)現(xiàn)有重復(fù)這組新元素就跳過(guò)，否則就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開(kāi)始的
        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ù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)標(biāo)題：XTUOJ1375Fibonacci-創(chuàng)新互聯(lián)
URL鏈接：http://jinyejixie.com/article12/djeddc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、營(yíng)銷(xiāo)型網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、關(guān)鍵詞優(yōu)化、自適應(yīng)網(wǎng)站、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)