К выполнению лабораторных работ

по дисциплине «Логической и функциональное программирование»

для студентов направления подготовки бакалавров 231000.62 - «Программная инженерия» по профилю «Разработка программно-информационных систем».

Махачкала 2013

УДК 681.3.04

Методические указания к выполнению лабораторных работ по дисциплине «Логическое и функциональное программирование» для студентов, обучающихся по направлению подготовки бакалавров 231000.62 – «Программная инженерия» и профилю «Разработка программно-информационных систем».- Махачкала: ДГТУ, 2013г. - 32с.

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

Составители: Абидова М.Ш., ст.преп. кафедры ПОВТиАС.

Рецензенты: д.т.н., зав.лаборатории информационных технологий в энергетике ФГБУН «Института проблем

геотермии ДНЦ РАН» Д.Н.Кобзаренко

д.т.н., профессор

зав кафедрой ВТ В.Б.Мелехин

Печатается согласно постановлению Ученого совета Дагестанского государственного технического университета.

от ___________________2013г.

Лабораторная работа №1

Общий обзор языка ПРОЛОГ. Основные механизмы языка ПРОЛОГ.

Цель работы. Знакомство с основами логического программирования. Изучение структуры программы, написанной на языке ПРОЛОГ. Изучение основных правил и конструкций языка ПРОЛОГ.

Краткие теоретические сведения.

Для загрузки системы ПРОЛОГ необходимо запустить на выполнение программу

Prolog.exe

Экран делится на 4 части:

1. Editor – окно-редактор для ввода текста программы.

2. Dialog – окно для ведения диалога с написанной программой.

3. Message – окно для вывода сообщений об ошибках.

4. Trace – окно для пошагового выполнения программы.

Верхняя строка окна редактора содержит информацию о высвечиваемом в этом окне файле. Line 1 и Col 1 свидетельствуют о том, что курсор в настоящий момент располагается в первой позиции первой строки. Надпись Indent сигнализирует о том, что включен режим автоматического выравнивания строк, а надпись Insert — о том, что задан режим вставки. WORK.PRO является заданным по умолчанию именем рабочего файла; .PRO есть заданное по умолчанию расширение для файлов, содержащих программы на Турбо-Прологе.

Главное меню системы ПРОЛОГ высвечивает 7 доступных пользователю опций (команд) в верхней части экрана. Для задания команды из любого пункта меню достаточно нажать первую букву ее названия.

Команды определяются 6 функциями системы ПРОЛОГ:

1. Работа с файлами ( Files ).

2. Редактирование текста программы ( Edit ).

3. Запуск программы на счет ( Run ).

4. Трансляция программы ( Compile ).

5. Заданий опций компилятора ( Options ).

6. Настройка системы в соответствии с индивидуальными потребностями ( Setup ).

Как правило, программа на Прологе состоит из двух программных секций: секции предикатов Predicates и секции предложений Clauses.

Predicates

…

Clauses

Pr1.

…

Prn.

В разделе Predicates описываются все предикаты Р1, …, Рn, которые используются в программе. Описание предикатов заключается в их перечислении с указанием доменов (типов) их аргументов. Встроенные предикаты объявлять не требуется. Формат объявления предиката:

predicate_name(argument_domain_1, argument_domain_2, …, argument_domain_n)

Предикат является одноместным, если зависит от одного элемента, двуместным – от двух элементов.

В разделе Clauses Pr1, …, Prn описываются все отношения между элементами согласно определенным предикатам.Здесь помещаются предложения – факты и правила, составляющие программу. Все предложения для одного предиката должны быть сгруппированы. Каждое предложение заканчивается точкой. Формат записи предложений:

1. fact(object_1, object_2, …, object_n).

2. rule(Var_1, Var_2, …, Var_m): –subgoal_1, subgoal_2, …, subgoal_k.

Например,

1. parents(tom, ted).

2. kids(Y, X): -parents(X, Y). (kids(Y, X) if parents(X, Y).)

Первое предложение объявляет факт наличия отношения родитель между объектами tom и ted. Второе предложение можно прочитать следующим образом:

для всех X и Y,

если X – родитель Y, то Y – ребенок X.

