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

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

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

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

несколькими предопределенными

операторами

+ сложение

- вычитание

* умножение

/ деление

mod модуль, остаток от целочисленного деления

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

?- Х = 1 + 2.

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

Х = 1 + 2

а не X = 3, как, возможно,ожидалось. Причина этого проста: выражение 1 + 2 обозначает лишь прологовский терм, в котором + является функтором, а 1 и 2 -его аргументами.

В вышеприведеннойцели нет ничего, что могло бы заставить

системувыполнить операцию сложения.

Для этого вПрологе

существует

специальныйоператор

(есть). Этотоператор заставит систему выполнить вычисление.Таким образом, чтобы правильно активизироватьарифметическую операцию, надо написать:

?- Х 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.

?- 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, а также предикатами сравнения <, =< и т.д.

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

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

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

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

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

операторы

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

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

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

Оглавление