Программирование на языке пролог (ЛП)

Мы лишь затронули вопрос о возможных способах организации поиска по графу. Сведения о том, как осуществлять поиск по графу с использованием более эффективных критериев, чем «первый лучший», можно найти в литературе по искусственному интеллекту. Например: Nilsson N. Principles of Artificial Intelligence,Springer-Verlag, 1982 [10]и Winstone P. Artificial Intelligence,(second edition), Addison-Wesley, 1984. ^[11]

7.10. Просеивай Двойки, Просеивай Тройки

Просеивай Двойки,
Просеивай Тройки,
Эратосфена Решето,
Пусть все кратные им отсеем,
Простые числа получим зато.

Аноним

Простое число – это целое положительное число, которое делится нацело только на 1 и на само себя. Например, число 5 – простое, а число 15 – нет, поскольку оно делится на 3. Один из методов построения простых чисел называется «решетом Эратосфена». Этот метод, «отсеивающий» простые числа, не превышающие N, работает следующим образом:

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.

7.11. Символьное дифференцирование

Символьным дифференцированием в математике называется операция преобразования одного арифметического выражения в другое арифметическое выражение, которое называется производной.Пусть 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)