Пользователь может задавать ПРОЛОГ – системе вопросы, касающиеся отношений, определенных в программе. В предложениях могут встречаться такие операции, как конъюнкция и дизъюнкция ( ‘, ’ и ’; ’ ).

Для отладки программы можно использовать возможности трассировки. Трассировка позволяет в пошаговом режиме проследить процесс нахождения решения. При работе в режиме трассировки вся текущая информация появляется в окне трассировки Trace.

Для того, чтобы включить трассировку, можно воспользоваться одним из двух способов:

1. в первой строке программы поместить директиву trace(далее [F10]);

· выбрать Trace из меню Options/Compiler Directives/Trace.

Сообщения в окне трассировки могут быть следующими:

1. CALL – вывод имени предиката и значений его параметров;

2. FAIL – вывод имени неудачно завершившегося предиката;

3. REDO – вывод сообщения о том, произведен поиск с возвратом;

4. RETURN – вывод имени удачно завершившегося предиката и значений его параметров (символ * показывает, что существуют другие решения).

Примеры программы на Прологе:

Пример 1. Известно, что Лене нравится теннис, Денису нравится футбол, Борису – бейсбол, Эдику – плавание, Марку нравится теннис, а Фёдору то, что нравится Борису. Записать факты на Прологе и ответить на вопросы: 1)Кому нравится теннис? 2) Что нравится Федору? 3)Кто занимается одинаковыми видами спорта?

База знаний «Предпочтения»

Predicates

likes(symbol, symbol)

Clauses

likes(lenа, tennis).

likes(denis, football).

likes(boris, baseball).

likes(edic, swimming).

likes(mark, tennis).

likes(fedor, Activity): - likes(boris, Activity).

/* Activity играет роль переменной*/

Запросы

1)? likes(X, tennis)

Ответ:

X= lenа

X= mark

2)? likes(fedor, X)

Ответ:

X= baseball

3)? likes(X, T), likes(Y, T)

Ответ:

X= lenа Y= mark T= tennis

X= mark Y= lenа T= tennis

X= boris Y= fedor T= baseball

X= fedor Y= boris T= baseball

Пример 2. Лена, Анна, Денис и Борис-люди, лада и нисан - автомобили, Лене нравится лада, Анне - пицца, Денису - футбол, а Борис - Мерседес, Ваське - рыбка. Пицца, лада, мерседес продаются. Человек может купить машину, если она продается, и она ему нравится. Сформулировать на прологе вопросы: 1)Какую машину может купить Лена? 2) Кто-нибудь может купить мерседес? 3) какие машины продаются, и ответить на них.

База знаний «Предпочтения и возможности»

Domains

s=symbol

Predicates

human(s)

car(s)

likes(s, s)

can_by(s, s)

cells(s)

Clauses

human( lena ).

human( anna ).

human( denis ).

human( boris ).

car( lada ).

car( nissan ).

likes( lena, lada ).

likes( anna, pizza ).

likes( denis, football ).

likes( boris, mersedes ).

likes( vasya, ribka ).

cells(pizza).

cells(lada).

cells(mersedes).

can_by(X, Y): -human(X), car(Y), likes(X, Y), cells(Y).

Запросы:

1) can_by(lena, X)

X=lada

2) can_by(_, mersedes)

3) car(X), cells(X)

X=lada

Лабораторное задание.

Во время лабораторного занятия студент должен:

1. Изучить возможности программной оболочки системы ПРОЛОГ.

2. Разработать программу на языке ПРОЛОГ, используя способы представления данных в виде фактов и правил вывода.

3. Используя возможности, предоставляемые программной оболочкой, проверить правильность работы созданной программы (при отладке программы использовать возможности трассировки).

4. Оценить полученные результаты.

5. Оформить результаты работы программы.

Содержание отчета.

1. Название лабораторной работы.

2. Цель работы.

3. Номер варианта.

4. Задание.

5. Описание родственных связей (в виде дерева).

6. Исходный текст программы (все строки программы пронумеровать).

7. Указать результаты пошаговой трассировки (информация находится в окне Trace) в виде:

< тип сообщения>: < имя предиката> (< значения> ) < номер строки, где находится этот предикат>

8. Выводы по работе. Оформить диалог пользователя с системой ПРОЛОГ в виде:

Goal: < цель>

< решение>.

Варианты заданий.

