Функциональное и логическое программирование 1

Первое контрольное задание

Задание состоит из трех задач, в которых требуется составить программы на Лиспе. В первой задаче не требуется рекурсия, остальные две задачи требуют применения простой рекурсии. При составлении программ (если не оговорено противное) можно использовать все встроенные функции Лиспа. Тексты всех программ, если вы мыслите в духе функционального программирования, бук-вально состоят из нескольких строчек.
Отладку программ можно осуществлять с помощью функции трасси-ровки (trace <имя функции>), трассировка функции отключается - (untrace <имя функции>).

Пример задания с решением
Задача 1
Пусть l1 и l2 -списки. Напишите функцию, которая возвращала бы t, если первые два элемента этих списков соответственно равны друг другу, и nil ? в противном случае (например, если длина одного из списков меньше 2).
Задача 2
Напишите функцию, зависящую от двух аргументов x и u, удаляющую все вхождения x в список u на всех уровнях.
Задача 3
Сортировка слиянием. Даны два упорядоченных по возрастанию списка чисел x и y. Написать функцию (merge x y), которая в качестве значения выдает общий упорядоченный список элементов x и y. Например,
merge('(1 3 5 7 8) '(2 3 5 7)) => (1 2 3 3 5 5 7 7 8).

Решение
Задача 1
(defun f (l1 l2)
(and (> (length l1) 1)
(> (length l2) 1)
(equal (first l1) (first l2))
(equal (second l1) (second l2))))
Задача 2
(defun f (x u)
(if (null u) nil
(let ((c (first u)) (r (rest u)))
(cond ((and (atom c) (equal x c)) (f x r ))
((atom c) (cons c (f x r)))
( t (cons (f x c) (f x r))))
))
)
Задача 3
(defun merge (x y)
(cond ((null x) y)
((null y) x)
((> (first x) (first y))
(cons (first y) (merge x (rest y))))
(t (cons (first x) (merge (rest x) y))))
)

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

Вариант 1
1. Напишите функцию трех аргументов (list3 x y z) такую, что (list3 x y z) =(x y z) для любых символьных выражений; не используйте функцию list.
2. Последовательность чисел Фибоначчи 1, 1, 2, 3, 5, 8, 13… строится по сле-дующему закону: первые два числа - единицы; любое следующее число есть сумма двух предыдущих f(n)=f(n-1)+f(n-2). Напишите функцию (f n f1 f2) c накапливающимися параметрами f1 и f2, которая вычисляет n-ое число Фибоначчи.
3. Определите умножение целых чисел (*2 x y) через сложение и вычитание.

Вариант 2
1. Напишите функцию, которая выдает истину, если ее аргумент удовлетво-ряет хотя бы одному из следующих условий:
а) является списком из двух элементов;
б) является списком из двух атомов;
в) является списком из трех элементов.
2. Определите возведение в целую степень (^ x n) через умножение и деление.
3. Напишите функцию (fullength x), считающую полное количество атомов (не равных nil) в списке x.

Вариант 3
1. Напишите с помощью композиции условных выражений функции от че-тырех аргументов (and4 x1 x2 x3 x4) и (or4 x1 x2 x3 x4), совпадающие с встроенными функциями and и or от четырех аргументов.
2. Напишите функцию, вычисляющую последний элемент списка.
3. Напишите функцию от двух аргументов x и n , которая создает список из n раз повторенных элементов x.

Вариант 4
1. Напишите функцию, осуществляющую циклическую перестановку
элементов в списке, т.е. (f g h j) -> (g h j f).
2. Напишите функцию, которая из данного одноуровнего списка строит список списков его элементов, например, (a b) -> ((a) (b)).
3. Определите функцию, зависящую от двух аргументов u и v, являющихся списками, которая вычисляет список всех элементов u, не содержащихся в v.

Вариант 5
1. Определите функцию (f a b c), которая равна истине тогда и только тогда, когда из отрезков с длинами a,b и c можно построить треугольник.
2. Определите функцию, зависящую от двух аргументов u и v, являющихся списками, которая вычисляет список всех элементов, содержащихся либо в u, либо в v, но не одновременно в u и v.
3. Напишите функцию, осуществляющую замену элементов списка y на соот-ветствующие элементы списка x в списке w, например,
y=(a b), x=(1 2), w=((a b) a (c (a (a d)))) -> ((1 2) 1 (c (1 (1 d)))).

