2

割り当てのために、私は名前付きディスクを使用してCommonLISPでハノイの塔を作成する必要があります。次のような出力を取得する必要があります。

[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*))

コードの問題は、呼び出された後に結果を破棄するだけなので、明らかにディスクの移動関数です。しかし、どのグローバル変数からプッシュおよびポップする必要があるかを正確に判断できるかどうかはわかりません。タワーを表すために大きなリストを使用し、ペグをサブリストにすることをいじりましたが、リストのどの部分を変更するかを決定するという同じ問題があります。どんな助けでもいただければ幸いです。完全に行き止まりになっているような気がします。

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が両方ともequalであり、両方ともNILであるため、名前を付けるこの種のロジックは機能しません。同様に、プッシュとポップはmove-disk内の変数fromとto変数を変更していますが、グローバルリストには何もしていません。

リスト名を渡す別の方法を見つける必要があります。基本的に、ハードコードされた変数の代わりに、ある種の実際の配列またはキー->値マップを使用して、キーを渡して正しいリストを変更できるようにします。

また、ペグの名前とその内容を渡す（プッシュとポップの代わりにcons、car、cdrを使用する）より純粋に機能的なソリューションを検討することもできます。これにより、すべての問題を引き起こしている可変代入演算子を完全に回避できます。

于 2011-10-11T00:45:04.697 に答える
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

第二に、状態の変化を追跡したい場合は、状態を多くのグローバル変数に分散させるのではなく、1 つの場所に保持する方がはるかに望ましいです。

(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 に答える
0

「簡単な」修正は、リストのベクトルをペグとして使用し、操作しているペグのインデックスを渡すことです。

これにより、MOVE-DISK 関数は次のようになります。

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

残りの変更は、それをベースにすれば簡単にできると思います。

于 2011-10-12T14:57:16.623 に答える