爬楼梯问题

chyanog

来自某公司面试题，假设一个楼梯有 N 阶台阶，人每次最多可以跨 M 阶，求总共的爬楼梯方案数。 例如楼梯总共有4个台阶，人每次最多跨2个台阶，则楼梯总共有这么几种走法： {{1, 1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {2, 2}}

KeyTo9_Fans

答案是 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 ……

chyanog

2# KeyTo9_Fans

chyanog

In Mathematica: f[{n_, m_}] := Last@LinearRecurrence[Array[1 &, m], 2^Range[0, m - 1], n];

chyanog

Join @@ Permutations /@ Select[IntegerPartitions[10], And @@ (# <= 3 & /@ #) &]

sheng_jianguo

设刚好爬到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 经验算，这两个结果正确。

wayne

将M个递推式子换成M*M的转移矩阵，最终 [A(n),A(n-1),...,A(n-M+1)] = B^M-1 * [A(M),A(M-1),..., A(1)] 而B^M-1 可以用快速幂算法， 效率要比浮点数的幂要高些 http://bbs.emath.ac.cn/thread-4054-1-1.html

wayne

2# KeyTo9_Fans Fibonacci ， Tribonacci ， Tetranacci ， Pentanacci ， Hexanacci ， Heptanacci ， Octanacci ， 再往后就是Fibonacci 9-step numbers.

hujunhua

Join @@ Permutations /@ Select, And @@ (# <= 3 & /@ #) &] chyanog 发表于 2013-3-6 12:47

IntegerPartitions可有函数范围选项，不必人工使用Select函数

1. Join @@ Permutations /@ IntegerPartitions[10, All, Range[3]]

复制代码

而且题目并不要求方案，只要方案数，计算长度之和可以了。

1. Plus@@Length/@ Permutations /@ IntegerPartitions[10, All, Range[3]]

复制代码

避免列出具体的方案的计算方法应该更高效一些

1. Plus@@ Multinomial @@@ FrobeniusSolve[Range[3], 10]

复制代码

chyanog

9# hujunhua (⊙o⊙)…，没细看帮助，LinearRecurrence应该比FrobeniusSolve快点