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

3. 4.    Арифметические действия

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

        +    сложение
        -    вычитание
        *    умножение
        /    деление
        mod     модуль, остаток от целочисленного деления

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

        ?-  Х = 1 + 2.

Пролог-система "спокойно" ответит

             Х = 1 + 2

а не  X = 3,  как, возможно, ожидалось. Причина этого проста: выражение  1 + 2   обозначает лишь прологовский терм, в котором   +  является функтором, а  1  и  2  - его аргументами. В вышеприведенной цели нет ничего, что могло бы заставить систему выполнить операцию сложения. Для этого в Прологе существует специальный оператор  is   (есть). Этот оператор заставит систему выполнить вычисление. Таким образом, чтобы правильно активизировать арифметическую операцию, надо написать:

        ?-  Х  is  1 + 2.

Вот теперь ответ будет

             Х = 3

Сложение здесь выполняется специальной процедурой, связанной с оператором   +.    Мы будем называть такие процедуры встроенными.

В Прологе не существует общепринятой нотации для записи арифметических действий, поэтому в разных реализациях она может слегка различаться. Например, оператор  '/'  может в одних реализациях обозначать целочисленное деление, а в других - вещественное. В данной книге под  '/'   мы подразумеваем вещественное деление, для целочисленного же будем использовать оператор div.   В соответствии с этим, на вопрос

        ?- Х  is  3/2,
            Y  is  3 div 2.

ответ должен быть такой:

            Х = 1.5
            Y = 1

Левым аргументом оператора  is   является простой объект. Правый аргумент - арифметическое выражение, составленное с помощью арифметических операторов, чисел и переменных. Поскольку оператор  is   запускает арифметические вычисления, к моменту начала вычисления этой цели все ее переменные должны быть уже конкретизированы какими-либо числами. Приоритеты этих предопределенных арифметических операторов (см. рис. 3.8) выбраны с таким расчетом, чтобы операторы применялись к аргументам в том порядке, который принят в математике. Чтобы изменить обычный порядок вычислений, применяются скобки (тоже, как в математике). Заметьте, что  +,  -,  *,    /  и  div  определены, как   yfx,  что определяет порядок их выполнения слева направо. Например,

        Х  is  5 - 2 - 1

понимается как

        X  is  (5 - 2) - 1

Арифметические операции используются также и при сравнении числовых величин. Мы можем, например, проверить, что больше - 10000 или результат умножения 277 на 37, с помощью цели

        ?-  277 * 37 > 10000.
        yes
            (да)

Заметьте, что точно так же, как и is,   оператор  '>'  вызывает выполнение вычислений.

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

        ?-  рожд( Имя, Год),
             Год >= 1950,
             Год <= 1960.

Ниже перечислены операторы сравнения:

        Х    >     Y                    Х больше Y

        Х    <     Y                    Х меньше Y

        Х    >=     Y                  Х больше или равен Y

        Х    =<     Y                  Х меньше или равен Y

        Х    =:=     Y                 величины Х и Y совпадают (равны)

        Х    =\=     Y                 величины Х и Y не равны

Обратите внимание на разницу между операторами сравнения '=' и '=:=', например, в таких целях как X = Y и Х =:= Y. Первая цель вызовет сопоставление объектов Х и Y, и, если Х и Y сопоставимы, возможно, приведет к конкретизации каких-либо переменных в этих объектах. Никаких вычислений при этом производиться не будет. С другой стороны, Х =:= Y вызовет арифметическое вычисление и не может привести к конкретизации переменных. Это различие можно проиллюстрировать следующими примерами:

        ?-    1 + 2 =:= 2 + 1.
        yes

        >-    1 + 2 = 2 + 1.
        no

        ?-    1 + А = В + 2.
        А = 2
        В = 1

Давайте рассмотрим использование арифметических операций на двух простых примерах. В первом примере ищется наибольший общий делитель; во втором - определяется количество элементов в некотором списке.

Если заданы два целых числа Х и Y, то их наибольший общий делитель Д можно найти, руководствуясь следующими тремя правилами:

(1)        Если Х и Y равны, то Д равен X.

(2)        Если Х > Y, то Д равен наибольшему общему делителю Х разности Y - X.

(3)        Если Y < X, то формулировка аналогична правилу (2), если Х и Y поменять в нем местами.

На примере легко убедиться, что эти правила действительно позволяют найти наибольший общий делитель. Выбрав, скажем, Х = 20 и Y = 25, мы, руководствуясь приведенными выше правилами, после серии вычитаний получим Д = 5.

Эти правила легко сформулировать в виде прологовской программы, определив трехаргументное отношение, скажем

        нод( X , Y, Д)

