Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1156449), страница 21
Текст из файла (страница 21)
В качестве меток вершин используются буквенныеидентификаторы или целые числа.Поиск путей по карте дорогЗадана карта железнодорожных и шоссейных дорог междунесколькими городами, все дороги между городами являютсядвусторонними. Не для всех возможных пар рассматриваемых городовсуществует железнодорожная или шоссейная дорога между ними, в то жевремя между некоторыми городами возможно наличие обоих типов дорог.Известно, что дорожное сообщение позволяет добраться из произвольногогорода в любой другой город.Для двух заданных городов найти все связующие их пути без циклов,длина которых не более чем в полтора раза превышает минимальный подлине путь между указанными городами, и из этих путей выбрать путь сминимальным количеством пересадок с одного вида транспорта на другой.В качестве результата вывести найденный минимальный по длинепуть и путь с минимальным числом пересадок, указав в нём пересадки.Если таких путей несколько, то последовательно показать их все,упорядочив по длине пути.
Если такого пути не существует, предложитьлюбой другой приемлемый путь из одного города в другой.Карта дорог задана в виде помеченного связного мультиграфа,вершины которого соответствуют городам и помечены названиямигородов, а рёбра графа соответствуют дорогам между городами. Каждоеребро графа помечено меткой типа дороги (железнодорожная, шоссейная),а также целым числом – длиной дороги между соответствующимигородами.
Граф записан как список входящих в него рёбер, причём каждоеребро представлено четырёхэлементным списком, который включаетназвания городов, соединенных этим ребром (дорогой), а также метку типадороги и её длину (расстояние между городами).1106. Литература1.McCarthy J. Recursive functions of symbolic expressions and theircomputation by machine.
Communications of the ACM, 1960, Vol. 3,N 4, p. 184-195.2.McCarthy J. Lisp 1.5 Programmer's Manual. MIT Press, Cambridge,Massachusetts, 1963.3.Revised Report on the Algorithmic Language Scheme. Rees J.,Clinger W., (Eds). SIGPLAN Notices 21(12), December 1986.4.Steele, G.L. Common Lisp – the Language (Second Edition). DigitalPress, Hanover, Massachusetts, 1990.5.Common Lisp Hyper Spec –http://www.lispworks.com/documentation/HyperSpec/Front/index.htm6.Баррон Д.
Рекурсивные методы в программировании : Пер. с англ. –М: Мир, 1974.7.Йенсен К., Вирт Н. Паскаль. Руководство для пользователя иописание языка : Пер. с англ. – М: Финансы и статистика, 1982.8.Лавров С.С., Силагадзе Г.С. Автоматическая обработка данных.Язык лисп и его реализация. – М.: Наука, 1978.9.Маурер У. Введение в программирование на языке лисп: Пер. сангл. – М.: Мир, 1976.10.
Пильщиков В.Н. Язык Плэнер. – М: Наука, 1983.11. Пратт Т., Зелковиц М. Языки программирования: разработка иреализация: Пер. с англ. – СПб: Питер, 2002.12. Руководствопользователяhttp://www.codenet.ru/progr/alisp/поязыкуAutoLisp–13. Семенов М.Ю. Язык лисп для персональных ЭВМ. – М: Изд-воМоск. ун-та, 1989.14.
Филд А., Харрисон П. Функциональное программирование: Пер. сангл. – М.: Мир, 1993.15. Хендерсон П. Функциональное программирование. Применение иреализация: Пер. с англ. – М.: Мир, 1983.16. Хювёнен Э., Сеппянен Й. Мир Лиспа. Том 1. Введение в язык Лисп ифункциональное программирование: Пер. с англ. – М: Мир, 1990.111Приложение: Встроенные функции языка Лисп+ - * /< > <= >= = /=add1andappendapplyatomcaar … cddddrcarcdrcoerce (Common Lisp)condconsdefmacrodefundo, do*eqeqlequalevalevenpfirstfuncallfunction (Common Lisp)getgoiflengthletlet*listlistploadloopmapcarmaplist1920192225649188986119951510010204911209657080103962217911820881026666membernotnullnumberporpack(MuLisp)prin1princprintprogprog1prog2progNputquotereadread-charreduceremproprestreturnreversesetsetqsub1symbolpsymbol-functionsymbol-plistsymbol-valueterpriunpack (MuLisp)11224212021228788888710310210210281108485728191034110010019213232328887.