hdu1568-Fibonacci

用到了斐波那契數列的通項公式。

先看對數的性質,loga(b^c)=c*loga(b),loga(b*c)=loga(b)+loga(c);
假設給出一個數10234432,那麼log10(10234432)=log10(1.0234432*10^7)=log10(1.0234432)+7;

log10(1.0234432)就是log10(10234432)的小數部分.

log10(1.0234432)=0.010063744
10^0.010063744=1.023443198
那麼要取幾位就很明顯了吧~
先取對數(對10取),然後得到結果的小數部分bit,pow(10.0,bit)以後如果答案還是<1000那麼就一直乘10。
注意偶先處理了0~20項是為了方便處理~

這題要利用到數列的公式:an=(1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n](n=1,2,3.....)

取完對數

log10(an)=-0.5*log10(5.0)+((double)n)*log(f)/log(10.0)+log10(1-((1-√5)/(1+√5))^n)其中f=(sqrt(5.0)+1.0)/2.0;
log10(1-((1-√5)/(1+√5))^n)->0
所以可以寫成log10(an)=-0.5*log10(5.0)+((double)n)*log(f)/log(10.0);
最後取其小數部分。

還用到了floor函數；

[1]floor(x),有時候也寫做Floor(x)，其功能是“向下取整”，或者說“向下捨入”，即取不大於x的最大整數(與“四捨五入”不同，下取整是直接去掉小數部分)，例如：
x=3.14，floor(x)=3
y=9.99999，floor(y)=9
[cpp] 
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<cmath>  
 
using namespace std; 
 
int fi[ 25 ] = { 0 , 1 , 1 } ; 
 
int main() 
{ 
    int n ; 
    for( int i = 3 ; i <= 25 ; ++i ) 
        fi[ i ] = fi[ i - 1] + fi[ i - 2 ] ; 
    while( cin >> n )  
    { 
        if( n < 21 ) 
        { 
            cout << fi[ n ] << endl ; 
            continue ; 
        } 
        else 
        { 
            double temp = -0.5 * log(5.0) / log( 10.0 )+ ((double )n ) * log((sqrt(5.0) + 1.0 ) /2.0 )/log(10.0) ; 
            temp -= floor( temp ) ; 
            temp = pow( 10.0 , temp ) ; 
            while( temp < 1000 ) 
                temp *= 10 ; 
            temp = (int)temp ; 
            cout << temp << endl ; 
        } 
    } 
    return 0 ; 
} 
         

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int fi[ 25 ] = { 0 , 1 , 1 } ;

int main()
{
 int n ;
 for( int i = 3 ; i <= 25 ; ++i )
  fi[ i ] = fi[ i - 1] + fi[ i - 2 ] ;
 while( cin >> n )
 {
  if( n < 21 )
  {
   cout << fi[ n ] << endl ;
   continue ;
  }
  else
  {
   double temp = -0.5 * log(5.0) / log( 10.0 )+ ((double )n ) * log((sqrt(5.0) + 1.0 ) /2.0 )/log(10.0) ;
   temp -= floor( temp ) ;
   temp = pow( 10.0 , temp ) ;
   while( temp < 1000 )
    temp *= 10 ;
   temp = (int)temp ;
   cout << temp << endl ;
  }
 }
 return 0 ;
}