Вариант 6
1. Определите функцию (f a b c), которая вычисляет список корней квадрат-ного уравнения a*x^2+b*x+c=0 (если корней нет, то список пустой).
2. Напишите функцию, аналогичную встроенной функции замены subst в списке s выражения x на y, но производящую взаимную замену x на y, т.е. x->y, y->x.
3. Определите функцию (f s), результатом которой является список, получа-ющийся после удаления на всех уровнях всех положительных элементов списка чисел s.

Вариант 7
1. Определите функцию, которая меняет местами первый и последний эле-менты списка, оставляя остальные на своих местах.
2. Определите функцию (summa_digits n), результатом которой является сум-ма цифр натурального числа n.
3. Определите функцию (f s), которая из данного списка s удаляет последний элемент.
2.4. Второе контрольное задание

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

Пример задания с решением
Задача 1
Напишите функцию, вычисляющую полное число подсписков, входящих в данный список на любом уровне. Для списка (a b ((a) d) e) оно равно двум.
Задача 2
Напишите функцию, удаляющую повторные вхождения элементов в список, например, (a b c d d a) -> (a b c d)
Задача 3
Напишите функцию, строящую список всех подмножеств данного множества.

Решение

Задача 1
; Предикат (p x) выясняет является ли список одноуровневым
(defun p (x)
(cond ((null x) t)
((listp (first x)) nil)
( t (p (rest x))))
)

(defun f (x)
(cond ((atom x) 0)
((p x) 0)
( t (if (listp (first x))
(+ 1 (f (first x)) (f (rest x)))
(f (rest x)))))
)

Задача 2
(defun f (x)
(labels
(( f1 (y z)
(cond ((null y) z)
((member (first y) z) (f1 (rest y) z))
( t (f1 (rest y) (append z (list (first y))))))))
(f1 x nil))
)

