学步园

题目：

        给你一个整数n，求出第n个斐波那契数的前四位。

        题意很明确，就是不会做，在网上百度的别人代码知道用斐波那契数列通项公式求的。

        通项公式为：

        对两边求log：log(an)=log(1/√5)+n*log((1+√5)/2)+log(1-((1-√5)/(1+√5))^n);

        第三项无限小，可以直接不要。剩下前两项，f=(1+√5)/2;

        log(an)=-0.5*log10(5.0)+((double)n)*log(f)/log(10.0);

        干掉log的整数部分，那部分是10的整数次幂对结果不影响，取小数部分后在用pow求出数值要前四位即可。

        注：小于四位的斐波那契数要单独处理。

        代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    int n,i,j,k,ff[50];
    ff[1]=1;ff[2]=1;
    for(i=3;i<30;i++)
        ff[i]=ff[i-1]+ff[i-2];
    //cout<<ff[4]<<endl;
    double d,f;
    f=(1+sqrt(5))/2;
    while(scanf("%d",&n)!=EOF)
    {
        if(n<21)
        {cout<<ff[n]<<endl;continue;}
        d=-0.5*log10(5.0)+((double)n)*log(f)/log(10.0);
        d = d - floor(d);
        d=pow(10,d);
        if(d<10000)
            printf("%d\n",(int)(d*1000));
        else
            cout<<(int)d<<endl;
    }
    return 0;
}