关于斐波那契数列的应用
我发现好多题目可以用斐波那契数列解决,但是不知道为什么,求高手解答一下,比如下面这道题:有一楼梯共M级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第M级,共有多少种走法? 这道题就是用斐波那契额数列。但是为什么呢,求讲解详细些,谢谢
设上到x级的方法有f(x)种。要上到x级可以从x - 1或者x - 2级迈上去,所以上到x级的方法是上到x - 1级与上到x - 2级的方法的和,所以f(x) = f(x - 1) + f(x - 2)。这不就是了么?初始条件,上到第1级只能从地面迈一步上去,所以f(1) = 1,上到第二级可以直接迈上去,也可以先上第一级再上去,所以f(2) = 2。
这里的基准面在地面,对于你的题目基准面在第一级台阶,减一就可以。