Управление поиском с возвратом: предикаты fail и отсечения.

fail – это тождественно-ложный предикат, искусственно создающий ситуацию неуспеха. После выполнения этого предиката управление передается в точку отката и поиск продолжается. Использование предиката fail позволяет найти все решения задачи.

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

Например, p:- p1, p2,!, p3.

Если достигнуты цели p1 и p2, то возврат к ним для поиска новых решений невозможен.

 

Пример 1

База данных содержит факты вида: student(имя, курс). Создать проект, позволяющий сформировать список студентов 1-го курса.

Решение:

PREDICATES

student(symbol,integer)

spisok

CLAUSES

student(vova,3).

student(lena,1).

student(dima,1).

student(ira,2).

student(marina,1).

spisok:-student(X,1),write(X),nl,fail.

GOAL

write("Список студентов 1-курса"),nl,spisok.

Результат выполнения программы:

Список студентов 1-курса

lena

dima

marina

Пример 2

База данных содержит факты вида father(name, name). Создать проект, позволяющий определить кто чей отец.

Решение:

DOMAINS

name=symbol

PREDICATES

father (name, name)

everybody

CLAUSES

father ("Павел", "Петр").

father ("Петр", "Михаил").

father ("Петр", "Иван").

everybody:- father (X, Y),

write(X," - это отец",Y,"а"),nl,

fail.

GOAL

everybody.

Результат выполнения программы:

Павел - это отец Петра

Петр - это отец Михаила

Петр - это отец Ивана

Пример 3

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

а) вывести всю информацию из справочника.

Решение:

DOMAINS

nom=integer

p, t=string

PREDICATES

poezd(nom,p,t)

CLAUSES

poezd(233,moskva,"12-30").

poezd(257,moskva,"22-40").

poezd(133,armavir,"10-20").

poezd(353,armavir,"20-40").

poezd(353,adler,"02-30").

poezd(413,adler,"11-10").

poezd(256,piter,"21-30").

GOAL

write(" Расписание поездов"), nl,

write("Номер Пункт прибытия Время отправления"),

nl, poezd(N,P,T), write(N," ",P," ",T),nl,fail.

Результат выполнения программы

Расписание поездов

Номер Пункт прибытия Время отправления

233 moskva 12-30

257 moskva 22-40

133 armavir 10-20

353 armavir 20-40

353 adler 02-30

413 adler 11-10

256 piter 21-30

 

б) организовать поиск поезда по пункту назначения.

Решение:

GOAL

write (" Пункт назначения:"), Readln(P), nl,

write ("Номер Время отправления"), nl,

poezd(N,P,T), write(N," ",T), nl, fail.

 

Комментарий: Readln –стандартный предикат ввода строкового значения

Результат выполнения программы

Пункт назначения:armavir

 

Номер Время отправления

133 10-20

353 20-40

в) вывести информацию о поездах, отправляющихся в заданный временной промежуток

Решение:

GOAL

write(" Время отправления:"),nl,

write("c..."), Readln(T1),

write("до..."), Readln(T2), nl,

write("Номер Пункт назначения Время отправления"),

nl,poezd(N,P,T),T>=T1,T<=T2,write(N," ",P," ", T),

nl, fail.

 

Результат выполнения программы

Время отправления:

c...10-00

до...15-00

 

Номер Пункт назначения Время отправления

233 moskva 12-30

133 armavir 10-20

413 adler 11-10

Пример 4

Имеется база данных, содержащая данные о спортсменах: имя и вид спорта. Определить возможные пары одного из спортсменов-теннисистов с другими теннисистами.

Решение:

DOMAINS

имя,вид_сп=string

PREDICATES

играет(имя,вид_сп)

спис_спортс

CLAUSES

играет("Саша",теннис).

играет("Аня",волейбол).

играет("Олег",футбол).

играет("Коля",теннис).

играет("Саша",футбол).

играет("Андрей",теннис).

спис_спортс:- играет(X,теннис),!,играет(Y,теннис),

X<>Y,write(X,"-",Y),nl,fail.

GOAL

write("Пары теннисистов"),nl,

спис_спортс.