Тогда наши три правила можно выразить тремя предложениями так:

        нод( X, X, X).

        нод( X, Y, Д) :-
              Х < Y,
              Y1 is Y - X,
              нод( X, Y1, Д),

        нод( X, Y, Д) :-
              Y < X,
              нод( Y, X, Д).

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

        X1 is Х - Y,
        нод( X1, Y, Д)

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

        длина( Список, N)

которая будет подсчитывать элементы списка Список и конкретизировать N полученным числом. Как и раньше, когда речь шла о списках, полезно рассмотреть два случая:

(1)        Если список пуст, то его длина равна 0.

(2)        Если он не пуст, то Список = [Голова1 | Хвост] и его длина равна 1 плюс длина хвоста Хвост.

Эти два случая соответствуют следующей программе:

        длина( [ ], 0).

        длина( [ _ | Хвост], N) :-
              длина( Хвост, N1),
              N is 1 + N1.

Применить процедуру длина можно так:

        ?- длина( [a, b, [c, d], e], N).

        N = 4

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

        N is 1 + N1

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

Интересно посмотреть, что произойдет, если мы попытаемся запрограммировать отношение длина без использования is. Попытка может быть такой:

        длина1( [ ], 0).

        длина1( [ _ | Хвост], N) :-
              длина1( Хвост, N1),
              N = 1 + N1.

Теперь уже цель

        ?- длина1( [a, b, [c, d], e], N).

породит ответ:

        N = 1+(1+(1+(1+0)))

Сложение ни разу в действительности не запускалось и поэтому ни разу не было выполнено. Но в процедуре длина1, в отличие от процедуры длина, мы можем поменять местами цели во втором предложении:

        длина1( _ | Хвост], N) :-
              N = 1 + N1,
              длина1( Хвост, N1).

Такая версия длина1 будет давать те же результаты, что и исходная. Ее можно записать короче:

        длина1( [ _ | Хвост], 1 + N) :-
              длина1( Хвост, N).

и она и в этом случае будет давать те же результаты. С помощью длина1, впрочем, тоже можно вычислять количество элементов списка:

        ?- длина( [а, b, с], N), Длина is N.

        N = 1+(1+(l+0))
        Длина = 3

        Итак:

Упражнения

3. 16.    Определите отношение

        mах( X, Y, Мах)

так, чтобы Мах равнялось наибольшому из двух чисел Х и Y.

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

3. 17.    Определите предикат

        максспис( Список, Мах)

так, чтобы Мах равнялось наибольшему из чисел, входящих в Список.

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

3. 18.    Определите предикат

        сумспис( Список, Сумма)

так, чтобы Сумма равнялось сумме чисел, входящих в Список.

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

3. 19.    Определите предикат

        упорядоченный( Список)

который принимает значение истина, если Список представляет собой упорядоченный список чисел. Например: упорядоченный [1, 5, 6, 6, 9, 12] ).

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

3. 20.    Определите предикат

        подсумма( Множ, Сумма, ПодМнож)

где Множ это список чисел, Подмнож подмножество этих чисел, а сумма чисел из ПодМнож равна Сумма. Например:

        ?- подсумма( [1, 2. 5. 3. 2], 5, ПМ).

        ПМ = [1, 2, 2];
        ПМ = [2, 3];
        ПМ = [5];
        . . .

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

3. 21.    Определите процедуру

        между( Nl, N2, X)

которая, с помощью перебора, порождает все целые числа X, отвечающие условию Nl <=X <=N2.

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

3. 22.    Определите операторы 'если', 'то', 'иначе' и ':=" таким образом, чтобы следующее выражение стало правильным термом:

        если Х > Y то Z := Х иначе Z := Y

Выберите приоритеты так, чтобы  'если' стал главным функтором. Затем определите отношение 'если' так, чтобы оно стало как бы маленьким интерпретатором выражений типа 'если-то-иначе'. Например, такого

        если Вел1 > Вел2 то Перем := Вел3
        иначе Перем := Вел4

где Вел1, Вел2, Вел3 и Вел4 - числовые величины (или переменные, конкретизированные числами), а Перем - переменная. Смысл отношения 'если' таков: если значение Вел1 больше значения Вел2, тогда Перем конкретизируется значением Вел3, в противном случае - значением Вел4. Приведем пример использования такого интерпретатора:

        ?-  Х = 2, Y = 3,
             Вел2 is 2*X,
             Вел4 is 4*X,
             Если Y>Вел2 то Z:=Y иначе Z:=Вел4.

             Если Z > 5 то W := 1 иначе W :=0.

        Х = 2
        Y = 3
        Z = 8
        W = 1

        Вел2 = 4
        Вел4 = 8

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

Резюме


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