У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

1. Поместить все числа от 2 до N в решето.

2. Выбрать и удалить из решета наименьшее число.

3. Включить это число в список простых.

4. Просеять через решето (удалить) все числа, кратные этому числу.

5. Если решето не пусто, то повторить шаги 2-5.

Чтобы перевести эти правила на Пролог, мы определим предикат целыедля получения списка целых чисел, предикат отсеятьдля проверки каждого элемента решета и предикат удалитьдля создания нового содержимого решета путем удаления из старого всех чисел, кратных выбранному числу. Это новое содержимое опять передается предикату отсеять.Предикат простые- это предикат самого верхнего уровня, такой что простые(N, L)конкретизирует Lсписком простых чисел, заключенных в диапазоне от 1до Nвключительно.

простые(Предел,Рs):- целые(2,Предел,Is),отсеять(Is,Рs).

целые (Min,Max,[Min|Oct]):-Min=‹Max,!, М is Min+1,целые(М,Мах,Ост).

целые(_,_,[]).

отсеять([],[]).

отсеять([I|Is],[I|Ps]):-удалить(I,Is,Нов),отсеять(Нов,Рs).

удалить(Р,[],[]).

удалить (P,[I|Is],[I|Nis]):-not(0 is I mod Р),!,удалить(Р,Is,Nis).

удалить (P,[I|Is],Nis):-0 is I mod Р,!,удалить(Р,Is,Nis).

Продолжая эту арифметическую тему, рассмотрим Пролог-программу, реализующую рекурсивную формулировку алгоритма Евклида для нахождения наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) двух чисел. Целевое утверждение нод(I,J,K)доказуемо, если Kявляется наибольшим общим делителем чисел Iи J. Целевое утверждение нок(I,J,K)доказуемо, если Kявляется наименьшим общим кратным чисел Iи J:

нод(I,0,I).

нод(I,J,K):- R is I mod J, нод(J,R,K).

нок(I,J,K):- нод(I,J,R), K is (I*J)/R.

Заметим, что из-за особенностей способа вычисления остатка эти предикаты не являются «обратимыми». Это означает, что для того чтобы они работали, необходимо заблаговременно конкретизировать переменные Iи J.

Упражнение 7.10.Если числа X , Y и Z таковы, что квадрат Z равен сумме квадратов X и Y (т. е. если Z ²= X ²+ Y ²), то про такие числа говорят, что они образуют Пифагорову тройку. Напишите программу, порождающую Пифагоровы тройки. Определите предикат pythagтакой что, задав вопрос

?- pythag(X,Y,Z).

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

Символьным дифференцированием в математике называется операция преобразования одного арифметического выражения в другое арифметическое выражение, которое называется производной. Пусть U обозначает арифметическое выражение, которое может содержать переменную х. Производная от U по х записывается в виде dU/dx и определяется рекурсивно с помощью некоторых правил преобразования, применяемых к U. Вначале следуют два граничных условия. Стрелка означает «преобразуется в»; U и V обозначают выражения, а с – константу:

dc/dx → 0

dx/dx → 1

d(-U)/dx → -(dU/dx)

d(U+V)/dx → dU/dx+dV/dx

d(U-V)/dx → dU/dx-dV/dx

d(cU)/dx → c(dU/dx)

d(UV)/dx → U(dV/dx) + V(dU/dx)

d(U/V)dx → d(UV -1)/dx

d(U c)/dx → cU c - l(dU/dx)

d(lnU)/dx → U -1(dU/dx)

Этот набор правил легко написать на Прологе, поскольку мы можем представить арифметические выражения как структуры и использовать знаки операций как функторы этих структур. Кроме того, сопоставление целевого утверждения с заголовком правила мы можем использовать как сопоставление образцов. Рассмотрим цель d(E,X, F), которая считается согласованной, когда производная выражения Eпо константе [12] Имеется в виду константа в смысле Пролога. - Прим. ред. Xесть выражение F. Помимо знаков операций +, -, *, /, которые имеют встроенные определения, нам нужно определить операцию ^, такую, что X^Yозначаете x y , а также одноместную операцию ~, такую что ~Хозначает «минус X». Эти определения операций введены исключительно для того, чтобы облегчить распознавание синтаксиса выражений. Например, после того как dопределен, можно было бы задать следующие вопросы:

?- d(x+1,x,X).

X = 1+0

?- d(x*x-2,x,X).

X = х*1+1*х-0

Заметим, что само по себе простое преобразование одного выражения в другое (на основе правил) не всегда дает результат в приведенной (упрощенной) форме. Приведение результата должно быть записано в виде отдельной процедуры (см. разд. 7.12). Программа дифференцирования состоит из определений дополнительных операций и построчной трансляции приведенных выше правил преобразования в утверждения Пролога: