爬楼梯问题(专家级)假设有M阶梯
解答:
设刚好爬到K(1≤K≤M)阶梯有A(K)种不同爬法,按条件不难得出:
A(1)=1,a(2)=2,…,A(N)=2^(N-1) 当1≤K≤N时
A(K)=A(K-1)+A(K-2)+…+A(K-N) 当N<K时
通过上式不断迭代求出需要的A(M),但若不用编程或不采用大数计算器,很难正确求得正确结果。
下面想法找出一般计算公式求A(M):
上面方程的特征方程为 x^N-x^(N-1)-…-x-1=0 (1)
解为 A(n)=C(1)*z(1)^n+C(2)*z(2)^n+…+C(N)*z(N)^n
其中C(i),i=1,…,t是常数,z(i),i...全部
解答:
设刚好爬到K(1≤K≤M)阶梯有A(K)种不同爬法,按条件不难得出:
A(1)=1,a(2)=2,…,A(N)=2^(N-1) 当1≤K≤N时
A(K)=A(K-1)+A(K-2)+…+A(K-N) 当N<K时
通过上式不断迭代求出需要的A(M),但若不用编程或不采用大数计算器,很难正确求得正确结果。
下面想法找出一般计算公式求A(M):
上面方程的特征方程为 x^N-x^(N-1)-…-x-1=0 (1)
解为 A(n)=C(1)*z(1)^n+C(2)*z(2)^n+…+C(N)*z(N)^n
其中C(i),i=1,…,t是常数,z(i),i=1,…,t是方程(1)的N个根。
仔细分析后可知,这N个根中有且只有1个根的模大于1(1实根。
所以,刚好爬到M阶梯的不同爬法
A(M)= round{(1-r)/(2N-(N+1)r)*r^M } (2)
其中round(y)为最接近y的整数,即y四舍五入得到的整数。
计算公式(2)是严格精确的,实际计算可能的误差只是计算过程中产生的误差。
例如,N=4时,r≈1。9275619754829253
按(2)式很容易算得A(30)=201061985,A(45)= 3788394725871
经验算,这两个结果正确。
。收起