塔樓命名光盤

Question

對於一個任務，我有一個名爲光盤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*)) 

與代碼的問題顯然是移動磁盤功能，因爲它只是扔掉結果它被稱爲後。但我不確定我究竟能夠確定哪些全局變量是我應該推動並從中彈出的。我用一個大的列表來代替塔，並把樁作爲子列表，但我有同樣的問題來確定要修改的列表的哪一部分。任何幫助，將不勝感激。我覺得我處於一個完全死角。

Answer 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 

Answer 2

這裏的基本問題是，所有功能都在變量peg1 peg2和peg3的內容上運行，而不是通過變量本身運行。在peg-name函數中，我們最初有peg2和peg3都是equals和eq，因爲兩者都是NIL，所以這種賦予名稱的邏輯不起作用。同樣，推動和持久性有機污染物正在修改移動盤內from和to變量，但什麼都不做的全局列表。

您需要找到一種不同的方式來傳遞列表名稱。基本上是某種實際的數組或鍵 - 值映射，而不是硬編碼變量，所以你可以傳遞鍵來修改正確的列表。

你也可以考慮一個更純粹的功能性的解決方案，經過PEG及其內容（使用利弊，汽車和CDR而不是push和pop）在一起的名字。這將完全避免造成所有麻煩的可變賦值運算符。

Answer 3

「簡單」的解決方法是使用列表的向量作爲您的樁，然後傳遞您正在操縱的釘的索引。

這會讓你的MOVE盤功能類似：

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

修改的其餘部分應該是相當直接的與作爲基礎，我想。

Answer 4

首先，如果我們只是想生成運動序列，我們並不需要保持所有內部狀態;以下是無副作用：

(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 
    | 
    | 
    |█▄▂ 

過的全局變量傳播中