Назад | Содержание| Вперёд 3. 4. Арифметические действия Пролог р...

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

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 div2.

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

            Х = 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

        Итак:

Для выполнения арифметических действий используются встроенные процедуры.

Арифметические операции необходимо явно запускать при помощи встроенной процедуры is. Встроенные процедуры связаны также с предопределенными операторами  +-,   */div  и   mod.

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

Значения арифметических выражений можно сравнивать с помощью таких операторов, как  <,   =<  и т.д. Эти операторы вычисляют значения своих аргументов.

Упражнения

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

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

Резюме

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

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

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

Новые операторы определяются с помощью директивы ор, в которой указываются его имя, тип и приоритет.

Как правило, с оператором не связывается никакой операции; оператор это просто синтаксическое удобство, обеспечивающее альтернативный способ записи термов.

Арифметические операции выполняются с помощью встроенных процедур. Вычисление арифметических выражений запускается процедурой is, а также предикатами сравнения <, =< и т.д.

Понятия, введенные в данной главе:

        список, голова списка, хвост списка

        списковая нотация

        операторы, операторная нотация

        инфиксные, префиксные и постфиксные

                операторы

        приоритет операторов

        арифметические встроенные процедуры

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









Главная | В избранное | Наш E-MAIL | Добавить материал | Нашёл ошибку | Наверх