1. Том является родителем Тэри и Мэри. Боб является родителем Тома. Том является Тиму братом. Используя предикаты parent(symbol, symbol), brother(symbol, symbol), woman(symbol), wife(symbol, symbol) и добавляя по необходимости новые предикаты и предложения, записать правила вывода для следующих отношений:

· как зовут детей Тома,

· является ли Тэри и Мэри сестрами,

· являются ли Мэри и Тэри потомками Боба (использовать отношение внук),

· чьим дядей является Тим,

· кто приходится матерью Тэри и Мери,

· всякий, кто имеет ребенка – счастлив,

· всякий, кто имеет ребенка, у которого есть сестра, имеет двух детей.

Одно родственное отношение студент должен придумать сам.

2. Пам и Том являются родителями Боба. Том является родителем Лиз. Боб является родителем Пат и Энн. Пат является родителем Джима. Используя предикаты parent(symbol, symbol), woman(symbol), kids(symbol, symbol) и добавляя по необходимости новые предикаты и предложения, записать правила вывода для следующих отношений:

· кто родитель Энн,

· является ли Джим далеким потомком Тома,

· кому Пам приходится матерью, кому – бабушкой,

· являются ли Джим и Лиз кровными родственниками,

· укажите всех предков Джима,

· являются ли Боб и Лиз родственниками,

· имеет ли Джим тетю (определить через отношение сестра).

Одно родственное отношение студент должен придумать сам.

3. Рэни является потомком Тэда. Джим является потомком Лиз. Тэд и Лиз являются потомками Сэма. Рэни и Джим являются родителями Пам и Энн соответственно. Стэн является мужем Пам. Бэн является потомком Стэна и Пам. Используя предикаты parent(symbol, symbol), child(symbol, symbol), husband(symbol, symbol) и добавляя по необходимости новые предикаты и предложения, записать правила вывода для следующих отношений:

· укажите всех прямых потомков Сэма,

· являются ли Стэн и Джим кровными родственниками,

· всякий, кто имеет обоих родителей – счастлив,

· укажите всех внуков Лиз,

· является ли Энн внучатой племянницей Теда,

· кто и кому приходится племянником и племянницей,

· всякий, кто имеет родителя, у которого есть сестра, имеет тетю.

4. Дана база данных “Теремок”:

живет (муха, горюха), живет(комар, пискун), живет(мышка, погрызуха), живет(лягушка, квакушка), живет(заюнок, кривоног),

живет( лиса, краса), живет(волк, хватыш), не_живет(медведь, пригнетыш).

Указать ответы на следующие вопросы:

? -живет(мышка, погрызуха).? -живет(волк, X).

? -живет(Х, кривоног).? -не_живет(М, P).

Сформулировать вопросы на Прологе: Живет ли лягушка в теремке? Какое прозвище у лисы? Кто имеет прозвище горюха? Какой следует задать вопрос, чтобы узнать обитателей теремка (без прозвищ)?

5. База данных “Рождение и хобби друзей”:

рождение(иванова, лена, 22, июнь, 1971), рождение(петров, сергей, 25, октябрь, 1973), рождение(сидорова, оля, 1, декабрь, 1974), любит(иванова, лена, книги), любит(иванова, лена, танцы), любит(петров, сергей, видео), любит(сидорова, оля, кино).

Сформулировать вопросы на Прологе: Кто родился в 1971 году? Кто родился в октябре? Кто любит книги? Кто любит и книги и танцы?

6. База данных “Колобок”: ушел(колобок, дедушка), ушел(колобок, бабушка), ушел(колобок, заяц), ушел(колобок, волк), ушел(колобок, медведь), не_ушел(колобок, лиса).

Сформулировать вопросы на Прологе: Кто ушел от волка? Кто не ушел от лисы? Кто ушел от волка и от бабушки? Какой следует задать вопрос, чтобы узнать всех персонажей сказки?

7. База данных “Распорядок дня”:

занятие(0, 7, сон), занятие(7, 8, завтрак), занятие(8, 13, школа), занятие(13, 14, обед), занятие(14, 19, свобода), занятие(19, 20, ужин), занятие(20, 23, отдых), занятие(23, 24, сон).

Сформулировать вопросы на Прологе: Когда бывает обед? Что бывает между 14 и 19 часами? Когда бывает сон? (сколько будет решений? )

