- 上台阶1.有N级台阶，每次可能上一级或二级。共有多少种上法？2.
- 1.有N级台阶，每次可能上一级或二级。共有多少种上法？
2. 有N级台阶，每次可能上1级or2级or3or4...orn级。共有多少种上法？
- 1.对上第k级阶梯，我们设有Ak种方法，并设A0=1
显然A1=1
对上第m+2级，我们知道可以从m+1级上一级达到，也可以从m级上两级达到
所以A(m+2)=A(m+1)+Am,其中A0=1,A1=1
2.同样的，由于第m级阶梯都可以有第0,1,2...,m-1级直接到达
所以Am=A0+A1+A2+...+A(m-1)
A0=1,A1=1
3.与第一题一样，对第k+m级阶梯，可由k,k+1,k+2,...k+m-1级到达
所以A(k+m)=Ak+A(k+1)+...+A(k+m-1)
对于不到m级的台阶p
与第二题一样，Ap=A0+A1+...+A(p-1)
现在对三种情况进行求解
第一个递推数列如真苗大侠所说其实是菲波那切数列(不过这里是A0=A1=1,而菲波那切数列A1=A2=1)
我们可以通过特征方程求解
A(m+2)=A(m+1)+Am
特征方程为x^2-x-1=0，两根x1,x2=(1±√5)/2(我们设x1为正，x2为负）
最终求得An=[(x1)^n-(x2)^n]/√5
对第二个数列
An=A0+A1+A2+...A(n-1)
A(n-1)=A0+A1+...+A(n-2)
两式相减，得An=2A(n-1)
则An为以2为公比，以1为首项的等比数列
所以An=2^(n-1)
对第三个数列
当n小于或等于m时
和第二题一样，An=2^(n-1)
即A0=1,A1=1,A2=2...Am=2^(m-1)
对n>m
An=A(n-m)+A(n-m+1)+...+A(n-1)
用特征方程
x^m-x^(m-1)-...-x-1=0
不过这个根我不会求.....