Question

急!有一个楼梯共10级,若规定每次只能跨上一级或两级,要上这段楼梯,共有多少种不同的走法

有一个楼梯共10级,若规定每次只能跨上一级或两级,要上这段楼梯,共有多少种不同的走法

Answer 1

把10级台阶依次编号为 ABCDEFGHIJ
对于每一级台阶而言，都有“被跨过”和“被踩上”两种选择

设“被跨过”为0，“被踩上”为1

这里还有一个隐藏的限制条件：
若ABCDEFGHIJ中某一位为0，那么下一位必然是1
因此这个二进制数：ABCDEFGHIJ最多包含五个零

下面分类讨论：
1个零：相当于在11111111中插入"01"，
共有C(9,1)=9种

2个零：相当于在111111中插入两组"01"，
并且它们之间隔开或绑定均可，所以共有：
C(7,2)+C(7,1)=21+7=28种

3个零：相当于在1111中插入三组"01"，按上述方法可得：
C(5,3)+C(5,2)+C(5,1)=25种

4个零：考虑*01*01*01*01*在星号处插入两个1，有：
C(5,2)+C(5,1)=15种

5个零：只有一种：0101010101

综上：一共有：
9+28+25+15+1=78种不同走法

Answer 2

这是数学上非常有名的菲波纳奇数列
1 2 3 5 8 13 21 34 55 89 ...
菲波纳奇数列的第n项就是走n级楼梯的方法总数。
1级楼梯自然只有一种方法。
2级楼梯自然有两种方法。
...
n级楼梯时，你可以先走1步，下面还剩下n-1级楼梯
也可以先走2步，下面还剩下n-2级楼梯
所以n级楼梯的方法总数是n-1级楼梯的方法数加上n-2级
楼梯的方法数。（这是此方法和此数列的精华所在）
具体的讲就是
3级楼梯等于1级楼梯方法数加上2级楼梯方法数 1＋2＝3
4级楼梯等于2级楼梯方法数加上3级楼梯方法数 2＋3＝5
接下去 5级楼梯 3＋5＝8
6级楼梯 5＋8＝13
7级楼梯 8＋13＝21
8级楼梯 13+21=34
9级楼梯 21＋34＝55
10级楼梯 34＋55＝89