Башни Ханоя с именованными дисками - PullRequest
Новая
       2

Башни Ханоя с именованными дисками

2 голосов
/ 10 октября 2011

Для выполнения задания мне нужно создать Ханойские башни в 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 ]

1 голос
/ 17 октября 2011

Код легко восстановить. Но ваше решение - не лучший стиль, поскольку колышки являются глобальными переменными.

Основная путаница в вашем коде - между списками и переменными. Макросы, такие как 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
0 голосов
/ 18 ноября 2012

Во-первых, если мы просто хотим создать последовательность движения, нам не нужно сохранять какое-либо внутреннее состояние; следующее не имеет побочных эффектов: 

(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
  |
  |
  |█▄▂
0 голосов
/ 12 октября 2011

«Легкое» исправление - использовать вектор списков в качестве колышков, а затем передавать индекс колышка, которым вы манипулируете.

Это сделало бы вашу функцию MOVE-DISK чем-то вроде: 

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

Остальные модификации должны быть довольно простыми, я думаю, что в качестве основы.

0 голосов
/ 11 октября 2011

Основная проблема здесь заключается в том, что все функции работают над содержимым переменных peg1, peg2 и peg3, а не над самими переменными.В функции peg-name у нас изначально peg2 и peg3 равны и eq, так как оба равны NIL, поэтому такая логика для имен не работает.Аналогично, push и pops изменяют переменные from и to внутри move-disk, но ничего не делают для глобальных списков.

Вам нужно найти другой способ передачи имен списков.По сути, это некая карта фактических массивов или ключей-> значений вместо жестко закодированных переменных, так что вы можете передавать ключи для изменения правильных списков.

Можно также рассмотреть более чисто функциональное решение, которое передает имяколышек вместе с его содержимым (и использует cons, car и cdr вместо push и pop).Это полностью исключило бы непостоянные операторы присваивания, которые вызывают все проблемы.

...