2

对于一项任务，我必须使用命名光盘在 Common LISP 中创建河内塔。我需要得到如下所示的输出：

[1]> (hanoi '(Small Medium Large))
Moved SMALL from Peg 1 to Peg 3
Moved MEDIUM from Peg 1 to Peg 2
Moved SMALL from Peg 3 to Peg 2
Moved LARGE from Peg 1 to Peg 3
Moved SMALL from Peg 2 to Peg 1
Moved MEDIUM from Peg 2 to Peg 3
Moved SMALL from Peg 1 to Peg 3
NIL
[2]> peg1
NIL
[3]> peg2
NIL
[4]> peg3
(Small Medium Large)

然而，当我运行我创建的程序时，我得到如下输出：

[1]> (hanoi '(Small Medium Large))
Move SMALL from Peg 1 to Peg 2
Move SMALL from Peg 1 to Peg 2
Move NIL from Peg 2 to Peg 2
Move SMALL from Peg 1 to Peg 2
Move NIL from Peg 2 to Peg 1
Move NIL from Peg 2 to Peg 2
Move SMALL from Peg 1 to Peg 2
NIL
[2]> peg1
(Small Medium Large)
[3]> peg2
NIL
[4]> peg3
NIL

这是我的代码：

(defvar *peg1* '())
(defvar *peg2* '())
(defvar *peg3* '())

(defun peg-name (peg)
     (cond ((equal peg *peg1*) "Peg 1")
     ((equal peg *peg2*) "Peg 2")
     ((equal peg *peg3*) "Peg 3")))

(defun move-disk (from to)
     (format t "Move ~a from ~a to ~a~%" (first from) (peg-name from) (peg-name to))
     (push (pop from) to))

(defun transfer (n source aux dest)
     (if (> n 0)
          (progn
          (transfer (1- n) source dest aux)
          (move-disk source dest)
          (transfer (1- n) aux source dest))))

(defun hanoi (disk-list)
     (setq *peg1* disk-list)
     (transfer (length disk-list) *peg1* *peg2* *peg3*))

代码的问题显然是 move-disk 函数，因为它只是在调用后丢弃结果。但我不确定我如何准确地确定我应该从哪些全局变量中推送和弹出。我一直在摆弄使用一个大列表来表示塔并将钉子作为子列表，但是我在确定要修改列表的哪一部分时遇到了同样的问题。任何帮助，将不胜感激。我觉得我完全处于死胡同。

4

4 回答 4

1

代码很容易修复。但是您的解决方案不是最好的样式，因为挂钩是全局变量。

代码中的主要混淆在于列表和变量之间。像 PUSH 和 POP 这样的宏在“位置”上工作，比如符号值、变量或对象的槽。直接使用列表不能按预期工作。

(defvar *peg1* '())
(defvar *peg2* '())
(defvar *peg3* '())

确保比较符号，而不是值。

(defun peg-name (peg)
  (cond ((equal peg '*peg1*) "Peg 1")
        ((equal peg '*peg2*) "Peg 2")
        ((equal peg '*peg3*) "Peg 3")))

由于我们传递符号，我们需要从符号的值中弹出和推送。

(defun move-disk (from to)
  (let ((disc (pop (symbol-value from))))
    (format t "Move ~a from ~a to ~a~%" disc (peg-name from) (peg-name to))
    (push disc (symbol-value to))))

(defun transfer (n source aux dest)
  (when (> n 0)
    (transfer (1- n) source dest aux)
    (move-disk source dest)
    (transfer (1- n) aux source dest)))

传递符号，而不是列表。重置其他钉子也很有用。

(defun hanoi (disk-list)
  (setq *peg1* disk-list)
  (setq *peg2* '())
  (setq *peg3* '())
  (transfer (length disk-list) '*peg1* '*peg2* '*peg3*))

测试：

CL-USER 15 > (hanoi '(Small Medium Large))
Move SMALL from Peg 1 to Peg 3
Move MEDIUM from Peg 1 to Peg 2
Move SMALL from Peg 3 to Peg 2
Move LARGE from Peg 1 to Peg 3
Move SMALL from Peg 2 to Peg 1
Move MEDIUM from Peg 2 to Peg 3
Move SMALL from Peg 1 to Peg 3
NIL

CL-USER 16 > *peg3*
(SMALL MEDIUM LARGE)

CL-USER 17 > *peg1*
NIL
于 2011-10-17T10:22:39.063 回答
0

这里的基本问题是所有函数都对变量 peg1、peg2 和 peg3 的内容进行操作，而不是对变量本身进行操作。在 peg-name 函数中，我们最初有 peg2 和 peg3 都是 equals 和 eq 因为两者都是 NIL，所以这种给名字的逻辑是行不通的。同样， push 和 pops 正在修改 move-disk 中的fromandto变量，但对全局列表没有任何作用。

您需要找到一种不同的方式来传递列表名称。基本上是某种实际的数组或键-> 值映射，而不是硬编码的变量，因此您可以传递键来修改正确的列表。

您还可以考虑一个更纯粹的功能解决方案，将 peg 的名称及其内容一起传递（并使用 cons、car 和 cdr 而不是 push 和 pop）。这将完全避免导致所有麻烦的可变赋值运算符。

于 2011-10-11T00:45:04.697 回答
0

“简单”的解决方法是使用列表向量作为您的挂钩，然后传递您正在操作的挂钩的索引。

这将使您的 MOVE-DISK 功能类似于：

(defun move-to (from to)
   (push (pop (aref *pegs* from)) (aref *pegs* to))

我认为，其余的修改应该非常简单，以此为基础。

于 2011-10-12T14:57:16.623 回答
0

首先，如果我们只想生成运动序列，我们不需要保留任何内部状态；以下是无副作用的：

(defun hanoi (disk-list)
  (labels ((transfer (i source aux dest)
             (when (< 0 i)
               (transfer (1- i) source dest aux)
               (move (1- i) source dest)
               (transfer (1- i) aux source dest)))
           (move (disk source dest)
             (format t "Move ~A from Peg ~A to Peg ~A~%"
                     (elt disk-list disk) source dest)))
    (transfer (length disk-list) 1 2 3)))

例子：

CL-USER> (hanoi '(small medium large))
Move SMALL from Peg 1 to Peg 3
Move MEDIUM from Peg 1 to Peg 2
Move SMALL from Peg 3 to Peg 2
Move LARGE from Peg 1 to Peg 3
Move SMALL from Peg 2 to Peg 1
Move MEDIUM from Peg 2 to Peg 3
Move SMALL from Peg 1 to Peg 3

其次，如果我们确实想跟踪状态变化，最好将状态保存在一个地方，而不是将其分散到许多全局变量中：

(defun hanoi* (disk-list)
  (let ((state (list disk-list nil nil)))
    (labels ((transfer (i source aux dest)
               (when (< 0 i)
                 (transfer (1- i) source dest aux)
                 (move (1- i) source dest)
                 (transfer (1- i) aux source dest)))
             (move (disk source dest)
               (format t "Move ~A from Peg ~A to Peg ~A~%"
                       (elt disk-list disk) (1+ source) (1+ dest))
               (push (pop (elt state source)) (elt state dest))
               (show state))
             (show (state)
               (format t "~{  |~{~A~}~%~}" (mapcar #'reverse state))))
      (show state)
      (transfer (length disk-list) 0 1 2))))

例子：

CL-USER> (hanoi* '(#\▂ #\▄ #\█))
  |█▄▂
  |
  |
Move ▂ from Peg 1 to Peg 3
  |█▄
  |
  |▂
Move ▄ from Peg 1 to Peg 2
  |█
  |▄
  |▂
Move ▂ from Peg 3 to Peg 2
  |█
  |▄▂
  |
Move █ from Peg 1 to Peg 3
  |
  |▄▂
  |█
Move ▂ from Peg 2 to Peg 1
  |▂
  |▄
  |█
Move ▄ from Peg 2 to Peg 3
  |▂
  |
  |█▄
Move ▂ from Peg 1 to Peg 3
  |
  |
  |█▄▂
于 2012-11-18T05:12:06.303 回答