recursion - 计算在 Towers of hanoi Lisp 中移动的磁盘数量

Question

我想统计磁盘的移动次数。但结果我得到了别的东西。

(setq x 0)

(defun towersOfHanoi (n from to help)
  (if (> n 0)
   ;progn evaluates multiple forms and returns the result from the last one.*/
   (progn
     (towersOfHanoi (- n 1) from help to)
     (format t "~d ----> ~d~%" from to)
     (towersOfHanoi (- n 1) help to from)
     (+ 1 x)
     )  

    ))



;(towersOfHanoi 3 'A 'B 'C)

当我运行它时，我得到了

(towersOfHanoi 3 'A 'B 'C)
A ----> B
A ----> C
B ----> C
A ----> B
C ----> A
C ----> B
A ----> B
1

为什么它是 1 而不是 7，我想每次递归调用都会将 x 的值重置为 0 但是，我如何才能获得磁盘的移动次数。谢谢。

Answer 1

在 lisp 中，if 最多接受三个参数；条件，当条件为真时评估的形式，以及当条件为假时评估的形式。

Selenium http://www.lispworks.com/documentation/HyperSpec/Body/s_if.htm了解详情。

为了在一个分支中评估多个表单，您可以使用 progn 评估多个表单并返回最后一个表单的结果。

此外，princ 期望只打印一个参数。为了一次打印几样东西，你可以使用format

在你的情况下(还要注意括号的位置):

(defun towersOfHanoi (n from to help)
 (if (> n 0)
   (progn
     (towersOfHanoi (1- n) from to help)
     (format t "~d ----> ~d~%" from to)
     (towersOfHanoi (1- n) help to from))))

没有 false 分支，你也可以使用 when 可以评估不止一种形式:

(defun towersOfHanoi (n from to help)
  (when (> n 0)
    (towersOfHanoi (1- n) from to help)
    (format t "~d ----> ~d~%" from to)
    (towersOfHanoi (1- n) help to from)))

为了对移动进行计数，您可以使用一个本地计数变量(由 let 引入)和一个更新此变量的内部工作函数(由 labels 引入)变量:

(defun towers-of-hanoi (n &optional (from 1) (to 2) (help 3))
  (let ((counter 0))                                          ; local variable
    (labels ((towers-of-hanoi-core (n from to help)           ; local function
               (when (> n 0)
                 (towers-of-hanoi-core (1- n) from to help)
                 (incf counter)                        
                 (format t "~d ----> ~d~%" from to)
                 (towers-of-hanoi-core (1- n) help to from))))
      (towers-of-hanoi-core n from to help))                  ; leave work to inner function
    (format t "Moves: ~d ~%" counter)))

在这里，from、to 和 help 也是可选的，默认为 1、2 和 3。

同样:细节可以在 Hyperspec 中找到:http://www.lispworks.com/documentation/HyperSpec/Front/