Назад | Содержание| Вперёд Глава 4 ИСПОЛЬЗОВАНИЕ СТ...

Назад | Содержание| Вперёд

Глава 4

ИСПОЛЬЗОВАНИЕ СТРУКТУР:

ПРИМЕРЫ

Структуры данных вместе с сопоставлением,автоматическими возвратами и арифметикойпредставляют собой мощный инструментпрограммирования. В этой главе мы расширимнавыки использования этого инструмента припомощи следующих учебных программных примеров:получение структурированной информации из базыданных, моделирование недетерминированногоавтомата, планирование маршрута поездки ирешение задачи о расстановке восьми ферзей нашахматной доске. Мы увидим также, как в Прологереализуется принцип абстракции данных.

4. 1. Получение структурированнойинформации из базы данных

Это упражнение развивает навыки представленияструктурных объектов данных и управления ими.Оно показывает также, что Пролог являетсяестественным языком запросов к базе данных.

База данных может быть представлена на Прологев виде множества фактов. Например, в базе данных осемьях каждая семья может описываться однимпредложением. На рис. 4.1 показано, как информациюо каждой семье можно представить в видеструктуры. Каждая семья состоит из трехкомпонент: мужа, жены и детей. Посколькуколичество детей в разных семьях может бытьразным, то их целесообразно представить в видесписка, состоящего из произвольного числаэлементов. Каждого члена семьи в свою очередьможно представить структурой, состоящей из

Рис. 4. 2. Описанияобъектов по их структурным свойствам: (а) любая семья Армстронгов; (b) любая семья,имеющая ровно трех детей; (с) любая семья,имеющая по крайней мере три ребенка.Структура (с) дает возможность получитьимя и фамилию жены конкретизацией переменных Имя и Фамилия.

Можно создать набор процедур, который служил быутилитой, делающей взаимодействие с нашей базойданных более удобным. Такие процедуры являлисьбы частью пользовательского интерфейса. Вотнекоторые полезные процедуры для нашей базыданных:

муж( X) :- % X - муж

семья(X, _, _ ).

жена( X) :- % X - жена

семья(_, X, _ ).

ребенок( X) :- % X - ребенок

семья(_, _, Дети),

принадлежит( X, Дети).

принадлежит( X, [X | L]).

принадлежит( X, [Y | L ]):-

принадлежит( X, L).

существует(Членсемьи) :-

% Любой член семьи в базе данных

муж(Членсемьи);

жена(Членсемьи);

ребенок(Членсемьи).

дата рождения(Членсемьи( _, _, Дата, _ ), Дата).

доход( Членсемьи( _,_, _, работает( _, S) ), S).

% Доход работающего

доход( Членсемьи( _,_, _, неработает), 0).

% Доход неработающего

Этими процедурами можно воспользоваться,например, в следующих запросах к базе данных:

Найти имена всех людей из базы данных:

?- существует( членсемьи( Имя,Фамилия, _, _ )).

Найти всех детей, родившихся в 1981 году:

?- ребенок( X), датарождения( X, дата( _, _, 1981) ).

Найти всех работающих жен:

?- жена( членсемьи( Имя, Фамилия, _, работает( _, _ ))).

Найти имена и фамилии людей, которые не работают и родились до 1963 года:

?- существует членсемьи( Имя, Фамилия, дата( _, _, Год), неработает) ),

Год < 1963.

Найти людей, родившихся до 1950 года, чей доход меньше, чем 8000:

?- существует( Членсемьи),

датарождения( Членсемьи, дата( _, _, Год) ),

Год < 1950,

доход( Членсемьи, Доход),

Доход < 8000.

Найти фамилии людей, имеющих по крайней мере трех детей:

?- семья( членсемьи( _, Фамилия, _, _ ), _, [ _, _, _ | _ ]).

Для подсчета общего дохода семья полезноопределить сумму доходов людей из некоторогосписка в виде двухаргументного отношения:

общий( Список_Людей,Сумма_их_доходов)

Это отношение можно запрограммировать так:

общий( [ ], 0). % Пустой список людей

общий( [ Человек |Список], Сумма) :-

доход( Человек, S),

% S - доход первого человека

общий(Список, Остальные),

% Остальные - сумма доходов остальных

Суммаis S + Остальные.

Теперь общие доходы всех семей могут бытьнайдены с помощью вопроса:

?- семья( Муж,Жена, Дети),

общий([Муж, Жена | Дети], Доход).

Пусть отношение длина подсчитывает количествоэлементов списка, как это было определено в разд.3.4. Тогда мы можем найти все семьи, которые имеютдоход на члена семьи, меньший, чем 2000, при помощивопроса:

?- семья( Муж,Жена, Дети),

общий( [Муж, Жена | Дети], Доход),

длина( [Муж, Жена | Дети], N),

Доход/N <2000.

Упражнения

4. 1. Напишите вопросы дляпоиска в базе данных о семьях.

(а) семей без детей;

(b) всех работающих детей;

(с) семей, где женаработает, а муж нет,

(d) всех детей, разница ввозрасте родителей которых составляет не менее 15лет.

Посмотреть ответ

4. 2. Определите отношение

близнецы( Ребенок1,Ребенок2)

для поиска всех близнецов в базе данных осемьях.

Посмотреть ответ

Назад | Содержание| Вперёд

Оглавление