Результат выполнения программы:

Пары теннисистов

Саша-Коля

Саша-Андрей

 

Пример 5

Студенту в зависимости от набранной в процессе обучения суммы баллов Z присваивается квалификация:

магистр (М), если 80<=Z<=100

специалист (S), если 60<= Z< 80

бакалавр (B), если 40<= Z< 60

неудачник (N), если 0<=Z< 40

Составить программу, которая определит квалификацию в зависимости от введенного значения Z

Решение:

Для решения задачи составим правило grade, устанавливающее связь между количеством баллов (z) и квалификацией (r). Правило состоит из нескольких частей. Первые две части обеспечивают проверку недопустимых значений Z с выводом соответствующего сообщения. Остальные части правила определяют квалификацию в зависимости от значения Z.

DOMAINS

z=integer

r=string

PREDICATES

grade(z,r)

CLAUSES

grade(Z,""):-Z<0,!, write("Неверный ввод данных!").

grade(Z,""):-Z>100,!,write("Неверный ввод данных!").

grade(Z,"M"):-Z>=80,!.

grade(Z,"S"):-Z>=60,!.

grade(Z,"B"):-Z>=40,!.

grade(Z,"N").

GOAL

write("Z="), readint(Z), grade(Z,R),write(R).

Комментарий: readint – стандартный предикат ввода целочисленного значения

Результат выполнения программы:

1-й случай:

Z=88

M

2-й случай:

Z=65

S

3-й случай:

Z=39

N

4-й случай:

Z=110

Неверный ввод данных!

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. База данных содержит факты вида: отдыхает(имя, город), украина(город), россия(город), женщина (имя), мужчина(имя).

а) вывести список женщин, отдыхающих в России;

б) вывести список мужчин, отдыхающих на Украине.

2. База данных содержит факты вида: книга(автор, название, издательство, год_издания), украина(город).

а) вывести весь список книг;

б) вывести список книг авторов Пушкина и Чехова;

в) вывести список книг, изданных в издательстве «Питер» не ранее 2000 года.

3. Составить программу, реализующую авиасправочник. В справочнике содержится следующая информация о каждом рейсе: номер рейса, пункт назначения, время вылета, дни(ежедн., чет, нечет). Вывести:

а) всю информацию из справочника;

б) информацию о самолетах, вылетающих в заданный пункт по четным дням;

в) информацию о самолетах, вылетающих ежедневно не позже указанного времени.

4. Составить программу, реализующую географический справочник. В справочнике содержится следующая информация о каждой стране: название страны, название столицы, численность населения, географическое положение (Европа или Азия). Вывести:

а) всю информацию из справочника;

б) информацию о странах, численность населения которых превышает заданное значение;

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

5. Составить программу, реализующую словарь. В словаре содержится следующая информация: слово и его перевод (русские и английские слова). Реализовать вывод всего словаря, перевод с русского на английский, с английского на русский (с несколькими значениями).

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

7. База данных содержит факты вида: ученик(имя, класс) и увлекается(имя, хобби). Составить программу, которая выводит:

а) список всех учеников и их увлечения;

б) подбирает одному из учеников указанного класса, увлекающемуся кино, пару из других классов. Вывести все возможные пары.

8. База данных содержит факты вида: ученик(имя, класс) и играет(имя, вид_спорта). Составить программу, которая:

а) выводит список всех учеников заданного класса и вид спорта, которым они увлекаются;

б) подбирает одному из учеников указанного класса, играющему в бадминтон, пару из других классов. Вывести все возможные пары.

 

Отчет о выполненной самостоятельной работе должен содержать:

1) тему лабораторной работы;

2) условие задачи;

3) листинг программы;

4) результаты ее тестирования с различными исходными данными.

Арифметические вычисления

Хотя Пролог не предназначен для решения вычислительных задач, его возможности вычислений аналогичны соответствующим возможностям таких языков программирования как Basic, C, Pascal.

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

Таблица 1. Математические операции и функции в Прологе

