1一个人上楼,他有两种走法,走一阶或走两阶,问他上30阶楼梯有几种走法

先介绍一种易于理解的方法。

设 f(x) 上x层楼的方法数，那么，显然

f(1) 1
f(2) 2

因为只有1层楼的话，只有一种方法可以走完，那就是直接走一阶；
只有2层楼的话，可以走两步一阶，或者走一步2阶，共两种走法；
本题就是求 f(30)。

考虑一般的 x (x > 3)：
假如你现在面对 x 层楼梯，你只有两种选择：

1. 要么走一阶，变成还剩 x-1 层，这种情况下剩下的楼层共有 f(x-1) 种走法。
2. 要么走两阶，变成 x-2 层，这种情况下剩下的楼层共有 f(x-2) 种走法。

所以对于一般的 x 层楼梯，你实际上有 f(x-1) + f(x-2) 种走法。

于是就得到了一个递推公式：

f(1) 1
f(2) 2
f(x) f(x-1) + f(x-2) (x > 3)

于是很容易推出：
f(3) f(2) + f(1) 2 + 1 3
f(4) f(3) + f(2) 3 + 2 5
f(5) 5 + 3 8
f(6) 8 + 5 13
f(7) 13 + 8 21
...

这样最终可以算出 f(30)。

这个方面思路上很简洁，但是做起来稍微比较麻烦，因为要一步一步递推出结果。这样如果要求 f(100000) 的话手算是不太现实的。顺便说一句这种方法学名叫做“动态规划”，经常用在计算机领域（因为电脑算 f(100000) 是很快的）。利用矩阵，还可以将计算量减小，f(100000)只需要算大概17次。

如果要手工算出 f(100000) 的值就需要把原来的递推公式变成一个通项公式（closed form），也就是只算一次就得到结果，具体方法是比较复杂的，而且针对楼主的题目推导出来的结论也很诡异。楼主可以去研究一下“生成函数”（Generating Functions），可用于解决这类问题。

另外实际上楼主这个题目就是一个 fibonacci 数列，这里有一些资料（包括求通项公式的方法）楼主可以参考一下：
ke.//112871.htm
google/search?hlzh-CN&qfibonacci

最后直接给出本题的通项公式：

f(x) 1/√5 * { [(1+√5)/2]^(x+1) - [(1-√5)/2]^(x+1) }

√5表示根号5（5的0.5次方）
[(1+√5)/2]^(x+1) 表示 [(1+√5)/2] 的 x+1 次方。

1阶楼梯1种走法，a(1)1,2阶楼梯2种走法，a(2)2,所以a(3)1+23,a(4)2+35,a(5)3+58,...,a(30)1346269.