斐波那契数列问题 |
您所在的位置:网站首页 › 斐波那契数列上台阶 › 斐波那契数列问题 |
著名的Fibonnaci数列相关的问题经常在面试中遇到。要解决这种问题需要两步: 1,确定遇到的问题是斐波那契数列。这是解决问题的关键点。 斐波那契数列的特点是:数列的第一项为1,第二项为1,从数列的第3项开始,每一项都等于前两项之和: 1,1,2,3,5,8,13,21.... 2,解决这个数列问题。
下面用实例说明: 问题一 一个人上台阶,一次可以上一级台阶,也可以一次上两级台阶。问,上n级台阶有多少种走法? 解决思路 1,首先我们可以简单计算一下1~4级台阶的上法分别是: 一级台阶只有1种上法;两级台阶有2种上法;三级台阶有3种上法;四级台阶有5种上法。 看到这几项,我们已经可以往斐波那契数列怀疑了。但我们不可能计算出所有的数值,只能总结出一般规律,才能确定这到底是不是斐波那契数列。 2,所以一般性规律,就是上n级台阶的方法和n-1级台阶的方法之间的关联性。 再次思考上台阶的问题,可以得到一个显而易见的结论: 一个人要上到第n级,有两个选择: 上到n-2级台阶以后,一次跨两级来到第n级台阶。这里不再考虑两次跨一级来到n级台阶了,因为这种方法和下面到n-1级台阶的方法部分重合了。 上到n-1级台阶以后,一次跨一级来到第n级台阶。因此问题已经非常清楚:n级台阶的上法等于上n-2级台阶的方法总数+上n-1级台阶的上法总数。 毫无疑问这就是Fibonnaci数列。 3,确定是Fibonnaci数列后,要解决就非常简单了。如使用递归: public static long Fib1(int n){ if (n==1) return 1; if (n==2) return 2; return Fib1(n-1)+Fib1(n-2); } 而Fibonnaci数列的通项公式就是:F(n)=F(n-1)+F(n-2)。由此可以看到数列的通项公式和递归算法之间的直接联系。
问题二 现在延伸一下上面的问题 一个人上台阶,一次可以上一级台阶,也可以一次上两级台阶,也可以一次上三级台阶。问,上n级台阶有多少种走法? 显而易见这是Fibonnaci数列的变种,通项公式应该是: F(n)=F(n-1)+F(n-2)+F(n-3) 还是用递归解决。
|
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |