一个楼梯有100级,一次可以爬一级或两级,爬完100级,有几种走法?

Question

一个楼梯有100级,一次可以爬一级或两级,爬完100级,有几种走法?

Answer 1

如果用n表示台阶的级数,a n表示某人走到第n级台阶时,所有可能不同的走法,容易得到：
① 当 n=1时,显然只要1种跨法,即a 1=1.
② 当 n=2时,可以一步一级跨,也可以一步跨二级上楼,因此,共有2种不同的
跨法,即a 2=2.
③ 当 n=3时,可以一步一级跨,也可以第一步跨一级,第二步跨二级或第一步跨二级,第二步跨一级上楼,因此,共有4种不同的跨法,即a 3=3.
④ 当 n=4时,分二种情况分别讨论跨法：
如果第一步跨一级台阶,那么还剩下三级台阶,由③可知有a3 =3（种）跨法.
如果第一步跨二级台阶,那么还剩下二级台阶,由②可知有a2 =2（种）跨法.
根据加法原理,有a 4= a2 +a3 =5.
类推：
a 5=a3+a4=3+5=8
a6=a4+a5=5+8=13
a7=a5+a6=21
a8=a6+a7=13+21=44
a100=a98+a99=429625986226725000000+695149448165036000000=1124775434391760000000