HDU1568 Fibonacci

題目大意：

　　對(duì)于每一個(gè)輸入n(0<=n<=100000000),輸出斐波那契數(shù)列第n項(xiàng)的前4個(gè)數(shù)字。

思路：

　　附：因?yàn)椴┲鞅容^懶，本文章中幾張公式的圖片來(lái)自 以下博客;

　　PY:看到這道題，第一個(gè)想到的是這是一道入門(mén)OI的斐波那契數(shù)列第n項(xiàng)取模的水題，結(jié)果就順手打了一個(gè)程序結(jié)果發(fā)現(xiàn)樣例WA了，然后才發(fā)現(xiàn)是第n項(xiàng)的前4個(gè)數(shù)字。。

　　這是一道數(shù)學(xué)題！

　　首先，我們來(lái)推幾個(gè)結(jié)論。

　　結(jié)論一：

　　　　記f(n)為fibonacci數(shù)列第n項(xiàng)的值，

　　　　那么f(n) = ，這是通項(xiàng)公式，這里不給出證明。 附：對(duì)于本題，當(dāng)n = 0, f(0) = 0。

　　結(jié)論二：

　　　　對(duì)于正實(shí)數(shù)n，顯然n = a * 10^k ( a <= 10， k為整數(shù)) （即科學(xué)計(jì)數(shù)法）。

　　　　那么log₁₀( n ) = log₁₀( a * 10^k ) = log₁₀( a ) + k ^_，

　　　　因?yàn)?#xff0c;a <= 10， 所以，log₁₀( a ) < 1，又因?yàn)閗為整數(shù)，所以，log₁₀( a ) 為 log₁₀( a * 10^k ) 的小數(shù)部分。

　　　　所以log₁₀( a ) = log₁₀( a * 10^k ) - [ log₁₀( a * 10^k ) ] ? //[ ? ] 為向下取整

　　結(jié)論三：

　　　　因?yàn)?0^{log₁₀( a )} =? a，所以 a 的前4位有效數(shù)字即為a * 10^k的前4位。

　　

　　有了以上三個(gè)結(jié)論，我們可以開(kāi)始推式子了：

　　　　首先，為了簡(jiǎn)化運(yùn)算，我們對(duì)通項(xiàng)公式取對(duì)數(shù)，可以得到：

　　　　 ?觀察這個(gè)式子，我們會(huì)發(fā)現(xiàn)當(dāng)n比較大的時(shí)候，最后一項(xiàng)幾乎就是0，因?yàn)橹灰Y(jié)果的前4位，方便計(jì)算，我們暫時(shí)忽略這一項(xiàng)試試。

　　　　所以我們就得到了這個(gè)東西：。

　　　　對(duì)于log₁₀( f(n) )，我們令log₁₀( a ) = log₁₀( f(n) ) - [log₁₀( f(n) )]，通過(guò)結(jié)論二，我們可以發(fā)現(xiàn)log₁₀( a ) 就是 log₁₀( (f(n) ) 的小數(shù)部分。

　　　　接下來(lái)， 我們運(yùn)用結(jié)論三，令ans =?10^{log₁₀( a )?} ，如果精度足夠高，那么ans =a，其實(shí)說(shuō)白了就是利用小數(shù)的運(yùn)算使答案的末尾數(shù)字直接失去精度而消失，留下答案的前幾位。

　　　　這時(shí)候我們?cè)倩氐浇Y(jié)論二的開(kāi)頭，我們會(huì)發(fā)現(xiàn) f(n) = ans * 10^k，當(dāng)然，精度不夠，可是f(n)的前幾位都在ans中保留下來(lái)了。

　　　　此時(shí)輸出ans前4位有效數(shù)字就能夠得到答案。

?

?

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 int ans[25]; 8 int i,n,m; 9 const double BASE1 = (1.0+sqrt(5.0))/2; 10 double num1,num2; 11 int main(){ 12 ans[0]=0; 13 ans[1]=ans[2]=1; 14 for(i=3;i<=21;i++){ 15 ans[i]=(ans[i-1]+ans[i-2]); 16 } 17 while(scanf("%d",&m)==1){ 18 if(m<=20){ 19 printf("%d\n",ans[m]); 20 }else{ 21 num1=m*log10(BASE1); num2=log10(1/sqrt(5)); 22 num1=num1+num2; 23 num1=num1-floor(num1); 24 num1=pow(10,num1); 25 while(num1<1000) num1*=10; 26 printf("%d\n",(int)num1); 27 } 28 } 29 return 0; 30 }

?

?

?

?

?

?

　　　　

?

?

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/linxif2008/p/9539683.html

總結(jié)

以上是生活随笔為你收集整理的HDU1568 Fibonacci的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。