8. Построить базу данных “Важнейшие события Древнего Мира” на основе установленных фактов, произошедших с 31 по 6 век до нашей эры.

Каждый факт приводить в виде событие(Х, Y, Z), где X — название государства, где произошло событие, Y - в каком веке произошло событие, Z — какое произошло событие.

В 31-м веке до нашей эры возникли первые города-государства. Единое государство в Египте образовалось в 30 веке до нашей эры. В 27 веке до нашей эры в Индии появились первые древнейшие города, а в Египте построена пирамида Хеопса. Первые греческие государства появились в 18 веке до нашей эры. В этом же веке в Египте произошло крупное восстание бедняков и рабов. В 15 веке до нашей эры появились первые государства в Китае. Тутмос III правил в Египте в 15 веке до нашей эры. Греция вела троянскую войну в 13 веке до нашей эры. Вторжение борийских племен в Грецию произошло в 11 веке до нашей эры. В 8 веке до нашей эры был основан город Рим. Олимпийские игры стали проводиться в Греции в 8 веке до нашей эры. В 6 веке до нашей эры в Риме была установлена республика, а в Греции произошли реформы Солона. В этом же веке персы взяли Вавилон в Междуречье и завоевали Египет.

1. Составить 3 запроса к этой базе данных.

2. Какие события произошли в период с 15 до 7 в. до н.э.

9. В таблице даны некоторые характеристики движения планет Солнечной системы(числовые величины округлены):

Таблица 6.

Характеристики движения планет солнечной системы

Планета	Расстояние до Солнца (у.е.)	Период обращения	Средние солнечные сутки
Меркурий		88 суток	176 суток
Венера		225 суток	117 суток
Земля		365 суток	24 часа
Марс		687 суток	25 часов
Юпитер		12 лет	10 часов
Сатурн		29 лет	10 часов
Уран		84 года	24 часа
Нептун		165 лет	22 часа
Плутон		247 лет	6 суток

Составить базу данных, учитывая измерение по некоторым параметрам в разных еденицах.

Ответить на вопросы: Какие планеты ближе к Солнцу, чем Земля? Какие планеты дальше от Солнца, чем Земля? На каких планетах солнечные сутки меньше, чем земные? На каких планетах период обращения измеряется в годах?

10. Построить базу знаний “Рабочая смена”:

Мария работает в дневную смену. Сергей работает в вечернюю смену. Борис работает в вечернюю смену. Валентина работает в вечернюю смену. Два служащих знают друг друга, если они работают в одну смену. Определить: Знает ли Сергей Бориса? Кого знает Валентина? Кого знает Мария?

11. Даны результаты сдачи экзаменов для группы из пяти учеников:

Таблица 7.

Успеваемость

Фамилия	Алгебра	Геометрия	История
Бобров
Вяткин
Кротов
Соснин
Вавилов

Построить базу знаний о результатах экзаменов, определив в ней следующие правила:

отличник - человек, у которого по всем предметам пятерки;

двоечник - есть хотя бы одна двойка;

математик - по алгебре и по геометрии учится на 4 и 5;

введите предикаты алгебра, геометрия, история для определения оценки Y для ученика X.

Получить ответы на следующие вопросы: Является ли Вяткин отличником? Определить всех отличников. Является ли Соснин математиком? Определить всех неуспевающих по истории.

12. Сформировать базу знаний “Квартет” из следующих фактов и правил:

Мартышка играет на скрипке. Осел играет на альте. Козел играет на виолончели. Мишка играет на контрабасе. Четверо музыкантов X, Y, Z и W могут образовать квартет, если один из них играет на скрипке, другой — на альте, третий — на виолончели и четвертый — на контрабасе.

Ответить на вопросы: Кто играет на альте? На чем играет мартышка? Образуют ли квартет Мартышка, Осел, Козел и Мишка? Кто из музыкантов данной базы знаний может образовать квартет?

13. База знаний “Воинская служба”:

возраст(борис, 18), возраст(андрей, 17), возраст(михаил, 18), возраст(анна, 18), возраст(юлия, 17), мужчина(андрей), мужчина(борис), мужчина(михаил), женщина(анна), женщина(юлия).

Определить правило подлежит призыву, не_подлежит_призыву.

