Иногда в ходе вычислений приходится снова и снова достигать одной и той же цели. Поскольку в системе Prolog отсутствует специальный механизм обнаружения подобных ситуаций, то повторяются целые последовательности вычислений.
В качестве примера рассмотрим программу вычисления Я-то числа Фибоначчи для заданного N. Ряд Фибоначчи имеет следующий вид: 1, 1, 2, 3, ъ, S, 13,...
Каждое число в этом ряде, за исключением первых двух, представляет собой сумму предыдущих двух чисел. Определим предикат liib; в, F)
для вычисления N-ro числа Фибоначчи, F, соответствующего заданному значению N. Эти числа можно получить последовательно, начиная с К = 1. В приведенной ниже программе fib вначале рассматриваются первые два числа Фибоначчи как два частных случая, а затем задается общее правило, касающееся ряда Фибоначчи.
fib E 1,1). % 1-е число Фибоначчи
fib(2, 1). % 2-е число Фибоначчи
fib(И, F):- % Ы-е числе Фибоначчи, N > 2
N > 2,
Ml is N - 1, Eifo(Ml, Fl!,
82 is N - 2, fib (N2, F2),
" is Fl + F2. % Ы-с числе - сумма дзух предшествующи к ему чисел
В данной программе часть вычислений почти всегда выполняется повторно. В этом можно легко убедиться, проведя трассировку выполнения следующей цели:
?- fib(6, F).
186 Часть I. Язык Prolog
На рис. 8.2 иллюстрируются характерные особенности вычислительного процесса. Например, третье число Фибоначчи, f (3), требуется в трех местах, и каждый раз повторяется одно и то же вычисление.
|
1 1
Рис. R.2. Вычисление 6-го числа Фибоначчи с помощью процедуры fib
Этого можно легко избежать, запоминая каждое вновь полученное число Фибоначчи. Идея состоит в том, что следует использовать встроенную процедуру asserta и вводить в базу данных такие (промежуточные) результаты как факты. Эти факты должны предшествовать другим предложениям, касающимся fib, чтобы можно было исключить необходимость в использовании общего правила в тех случаях, если результат уже известен. Модифицированная процедура fib2 отличается от процедуры fib только тем, что в ней предусмотрено внесение информации в базу данных следующим образом:
fib2! 1,1}. % 1-е число Фибоначчи
fib2(2, 1). % 2-е число Фибоначчи
fib2( N, F) :- % Н-е ЧИ С Л О Фибоначчи, Ы> 2
N > 2,
N1 is N - 1,
fib2(Ml, Fib
N2 is К - 2,
fib2(N2, F2),
| 1-е число |
F is Fl + F2,
asserta [ fxb2 [ H,
| :-■: |
К Запомнить
Эта программа предпринимает попытки найти ответ на любую цель fib2, вначале рассматривая сохраненные в базе данных факты, касающиеся этого отношения, и только после этого обращается к общему правилу. В результате после выполнения цели fib2 { N, Fi все числа Фибоначчи вплоть до N-го числа становятся зафиксиро-
Плава 8. Стиль и методы программирования
ванными. На рис, 8.3 показан процесс вычисления 6-го числа Фибоначчи процедурой fib2. Сравнение с рис. 8.2 показывает, что вычислительная сложность процедуры уменьшилась. Чем больше значение К, тем более существенным становится это уменьшение.
|
| 3(из базы данных) |
Рис. 8.3. Вычисление 6-ю числа Фибоначчи с помощью процедуры £1Ь2, которая запоминает предыдущие результаты; благодаря, этому сокращается объем вычислений, по сравнению с процедурой fib (см. рис. 8.2)
Внесение в базу данных промежуточных результатов, называемое также кэшированием, — это стандартный метод предотвращения повторных вычислений. Но следует отметить, что в случае чисел Фибоначчи можно применить более предпочтительный метод предотвращения повторных вычислений с использованием другого алгоритма, а не вносить а базу данных промежуточные результаты. Этот другой алгоритм приводит к созданию программы, которая является более трудной для понимания, но более эффективной при выполнении. В предыдущей версии М-е число Фибоначчи определялось как сумма своих двух предшественников, а для развертывания всего процесса вычислений "в направлении вниз", к двум первоначальным числам Фибоначчи применялись рекурсивные вызовы. Вместо этого можно организовать работу "в направлении вверх", начиная с двух исходных чисел и вычисляя значения ряда одно за другим, по возрастанию. При этом достаточно только во время остановиться после получения Ы-го значения. Основная часть работы в такой программе выполняется с помощью следующей процедуры: forwardfib(К, N, Fl, F2, F)
где F1 и F2 — Ш-1)-еи М-е числа Фибоначчи, a F - Ы-е число Фибоначчи. Принцип действия отношения forwardfхЬпоказан на рис, 8.4. В соответствии с этим рисунком процедура forwardfib находит последовательность преобразований, позволяю-
Часть I. Язык Prolog
щую достичь окончательной конфигурации (при которой М = N) из заданной начальной конфигурации. При вызове forwardfib все параметры, кроме F, должны быть конкретизированными, а К должно быть меньше или равно N. Соответствующая программа показана ниже.
| % Первые двачисла Фибоначчи равны 1 "? Н-е число Фибоначчи достигнуто % N-e число Фибоначчи еще не достигнуто |
Eib3! я, F):-
forwardfib(2, N, 1, 1, F). forwardfib! M, N, П., F2, F2}:-
М ?- N. forwardfib! И, N, F1, Г2, F):-
!•: <::,
HextM is И + 1,
HeJStF2 is Fl + F2,
forwardfib(NextM, И, F2, NextF2, F).
|
|
|
Начальная конфигурация. гдаМ = 2
Перевод
от конфигурации М
кМ+ 1
Конечная конфигурация. где М = N
Рис. 8.4. Соотношения между числами ряда Фибоначчи; конфигурация, обозначенная большим кружком, определяется тремя компонентами: индексом и и двумя последовательными числами Фибоначчи. f(M-l) и £<М)
Следует отметить, что в процедуре forwardfib применяется хвостовая рекурсия, а м, F1 и F2 представляют собой накапливающие параметры.
