离散数学问题求解，一个人要登上n级台阶,如果他每步可以跨一级或两级,共有多少种方法?

Question

如题所述

Answer 1

设一级x步，2级y部；则x+2y=n,
1.:n为奇数2k-1 时，x为奇数，y=(n-x)/2, 只要从x+y =(n+x)/2步中选出x步走一阶，其余走2阶即可 ，有C((n+x)/2,x)种走法，令x=1,3,5,……，n, 再相加即得：
N=C(K,1)+C(K+1,3)+……+C(2k-1,2k-1）；
2.n为偶数2k时，x为偶数，同理，N=C(k,0)+C(K+1,2)+C(K+2,4)+……+C(2k,2k）；

Answer 2

可以根据走2步的不同情况分析，最少一个2步都不走，最多为5个。（也可以根据1步，但太多了。）
(1)一个2步都不走，为1种情况。
(2)走1个2步，总共步数为9，从9个中随便选1个为2步的。C91
(3)走2个2步，总共步数为8，从8个中随便选2个为2步的。C82
依次类推为C73,C64,C55。
所以总和就是 1+C91+C82+C73+C64+C55 = 89
（不排除计算错误，思路就是这样的）。

Answer 3

用递推关系求解
设共有f(n)种方法
则f(n)=f(n-1)+2f(n-2) n>=3
其中：f(1)=1 ； f(2)=2

Answer 4

利用递推法 f(n)=f(n-1)+f(n-2) f(0)=0,f(1)=1,f(2)=2,然后解递推方程就行。