- •Оглавление
- •Логическое программирование. Язык Prolog.
- •1. Предикаты Пример 1.1. Максимум из двух чисел
- •Пример 5.2. Вычисление факториала
- •6. Хвостовая рекурсия Пример 6.1. Вычиление факториала с с использованием хвостовой рекурсии
- •Пример 6.2. Вычисление чисел Фибоначчи
- •Пример 7.4. Обращение списка
- •Пример 7.5. Среднее арифметическое элементов списка.
- •7. Обработка списков Пример 7.1. Вычисление длины списка
- •Пример 7.2. Проверка принадлежности элемента списку
- •Пример 7.3. Соединение двух списков
- •8. Сортировка списков Пример 8.1. Пузырьковая сортировка
- •Пример 8.2. Сортировка вставкой
- •Пример 8.3. Сортировка выбором
- •9. Строки
- •Пример 9.3. Преобразование строки в список символов
- •Пример 9.4. Подсчет кол-ва вхождений заданного символа в строку
- •Пример 9.6. Замена заданного символа в строке – на другой
- •Пример 9.7. Удаление части строки
- •Пример 9.8. Копирование части строки
- •Пример 9.9. Вставка одной строки внутрь другой
- •10. Множества Пример 10.1. Превращение произвольного списка в множество
- •Пример 10.2. Операция объединения двух множеств.
- •Пример 10.3. Пересечение множеств
- •Пример 10.4. Разность множеств
- •Пример 10.5. Проверка, является ли одно множество подмножеством другого.
- •Пример 10.6. Предикат, реализующий отношение равенства двух множеств.
- •Пример 10.7. Определение собственного подмножества множества
- •Пример 10.8. Симметричная разность
- •Пример 10.9. Дополнение множества
- •11. Деревья Пример 11.1. Принадлежность элемента дереву
- •Пример 11.2. Замена заданного значения на другое в дереве
- •Пример 11.3. Подсчет общего количества вершин дерева
- •Пример 11.4. Подсчет количества листьев (узлов без сыновей)
- •Пример 11.5. Подсчет суммы чисел в вершинах дерева
- •Пример 11.6. Предикат, вычисляющий высоту дерева
- •Пример 11.7. Проверка принадлежности значения двоичному справочнику .
- •Пример 11.8. Добавление элемента в двоичный справочник
- •Пример 11.9. Генератор случайного двоичного справочника из чисел
- •Пример 11.10. Удаление заданного значения из двоичного справочника
- •Пример 11.11. Преобразование произвольного списка в двоичный справочник
- •Пример 11.12. Предикат, сворачивающий заданный двоичный справочник в список
- •12. Базы знаний Пример 12.1. Вычисление чисел Фибоначчи с запоминанием результатов
- •13. Логические задачи (головоломки) Пример 13.1. Перестановка кубиков
- •Пример 13.2. Ханойский башни
- •Пример 13.3. Волк, коза и капуста
- •Пример 13.4. Побег из Зурга
Пример 11.4. Подсчет количества листьев (узлов без сыновей)
Предикат будет иметь два параметра. Входной - исходное дерево , выходной - количество листьев дерева , находящегося в первом параметре.
Так как в пустом дереве нет вершин, в нем нет и вершин, являющихся листьями . Это первый базис рекурсии. Второй базис будет заключаться в очевидном факте, что дерево , состоящее из одной вершины, имеет ровно один лист . Шаг: для того, чтобы посчитать количество листьев дерева , нужно просто сложить количество листьев в левом и правом поддереве.
/* в пустом дереве листьев нет */
tree_leaves(nil,0).
/* в дереве с одним корнем - один лист */
tree_leaves(tr(_, nil, nil),1):- !.
tree_leaves(tr(_,L,R),N):-
/* N1 - количество листьев в левом поддереве */
tree_leaves(L, N1),
/* N2 - количество листьев в правом поддереве */
tree_leaves(R, N2),
/* Находим сумму в левом и правом поддереве */
N is N1 + N2.
?- tree_leaves(tr(2, tr(7,nil, nil), tr(3, tr(4,nil,nil), tr(1,nil,nil))), N).
N = 3
Пример 11.5. Подсчет суммы чисел в вершинах дерева
Предикат будет иметь два аргумента. Первый - исходный список, второй - сумма чисел, находящихся в вершинах дерева , расположенного в первом аргументе.
Идея реализации будет очень простой и немного похожей на подсчет количества вершин. Базис рекурсии: сумма элементов пустого дерева равна нулю, потому что в пустом дереве нет элементов. Чтобы подсчитать сумму значений, находящихся в вершинах непустого дерева , нужно сложить сумму элементов, хранящихся в левом и правом поддереве, и не забыть добавить корневое значение.
/* в пустом дереве вершин нет */
tree_sum(nil, 0).
tree_sum(tr(X,L,R),N):-
/* N1 - сумма элементов левого поддерева */
tree_sum(L, N1),
/* N2 - сумма элементов правого поддерева */
tree_sum(R, N2),
/* складываем N1, N2 и корневое значение */
N is N1+N2+X.
% ?- tree_sum(tr(2, tr(7,nil, nil), tr(3, tr(4,nil,nil), tr(1,nil,nil))), N).
N = 17
Пример 11.6. Предикат, вычисляющий высоту дерева
Высота дерева - это наибольшая длина пути от корня дерева до его листа . Предикат будет иметь два параметра. Первый (входной) - дерево , второй (выходной) - высота дерева , помещенного в первый параметр.
Базис рекурсии будет основан на том, что высота пустого дерева равна нулю. Шаг рекурсии - на том, что для подсчета высоты всего дерева нужно найти высоты левого и правого поддеревьев, взять их максимум и добавить единицу (учесть уровень, на котором находится корень дерева ). Предикат max (или max2), вычисляющий максимум из двух элементов, был разработан нами еще в третьей лекции. Воспользуемся им при вычислении высоты дерева .
Получается следующее.
/* Высота пустого дерева равна нулю */
tree_height(nil, 0).
tree_height(tr(_,L,R),D) :-
tree_height(L,D1), /* D1 - высота левого поддерева */
tree_height(R,D2), /* D2 - высота правого поддерева */
max(D1,D2,D_M), /* D_M - максимум из высот левого и правого поддеревьев */
D is D_M+1. /* D - высота дерева, получается увеличением D_M на единицу*/
?- tree_height(tr(2, tr(7,nil, nil), tr(3, tr(4,nil,nil), tr(1,nil,nil))), N).
N = 3 ;
