Читаем Prolog полностью

        собрать( [X | Открытый], Закрытый, Спис) :-

                соседи( X, Соседи),

                                % Найти соседей Х

                конк( Соседи, Открытый, Открытый1),

                                % Поместить их в Открытый

                собрать( Открытый1, [X | Закрытый], Спис).

                                % Собрать остальные

Отношение конк - как всегда - отношение конкатенации списков.

8. 5. 3.    Повышение эффективности конкатенации списков за счет совершенствования структуры данных

До сих пор в наших программах конкатенация была определена так:

        конк( [ ], L, L).

        конк( [X | L1], L2, [X | L3] ) :-

                конк( L1, L2, L3 ).

Эта процедура неэффективна, если первый список - длинный. Следующий пример объясняет, почему это так:

        ?-  конк( [а, b, с], [d, e], L).

Этот вопрос порождает следующую последовательность целей:

        конк( [а, b, с], [d, e], L)

            конк( [b, с], [d, e], L')                 где L = [a | L']

                конк( [с], [d, e], L")                    где L' = [b | L"]

                    конк( [ ], [d, e], L'")                   где L" = [c | L''']

                        true             (истина)                   где L'" = [d, е]

Ясно, что программа фактически сканирует весь первый список, пока не обнаружит его конец.

А нельзя ли было бы проскочить весь первый список за один шаг и сразу подсоединить к нему второй список, вместо того, чтобы постепенно продвигаться вдоль него? Но для этого необходимо знать, где расположен конец списка, а следовательно, мы нуждаемся в другом его представлении. Один из вариантов - представлять список парой списков. Например, список

        [а, b, с]

можно представить следующими двумя списками:

        L1 = [a, b, c, d, e]

        L2 = [d, e]

Подобная пара списков, записанная для краткости как L1-L2, представляет собой "разность" между L1 и L2. Это представление работает только при том условии, что L2 - "конечный участок" списка L1. Заметим, что один и тот же список может быть представлен несколькими "разностными парами". Поэтому список [а, b, с] можно представить как

        [а, b, с]-[ ]

или

        [a, b, c, d, e]-[d, e]

или

        [a, b, c, d, e | T]-[d, e | T]

или

        [а, b, с | Т]-Т

где Т - произвольный список, и т.п. Пустой список представляется любой парой L-L.

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

        конкат( A1-Z1, Z1-Z2, A1-Z2).

Давайте используем конкат для конкатенации двух списков: списка [а, b, с], представленного парой [а, b, с | Т1]-Т1, и списка [d, e], представленного парой [d, e |  Т2]-Т2 :

        ?-  конкат( [а, b, с | Т1]-T1, [d, е | Т2]-Т2, L ).

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

        T1 = [d, e | Т2]

        L = [a, b, c, d, e | T2]-T2

Рис. 8. 1.  Конкатенация списков, представленных в виде разностных пар.

L1 представляется как A1-Z1, L2 как A2-Z2 и результат L3 - как A1-Z2.

При этом должно выполняться равенство Z1 = А2.

8. 5. 4.    Повышение эффективности зa счет добавления вычисленных фактов к базе данных

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

В качестве примера рассмотрим программу вычисления N-го числа Фибоначчи для некоторого заданного N. Последовательность Фибоначчи имеет вид:

        1,  1,  2,  3,  5,   8,  13,  ...

Каждый член последовательности, за исключением первых двух, представляет собой сумму предыдущих двух членов. Для вычисления N-гo числа Фибоначчи F определим предикат

        фиб( N, F)

Нумерацию чисел последовательности начнем с N = 1. Программа для фиб обрабатывает сначала первые два числа Фибоначчи как два особых случая, а затем определяет общее правило построения последовательности Фибоначчи:

        фиб( 1, 1).                             % 1-е число Фибоначчи

        фиб( 2, 1).                             % 2-е число Фибоначчи

        фиб( N, F) :-                         % N-е число Фиб., N > 2

                N > 2,

                N1 is N - 1, фиб( N1, F1),

                N2 is N - 2, фиб( N2, F2),

                F is F1 + F2.                % N-e число есть сумма двух

                                                    % предыдущих

Перейти на страницу:

Похожие книги

Слово о полку Игореве
Слово о полку Игореве

Исследование выдающегося историка Древней Руси А. А. Зимина содержит оригинальную, отличную от общепризнанной, концепцию происхождения и времени создания «Слова о полку Игореве». В книге содержится ценный материал о соотношении текста «Слова» с русскими летописями, историческими повестями XV–XVI вв., неординарные решения ряда проблем «слововедения», а также обстоятельный обзор оценок «Слова» в русской и зарубежной науке XIX–XX вв.Не ознакомившись в полной мере с аргументацией А. А. Зимина, несомненно самого основательного из числа «скептиков», мы не можем продолжать изучение «Слова», в частности проблем его атрибуции и времени создания.Книга рассчитана не только на специалистов по древнерусской литературе, но и на всех, интересующихся спорными проблемами возникновения «Слова».

Александр Александрович Зимин

Древнерусская литература / Прочая старинная литература / Прочая научная литература / Древние книги / Литературоведение / Научная литература