首页 / 算法 / 斐波那契额数列--算法
斐波那契额数列--算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了斐波那契额数列--算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含8485字,纯文字阅读大概需要13分钟。
内容图文
![斐波那契额数列--算法](/upload/InfoBanner/zyjiaocheng/843/42318fccc1794c939bee3e2eb6ca35ce.jpg)
面试官问你斐波那契数列的时候不要高兴得太早
前言假如面试官让你编写求斐波那契数列的代码时,是不是心中暗喜?不就是递归么,早就会了。如果真这么想,那就危险了。
递归解法
递归,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。
斐波那契数列的计算表达式很简单:
F(n)?=?n;?n?=?0,1
F(n)?=?F(n-1)?+?F(n-2),n?>=?2;
因此,我们能很快根据表达式写出递归版的代码:
/*fibo.c*/
#include?<stdio.h>
#include?<stdlib.h>
/*求斐波那契数列递归版*/
unsigned?long?fibo(unsigned?long?int?n)
{
????if(n?<=?1)
????????return?n;
????else?
????????return?fibo(n-1)?+?fibo(n-2);
}
int?main(int?argc,char?*argv[])
{
????if(1?>=?argc)
????{
???????printf("usage:./fibo?num ");
???????return?-1;
????}
????unsigned?long??n?=?atoi(argv[1]);
????unsigned?long??fiboNum?=?fibo(n);
????printf("the?%lu?result?is?%lu ",n,fiboNum);
????return?0;
}
关键代码只有4行。简洁明了,一气呵成。
编译:
gcc?-o?fibo?fibo.c
运行计算第5个斐波那契数:
$?time?./fibo?5
the?5?result?is?5
real????0m0.001s
user????0m0.001s
sys????0m0.000s
看起来并没有什么不妥,运行时间也很短。
继续计算第50个斐波那契数列:
$?time?./fibo?50
the?50?result?is?12586269025
real????1m41.655s
user????1m41.524s
sys????0m0.076s
计算第50个斐波那契数的时候,竟然将近两多钟!
递归分析
为什么计算第50个的时候竟然需要1分多钟。我们仔细分析我们的递归算法,就会发现问题,当我们计算fibo(5)的时候,是下面这样的:
?????????????????????????|--F(1)
??????????????????|--F(2)|
???????????|--F(3)|??????|--F(0)
???????????|??????|
????|--F(4)|??????|--F(1)
????|??????|??????
????|??????|??????|--F(1)
????|??????|--F(2)|
????|?????????????|--F(0)
F(5)|?????????????
????|?????????????|--F(1)
????|??????|--F(2)|
????|??????|??????|--F(0)
????|--F(3)|
???????????|
???????????|--F(1)
为了计算fibo(5),需要计算fibo(3),fibo(4);而为了计算fibo(4),需要计算fibo(2),fibo(3)……最终为了得到fibo(5)的结果,fibo(0)被计算了3次,fibo(1)被计算了5次,fibo(2)被计算了2次。可以看到,它的计算次数几乎是指数级的!
因此,虽然递归算法简洁,但是在这个问题中,它的时间复杂度却是难以接受的。除此之外,递归函数调用的越来越深,它们在不断入栈却迟迟不出栈,空间需求越来越大,虽然访问速度高,但大小是有限的,最终可能导致栈溢出。
在linux中,我们可以通过下面的命令查看栈空间的软限制:
$?ulimit?-s
8192
可以看到,默认栈空间大小只有8M。一般来说,8M的栈空间对于一般程序完全足够。如果8M的栈空间不够使用,那么就需要重新审视你的代码设计了。
递归改进版
既然我们知道最初版本的递归存在大量的重复计算,那么我们完全可以考虑将已经计算的值保存起来,从而避免重复计算,该版本代码实现如下:
/*fibo0.c*/
#include?<stdio.h>
#include?<stdlib.h>
/*求斐波那契数列,避免重复计算版本*/
unsigned?long?fiboProcess(unsigned?long?*array,unsigned?long?n)
{
????if(n?<?2)
????????return?n;
????else
????{
????????/*递归保存值*/
????????array[n]?=?fiboProcess(array,n-1)?+?array[n-2];
????????return?array[n];
????}
}
unsigned?long??fibo(unsigned?long??n)
{
????if(n?<=?1)
????????return?n;
????unsigned?long?ret?=?0;
????/*申请数组用于保存已经计算过的内容*/
????unsigned?long?*array?=?(unsigned?long*)calloc(n+1,sizeof(unsigned?long));
????if(NULL?==?array)
????{
????????return?-1;
????}
????array[1]?=?1;
????ret?=?fiboProcess(array,n);
????free(array);
????array?=?NULL;
????return?ret;
}
/**main函数部分与fibo.c相同,这里省略*/
效率如何呢?
$?gcc?-o?fibo0?fibo0.c
$?time?./fibo0?50
the?50?result?is?12586269025
real????0m0.002s
user????0m0.000s
sys????0m0.002s
可见其效率还是不错的,时间复杂度为O(n)。但是特别注意的是,这种改进版的递归,虽然避免了重复计算,但是调用链仍然比较长。
迭代解法
既然递归法不够优雅,我们换一种方法。如果不用计算机计算,让你去算第n个斐波那契数,你会怎么做呢?我想最简单直接的方法应该是:知道第一个和第二个后,计算第三个;知道第二个和第三个后,计算第四个,以此类推。最终可以得到我们需要的结果。这种思路,没有冗余的计算。基于这个思路,我们的C语言实现如下:
/*fibo1.c*/
#include?<stdio.h>
#include?<stdlib.h>
/*求斐波那契数列迭代版*/
unsigned?long??fibo(unsigned?long??n)
{
????unsigned?long??preVal?=?1;
????unsigned?long??prePreVal?=?0;
????if(n?<=?2)
????????return?n;
????unsigned?long??loop?=?1;
????unsigned?long??returnVal?=?0;
????while(loop?<?n)
????{
????????returnVal?=?preVal?+prePreVal;
????????/*更新记录结果*/
????????prePreVal?=?preVal;
????????preVal?=?returnVal;
????????loop++;
????}
????return?returnVal;
}
/**main函数部分与fibo.c相同,这里省略*/
编译并计算第50个斐波那契数:
$?gcc?-o?fibo1?fibo1.c
$?time?./fibo1?50
the?50?result?is?12586269025
real????0m0.002s
user????0m0.000s
sys????0m0.002s
可以看到,计算第50个斐波那契数只需要0.002s!时间复杂度为O(n)。
尾递归解法
同样的思路,但是采用尾递归的方法来计算。要计算第n个斐波那契数,我们可以先计算第一个,第二个,如果未达到n,则继续递归计算,尾递归C语言实现如下:
/*fibo2.c*/
#include?<stdio.h>
#include?<stdlib.h>
/*求斐波那契数列尾递归版*/
unsigned?long?fiboProcess(unsigned?long?n,unsigned?long??prePreVal,unsigned?long??preVal,unsigned?long?begin)
{
????/*如果已经计算到我们需要计算的,则返回*/
????if(n?==?begin)
????????return?preVal+prePreVal;
????else
????{
????????begin++;
????????return?fiboProcess(n,preVal,prePreVal+preVal,begin);
????}
}
unsigned?long??fibo(unsigned?long??n)
{
????if(n?<=?1)
????????return?n;
????else?
????????return?fiboProcess(n,0,1,2);
}
/**main函数部分与fibo.c相同,这里省略*/
效率如何呢?
$?gcc?-o?fibo2?fibo2.c
$?time?./fibo2?50
the?50?result?is?12586269025
real????0m0.002s
user????0m0.001s
sys????0m0.002s
可见,其效率并不逊于迭代法。尾递归在函数返回之前的最后一个操作仍然是递归调用。尾递归的好处是,进入下一个函数之前,已经获得了当前函数的结果,因此不需要保留当前函数的环境,内存占用自然也是比最开始提到的递归要小。时间复杂度为O(n)。
矩阵快速幂解法
这是一种高效的解法,需要推导,对此不感兴趣的可直接看最终推导结果。下面的式子成立是显而易见的,不多做解释。
如果a为矩阵,等式同样成立,后面我们会用到它。
假设有矩阵2*2矩阵A,满足下面的等式:
可以得到矩阵A:
因此也就可以得到下面的矩阵等式:
再进行变换如下:
以此类推,得到:
实际上f(n)就是矩A^(n-1)中的A[0][0],或者是矩A^n中的A[0][1]。
那么现在的问题就归结为,如何求A^n,其中A为2*2的矩阵。根据我们最开始的公式,很容易就有思路,代码实现如下:
/*fibo3.c*/
#include?<stdio.h>
#include?<stdlib.h>
#include?<string.h>
#define?MAX_COL?2
#define?MAX_ROW?2
typedef?unsigned?long?MatrixType;
/*计算2*2矩阵乘法,这里没有写成通用形式,有兴趣的可以自己实现通用矩阵乘法*/
int?matrixDot(MatrixType?A[MAX_ROW][MAX_COL],MatrixType?B[MAX_ROW][MAX_COL],MatrixType?C[MAX_ROW][MAX_COL])
{
???/*C为返回结果,由于A可能和C相同,因此使用临时矩阵存储*/
????MatrixType?tempMa[MAX_ROW][MAX_COL]?;
????memset(tempMa,0,sizeof(tempMa));
????/*这里简便处理*/
????tempMa[0][0]?=?A[0][0]?*?B[0][0]?+?A[0][1]?*?B?[1][0];
????tempMa[0][1]?=?A[0][0]?*?B[0][1]?+?A[0][1]?*?B?[1][1];
????tempMa[1][0]?=?A[1][0]?*?B[0][0]?+?A[1][1]?*?B?[1][0];
????tempMa[1][1]?=?A[1][0]?*?B[0][1]?+?A[1][1]?*?B?[1][1];
????memcpy(C,tempMa,sizeof(tempMa));
????return?0;
}
MatrixType?fibo(int?n)
{
????if(n?<=?1)
????????return?n;
????MatrixType?result[][MAX_COL]?=?{1,0,0,1};
????MatrixType?A[][2]?=?{1,1,1,0};
????while?(n?>?0)?
????{
????????/*判断最后一位是否为1,即可知奇偶*/
????????if?(n&1)?
????????{
????????????matrixDot(result,A,result);
????????}
????????n?/=?2;
????????matrixDot(A,A,A);
????}
????return?result[0][1];
}
/**main函数部分与fibo.c相同,这里省略*/
该算法的关键部分在于对A^n的计算,它利用了我们开始提到的等式,对奇数和偶数分别处理。假设n为9,初始矩阵为INIT则计算过程如下:
9为奇数,则计算INIT*A,随后A变为A*A,n变为9/2,即为4
4为偶数,则结果仍为INIT*A,随后A变为,n变为4/2,即2
2为偶数,则结果仍未INIT*A,随后变A变为 ,n变为2/2,即1
1为奇数,则结果为INIT*(A^8)*A
可以看到,计算次数类似与二分查找次数,其时间复杂度为O(logn)。
运行试试看:
$?gcc?-o?fibo3?fibo3.c
$?time?./fibo3?50
the?50?result?is?12586269025
real????0m0.002s
user????0m0.002s
sys????0m0.000s
通项公式解法
斐波那契数列的通项公式为:
关于通项公式的求解,可以当成一道高考数列大题,有兴趣的可以尝试一下(提示:两次构造等比数列)。C语言代码实现如下:
/*fibo4.c*/
#include?<stdio.h>
#include?<stdlib.h>
#include?<math.h>
unsigned?long?fibo(unsigned?long?n)
{
????if(n?<=1?)
????????return?n;
????return?(unsigned?long)((pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n))/sqrt(5));
}
/**main函数部分与fibo.c相同,这里省略*/
来看一下效率:
$?gcc?-o?fibo4?fibo4.c?-lm
$?time?./fibo4
the?50?result?is?12586269025
real????0m0.002s
user????0m0.002s
sys????0m0.000s
计算第50个,速度还不错。
列表法
如果需要求解的斐波那契数列的第n个在有限范围内,那么完全可以将已知的斐波那契数列存储起来,在需要的时候读取即可,时间复杂度可以为O(1)。
斐波那契数列应用
关于斐波那契数列在实际中很常见,数学上也有很多奇特的性质,有兴趣的可在百科中查看。
总结
总结一下递归的优缺点:
优点:
实现简单
可读性好
缺点:
递归调用,占用空间大
递归太深,易发生栈溢出
可能存在重复计算
可以看到,对于求斐波那契数列的问题,使用一般的递归并不是一种很好的解法。
所以,当你使用递归方式实现一个功能之前,考虑一下使用递归带来的好处是否抵得上它的代价。
内容总结
以上是互联网集市为您收集整理的斐波那契额数列--算法全部内容,希望文章能够帮你解决斐波那契额数列--算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。