爬楼梯问题

题意: 有一楼梯共M级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第M级,共有多少种走法?

这个题目是经典的递归、递推问题。

这里先说说递归的思想吧。

我们令f(n)表示n步台阶的走法。那么要走到n步之前只有两种情况。一种是走到了n-1步台阶上,另一种是走到了n-2步台阶上。

于是我们有了方程: f(n) = f(n-1) + f(n-2)

这个时候我们只需要手算一下n=1有几种走法,显然一种。手算一下n=2有几种走法,显然两种。

(defun step-method (n)
    (if (= n 1)
        1
        (if (= n 2)
            2
            (+ (step-method (- n 1)) (step-method (- n 2))))))

(format t "~D~%" (step-method 10))