Решение рекурсивных башен Ханоя в Лиспе - PullRequest
Новая
       25

Решение рекурсивных башен Ханоя в Лиспе

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

Мой код в lisp выглядит следующим образом: 

(defun solve-hanoi(from) (hanoi (length from) from '() '()))    

(defun hanoi(height from to aux) (when (>= height 1) 
                   (hanoi (- height 1) from aux to)
                   (format t "~%Move ~a from ~a to ~a" (nth 0 from) from to)
                   (push (pop from) to) 
                   (hanoi (- height 1) aux to from)))

Я новичок в Лиспе и понятия не имею, что я делаю неправильно. Помощь с этим будет высоко ценится, так как я был в этом в течение нескольких часов.

Спасибо.

1 Ответ

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

Рекурсивный алгоритм:

Чтобы переместить n дисков из колышка A в колышек C:
1. переместите n − 1 дисков от A до B. Это оставит диск n на колышке A
2. переместите диск n с A на C
3. переместите n − 1 дисков из B в C, чтобы они находились на диске n

(с http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution)

Так как значения A, B и C (ваши from, aux и to) относятся к текущей итерации и продолжают изменяться, легче не передавать состояние игры и пытаться понять, что это значит, а просто сгенерировать решающие инструкции.

Для реализации алгоритма, описанного выше, вам необходимо следующее внутри (when (>= height 1):
1. Рекурсивный вызов с n-1, меняя местами B и C. Вы уже правильно поняли это.
2. Распечатайте информацию о переезде, например (format t "~%Move ~a to ~a" from to).
3. Рекурсивный вызов с n-1, поменяв местами A и B. Вы тоже это правильно поняли.

Затем измените ваш (solve-hanoi) так, чтобы он принимал в качестве аргумента количество дисков на первом стержне, и вызывает (hanoi) с этим номером и любыми именами, которые вы хотите использовать для стержней, например (hanoi 4 'A 'B 'C) или (hanoi 4 1 2 3) на 4 диска.

...