0

我在编程课上的一项任务是“河内塔”，我使用的语言是 Common Lisp，源代码如下：

编码 ：

变量：

(defparameter *Source*      "Peg 1")
(defparameter *Spare*       "Peg 2")
(defparameter *Destination* "Peg 3")

我希望上面的变量声明在函数内部

(defun towers-of-hanoi (disks)

;disks accept list as parameter , for e.g `(s m l)

  (let ((tempPeg))
    (if (= (list-length disks) 1)
      (format t "Move ~{~A~} from ~A to ~A~%"
              (last disks) *Source* *Destination*) 
      (progn
        (setq tempPeg *Spare*)
        (setq *Spare* *Destination*)
        (setq *Destination* tempPeg) 

        (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1)))

        (setq tempPeg *Spare*)
        (setq *Spare* *Destination*)
        (setq *Destination* tempPeg)

        (format t "Move ~{~A~} from ~A to ~A~%"
                (last disks) *Source* *Destination*) 

        (setq tempPeg *Spare*)
        (setq *Spare* *Source*)
        (setq *Source* tempPeg)
        (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1)))
        (setq tempPeg *Spare*)
        (setq *Spare* *Source*)
        (setq *Source* tempPeg)
        (format t "")))))

问题：

1.）我正在使用递归算法来解决这个问题，正如我在这个算法中所知道的那样，3 个变量（Source、Spare 和 Destination）必须相互交换（通过一些规则）。如果我将defvar函数放在函数内部，即使我(setq tempPeg *Spare*) (setq *Spare* *Destination*) (setq *Destination* tempPeg)在再次调用 towers-of-hanoi 函数之前执行了这 3 个操作，但函数再次通过它的原始值重新定义了 3 个变量。

2.）我想知道的是，我是否可以将 3 个变量的声明放在函数内，并且仍然能够防止函数为每个调用的递归重新定义相同的变量？

P/S 分配只允许我定义一个函数头，它接受磁盘作为唯一的参数，但不接受 Source 、 Spare 和 Destination 棒。

4

2 回答 2

2

这里可能有两个不错的选择。首先是因为函数依赖于一些值，所以函数可以将它们作为参数。这可能是做你想做的事情的最清晰的方法，它使递归调用更清晰，因为你不需要在调用之前重新绑定或分配一堆变量。例如，这是一个简单的递归函数：

(defun swap-until-x-is-zero (x y)
  (print `(swap-until-zero ,x ,y))
  (unless (zerop x)
    (swap-until-x-is-zero (1- y) (1- x))))

CL-USER> (swap-until-x-is-zero 3 5)

(SWAP-UNTIL-ZERO 3 5) 
(SWAP-UNTIL-ZERO 4 2) 
(SWAP-UNTIL-ZERO 1 3) 
(SWAP-UNTIL-ZERO 2 0) 
(SWAP-UNTIL-ZERO -1 1) 
(SWAP-UNTIL-ZERO 0 -2) 
NIL

现在，如果应该从一些合理的默认值开始，那么可以将这些函数参数设为可选：

(defun swap-until-x-is-zero (&optional (x 3) (y 5))
  (print `(swap-until-zero ,x ,y))
  (unless (zerop x)
    (swap-until-x-is-zero (1- y) (1- x))))

然后你可以简单地调用(swap-until-x-is-zero)：

CL-USER> (swap-until-x-is-zero)

(SWAP-UNTIL-ZERO 3 5) 
(SWAP-UNTIL-ZERO 4 2) 
(SWAP-UNTIL-ZERO 1 3) 
(SWAP-UNTIL-ZERO 2 0) 
(SWAP-UNTIL-ZERO -1 1) 
(SWAP-UNTIL-ZERO 0 -2)

应该清楚如何将这种方法应用于河内问题；您只需将三个可选参数添加到hanoi并使用更改后的值递归调用它：

(defun towers-of-hanoi (disks &optional (source "Peg 1") (spare "Peg 2") (destination "Peg 3"))
  ...
  ;; instead of:
  ;;   (progn
  ;;     (setq tempPeg *Spare*)
  ;;     (setq *Spare* *Destination*)
  ;;     (setq *Destination* tempPeg) 
  ;;     (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1))))
  ;; we do:
  (let ((tempPeg spare))
    (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1))
                     source      ; stays the same
                     destination ; swap destination and spare
                     spare))     ; swap destination and spare
  ...)

也就是说，有时有足够的参数，更容易为它们使用特殊变量（即动态范围的变量）（尽管我不认为这是这种情况），并且要获得这些，您可以使用special声明：

(defun towers-of-hanoi (disks)
  (declare (special *source* *spare* *destination*))
  (let ((tempPeg))
    (if (= (list-length disks) 1)
        (format t "Move ~{~A~} from ~A to ~A~%" (last disks) *Source* *Destination*) 
        (progn
          (setq tempPeg *Spare*)
          (setq *Spare* *Destination*)
          (setq *Destination* tempPeg) 
          (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1)))
          ...))))

但是，您仍然必须建立变量的初始绑定，因此对于最外层的调用，您必须执行以下操作：

(defun hanoi-driver (disks)
  (let ((*source* "Peg 1")
        (*spare* "Peg 2")
        (*destination* "Peg 3"))
    (declare (special *source* *spare* *destination*))
    (hanoi disks)))

我认为简单地添加三个&optional变量hanoi最终是一个更清洁的解决方案，就个人而言。

于 2013-07-14T13:16:55.507 回答
1

您对列表的使用不是惯用的。记住 Lisp 中的列表是单链接的 cons 单元格。所有遍历列表或从列表末尾开始的操作都是低效的。

要回答您的问题：

(defun do-something (a)
   (let ((foo 42))                            ; binding
      (labels ((do-something-recursively (b)  ; local recursive function
                 (...)))
        (do-something-recursively a))))
于 2013-07-14T19:22:02.877 回答