首页 > 代码库 > 【剑指offer】斐波那契数列
【剑指offer】斐波那契数列
题目1描述:
写一个函数,输入n,求斐波那契数列的第n项。斐波那契数列的定义如下:
f(n) = 0 (n = 0); f(n) = 1 (n = 1); f(n) = f(n-1)+f(n-2) (n > 1);
分析描述:
在大多数的C语言教科书中,一般会用递归求斐波那契数列。代码如下:
long long Fibonacci(unsigned int n) { if(n <= 0) return 0; if(n <= 1) return 1; return Fibonacci(n-1)+ Fibonacci(n-2); }
递归方法的优点是代码清晰,但存在更严重的缺点即计算重复。在《数据结构与算法分析——C语言描述》的P9页里,介绍了递归的四条基本法则,其中的第4条就是”合法效益法则“,即在求解一个问题的同一实例时,切勿在不同的递归调用中做重复性的工作。此处就违背了这条规则。因此必须寻找别的办法,避免重复计算问题。
可以从下往上计算,首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)……依次类推就可以算出第n项了。
long long Fibonacci(unsigned n) { int result[2] = {0, 1}; if(n < 2) return result[n]; long long fibNMinusOne = 1; long long fibNMinusTwo = 0; long long fibN = 0; for(unsigned int i = 2; i <= n; ++i){ fibN = fibNMinusOne = fibNMinusTwo; fibNMinusTwo = fibNMinusOne; fibNMinusOne = fibN; } return fibN; }
该方法的时间复杂度为O(n)。
题目2描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析描述:
把n级台阶的跳法看成是n的函数,记为f(n)。当n>2时,第一次跳的时候就有两种不同的选择:一是第一次只跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);另外一种选择是第一次跳2级,此时跳法数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2)。因此n级台阶的不同跳法的总数f(n) = f(n-1) + f(n-2)。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。