Сформулировать вопросы: Кто подлежит призыву? Подлежит ли призыву Анна?

14. Построить базу знаний и сформулировать к ней вопросы, основываясь на следующих утверждениях: Резвый - это собака. Рекс-это собака. Белка – это кошка. Быстрая - это лошадь. Резвый - черная. Белка - белая. Рекс -рыжая. Быстрая - белая. Домашние животные - это собака или кошка. Животные – это либо лошадь, либо домашние животные. Том владеет тем, кто собака и не черного цвета. Кейт владеет тем, кто либо черного цвета, либо лошадь.

15. Построить базу знаний. Муська — коричневая кошка, Стрелка — черная кошка, Мурка — рыжая кошка. Рекс, Дружок и Мухтар — собаки. Дружок — рыжая, Мухтар — белая. Все животные, которыми владеют Анатолий и Николай, имееют родословные. Анатолий владеет всеми черными и коричневыми животными, а Николай владеет всеми собаками небелого цвета, которые не являются собственностью Анатолия. Иван владеет Муркой, если Николай не владеет Муськой и если Мухгар не имеет родословной. Рекс — пятнистая собака. Определить, какие животные не имеют хозяев.

16. Составить базу знаний “Знакомства” из следующих фактов и правил:

Мери прелестна. Джон добрый. Джон мужественный. Джон сильный. Некто счастлив, если богатый или нравится женщинам. Мужчина нравится женщине, если женщина нравится мужчине и он добрый, либо мужчина добрый и сильный. Мужчине нравится женщина, если она прелестна.

Сформулировать вопрос: счастлив ли Джон? Найти мужчин, которые могут нравиться женщинам.

17. Ответьте на вопрос “Что ест моя кошка? “, если:

Птицам нравятся червяки. Кошкам нравятся рыбы. Друзья нравятся друг другу. Моя кошка мой друг. Моя кошка ест все, что ей нравится.

18. Запрограммируйте утверждения.

Число четное. Число не четное. Ни одно число не является четным и нечетным одновременно. Число не четное, если следующее за ним четное. Число, следующее за данным числом нечетное, если данное число четное, число, следующее за данным числом четное, если данное число нечетное.

Контрольные вопросы

1. Механизмы пролога

2. Структура программы на Прологе.

3. Фразы Хорна и и предложения на Прологе.

4. Структура предложений на Прологе.

5. Виды предложений на Прологе.

6. Что представляет собой программирование на Прологе

7. Внутренние и внешние цели, различие в их выполнении.

8. Объекты на Прологе. Синтаксис.

Лабораторная работа №2

Организация рекурсивных программ. Использование отсечения в ПРОЛОГ – программах.

Цель работы. Научиться эффективно использовать рекурсию в ПРОЛОГ - программах. Изучить встроенные предикаты! (для предотвращения поиска с возвратом) и fail(для поддержания поиска с возвратом).

Краткие теоретические сведения.

Одной из важнейших особенностей языка Пролог является возможность поиска всех решений. Поиск всех решений достигается использованием механизма поиска с возвратом. Можно сформулировать четыре основных правила поиска с возвратом:

· подцели должны быть согласованы по порядку, слева направо (сверху вниз);

· предикатные предложения проверяются в том порядке, в котором они появляются в программе, сверху вниз;

· когда подцель сопоставляется с заголовком правила, тело этого правила должно быть доказано (тело правила состоит, в свою очередь, из новых подцелей, которые должны быть доказаны);

· целевое утверждение считается согласованным, когда соответствующие факты найдены для каждой листьевой вершины дерева целей.

Пример 1. Выводить на экран квадрат числа, вводимого пользователем, пока не будет введен 0.

Domains

x=integer

Predicates

repeat

check(x)

Clauses

repeat.

repeat: - repeat.

go: - repeat, write (“Введите число пожалуйста или 0-для выхода ”),

readint(A), check(A).

check(0): -nl, write(“ok”),!.

check(A): -B=A*A, write(B), nl, fail.

Или

go: - repeat, write (“Введите число ”), readint(A),

B=A*A, write(А, “^2= ”, B), nl,

write(“прервать да/нет (y/n) ”), readchar(C), C= “n”,!.

Пример 2. Организовать меню для выбора арифметической операции.

Domains

x=integer

Predicates

