首页 > 代码库 > 剑指Offer之斐波那契数列
剑指Offer之斐波那契数列
斐波那契数列教科书都有,而且基本都会出现在递归那一节。但是并不是说递归就是斐波那契的最好解法,而是因为它能更好的诠释什么是递归。但是真正的软件开发并不会使用此种方法。递归有其最大的好处就是简洁,将大的问题转化为小的问题。在宏观上很好理解。但是递归的效率也是很值得探讨的。递归需要系统自己本身不停的压栈,保存中间量和状态,而且调用函数也是需要时间和空间的。因此效率上就出现了问题。而且每个进程所开的栈的容量都是有限制的,如果栈过大就会出现溢出的现象。比如n=5000,循环算法可以求出正确的值但是递归就会因此爆栈。除此之外还有一点就是重复性计算。递归的原理是将大问题转化为小问题,但是在转化为小问题的时候可能会出现重叠的情况,这就导致了效率的直线下降。
我们可以定义一个数组a[3]={0,1};a[0]=0;a[1]=1;当n>=2是进行循环:a[2]=a[0]+a[1];a[2]=a[1];a[1]=a[0];注意赋值的顺序。九度OJ 10MS。
#include <stdio.h> #include <iostream> using namespace std; long long Feibonacci(int n) { long long a[3]={0,1},i; if(n<=1) return a[n]; for(i=2;i<=n;i++) { a[2]=a[0]+a[1]; a[0]=a[1]; a[1]=a[2]; } return a[2]; } int main() { //freopen("/Users/sanyinchen/Workspaces/oc/conse/B_ali/B_ali/in.txt","r",stdin); int n; while(cin>>n) cout<<Feibonacci(n)<<endl; return 0; }
剑指Offer之斐波那契数列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。