Решение. Задание состоит из 5 задач, в которых требуется составить программы на Прологе

Задание 1

Задание состоит из 5 задач, в которых требуется составить программы на Прологе. Первые две задачи требуют запрограммировать простые предикаты. Следующие две - требуют написать простые программы. В последней задаче требуется составить более сложную программу на Прологе (как правило, требуется определить несколько предикатов). При составлении программ (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Тексты всех программ, если вы мыслите в духе логического программирования, получаются небольшие.

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

Определите умножение целых чисел через сложение и вычитание.

Задача 3

Сортировка списка простым обменом (по возрастанию).

Задача 4

Пусть бинарное дерево задается рекурсивной структурой tree(< левое поддерево>, < корень>, < правое поддерево>) и пустое дерево задано термом nil. Составьте программу subtree(+S, +T), определяющую, является ли S поддеревом T.

Задача 5a

Определим операторы:

: - op(100, fy, ~).

: - op(110, xfy, &).

: - op(120, xfy, v).

Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X & Y, ~X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный оператор отрицания.

Напишите программу, распознающую логические формулы в конъюнктивной нормальной форме, т.е. формулы, являющиеся конъюнкцией дизъюнкций литералов, где литерал - атомарная формула или ее отрицание.

Задача 5b

Напишите предикат p(+N, -L) - истинный тогда и только тогда, когда список L содержит все последовательности (списки) из N нулей, единиц и двоек, в которых никакая цифра не повторяется два раза подряд (нет куска вида XX).

Решение

Задача 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).

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=< X,

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).

Задача 3

Заданный список L сортируется по следующему алгоритму:

(1) если L содержит два соседних элемента, нарушающих требуемое упорядочение, то эти элементы меняются местами, после чего к полученному списку применяется этот же алгоритм;

(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).

Отсечения в данном случае ликвидируют многочисленные правильные ответы.

Задача 4

Для решения используется очевидная рекурсия.

subtree(X, X).

subtree(X, tree(L, _, _)): -

subtree(X, L).

subtree(X, tree(_, _, R)): -

subtree(X, R).

Задача 5a

Из определения операций видно, что конъюнкция и дизъюнкция являются право ассоциативными, т. е. запрос

? - X & Y & Z = A & B

приводит к унификации X = A, Y & Z = B.

Определим два вспомогательных предиката literal(X) и dis(X), которые проверяют является ли X литералом и элементарной дизъюнкцией соответственно.

literal(true).

literal(false).

literal(~ X): -

literal(X).

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

Задача 5b

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, 1|T], [2, 1|T]]).

s([2|T], [[0, 2|T], [1, 2|T]]).

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

Вариант 8

1. Определите предикат p(+V, -L) - истинный тогда и только тогда, когда L - список всех элементов списка V, встречающихся в нем более одного раза.

2. Напишите предикат subst(+V, +X, +Y, -L) - истинный тогда и только тогда, когда список L получается после замены всех вхождений элемента X в списке V на элемент Y.

3. Напишите вариант программы plus(? X,? Y,? Z), пригодный для сложения, вычитания и разбиения чисел на слагаемые.

(Указание. Используйте для порождения чисел встроенный предикат between(+Low, +High,? Value), который порождает все целые числа от нижней границы Low до верхней границы High.)

4. Опишите процедуру для предиката расщепить/4, которая берет список целых чисел L1 и целое число N и выдает списки L2 и L3 такие, что числа из исходного списка, меньшие, чем N, помещаются в список L2, а остальные - в список L3.

5. Множественное число большинства английских существительных получается путем добавления буквы " s" к форме единственного числа. Но если существительное заканчивается буквой " y", следующей за согласной, множественное число образуется путем замены буквы " y" на сочетание " ies"; если же существительное заканчивается буквой " o", следующей за согласной, множественное число образуется путем добавления сочетания " es". Напишите утверждения для предиката множественное_число/2, которые задают все эти правила. Указание. Воспользуйтесь предикатом name/2.