Задача 3
Следующее решение принадлежит Клыкову Виктору, студенту кафедры АСУ группы 437-1.
; встроенная функция (union list1 list2) создает список всех элементов, входя-щих в список list1 или в list2 (объединение множеств): ; (union '(1 2 3) '(2 5 7 1)) => ( 7 5 1 2 3) (defun f(s) (if (null s) (list s) (union (mapcar '(lambda (x) (cons (car s) x)) (f (cdr s)))
(f (cdr s)))
)
)
Варианты заданий

Вариант 1
1. Определите функцию, зависящую от одного аргумента, которая по данному списку вычисляет список его элементов, встречающихся в нем более одного раза. Проверьте, как она будет работать на примере '(a a a a b a).
2. Определите функцию, зависящую от двух аргументов u и n, которая по
данному списку строит список его элементов, встречающихся в нем не менее n раз. Проверьте работу этой функции на примере (a a b a c b c a b b d a b) для n=1,2,5,0. 3. Используя функционалы, напишите функцию, которая из данного списка
строит список списков его элементов, например, (a b) -> ((a) (b)).
Вариант 2 1. Определите функцию, обращающую список и все его подсписки на любом уровне, например, (a b (c d) e) -> (e (d c) b a). 2. Напишите функцию, заменяющую Y на число, равное глубине вложения Y в W, например, Y=a, W=((a b) a (c (a (a d)))) -> ((2 b) 1 (c (3 (4 d)))). 3. Напишите функцию, единственным аргументом которой являлся бы список списков, объединяющую все эти списки в один.
Вариант 3 1. Напишите функцию, определяющую глубину первого вхождения элемента y в список w. 2. Напишите функцию, которая делает из списка множество, т.е. удаляет все повторяющиеся элементы. 3. Напишите функцию (exists p x), которая проверяет "Существует ли элемент списка x, удовлетворяющий предикату p?" (p - функция или функциональное имя ).



Вариант 4
1. Напишите функцию, которая определяет является ли данное натуральное число простым. Воспользуйтесь более общей задачей: (ispr n m) - "Число n не делится ни на одно число большее или равное m и меньшее n". Имеем (ispr n m) -истинно, во-первых, если n = m, и, во-вторых, если истинно (ispr n m+1) и n не делится на m. 2. Напишите функцию, которая сортирует список чисел, используя алгоритм простой вставки.
3. Напишите функцию (all p x), которая проверяет "Для всех ли элементов списка x выполняется предикат p? "
(p - функция или функциональное имя ).
Вариант 5
1. Напишите функцию, которая сортирует список чисел, используя алгоритм простого выбора.
2. Определите функцию (f s), результатом которой является список, получа-ющийся из списка списков s после удаления всех подсписков, содержащих числа. 3. Напишите функцию (filter p x), которая "фильтрует" (создает список) эле-менты списка x, удовлетворяющие предикату p (p - функция или функциональное имя ).
Вариант 6 1. Определите функцию (f a n), которая от двух числовых аргументов
вычисляет величину a+a*(a+1)+a*(a+1)*(a+2)+...+a*(a+1)*...*(a+n). 2. Определите функцию (f s), которая вычисляет список (m1 m2 m3),
состоящий из трех наибольших элементов списка s: m1 >= m2 >= m3. Исходный список содержит не менее трех элементов. 3. Определите функцию (f s n), которая из списка чисел s создает новый спи-сок, прибавляя к каждому атому число n. Исходный список не предполагается одноуровневым.
Вариант 7 1. Определите функцию (f n), n кратное 3, вычисляющую сумму: 1*2*3+4*5*6+...+(n-2)*(n-1)*n.
2. Определите функцию (f s), которая в одноуровневом списке чисел s переставляет все отрицательные элементы в начало списка, например, (f '(4 -8 6 -9 -7)) -> (-8 -9 -7 4 6). 3. Определите функцию (f s), которая из списка чисел s создает новый список, меняя знак у каждого атома. Исходный список не предполагается одноуров-невым.
Вариант 8 1. Определите функцию (f s), вычисляющую знакочередующую сумму a1-a2+a3-a4+...+ak*(-1)^(k+1) для списка s, имеющего вид (a1 a2 a3 ... ak). 2. Определите функцию (f n), которая для натурального числа n вычисляет 1!+2!+3!+...+n!. 3. Напишите функцию (count p x), которая подсчитывает, сколько атомов в списке x удовлетворяет предикату p (p -функция или функциональное имя). Список x не предполагается одноуровневым.




Первое контрольное задание

Задание состоит из двух задач, в которых требуется составить програм-мы на Прологе для написания простых предикатов. При составлении про-грамм (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Тексты всех программ, если вы мыслите в духе логиче-ского программирования, получаются небольшие.
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).

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

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

Вариант 1
1. Определите возведение в целую степень через умножение и деление.
2. Напишите предикат p(+L, -N) - истинный тогда и только тогда, когда N - предпоследний элемент списка L, имеющего не менее двух элементов.

Вариант 2
1. Напишите предикат p(+X, +N, -L) - истинный тогда и только тогда, когда L - список из N раз повторенных элементов X.
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, встречающихся в нем более одного раза.
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": [cli-ent(a,29,3),client(b,29,6),client(c,40,2)].
Первым аргументом каждой структуры служит имя клиента, вторым - суточ-ный тариф, а третьим - количество дней, на которое взята автомашина. Напишите правило, позволяющее вычислить итоговую сумму оплаты, объ-единяющую выплаты всех клиентов, данные о которых содержатся в списке.

Вариант 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 содержит два соседних элемента, нарушающих требуемое упоря-дочение, то эти элементы меняются местами, после чего к полученному спис-ку применяется этот же алгоритм;
(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.

Вариант 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 булевой форму-лой.
Вариант 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.




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

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

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

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



Вариант 2
1. Определите отношение ordered(+Tree), выполненное, если дерево Tree яв-ляется упорядоченным деревом целых чисел, т. е. число, стоящее в любой вершине дерева, больше любого элемента в левом поддереве и меньше любо-го элемента в правом поддереве. Определение структуры "дерево" см. раздел "Второе контрольное задание". Указание. Можно использовать вспомогательные предикаты ordered_left(+X, +Tree) и ordered_right(+X, +Tree), которые проверяют, что X меньше (боль-ше) всех чисел в вершинах левого (правого) поддерева дерева Tree и дерево Tree - упорядочено.
2. Определим операторы:
:- op( 100, fy, ~).
:- op( 110, xfy, &).
:- op( 120, xfy, v).

Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X & Y, ~X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный оператор отрицания.
Напишите программу, распознающую логические формулы в дизъюнктивной нормальной форме, т.е. формулы, являющиеся дизъюнкцией конъюнкций ли-тералов, где литерал - атомарная формула или ее отрицание. Вариант 3 1. Определим операторы:
:- op( 100, fy, ~).
:- op( 110, xfy, &).
:- op( 120, xfy, v).

Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X & Y, ~X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный оператор отрицания. Напишите программу, задающую отношение negation_inward(+F1,-F2), кото-рое выполнено, если логическая формула F2 получается из логической фор-мулы F1 внесением всех операторов отрицания внутрь конъюнкций и дизъ-юнкций.

Вариант 4
1. Определите предикат occurances(+Sub,+Term,-N), истинный, если число N равно числу вхождений подтерма Sub в терм Term. Предполагается, что терм Term не содержит переменных. 2. Разработайте программу "Советник по транспорту". Выберите либо сеть, состоящую из городов, либо транспортную сеть маршрутов поездов или авто-бусов в пределах одного города. Вы должны информировать систему о том, откуда и куда Вы собираетесь добраться, а система должна выдавать реко-мендации о том, какими поездами, автобусами, самолетами и т. д. Вам следует воспользоваться, чтобы добраться до пункта назначения.

Вариант 5
1. Напишите предикат p(+S, -L), который переводит предложение S, пред-ставленное строкой, в список атомов L. Например, p('gfrtyre hjnki <> pi 876 h', [ gfrtyre, hjnki, '<>', pi, 876,h]) выполнено. Указание. Воспользуйтесь предика-том name/2.
2. Множественное число большинства английских существительных получа-ется путем добавления буквы "s" к форме единственного числа. Но если су-ществительное заканчивается буквой "y", следующей за согласной, множе-ственное число образуется путем замены буквы "y" на сочетание "ies"; если же существительное заканчивается буквой "o", следующей за согласной, множе-ственное число образуется путем добавления сочетания "es". Напишите ут-верждения для предиката множественное_число/2, которые задают все эти правила. Указание. Воспользуйтесь предикатом name/2.

Вариант 6
1. Простейшая система кодирования сообщений заключается в замене каждой буквы сообщения на букву, находящуюся на N-й по отношению к ней позиции в алфавите. Например, для N=2 буква "a" заменяется на "c", буква "y" на "a" и т.д. Зная, что коды ASCII букв от "a" до "z" изменяются от 97 до 122, напишите процедуру для предиката шифратор/3, который берет шифруемое слово и целое число и выдает слово, представляющее шифр данного слова, полученный с помощью указанного метода.
Указание. Воспользуйтесь предикатом name/2.
2. Напишите предикат предшествует/2, который берет два атома в качестве своих аргументов и успешно согласуется, если первый из них в лексико-графическом порядке предшествует второму.
Указание. Воспользуйтесь предикатом name/2.

Вариант 7
1. Одним из примеров использования предиката name/2 может служить гене-рация новых атомов для представления вновь вводимых объектов, например, abc1, abc2, abc3 и т.д. Эти имена характеризуются тем, что все они состоят из корня, определяющего тип именуемого объекта, и целочисленного суффикса для различения объектов одного типа. Напишите программу
новое_имя(+X, -Y). Последовательность имен создается с помощью возвра-тов. Указание. Воспользуйтесь предикатом int_to_atom(+N,-X), который кон-вертирует натуральное число N в атом X. 2. Построить программу "сжать", назначение которой - преобразование ан-глийских слов в их "звуковой" код. Этот процесс предусматривает "сжатие" примерно одинаково звучащих слов в одинаковый их код - своего рода, аб-бревиатуру этих слов. Слова "сжимаются" в соответствии со следующими правилами:
- первая буква слова сохраняется;
- все последующие за ней гласные, а также буквы "h", "w" и "y" удаляются;
- сдвоенные буквы заменяются одиночными;
- закодированное слово состоит не более чем из четырех букв, остальные бук-вы удаляются.
Примеры: сжать(barrington, brng) и сжать(llewellyn, ln) - выполнено.
Указание. Воспользуйтесь предикатом name/2.