X + Y	Сумма X и Y
X – Y	Разность X и Y
X * Y	Произведение X и Y
X / Y	Деление X на Y
X mod Y	Остаток от деления X на Y
X div Y	Целочисленное деление X на Y
abs(X)	Абсолютная величина числа X
sqrt(X)	Квадратный корень из X
random(X)	Случайное число в диапазоне от 0 до 1
random(Int,X)	Случайное целое число в диапазоне от 0 до Int
round(X)	Округление Х
trunc(X)	Целая часть Х
sin(X)	Синус X
cos(X)	Косинус X
arctan(X)	Арктангенс Х
tan(X)	Тангенс X
ln(X)	Натуральный логарифм X
log(X)	Логарифм Х по основанию 10

Пример 1.

Вычислить значение выражения Z=(2*X+Y)/(X-Y) для введенных X и Y.

Решение:

PREDICATES

знач_выраж(real,real)

CLAUSES

знач_выраж(X,Y):-X<>Y, Z=(2*X+Y)/(X-Y),

write("Z=",Z);

write ("Делить на 0 нельзя!").

GOAL

Write("X="),readreal(X),

Write("Y="),readreal(Y),знач_выраж(X,Y),nl.

Комментарий: readreal – предикат для ввода действительных чисел

Результат выполнения программы:

1-й случай:

X=4

Y=4

Делить на 0 нельзя!

2-й случай:

X=5

Y=2

Z=4

Пример 2.

Найти минимальное из двух введенных A и B.

Решение:

PREDICATES

min(integer,integer,integer)

CLAUSES

min(A,B,A):-A<=B,!.

min(A,B,B).

GOAL

Write("A="),readreal(A),Write("B="),readreal(B),

min(A,B,Min),write("min=",Min),nl.

Результат выполнения программы:

1-й случай:

A=5

B=17

min=5

2-й случай:

A=35

B=18

min=18

3-й случай:

A=8

B=8

min=8

 

Пример 3.

Определить, является четным или нечетным случайным образом выбранное число от 0 до 20.

Решение:

PREDICATES

chet

CLAUSES

chet:-random(20,X),write(X),X mod 2=0,

write(" - четное"),!.

chet:-write(" - нечетное").

GOAL

chet.

 

Результат выполнения программы:

1-й случай:

6 – четное

2-й случай:

19 – нечетное

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Составить программу для вычисления значения выражения Y=(X2+1)/(X-2) для введенного X.

2. Составить программу для вычисления значения выражения S=2(X2+Y2)/(X+Y) для введенных X и Y.

3. Составить программу для вычисления значения выражения z=e^xsinx +3lnx для введенного X.

4. Составить программу для вычисления значения выражения y=ln(lg(sinx+e^x))для введенного X.

5. Составить программу для вычисления среднего арифметического двух введенных чисел.

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

7. Составить программу для проверки введенного натурального числа на четность.

8. Составить программу для проверки попадает ли введенное число X в заданный промежуток [a,b].

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

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

 

Отчет о выполненной самостоятельной работе должен содержать:

1) тему лабораторной работы;

2) условие задачи;

3) листинг программы;

4) результаты ее тестирования с различными исходными данными.

Рекурсия

Рекурсивная процедура – это процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию. Такое условие называют граничным. Рекурсивное правило всегда состоит по крайней мере из двух частей, одна из которых является нерекурсивной. Она и определяет граничное условие.

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

Пример 1.

База данных содержит следующие факты:

roditel(ivan,oleg).

roditel(inna,oleg).

roditel(oleg,dima).

roditel(oleg,marina).

Составить рекурсивное правило предок и определить всех предков и их потомков.

Решение:

DOMAINS

name=string

PREDICATES

roditel(name,name)

predok(name,name)

CLAUSES

roditel(ivan,oleg).

roditel(inna,oleg).

roditel(oleg,dima).

roditel(oleg,marina).

predok(X,Z):-roditel(X,Z). % нерекурсивная часть правила

predok(X,Z):-roditel(X,Y), % рекурсивная часть правила

predok(Y,Z).

GOAL

predok(X,Y),

write("Рredok -",X," Еgo potomok-",Y),nl,fail.

Результат выполнения программы:

Рredok -ivan Еgo potomok-oleg

