14. Двоичные деревья, двоичные справочники.

Напишем предикат, подсчитывающий общее количество вершин дерева. У него будет два параметра. Первый (входной) параметр - дерево, второй (выходной) - количество вершин в дереве.

Как всегда, пользуемся рекурсией. Базис: в пустом дереве количество вершин равно нулю. Шаг рекурсии: чтобы посчитать количество вершин дерева, нужно посчитать количество вершин в левом и правом поддереве, сложить полученные числа и добавить к результату единицу (посчитать корень дерева ).

15. Решение логических задач, головоломок.

Одно из основных применений языка Пролог – решение задач логики, головоломок, игровых задач.

Один из подходов решения логических задач рассмотрим на следующем примере.

Три друга заняли первое, второе и третье места в соревнованиях универсиады. Друзья – разной национальности, зовут их по-разному, и любят они разные виды спорта.

Майкл предпочитает баскетбол и играет лучше, чем американец. Израильтянин Саймон играет лучше теннисиста. Игрок в крокет занял первое место.

Кто является австралийцем? Каким спортом занимается Ричард?

Подобные логические головоломки изящно решаются посредством конкретизации значений подходящей структуры данных и выделения значения, приводящего к решению. Каждый ключ к решению преобразуется в факт относительно структуры данных. Это может быть сделано с использованием абстракции данных до определения точной формы структуры данных. Проанализируем первый ключ к разгадке: «Майкл предпочитает баскетбол и играет лучше, чем американец». Очевидно, речь идет о двух разных людях. Одного зовут Майкл, и занимается он баскетболом, в то время как второй – американец. Кроме того, Майкл лучше играет в баскетбол, чем американец. Предположим, что Друзья – структура данных, подлежащая конкретизации, тогда искомый ключ может быть выражен следующей конъюнкцией целей:

играет_лучше(Мужчина_1, Мужчина_2, Друзья),

имя(Мужчина_1, Майкл), спорт(Мужчина_1, баскетбол),

национальность(Мужчина_2, американец).

Аналогично второй ключ можно представить конъюнкцией целей:

играет_лучше(Мужчина_1, Мужчина_2, Друзья),

имя((Мужчина_1,Саймон),

национальность(Мужчина_1,израильтянин),

спорт(Мужчина_2, теннис).

Наконец, третий ключ к разгадке выразится следующим образом:

первый(Друзья, Мужчина), спорт(Мужчина, крокет).

Базовый предикат для решения головоломок:

решить_головоломку(Головоломка, Решение)., где Решение является решением головоломки Головоломка. Головоломка представляется структурой головоломка(Ключи, Вопросы, Решение). Общую схему решения головоломки можно представить следующим образом:

решить_головоломку(головоломка(Ключи,Вопросы,Решение), Решение):- решить(Ключи), решить(Вопросы).

решить([]).

решить([Ключ|Ключи]):-решить(Ключ).

Каждый человек имеет три атрибута и представляется структурой вида: друг(Имя, Страна, Спорт)., а в качестве структуры данных последовательность трех элементов, представляющим список: [друг(N1,C1,S1), друг(N2, C2, S2), друг(N3, C3, S3)]. Ключи и вопросы в данном примере предлагается составить самостоятельно. Для проверки: Майкл – австралиец, а Ричард играет в теннис.

Эта схема решения дает представление об общем подходе для решения головоломок. Часто подобную схему называют решателем головоломок.