actions(x)

repeat

Clauses

repeat.

repeat: - repeat.

menu: - repeat,

write(“Введите 1 для +, 2 для *, 3-для -, 0-для выхода\n”),

readint(N),

actions(N).

actions(0): -!.

actions(1): -write(“Введите первое число”), nl, readint(A),

write(“Введите второе число”) nl, readint(B),

С=A+B, write(C), nl, fail.

actions(2): - write(“Введите первое число”), nl, readint(A),

write(“Введите второе число”) nl, readint(B),

С=A*B, write(C), nl, fail.

actions(3): - write(“Введите первое число”), nl, readint(A),

write(“Введите второе число”) nl, readint(B),

С=A-B, write(C), nl, fail.

Для управления поиском решений существует два стандартных предиката:

1. предикат fail, использующийся для поддержания поиска с возвратом;

2. предикат!, использующийся для предотвращения поиска с возвратом.

Предикат fail всегда дает неудачу в доказательстве и, таким образом, поддерживает поиск с возвратом.

Предикат! убирает все точки возврата, то есть через отсечение нельзя совершить поиск с возвратом.

Пример.

r(1, А): - А=10,!.

r(2, А): - А> 10,!.

r(3, А): - A< 10.

Goal: r(X, 10)

X=1

Правила для определения отношения r являются взаимоисключающими, поэтому успешно завершиться только одно из этих правил. Следовательно, при наступлении успеха нет необходимости проверять все остальные правила. Для предотвращения бесполезного перебора всех правил мы должны указать, что осуществлять возврат из этой точки нет необходимости. Такая проблема решается с помощью предиката отсечения (! ). Результат работы программы, использующей отсечение, будет таким, как и в случае без него, но для достижения цели ей понадобится меньше времени, что при большом объеме программы играет немаловажную роль.

Рекурсивная процедура – это процедура, которая вызывает сама себя. Рекурсия – хороший способ для решения задач, содержащих в себе подзадачу такого же типа. Например, задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n.

PREDICATES

factorial (integer, real)

CLAUSES

factorial (0, 1): -!. %факториал 0! равен 1 (граничное условие,
%останавливающее рекурсию)

factorial (N, FactN): -M=N-1, factorial (M, FactM), FactN= FactM*N.

%факториал n! равен (n-1)! *n (рекурсивное условие)

Goal: factorial (3, FactN)

FactN=6

Для наглядного представления нахождения решения удобно использовать дерево целей:

Во время лабораторного занятия студент должен:

1. Разработать программу на языке ПРОЛОГ, используя способы представления данных в виде фактов и правил вывода.

2. Используя возможности, предоставляемые программной оболочкой, проверить правильность работы созданной программы (при отладке программы использовать возможности трассировки).

1. Оценить полученные результаты.

2. Оформить результаты работы программы.

Содержание отчета.

1. Название лабораторной работы.

2. Цель работы.

3. Номер варианта.

4. Задание.

5. Описание родственных связей (в виде дерева).

6. Исходный текст программы (все строки программы пронумеровать).

7. Указать результаты пошаговой трассировки (информация находится в окне Trace) в виде:

< тип сообщения>: < имя предиката> (< значения> ) < номер строки, где находится этот предикат>

9. Выводы по работе. Оформить диалог пользователя с системой ПРОЛОГ в виде:

Goal: < цель>

< решение>.

Варианты заданий.

1) Вычислить N!.

2) Вычислить n-ый член последовательности Фибоначчи.

3) Вывести все числа от n до 1.

4) Вывести все числа от 1 до n.

5) Вычислить сумму чисел от 1 до n.

6) Определите xⁿ, n> 0.

7) Определите 2ⁿ, n> 0.

8) Определите N⁵, n> 0.

9) Вычислите сумму четных чисел от 1 до n.

10) Вычислите сумму квадратов нечетных чисел от 1 до n.

11) Вычислите сумму a_k, где a_k=1/(1+k).

12) Вычислить .

13) Вычислить .

14) Определите корень уравнения методом половинного деления.

15) Найти наибольший общий делитель двух чисел, трех чисел.

16) Определить число сочетаний .

17) Вычислить N! +(N-1)! +...+2! +1!.

18) Вычислить количество четных элементов на заданном интервале.