Рredok -inna Еgo potomok-oleg

Рredok -oleg Еgo potomok-dima

Рredok -oleg Еgo potomok-marina

Рredok -ivan Еgo potomok-dima

Рredok -ivan Еgo potomok-marina

Рredok -inna Еgo potomok-dima

Рredok -inna Еgo potomok-marina

 

Пример 2. Вычисление факториала.

Решение:

PREDICATES

fact(integer,integer)

CLAUSES

fact(0,1):-!. % Факториал нуля равен единице

fact(N,F):- N1=N-1, % уменьшаем N на единицу,

fact(N1,F1), % вычисляем факториал нового числа,

F=N*F1. % а затем умножает его на N

GOAL

write("N="),readint(N),fact(N,F),write("F=",F),nl.

Результат выполнения программы:

1-й случай:

N=0

F=1

2-й случай:

N=1

F=1

3-й случай:

N=4

F=24

 

Пример 3

Составить программу для вычисления Y=Xⁿ, X, n – целые числа

Решение:

Составим правило stepen, состоящее из 3-х частей.

1-я часть правила (нерекурсивная) определяет, что Х⁰=1.

2-я часть правила (рекурсивная) вычисляет Хⁿ для положительного n.

3-я часть (рекурсивная) - вычисляет Хⁿ для отрицательного n (добавляется необходимое условие Х<>0)

 

PREDICATES

stepen(real,real,real)

CLAUSES

stepen(X,0,1):-!.

stepen(X,N,Y):-N>0,N1=N-1,stepen(X,N1,Y1),Y=Y1*X,!.

stepen(X,N,Y):-X<>0,K=-N,stepen(X,K,Z),Y=1/Z.

GOAL

write("X="),readreal(X),

write("N="),readreal(N),

stepen(X,N,Y),write("Y=",Y),nl.

Результат выполнения программы:

1-й случай:

X=3

N=2

Y=9

2-й случай:

X=2

N=-2

Y=0.25

Пример 4. Ханойские башни

Имеется три стержня: A, B и C. На стержне А надеты N дисков разного диаметра, надетые друг на друга в порядке убывания диаметров. Необходимо переместить диски со стержня А на стержень С используя В как вспомогательный, если перекладывать можно только по одному диску и нельзя больший диск класть на меньший.

Решение:

Составим правило move, определяющее порядок переноса дисков.

1-я (нерекурсивная) часть правила определяет действие, если на стержне находится 1 диск.

2-я (рекурсивная) часть правила перемещает сначала верхние N-1 диск на стержень B, используя С как вспомогательный, затем оставшийся диск на стержень C и, наконец, диски со стержня B на C, используя А как вспомогательный.

PREDICATES

move(integer,char,char,char)

CLAUSES

move(1,A,B,C):-

write("Перенести диск с ",A," на ",C),nl,!.

move(N,A,B,C):-

M=N-1,move(M,A,C,B),

write("Перенести диск с ",A," на ",C),nl,

move(M,B,A,C).

GOAL

write("Ханойские башни"), nl,

write("Количество дисков:"), readint(N),nl,

move(N,'A','B','C').

 

Результат выполнения программы:

Ханойские башни

Количество дисков:3

 

Перенести диск с A на C

Перенести диск с A на B

Перенести диск с C на B

Перенести диск с A на C

Перенести диск с B на A

Перенести диск с B на C

Перенести диск с A на C

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Вычислить сумму 1+2+3+…+N.

2. Подсчитать сумму ряда целых четных чисел от 2 до N.

3. Вычислить сумму ряда целых нечетных чисел от 1 до n.

4. Найти значение произведения: 2*4*6*...*26

5. Найти значение произведения: 1*3*5*...*11

6. Вычислить значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1,
f(n)=f(n-1)+f(n-2).

7. Используя базу данных и правило предок из примера 2 составить правило для определения всех потомков-мужчин.

8. Используя базу данных и правило предок из примера 2 составить правило для определения всех потомков-женщин.

Отчет о выполненной самостоятельной работе должен содержать:

1) тему лабораторной работы;

2) условие задачи;

3) листинг программы;

4) результаты ее тестирования.