爬楼梯问题
来自某公司面试题，假设一个楼梯有 N 阶台阶，人每次最多可以跨 M 阶，求总共的爬楼梯方案数。例如楼梯总共有4个台阶，人每次最多跨2个台阶，则楼梯总共有这么几种走法：
{{1, 1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {2, 2}} 答案是
M-generalized Fibonacci number
http://oeis.org/A048887
的第$N$项。
更具体地，当$M=1$时，答案是
All 1's sequence
http://oeis.org/A000012
当$M=2$时，答案是
Fibonacci number
http://oeis.org/A000045
当$M=3$时，答案是
Tribonacci number
http://oeis.org/A000073
当$M=4$时，答案是
Tetranacci number
http://oeis.org/A000078
当$M=5$时，答案是
Pentanacci number
http://oeis.org/A001591
当$M=6$时，答案是
Hexanacci number
http://oeis.org/A001592
当$M=7$时，答案是
Heptanacci number
http://oeis.org/A066178
当$M=8$时，答案是
Octanacci number
http://oeis.org/A079262
…… 2# KeyTo9_Fans
:b: In Mathematica:
f[{n_, m_}] := Last@LinearRecurrence, 2^Range, n]; Join @@ Permutations /@Select,And @@ (# <= 3 & /@ #) &] 设刚好爬到K（1≤K≤N）阶梯有A(K)种不同爬法，按条件不难得出：
A(1)=1,a(2)=2,…,A(M)=2^(M1) 当1≤K≤M时
A(K)=A(K-1)+A(K-2)+…+A(K-M) 当M＜K时
通过上式不断迭代求出需要的A(M)，但若不用极强的大数计算器（或编程），当N很大时，很难正确求得正确结果。
下面想法找出一般计算公式求A(M)：
方法是由mathe得出的，参见：http://bbs.emath.ac.cn/thread-667-1-1.html
上面方程的特征方程为 x^M-x^(M-1)-…-x-1=0 (1)
解为 A(n)=C(1)*z(1)^n+C(2)*z(2)^n+…+C(M)*z(M)^n
其中C(i),i=1,…,t是常数，z(i),i=1,…,t是方程（1）的M个根。
仔细分析后可知，这M个根中有且只有1个根的模大于1(<2),不妨设为z(1)，其余根的模小于1，且|C(2)*z(2)^n+…+C(M)*z(M)^n|<0.5，故只要求出C(1)*z(1)^n。仔细推算后得：
C(1)*z(1)^n=(1-r)/(2N-(N+1)r)*r^n
其中r是特征方程（1）或x^(M+1)-2x^M+1=0的>1实根。
所以，刚好爬到N阶梯的不同爬法
A(N)= round{(1-r)/(2M-(M+1)r)*r^N } （2）
其中round(y)为最接近y的整数，即y四舍五入得到的整数。
计算公式（2）是严格精确的，实际计算可能的误差只是计算过程中产生的误差。
例如，M=4时，r≈1.9275619754829253
按（2）式很容易算得A(30)=201061985，A(45)= 3788394725871
经验算，这两个结果正确。 将M个递推式子换成M*M的转移矩阵，最终
= BM-1 *
而BM-1 可以用快速幂算法， 效率要比浮点数的幂要高些
http://bbs.emath.ac.cn/thread-4054-1-1.html 2# KeyTo9_Fans
Fibonacci ，
Tribonacci ，
Tetranacci ，
Pentanacci ，
Hexanacci ，
Heptanacci ，
Octanacci ，
再往后就是Fibonacci 9-step numbers.
:lol Join @@ Permutations /@Select,And @@ (# <= 3 & /@ #) &]
chyanog 发表于 2013-3-6 12:47
IntegerPartitions可有函数范围选项，不必人工使用Select函数Join @@ Permutations /@ IntegerPartitions]而且题目并不要求方案，只要方案数，计算长度之和可以了。Plus@@Length/@ Permutations /@ IntegerPartitions]避免列出具体的方案的计算方法应该更高效一些
Plus@@ Multinomial @@@ FrobeniusSolve, 10] 9# hujunhua
(⊙o⊙)…，没细看帮助，LinearRecurrence应该比FrobeniusSolve快点
页:
[1]
2