МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к лабораторным работам
по дисциплине «Функциональное и логическое программирование»
Лабораторная работа №1. Знакомство с основами логического программирования (Prolog)..... 1
Лабораторная работа №2. Поиск с возвратом и рекурсия (Prolog)................................................. 3
Лабораторная работа №3. Рекурсивные структуры данных (списки и деревья) (Prolog)............. 9
Лабораторная работа №4. Знакомство с основами функционального программирования (Lisp) 12
Лабораторная работа №1. Знакомство с основами логического программирования (Prolog)
Тема:
Знакомство с основами логического программирования.
Задание:
При отладке программы использовать возможности трассировки.
Используя предикаты parent(symbol,symbol), man(symbol), woman(symbol), married(symbol,symbol), записать факты, описывающие Вашу семью. Записать 8 правил вывода для любых родственных отношений в Вашей семье (например: мать, отец, сестра, брат, племянница, племянник, тетя, дядя, внучка, внук, бабушка, дедушка, двоюродная сестра, двоюродный брат и т.д.).
Содержание отчета:
- титульный лист;
- задание;
- описание родственных связей (в виде дерева);
- исходный текст;
- выводы по работе.
Методические указания:
Как правило, программа на Прологе состоит из двух программных секций: секции предикатов PREDICATES и секции предложений CLAUSES.
В секции PREDICATES описываются собственные предикаты. Описание предикатов заключается в их перечислении с указанием доменов (типов) их аргументов. Встроенные предикаты объявлять не требуется. Формат объявления предиката:
predicate_name(argument_domain_1, argument_domain_2, …, argument_domain_n)
В секции CLAUSES помещаются предложения – факты и правила, составляющие программу. Все предложения для одного предиката должны быть сгруппированы. Каждое предложение заканчивается точкой. Формат записи предложений:
fact(object_1, object_2, …, object_n).
rule(Var_1, Var_2, …,Var_m):–subgoal_1, subgoal_2, …, subgoal_k.
Пример программы на Прологе:
PREDICATES
bird(symbol)
parent(symbol,symbol)
CLAUSES
bird(sparrow). % Воробей – это птица.
bird(X):–parent(Y,X), bird(Y). % X – это птица, если у него есть родитель,
% который является птицей.
parent(sparrow,nestling). % Воробей – родитель птенца.
Для отладки программы можно использовать возможности трассировки. Трассировка позволяет в пошаговом режиме проследить процесс нахождения решения.
Для того чтобы включить трассировку, можно воспользоваться одним из двух способов:
- в первой строке программы поместить директиву trace;
- выбрать Trace из меню Options/Compiler Directives/Trace.
При работе в режиме трассировки вся текущая информация появляется в окне трассировки Trace. Для пошагового выполнения программы в режиме трассировки используется клавиша F10.
Сообщения в окне трассировки могут быть следующими:
- CALL – вывод имени предиката и значений его параметров;
- FAIL – вывод имени неудачно завершившегося предиката;
- REDO – вывод сообщения о том, произведен поиск с возвратом;
- RETURN – вывод имени удачно завершившегося предиката и значений его параметров (символ * показывает, что существуют другие решения).
Лабораторная работа №2. Поиск с возвратом и рекурсия (Prolog)
Тема:
Поиск с возвратом и рекурсия.
Задание:
При отладке программы использовать возможности трассировки.
Вариант 1
- Написать программу, реализующую телефонный справочник. В справочнике содержится следующая информация о каждом абоненте: имя и телефон. Реализовать вывод всей информации из справочника, поиск телефона по имени, поиск имени по телефону. Для удобства работы реализовать меню с соответствующими пунктами.
- Подсчитать, сколько раз встречается некоторая буква в строке. Строка и буква должны вводиться с клавиатуры. Для разделения строки на символы использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий разделять строку String на первый символ Char и остаток строки StringRest. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 2
- Написать программу, реализующую географический справочник. В справочнике содержится следующая информация: названия страны и площади страны, названия рек и длины рек, названия озер и глубины озер. Реализовать вывод всей информации из справочника, поиск по названию. Реализовать поиск по площади, длине или глубине, при этом должна быть возможность ввести некоторое пороговое значение (например, вывести названия всех рек, длина которых не менее 3000 км). Для удобства работы реализовать меню с соответствующими пунктами.
- Вычислить значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1,
f(n)=f(n-1)+f(n-2). Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 3
- Написать программу, реализующую словарь. В словаре содержится следующая информация: слово и его несколько переводов. Реализовать вывод всего словаря, перевод с русского на английский, с английского на русский. Для удобства работы реализовать меню с соответствующими пунктами.
- Вычислить произведение двух целых положительных чисел (используя суммирование). Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 4
- Написать программу, реализующую калькулятор на четыре арифметических действия (без скобок).
- Подсчитать, сколько раз встречается некоторое слово в строке. Строка и слово должны вводиться с клавиатуры. Для разделения строки на слова использовать стандартный предикат fronttoken (String, Lexeme, StringRest), позволяющий разделить строку String на первое слово Lexeme и остаток строки StringRest. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 5
- Написать программу, реализующую авиасправочник. В справочнике содержится следующая информация о каждом рейсе: номер рейса, пункт назначения, цена билета. Реализовать вывод всей информации из справочника, поиск пункта назначения по номеру рейса. Реализовать поиск по пункту назначения с указанием максимально возможной цены билета (должны быть выведены все рейсы, цена билета на которые ниже указанного значения) Для удобства работы реализовать меню с соответствующими пунктами.
- Поменять порядок следования букв в слове на противоположный. Для разделения строки на символы использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий разделять строку String на первый символ Char и остаток строки StringRest. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 6
- Написать программу для продажи театральных билетов. Должна быть представлена следующая информация: спектакль, свободные места, цена билета. Реализовать вывод всей информации о билетах, поиск билета по ряду. Реализовать поиск по цене с указанием максимально возможной цены (должна быть выведена информация о билетах, цены на которые ниже указанного значения). Для удобства работы реализовать меню с соответствующими пунктами.
- Вычислить сумму ряда целых нечетных чисел от 1 до n. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 7
- Написать программу, реализующую автомагазин. Должна быть представлена следующая информация о каждом автомобиле: модель, мощность двигателя, цвет, цена. Реализовать вывод всей информации по автомобилям, поиск по цвету. Реализовать поиск по мощности с указанием минимальной мощности (должна быть выведена информация обо всех моделях, мощность которых выше указанного значения). Для удобства работы реализовать меню с соответствующими пунктами.
- Поменять порядок следования слов в предложении на противоположный. Для разделения строки на слова использовать стандартный предикат fronttoken (String, Lexeme, StringRest), позволяющий разделить строку String на первое слово Lexeme и остаток строки StringRest. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 8
- Написать программу, реализующую книжный магазин. Должна быть представлена следующая информация: название книги, количество экземпляров, цена. Реализовать вывод всей информации о книгах, поиск книги по названию. Реализовать поиск по цене с указанием интервала возможной цены (должна быть выведена информация о книгах, цены которых попадают в указанный интервал). Для удобства работы реализовать меню с соответствующими пунктами.
- Вычислить сумму ряда целых четных чисел от 2 до n. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 9
- Написать программу для продажи туристических туров. Должна быть представлена следующая информация: название тура, страна, продолжительность, цена. Реализовать вывод информации обо всех турах, поиск тура по стране. Реализовать поиск по продолжительности с указанием интервала возможной продолжительности (должна быть выведена информация о турах, продолжительность которых попадает в указанный интервал). Для удобства работы реализовать меню с соответствующими пунктами.
- Организовать ввод целых положительных чисел и их суммирование до тех пор, пока сумма не превысит некоторого порогового значения. Введенные отрицательные целые числа суммироваться не должны. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 10
- Написать программу для заказа мест в отеле. Должна быть представлена следующая информация: название отеля, класс отеля, свободные места, цена номера. Реализовать вывод информации обо всех свободных номерах, поиск отеля по классу. Реализовать поиск по цене с указанием максимально возможной цены (должна быть выведена информация о номерах, цены на которые ниже указанного значения) Для удобства работы реализовать меню с соответствующими пунктами.
- Организовать ввод букв и их соединение в строку до тех пор, не будет введен символ #. Для присоединения символа к строке использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий присоединять символ Char к строке StringRest и получать строку String. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.