Question

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

Answer 1

http://zhidao.baidu.com/q?ct=24&cm=16&tn=ikusercenter#answer
1346269.
设Fn表示上n阶楼梯的方法数,F1=1,F2=2,则有
Fn=F(n-1)+F(n-2)
F(n-1)表示最后一步上一阶的方法数,F(n-2)表示最后一步上二阶的方法数,两者加起来恰是上n阶楼梯的方法数,规定了F0=1,数列恰是著名的Fibonacci数列,前几个Fibonacci数列为F0=1,F1=1,F2=2,F3=3,F4=5,F5=8,F6=13,F7=21,F8=34,
利用公式F(n+m)=F(n)*F(m)+F(n-1)*F(m-1)计算如下:
F(30)=F(15)*F(15)+F(14)*F(14)=(F(8)F(7)+F(7)F(6))^2+(F(7)F(7)+F(6)*F(6))^2=(34*21+21*13)^2+(21^2+13^2)^2=987^2+610^2=1346269
故上30阶楼梯有1346269种走法.