爱因斯坦楼梯从一楼到二楼有若干个台阶,可以一步跨一个台阶,也可以一步跨两个台阶,这样就有不同的上楼梯方法.比如,当台阶数为3时,就有3种上法.问当台阶数为8时,共有（）种上楼梯方法?

Question

爱因斯坦楼梯从一楼到二楼有若干个台阶,可以一步跨一个台阶,也可以一步跨两个台阶,这样就有不同的上楼梯方法.比如,当台阶数为3时,就有3种上法.问当台阶数为8时,共有（ ）种上楼梯方法?

Answer 1

这是一个斐波那契数列,
1、2、3、5、8、13、21、34
共有34种上法
理由：
设上n级台阶可能的步数为f(n)
上8级台阶步数为 f(8)
那么上8级台阶的最后一步有2种情况,从6步到8,或从7步到8
所以 f(6) + f(7) = f(8)
以此类推得 f(1) + f(2) =f(3)
f(2) +f(3)= f(4),
这时一个斐波那契数列,其步数如上所示