Question

小明爬楼梯

可爱的小明特别喜欢爬楼梯，他有的时候一次爬一个台阶，有的时候一次爬两个台阶，有的时候一次爬三个台阶。如果这个楼梯有36个台阶，小明一共有多少种爬法呢？

Answer 1

共有2082876103种，其实这是一道典型的递归编程题，与其说是数学题，不如说是属于计算机科学的范畴。

设f(n)表示n级台阶的爬法数目，则前几个f值可以穷举得f(1)=1，f(2)=2，f(3)=4。

n>=4后，有如下递归关系：f(n)=f(n-1)+f(n-2)+f(n-3)，因为把爬n级台阶的最后一步分类，则f(n-1)代表最后一步是爬1级的所有走法，f(n-2)代表最后一步是爬2级的所有走法，f(n-3)代表最后一步是爬3级的所有走法，因此关系式成立。

用计算机迭代，得36级台阶的爬法数目为f(36)=2082876103种。

Matlab语言程序：

f=zeros(1,36);
f(1)=1; f(2)=2; f(3)=4;
for i=4:36
f(i)=f(i-1)+f(i-2)+f(i-3);

end

f(36)

如果想求解析解，可以考虑特征方程x^3=x^2+x+1的根为X，Y，Z，则数列的通解为
f(n)=A*X^n+B*Y^n+C*Z^n，通过f(1)，f(2)，f(3)的值，可以求出待定系数A，B和C。不过看来是挺麻烦的，因为特征方程的解是一个无理实数，和两个共轭虚数。

Answer 2

1. 1*36
2. 2*18
3 3*12
4. （1+2）*12, 24的排列
5. （1+3）*9 18的排列
太多了，就是1个和2个的组合，也可以不一样多个，如1个的18个，9个2的组合

Answer 3

这题其实跟“斐波那契数列”很相似。我们采 用逆向思维去解这道题。 我们设一个函数f(x)=n,表示小明走x个台阶 有n种走法。 则f(1)=1,f(2)=2,f(3)=4(这个自己不难想到吧) 。 那么f(4)，即有4个台阶时，小明的走法总 数，可以这样分类， ①如果第一步走一个台阶，则剩下的台阶 有f(3)种走法。 ②如果第一步走两个台阶，则剩下的台阶 有f(2)种走法。 ③如果第一步走三个台阶，则剩下的台阶 有f(1)种走法。 所以 f(4)=f(1) f(2) f(3) f(5)=f(4) f(3) f(2) f(6)=f(5) f(4) f(3) …… f(36)=f(35) f(34) f(33) 自己算可以吗......

Answer 4

貌似有7种。。。 可能不太准确 勿怪

追问

不止7种的，上百种都不一定