3.
ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Почти все наши ошибки, в сущности, языково-
го характера. Мы сами создаем себе трудно-
сти, неточно описывая факты. Так, например,
разные вещи мы называем одинаково и,
наоборот, даем разные определения одному и
тому же.
Олдос Хаксли
3.1. Контроль обучения
В процессе дистантного обучения дисциплине "Логическое программи- рование" студент должен выполнить три контрольных задания, курсовую ра- боту и обучение заканчивается выполнением компьютерной экзаменационной работы. Контрольные задания представлены ниже и состоят каждое из двух задач, требующих составить программы на Прологе. Составленные и отла- женные программы (обязательно с комментариями) студент по мере освоения логического программирования периодически пересылает по электронной почте диспетчеру центра дистантного обучения, который в свою очередь пе- ресылает их лектору. Лектор проверяет программы и при правильном выпол- нении программы студент получает подтверждение о том, что они зачтены.
Если программа составлена неправильно, студент получает от лектора тек- стовый файл, в котором содержится описание ошибок программы.
3.2. Инсталляция SWI-Prolog'а
Интерпретатор с языка Пролог представлен в виде упакованного файла pl.arj. SWI-Prolog работает в среде Windows (3.11 или 95); для его установки на компьютере достаточно распаковать файл pl.arj вместе со всеми хранящи- мися в этом файле каталогами. Запустите файл pl.exe из каталога pl\bin и вы войдете в интерпретатор. Пролог выдает приглашение "?-" и ждет вашего ввода.
Чтобы набирать программы, надо воспользоваться каким-либо внеш- ним текстовым редактором (SWI-Prolog не имеет собственного редактора).
Например, вы можете пользоваться стандартной программой Notepad ("блок- нот"). Набранные программы сохраняйте в виде текстовых файлов с расши- рением pl (но можно и расширение txt) в рабочем каталоге. По умолчанию рабочим каталогом будет pl\bin, но вы можете это изменить: для этого со- здайте ярлык для pl.exe и измените рабочий каталог в свойствах этого ярлыка.
Чтобы загрузить программу из файла c:\pl\work\name.pl, находясь в среде ин- терпретатора, вы должны в ответ на приглашение "?-" набрать имя файла в квадратных скобках
15 ?- [name]. если установлен рабочий каталог - pl\work, или набрать имя файла с полным путем к нему, ?-['c:\pl\work\name.pl']. если установлен другой рабочий каталог. Отметим следующую особенность работы в SWI-Prolog с блокнотом. После набора текста программы обяза- тельно перейдите курсором на новую строчку, иначе SWI-Prolog при загрузке файла с программой выдаст ошибку "неожиданный конец файла". 3.3. Первое контрольное задание Задание состоит из двух задач, в которых требуется составить програм- мы на Прологе для написания простых предикатов. При составлении про- грамм (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Тексты всех программ, если вы мыслите в духе логиче- ского программирования, получаются небольшие. SWI-Prolog не имеет стандартного help'а для Windows, для этого ис- пользуется предикат help. Вызов help(<имя предиката>) выдает на экран ин- формацию об этом предикате. Вызов help(7) выдает на экран список всех встроенных предикатов с комментариями. Текстовый файл руководства по SWI-Prolog - pl\library\manual. Отладку предикатов можно осуществлять с помощью предиката трассировки trace(<имя предиката>), трассировка преди- ката отключается - trace(<имя предиката>, -all). Пример задания с решением Задача 1 Постройте предикат position_max(+L, -M, -N), который в списке L находит максимальное значение M и порядковый номер N этого значения. Задача 2 Определите умножение целых чисел через сложение и вычитание. Решение Задача 1 Будем использовать метод накапливающего параметра. Для этого введем вспомогательный предикат position_max(+List, +I, +M0, +N0, -M, -N), где I равен номеру рассматриваемого элемента в исходном списке, M0 - текущее значение максимума, N0 - позиция текущего максимума. position_max([X|T],M,N):- position_max(T,1,X,1,M,N). position_max([],_,M,N,M,N). 16 position_max([A|T],I,X,_,M,N):- A>X, K is I+1, position_max(T,K,A,K,M,N). position_max([A|T],I,X,Y,M,N):- A= K is I+1, position_max(T,K,X,Y,M,N).
?- position_max([3,2,5,1,4,3],M,N).
M = 5
N = 3
Yes
Задача 2
Определим предикат p(+X,+Y,?R), где X и Y сомножители, R - произведение.
Делаем рекурсию по второму аргументу предиката, используя рекурсивное определение X*Y=X*(Y-1)+X. p(X,0,0). p(X,Y,R):- Y>0,
Y1 is Y-1, p(X,Y1,R1),
R is R1+X. p(X,Y,R):- Y<0,
Y1 is -Y, p(X,Y1,R).
Варианты заданий
Вариант 1 1. Определите возведение в целую степень через умножение и деление.
2. Напишите предикат p(+L, -N) - истинный тогда и только тогда, когда N - предпоследний элемент списка L, имеющего не менее двух элементов.
Вариант 2 1. Напишите предикат p(+X, +N, -L) - истинный тогда и только тогда, когда L
- список из N раз повторенных элементов X.
17 2. Напишите предикат p(+L, -S) - истинный тогда и только тогда, когда S - список списков элементов списка L, например, p([a, b, c],[[a], [b], [c]]) - исти- на. Вариант 3 1. Напишите предикат p(+L, -S) - истинный тогда и только тогда, когда L - список списков, а S - список, объединяющий все эти списки в один. 2. Напишите предикат p(+L, -S) - истинный тогда и только тогда, когда спи- сок S есть циклическая перестановка элементов списка L, например, p([f, g, h, j], [g, h, j, f]) -истина. Вариант 4 1. Напишите предикат p(+X, +N, +V, -L) - истинный тогда и только тогда, ко- гда список L получается после добавления X на N-е место в список V. 2. Напишите предикат p(+N, +V, -L) - истинный тогда и только тогда, когда список L получается после удаления N-го элемента из списка V. Вариант 5 1. Напишите предикат p(+V, -L) - истинный тогда и только тогда, когда спи- сок L получается после удаления всех повторных вхождений элементов в список V, например, p([a, b, c, d, d, a], [a, b, c, d]) - истина. 2. Напишите предикат p(+V, -L) - истинный тогда и только тогда, когда спи- сок L получается после удаления из списка V всех элементов, стоящих на четных местах, например, p([1, 2, 3, 4, 5, 6], [1, 3, 5]) - истина. Вариант 6 1. Напишите предикат p(+V, +X, -L) - истинный тогда и только тогда, когда список L получается из списка V после удаления всех вхождений X на всех уровнях, например, p([1, [2, 3, [1]], [3, 1]], 1, [[2, 3, []], [3]]) - истина. 2. Напишите обобщение предиката member, когда ищется элемент на всех уровнях в списке. Вариант 7 1. Определите предикат p(+U, +V, -L) - истинный тогда и только тогда, когда список L есть список всех элементов списка U, не содержащихся в списке V. 2. Определите предикат p(+U, +V, -L) - истинный тогда и только тогда, когда L - список всех элементов, содержащихся либо в списке U, либо в списке V, но не одновременно в U и V. Вариант 8 1. Определите предикат p(+V, -L) - истинный тогда и только тогда, когда L - список всех элементов списка V, встречающихся в нем более одного раза. 18 2. Напишите предикат subst(+V, +X, +Y, -L) - истинный тогда и только тогда, когда список L получается после замены всех вхождений элемента X в списке V на элемент Y. Вариант 9 1. Напишите предикат p(+V, -L) - истинный тогда и только тогда, когда спи- сок L получается из списка V после удаления всех повторяющихся элементов, т. е. из списка получается множество. 2. Напишите предикат exists(+P, +L), который проверяет "Существует ли эле- мент списка L, удовлетворяющий предикату P?" Вариант 10 1. Напишите предикат all(+P, +L), который проверяет "Для всех ли элементов списка L выполняется предикат P? " 2. Напишите предикат filter(+V, +P, -L) - истинный тогда и только тогда, ко- гда список L есть список всех элементов из списка V, удовлетворяющих пре- дикату P ("фильтрация" списка). Вариант 11 1. Используя предикаты "родитель"(Родитель, Отпрыск), "женщи- на"(Человек), "мужчина"(Человек) и "супруги"(Жена, Муж), определите от- ношения теща, шурин и зять. 2. Башня из кубиков может быть описана совокупностью фактов вида "на"(Кубик1, Кубик2), которые истинны, если Кубик1 поставлен на Кубик2. Определите предикат "выше"(Кубик1, Кубик2), который истинен, если Ку- бик1 расположен на башне выше, чем Кубик2. (Указание: "выше" является транзитивным замыканием отношения "на".) Вариант 12 1. Напишите предикат gcd(+A,+B,-D) - истинный тогда и только тогда, когда D -наибольший общий делитель двух целых положительных чисел A и B. 2. Напишите программу для отношения double(+List, -ListList), в котором каждый элемент списка List удваивается в списке ListList, например, double([1,2,3],[1,1,2,2,3,2]) выполнено. Вариант 13 1. Напишите новую версию предиката length(+L, -N), в котором при подсчете количества элементов списка не учитывается пустой список. К при- меру, для списка [a,b,c,d,e] новая версия процедуры должна сообщить, что длина списка равна пяти, а для списка [a,[],c,d,[]] эта процедура должна да- вать длину, равную трем. 2. Пусть имеется список структур "client": [client(a,29,3),client(b,29,6),client(c,40,2)].
19
Первым аргументом каждой структуры служит имя клиента, вторым - суточ- ный тариф, а третьим - количество дней, на которое взята автомашина.
Напишите правило, позволяющее вычислить итоговую сумму оплаты, объ- единяющую выплаты всех клиентов, данные о которых содержатся в списке.
Вариант 14 1. Опишите процедуру для предиката расщепить/4, которая берет список це- лых чисел L1 и целое число N и выдает списки L2 и L3 такие, что числа из исходного списка, меньшие, чем N, помещаются в список L2, а остальные - в список L3.
2. Напишите предикат для вычисления чисел Фибоначчи, используя метод накапливающего параметра.
Вариант 15 1. Напишите предикат digits(+N, -L) - истинный тогда и только тогда, когда L
- список цифр натурального числа N.
2. Напишите предикат summa_digits(+N, -S) - истинный тогда и только тогда, когда S - сумма цифр натурального числа N.
3.4. Второе контрольное задание
Задание состоит из двух задач, в которых требуется составить програм- мы на Прологе для написания простых программ. При составлении программ
(если не оговорено противное) можно использовать все встроенные предика- ты Пролога. Тексты всех программ, если вы мыслите в духе логического про- граммирования, получаются небольшие.
Пример задания с решением
Задача 1
Сортировка списка простым обменом (по возрастанию).
Задача 2
Пусть бинарное дерево задается рекурсивной структурой tree(<левое подде- рево>,<корень>,<правое поддерево>) и пустое дерево задано термом nil.
Составьте программу subtree(+S, +T), определяющую, является ли S поддере- вом T.
Решение
Задача 1
Заданный список L сортируется по следующему алгоритму:
(1) если L содержит два соседних элемента, нарушающих требуемое упоря- дочение, то эти элементы меняются местами, после чего к полученному спис- ку применяется этот же алгоритм;
20
(2) если в L не встречается ни одной неупорядоченной пары соседних эле- ментов, то список L отсортирован и тем самым является искомым списком.
Предикат ord(+L) проверяет является ли список L отсортированным. ord([]). ord([_]). ord([X,Y|T]):-
X =< Y, ord([Y|T]). change(L,L):- ord(L),!. change(L,S):- append(L1,[X,Y|L2],L),
X>Y,!, append(L1,[Y,X|L2],Z), change(Z,S).
Отсечения в данном случае ликвидируют многочисленные правильные отве- ты.
Задача 2
Для решения используется очевидная рекурсия. subtree(X, X). subtree(X, tree(L,_,_)):- subtree(X,L). subtree(X,tree(_,_,R)):- subtree(X,R).
Варианты заданий
Вариант 1 1. Напишите предикат, аналогичный предикату subst (см. первое контрольное задание, вариант 8, задача 2), но производящий взаимную замену X на Y, т.е.
X->Y, Y->X.
2. Напишите предикат, который определяет, является ли данное натуральное число простым.
Воспользуйтесь более общей задачей: ispr(N, M) - "Число N не делится ни на одно число большее или равное M и меньшее N".
Имеем ispr(N, M) -истинно, во-первых, если N = M, и, во-вторых, если ис- тинно ispr(N,M+1) и N не делится на M.
21
Вариант 2 1. Сортировка списка простой вставкой (по возрастанию).
2. Сортировка списка простым выбором (по возрастанию).
Вариант 3 1. Напишите предикат p(+L, -N) - истинный тогда и только тогда, когда N - количество различных элементов списка L.
2. Напишите предикат p(+X, +Y, -Z) - истинный тогда и только тогда, когда Z есть "пересечение" списков X и Y, т.е. список, содержащий их общие элемен- ты, причем кратность каждого элемента в списке Z равняется минимуму из его кратностей в списках X и Y.
Вариант 4 1. Запрограммируйте предикат p(+A,+B), распознающий, можно ли получить список элементов A из списка элементов B посредством вычеркивания неко- торых элементов.
Алгоритм: Если A - пустой список, то ответом будет "да". В противном слу- чае нужно посмотреть, не пуст ли список B. Если это так, то ответом будет "нет". Иначе нужно сравнить первый элемент списка A с первым элементом списка B. Если они совпадают, то надо снова применить тот же алгоритм к остатку списка A и остатку списка B. В противном случае нужно снова при- менить тот же алгоритм к исходному списку A и остатку списка B.
2. Напишите предикат p(+X, +Y, +L) - истинный тогда и только тогда, когда
X и Y являются соседними элементами списка L.
Вариант 5.
1. Определите отношение sum_tree(+TreeOfInteger, -Sum), выполненное, если число Sum равно сумме целых чисел, являющихся вершинами дерева
TreeOfInteger.
2. Определим операторы:
:- op( 100, fy, ).
:- op( 110, xfy, &).
:- op( 120, xfy, v).
Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X &
Y, X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а - унарный оператор отрицания. Напишите предикат p(+T), определяющий, является ли данный терм T булевой форму- лой.
22 Вариант 6 1. Встроенный предикат functor(+Term, ?Functor, ?Arity) определяет для за- данного составного терма Term его функтор Functor и местность Arity. Встроенный предикат arg(+N, +Term, ?Value) определяет для целого числа N и заданного составного терма Term его N-ый аргумент Value. Определите предикаты functor1 и arg1 - аналоги предикатов functor и arg через предикат univ (=..) 2. Напишите предикат range(?M, ?N, ?L), истинный тогда и только тогда, ко- гда L - список целых чисел, расположенных между M и N включительно (предикат должен допускать различное использование, когда не менее двух из трех аргументов конкретизованы). (Указание. Используйте предикаты var(+X) и nonvar(+X)). Вариант 7 1. Напишите вариант программы plus(?X, ?Y, ?Z), пригодный для сложения, вычитания и разбиения чисел на слагаемые. (Указание. Используйте для порождения чисел встроенный предикат between(+Low, +High, ?Value), который порождает все целые числа от нижней границы Low до верхней границы High.) 2. Напишите программу вычисления целочисленного квадратного корня из натурального числа N, определяемого как число I, такое, что I*I N, но (I+1)*(I+1) > N . Используйте определение предиката between/3 для генериро- вания последовательности натуральных чисел с помощью механизма возвра- тов. Вариант 8 1. Напишите новую версию процедуры "предок", которая вырабатывает спи- сок представителей всех промежуточных поколений, располагающихся меж- ду предком и потомком. Предположим, например, что Генри является отцом Джека, Джек - отцом Ричарда, Ричард - отцом Чарльза, а Чарльз - отцом Джейн. При запросе о том, является ли Генри предком Джейн, должен выдаваться список, характеризующий родственную связь этих людей, кон- кретно: [джек, ричард, чарльз]. 2. Определите предикат p(+V, +N, -L) - истинный тогда и только тогда, когда L - список элементов списка V, встречающихся в нем не менее N раз. Про- верьте работу этого предиката на примере [a, a, b, a, c, b, c, a, b, b, d, a, b] для N=1,2,5,0. 23 3.5. Третье контрольное задание Задание состоит из двух задач, в которых требуется составить более сложные программы на Прологе (как правило, требуется определить несколь- ко предикатов). При составлении программы (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Текст программы, если вы мыслите в духе логического программирования и используете рекур- сию, получается небольшой. Пример задания с решением Задача 1 Определим операторы: :- op( 100, fy, ). :- op( 110, xfy, &). :- op( 120, xfy, v). Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X & Y, X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а - унарный оператор отрицания. Напишите программу, распознающую логические формулы в конъюнктивной нормальной форме, т.е. формулы, являющиеся конъюнкцией дизъюнкций ли- тералов, где литерал - атомарная формула или ее отрицание. Задача 2 Напишите предикат p(+N, -L) - истинный тогда и только тогда, когда список L содержит все последовательности (списки) из N нулей, единиц и двоек, в которых никакая цифра не повторяется два раза подряд (нет куска вида XX). Решение Задача 1 Из определения операций видно, что конъюнкция и дизъюнкция являются право ассоциативными, т. е. запрос ?- X & Y & Z = A & B приводит к унификации X = A, Y & Z = B. Определим два вспомогательных предиката literal(X) и dis(X), которые прове- ряют является ли X литералом и элементарной дизъюнкцией соответственно. literal(true). literal(false). literal( X):- literal(X). 24 dis(X):- literal(X). dis(X v Y):- literal(X), dis(Y). con(X):- dis(X). con(X & Y):- dis(X), con(Y). ?- con( true & ( false v true v false) & true). Yes Задача 2 p(1,[[0],[1],[2]]). p(N,R):- N>1, N1 is N-1, p(N1,R1), t(R1,R). t([],[]). t([X|T],Z):- t(T,R1), s(X,R), append(R,R1,Z). s([0|T],[[1,0|T],[2,0|T]]). s([1|T],[[0,1T],[2,1|T]]). s([2|T],[[0,2|T],[1,2|T]]). |
Скачать 2.34 Mb.