Назад | Содержание| Вперёд 8. 2. Как представлять себе программына Прологе...

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

8. 2. Как представлять себе программына Прологе

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

8. 2. 1. Использование рекурсии

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

(1) тривиальные, или"граничные" случаи;

(2) "общие" случаи, вкоторых решение получается из решений для (болеепростых) вариантов самой исходной задачи.

Этот метод мы использовали в Прологе постоянно.Рассмотрим еще один пример: обработка спискаэлементов, при которой каждый элементпреобразуется по одному и тому же правилу. Пустьэто будет процедура

преобрспис( Спис, F,НовСпиc)

где Спис - исходный список, F -правило преобразования (бинарное отношение), а НовСпиc- список всех преобразованных элементов. Задачупреобразования списка Спис можноразбить на два случая:

(1) Граничный случай: Спис= [ ]

Если Спис= [ ], то НовСпиc = [ ], независимо от F

(2) Общий случай: Спис= [X | Хвост]

Чтобыпреобразовать список вида [X | Хвост],необходимо:

преобразовать список Хвост; результат - НовХвост;

преобразовать элемент Х по правилу F;результат - НовХ;

результат преобразования всего списка - [НовХ| НовХвост].

Тот же алгоритм, изложенный на Прологе:

преобрспис( [ ], _, [ ]).

преобрспис( [Х |Хвост], F, [НовХ | НовХвост] :-

G =.. [F, X, НовХ],

саll( G),

пpeoбpcпиc( Хвост, F, НовХвост).

Одна из причин того, что рекурсия такестественна для определения отношений наПрологе, состоит в том, что объекты данных частосами имеют рекурсивную структуру. К такимобъектам относятся списки и деревья. Список либопуст (граничный случай), либо имеет голову ихвост, который сам является списком (общийслучай). Двоичное дерево либо пусто (граничныйслучай), либо у него есть корень и два поддерева,которые сами являются двоичными деревьями (общийслучай). Поэтому для обработки всего непустогодерева необходимо сначала что-то сделать с егокорнем, а затем обработать поддеревья.

8. 2. 2. Обобщение

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

восемьферзей( Поз)

Оно выполняется (истинно), если Поз -представленная тем или иным способом позиция,удовлетворяющая условию задачи. Можнопредложить следующую полезную идею: обобщитьзадачу, перейдя от 8 ферзей к произвольномуколичеству - N. Количество ферзей станетдополнительным аргументом:

n_ферзей( Поз, N)

Преимущество такого обобщения состоит в том,что отношение n_ферзей допускаетнепосредственную рекурсивную формулировку:

(1) Граничный случай: N = 0

Разместить 0 ферзей - тривиальная задача.

(2) Общий случай: N > 0

Для"безопасного" размещения N ферзейнеобходимо:

получить требуемое размещение для (N - 1) ферзей и

добавить оставшегося ферзя так, чтобы он не бил ни одного из уже поставленных ферзей.

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

восемьферзей( Поз) :-n_ферзей( Поз, 8)

8. 2. 3. Использование рисунков

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

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

(1) Пролог особеннохорошо приспособлен для задач, в которыхфигурируют объекты и отношения между ними. Частотакие задачи естественно иллюстрироватьграфами, в которых узлы соответствуют объектам, адуги - отношениям.

(2) Естественнымнаглядным изображением структурных объектовПролога являются деревья.

(3) Декларативныйхарактер пролог-программ облегчает переводграфического представления на Пролог. Впринципе, порядок описания "картинки" неиграет роли, мы просто помещаем в программу то,что видим, в произвольном порядке. (Возможно, чтоиз практических соображений этот порядоквпоследствии придется подправить с цельюповысить эффективность программы.)

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

Оглавление