HDU 1568 Fibonacci

题解：首先，对于小于10000的斐波那契数，我们直接计算，当大于10000时，用公式，由于只要输出前四位，所以不用考虑浮点数的问题，算出其取log的结果：

tmp=(log(sq5/5)+n*log(0.5+sq5/2))/log(10.0)

然而为什么要取log呢，考虑这样的情况，若结果前四位为1493，那么计算的结果一定是log(10^n*1.493……)=log(1.493……)+n，那么只要减去整数部分，就得到log(1.493……)，

将结果加3，得到log(1.493……)+3=log(1493.……),然后计算一下10的幂后取整就是结果了。

#include <cstdio>

#include <cmath>

using namespace std;

int main(){

    int fib[100],fibs;

    fib[0]=0,fib[1]=1;

    for(fibs=2;fib[fibs-1]<10000;fibs++)fib[fibs]=fib[fibs-1]+fib[fibs-2];

    fibs-=2;

    int n;

    double sq5=sqrt(5);

    while(scanf("%d",&n)!=EOF){

        if(n<=fibs)printf("%d\n",fib[n]);

        else{

            double tmp=(log(sq5/5)+n*log(0.5+sq5/2))/log(10.0);

            tmp=tmp-int(tmp);

            printf("%d\n",(int)pow(10,tmp+3));

        }

    }

    return 0;

}

巴特西

HDU 1568 Fibonacci

最新文章

热门文章