ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
ПРИМЕР ПРОГРАММИРОВАНИЯ НА ЛИСПЕ
Рассмотрим в качестве примера программирования на Лиспе менее элементарную классическую задачу, носящую название игры в «ханойские башни». Игра состоит в следующем. Используются три вертикальных стержня А, В, С и набор 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 А->В С->А С->В А->В ГОТОВО
Можно убедиться, что определенная нами функция дает правильное решение для произвольного числа дисков, однако время решения задачи с увеличением числа дисков быстро возрастает.
СВОЙСТВА СИМВОЛОВ
В Лиспе могут быть определены, так называемые, свойства символов. Список свойств имеет вид:
(имя_свойства1 значение1 имя_свойства2 значение2... имя_свойстваN значениеN).
Присваивание нового свойства или изменение значения существующего осуществляется с помощью функции PUTPROP (или просто PUT):
(PUTPROP символ свойство значение).
Выяснить значение свойства, связанного с символом, можно с помощью функции GET:
(GET символ свойство).
С использованием этой функции можно также присваивать свойства символам:
(SETF (GET символ свойство) значение).
Свойства символов глобальны Эта конструкция языка Лисп полезна во многих типичных случаях представления данных, в том числе семантических сетей, фреймов и объектов объектно-ориентированного программирования.
Контрольные вопросы и задания 1. В чем состоит основная идея функционального программирования? 2. Что называется символом в программировании на Лиспе? 3. Что такое атомы в программах на Лиспе? 4. Что такое список? 5. Охарактеризуйте примитивные функции языка Лисп. 6. Как можно связать с символом некоторое значение? Как поместить значение в ячейку памяти? 7. Приведите примеры 1-выражений в Лиспе. 8. Как можно определить функцию и дать ей имя для последующих вызовов в Лиспе? 9. Охарактеризуйте управляющие формы в Лиспе. 10. Какую роль играет в функциональном программировании рекурсия? 11. Запишите рекурсивные определения функции проверяющую наличие в списке некоторого заданного элемента, подсчитывающую число элементов в списке, соединяющую два списка (с использованием точечной нотации).
Не нашли, что искали? Воспользуйтесь поиском:
|