ПРИМЕР ПРОГРАММИРОВАНИЯ НА ЛИСПЕ

 

Рассмотрим в качестве примера программирования на Лиспе менее элементарную классическую задачу, носящую название игры в «ханойские башни».

Игра состоит в следующем. Используются три вертикальных стержня А, В, С и набор N дисков разного диаметра с отверстием посередине (так что их можно надевать на стержни). В начальном положении все диски надеты на стержень А по порядку убывания диаметров: внизу самый большой, над ним - поменьше и т.д., а наверху - самый маленький. Целью является перенос всех дисков со стержня А на стержень В по следующим правилам:

1) за один раз можно перенести только один диск;

2) больший по размеру диск нельзя положить на меньший;

3) третий стержень С можно использовать как вспомогательный. Алгоритм решения задачи можно представить в виде трех следующих рекурсивных подзадач:

1) перенести со стержня А N-1 дисков на вспомогательный стержень С;

5) перенести нижний диск со стержня А на стержень В;

6) перенести со стержня С N-1 дисков на стержень В.

Программа состоит из трех последовательно определяемых функций «ханойские-башни», «перенос», «выведи» и имеет вид:

Программа 130

(defun ханойские-башни (высота)

(рrоgn (перенос "а "Ь "с высота) "готово))

ХАНОЙСКИЕ-БАШНИ

(defun перенос (из в вспомогательный n)

(cond

((= п 1) ; ветвь 2

(выведи из в) (t (перенос из ; ветвь1 вспомогательный

в

(- n 1))

(выведи из в)

(перенос вспомогательный ; ветвь 3

в

из

(- п 1)))))

ПЕРЕНОС

(defun выведи (из в)

(format t "~S -> ~S~%"из в))

ВЫВЕДИ

 

Вызов функции «ханойские башни» дает такое решение:

(ханойские-башни 3)

А->В

А->С

В->C

А->В

С->А

С->В

А->В

ГОТОВО

 

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

 








Дата добавления: 2015-10-13; просмотров: 586;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.