题目一:写一个函数,输入n,求斐波拉契数列的第n项。

斐波拉契数列的定义如下:

      {                       n=;
f(n)={ n=;
{ f(n-)+f(n-) n>;

斐波拉契问题很明显我们会想到用递归来解决:

 long long Fibonacci(unsigned int n)
{
if(n==)
   return ;
if(n==)
return ; if(n>)
return Fibonacci(n-)+Fibonacci(n-);
}

这道题用递归解决思路很清晰,代码很简单,那么问题来了

根据马克思辩证主义思想,往往简单的思路会带来较大的

时间空间开销。在这种递归计算的过程中往往会计算很多

重复的项,比如计算f(6)时就需要计算f(5),f(4),计算f(5)时

会计算f(4),f(3)然而f(4)在之前计算f(6)的过程中就已经计算

过了。看似这不会带来很大的开销,但是我们这样想一想

斐波拉契中的每个数的计算都由两个数组成,然而这两个数

中就有一个是已重复计算了,相当于计算时间增加了1倍,效率

降低了一倍。

下面我们用非递归解法来解这道题:

 #include <iostream>
using namespace std; long Fibonacci(unsigned int n)
{
long int answer[]={,};
if(n<)
return answer[n]; long int nums2=;
long int nums1=;
long int ans=; for(int i=;i<=n;i++)
{
ans=nums2+nums1;
nums1=nums2;
nums2=ans;
}
return ans;
} int main()
{
unsigned int data;
cout<<"Input the n: ";
cin>>data; cout<<"The answer is: "<<Fibonacci(data)<<endl;
return ;
}

运行截图:

剑指offer-面试题9.斐波拉契数列-LMLPHP

当然剑指Offer一书还提到了另外两种方法:

1.由于在计算的时候有重复项,那么我们可以保存计算的中间项,当计算的时候如果找到

   已经计算的重复项则不必重复计算

2.另外一种方法是时间复杂度为logn的方法,这种方法具体可以参考剑指offer一书。

04-27 15:51