第19题:

题目:定义Fibonacci数列如下: 

 / 0 n=0

f(n)= 1 n=1

 \ f(n-1)+f(n-2) n=2

 

输入n，用最快的方法求该数列的第n项。

分析:在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。

因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。

 

留意最后一句话，说明不能用递归求值。我们打表，用递推将能存下的数保存在数组中，查询时间为O（1）

 

#include
     
      //fib[46]不会爆int，47就爆了int fib[50];void fun(){//打表    fib[0]=0;    fib[1]=1;    for(int i=2;i<47;i++)        fib[i]=fib[i-1]+fib[i-2];}int main(){    fun();    int n;    printf("请输入一个有意义的数(0~46)，ctrl+z结束输入\n");    while(~scanf("%d",&n)){        if(n>46) printf("计算数值超过int，请从新输入\n");        else if(n<0) printf("数值小于0，无意义，请从新输入\n");        else printf("fib[%d]=%d\n",n,fib[n]);        printf("请输入一个有意义的数(0~46)，ctrl+z结束输入\n");    }    return 0;}