19) Перевести число из десятичной системы счисления в систему с основанием N, где N< 10, N> 1.

Контрольные вопросы

1. Методы организации рекурсии и повтора на Прологе.

2. Виды рекурсии.

Лабораторная работа №3

Рекурсивные структуры данных (списки).

Цель работы. Изучить способы представления списков на языке ПРОЛОГ. Научиться разрабатывать программы для выполнения типовых операций над списками.

Краткие теоретические сведения.

Список – это объект данных, содержащий конечное число других объектов (элементов списка). Список, содержащий числа 1, 2 и 3, записывается следующим образом:

[1, 2, 3]

Для объявления списка используется следующее описание домена:

Domains

integerlist=integer*

Список является рекурсивным составным объектом, он состоит из двух частей:

· головы списка – первого элемента списка;

· хвоста списка – списка, включающего все последующие элементы.

[1| [2, 3]]: голова списка 1, хвост списка [2, 3].

Так как список имеет рекурсивную составную структуру, для работы со списками используется рекурсия.

Пример: печать элементов списка.

DOMAINS

integerlist=integer*

PREDICATES

printlist (integerlist)

CLAUSES

printlist ([]): -!. %для пустого списка ничего не делать

printlist ([H|T]): -write (H), nl, printlist (T). %для непустого списка отделить голову,
GOAL

printlist([1, 2, 3]). %напечатать ее, продолжить печать для
%хвоста списка

Лабораторное задание.

Во время лабораторного занятия студент должен:

3. Оценить полученные результаты.

4. Оформить результаты работы программы.

Содержание отчета.

1. Название лабораторной работы.

2. Цель работы.

3. Номер варианта.

4. Задание.

5. Исходный текст программы (все строки программы пронумеровать).

6. Указать результаты пошаговой трассировки (информация находится в окне Trace) в виде:

< тип сообщения>: < имя предиката> (< значения> ) < номер строки, где находится этот предикат>

Варианты заданий.

1.1 Написать программу для сцепления списков с последующим реверсом элементов полученного списка. Например: [1, 2, 3] и [4, 5]® [1, 2, 3, 4, 5]→ [5, 4, 3, 2, 1]. Исходный и полученный списки вывести на экран.

1.2 Написать программу для нахождения максимального числа в списке. Максимальный элемент должен быть удален из списка. Полученный список вывести на экран.

2.1. Написать программу для вывода n-го элемента списка. Например: [1, 2, 3] ® 2-ой элемент

равен 2.

2.2. Написать программу для нахождения суммы элементов списка.

3.1.Написать программу для удаления из списка всех элементов, равных 0. Например: [1, 0, 2,

0, 3, 0] ® [1, 2, 3]. Если список имеет четную длину, то вывести на экран ‘Четный список

< список> ’, иначе вывести ‘Нечетный список < список> ’.

3.2.Написать программу для упорядочивания списка. Например: [1, 4, 3, 7, 2] ® [1, 2, 3, 4, 7].

4.1.Написать программу для перевода списка арабских чисел (от 1 до 10) в список римских

чисел. Например: [1, 2, 3] ® [I, II, III]. Полученный список вывести на экран.

4.2.Удалить из списка все элементы, стоящие на нечетной позиции, т.е. 1-ый, 3-ий и т.д. Например: [1, 2, 3, 4, 5, 6] ® [1, 3, 5]. Полученный список вывести на экран.

5.1. Удалить из списка все элементы, стоящие на четной позиции, т.е. 2-ой, 4-ый и т.д.

Например: [1, 2, 3, 4, 5, 6] ® [1, 3, 5]. Полученный список вывести на экран.

5.2. Написать программу для сдвига элементов списка влево на заданное количество позиций.

Например: [1, 2, 3, 4, 5]®[3, 4, 5, 1, 2]. Полученный список вывести на экран.

Контрольные вопросы

1. Представление списков на Прологе.

2. Реализация основных операций над списками на Прологе.

3. Реализация алгоритмов сортировки.

Лабораторная работа № 1.
Основные понятия языка Haskell. Базовые функции языка Haskell

Цели работы

Знакомство с основами функционального программирования. Изучение основных арифметических и логических операций в языке Haskell. Изучение базовых функций языка Haskell.

⇐ Предыдущая 123 Следующая ⇒