前不久接觸到藍(lán)橋杯勘畔，有一個(gè)藍(lán)橋杯組委會(huì)的老師來(lái)我們學(xué)校宣講，鼓勵(lì)我們參賽庆寺，雖然是大一诉字，但是對(duì)計(jì)算機(jī)編程很感興趣壤圃，還是報(bào)名了校賽選拔，又好運(yùn)氣的通過(guò)了校內(nèi)選拔踊挠。
上學(xué)期剛剛來(lái)到大學(xué)校園效床，都忙著玩了权谁。不知道你們是不是這樣旺芽。過(guò)年回去買了一本劉汝佳的算法競(jìng)賽。也沒(méi)有看多少〔烧拢現(xiàn)在開(kāi)學(xué)了悯舟，想到即將到來(lái)的藍(lán)橋杯省賽，心里一點(diǎn)底氣也沒(méi)有翩活，所以趕緊突擊一下吧便贵。
藍(lán)橋杯 入門訓(xùn)練 Fibonacci數(shù)列
問(wèn)題描述
Fibonacci數(shù)列的遞推公式為：Fn=Fn-1+Fn-2承璃，其中F1=F2=1。
當(dāng)n比較大時(shí)隘梨，F(xiàn)n也非常大舷嗡，現(xiàn)在我們想知道，F(xiàn)n除以10007的余數(shù)是多少捻脖。
輸入格式
輸入包含一個(gè)整數(shù)n中鼠。
輸出格式
輸出一行可婶，包含一個(gè)整數(shù)，表示Fn除以10007的余數(shù)援雇。
說(shuō)明：在本題中矛渴，答案是要求Fn除以10007的余數(shù)，因此我們只要能算出這個(gè)余數(shù)即可惫搏，而不需要先計(jì)算出Fn的準(zhǔn)確值具温，再將計(jì)算的結(jié)果除以10007取余數(shù)，直接計(jì)算余數(shù)往往比先算出原數(shù)再取余簡(jiǎn)單筐赔。
樣例輸入
10
樣例輸出
55
樣例輸入
22
樣例輸出
7704
數(shù)據(jù)規(guī)模與約定
1 <= n <= 1,000,000铣猩。
拿到題目一看，呀川陆！這貨上課的時(shí)候老師講過(guò)剂习，飛快的用遞歸搞定他较沪。
#include <stdio.h>
#include <stdlib.h>
int fun(int i){
long n=0;
if(i==1||i==2)
n=1;
else
n=fun(i-2)+fun(i-1);
return n;
}
int main(void){
div_t a;
int x;
scanf("%d",&x);
a = div(fun(x),10007);
printf("%d", a.rem);
return 0;
}
這里用到了一個(gè)C語(yǔ)言的一個(gè)庫(kù)函數(shù)div,其作用是對(duì)兩個(gè)數(shù)求商和求余鳞绕。
div_t (int number, int denom);/* div_t （“整數(shù)”類型 number，“整數(shù)”類型 denom）尸曼； */
簡(jiǎn)單測(cè)試后提交系統(tǒng)進(jìn)行核驗(yàn)们何，結(jié)果是運(yùn)行超時(shí)。果然是這樣控轿。畢竟是算法訓(xùn)練冤竹，這么簡(jiǎn)單就沒(méi)意義了拂封，然后看了看題目，好像的確需要按照人家的要求來(lái)寫鹦蠕，也沒(méi)有太多的思路冒签，就去問(wèn)了問(wèn)度娘，然后找到了一個(gè)資源
簡(jiǎn)短快捷钟病。
#include <stdio.h>
int main()
{
unsigned long s=0,f1=1,f2=1,f3=1,n=0;
scanf("%d",&n);
if(n>2)
for(s=3;s<=n;s++)
{
f3=(f2+f1)%10007;
f1=f2;
f2=f3;
}
printf("%d",f3);
return 0;
}
這個(gè)程序用了三個(gè)變量來(lái)處理數(shù)據(jù)萧恕，每一次循環(huán)都進(jìn)行取余，得到一個(gè)值肠阱，避免了遞歸壓棧耗時(shí)票唆。
總結(jié)
每一個(gè)看似簡(jiǎn)單的問(wèn)題背后都有難以解決的部分，要想取得進(jìn)步屹徘，就必須耐著性子走趋。今天學(xué)到了C語(yǔ)言的庫(kù)函數(shù)div,并且還有這樣的Fibonacci數(shù)列解決方法。
明天繼續(xù)加油Ｔ胍痢２净汀！
