systemII2003 (1086256), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Программа 1.

song:- write('бегу,'),song.

Рассмотрим дерево вывода ответа на запрос:

?- write('Я '),song.

1. Будем обозначать в деревьях вывода двойной линией связь "и", одинарной - связь "или", стрелками с номерами - порядок унификаций, а перечеркиванием - неуспех унификации.

Как видно, в процессе выполнения программы возникает бесконечно длинная строка. Это пример так называемой бесконечной рекурсии ("зацикливание" программы).

Запустите программу. Kогда Вам надоест любоваться красотами написания этой песни, нажмите на клавиши CTRL+BREAK для приостановки бесконечного вывода, а CTRL+C - для выхода.

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

Рассмотрим следующий вариант программы.

Программа 2.

song(X):-(X>1),write('бегу,'),(Y is X - 1),song(Y).

song(1).

?-write('Я '),song(3),write('бегу по гаревой дорожке').

В данной программе используются встроенные арифметические предикаты отношения ( X > Y ) и присваивания (X is A, где X - неконкретизированная переменная, а A - арифметическое выражение, конкретизированное числовым значением).

Задание 7. Запустите программы 1 и 2.

Рассмотрим задачу нахождения факториала некоторого целого неотрицательного числа.

Программа 3. Рекурсивное вычисление фактoриала (вариант 1).

factorial(1,1) . /* Условие выхода из рекурсии 1!=1 */

factorial(N,F):-

Можно выделить три случая использования отсечения:

N>1,

N1 is N-1,

factorial(N1, F1),

F is N*F1.

Рассмотрим дерево вывода ответа на вопрос:

?-factorial(3,X).

Прямой ход: 1, 2, 3, 4, 5, 6, 7.

Обратный ход: 8, 9, 10, 11,12

$ - точка возврата, - - - - невыполняемая ветвь дерева.

Альтернативный прямой ход: 13, 14, fail.

Задание 8. Запустите программу с отладчиком.

Введите запросы: ?-factorial(3,X).

?-factorial(1,X).

?-factorial(0,X).

2. ПРОГРАММИРОВАНИЕ С НАКОПИТЕЛЯМИ

При реализации рекурсии данные помещаются в стек всякий раз, когда выполняется рекурсивный вызов. Чем больше глубина рекурсии, тем больше требуется стековой памяти. Итеративные программы работают в фиксированном объеме памяти, не зависящем от числа итераций.

Итеративные вычисления можно смоделировать, используя в рекурсивных определениях с одним рекурсивным вызовом в правой. части дополнительные аргументы-переменные для передачи промежуточных значений. Эти переменные называются накопителями (аккумуляторами).

Программа 4. Итеративное определение факториала (вариант 1).

factorial(N,FactN):-

fact(N,FactN,1,1).

fact(N,FactN,I,P):- /* накопитель I - аналог счетчика */

I<N, /* накопитель P - промежуточное */

I1 is I+1, /* значение факториала */

P1 is P*I1,

fact(N,FactN,I1,P1).

fact(N,FactN,N,FactN).

Задание 3. Выполните программу 4 в режиме трассировки.

Введите запрос: ?-factorial(3,F).

Программа 5. Итеративное определение факториала (вариант2, более эффективный).

factorial(N,FactN):-

fact(N,FactN,1).

fact(N,FactN,P):-

N>0,

P1 is P*N,

N1 is N-1,

fact(N1,FactN,P1).

fact(0,FactN,FactN).

Задание 9. Выполните программу 5 в режиме трассировки.

Введите запрос: ?-factorial(4,F).

Нарисуйте дерево вывода.

РЕКУРСИВНЫЕ ОБЪЕКТЫ

Другим типом рекурсии в Прологе является рекурсия по данным.

Программа 6. Рекурсивное определение списка студентов.

/* группа номер 1, состоящая из студентов

'Шекспир','Мольер','Чехов' */

kurs(1,gruppa('Шекспир',gruppa('Мольер',

gruppa('Чехов',empty)))).

kurs(2,gruppa('Гильберт',gruppa('Эйлер',gruppa('Лейбниц',

gruppa('Кантор',empty))))).

Задание 10. Запустите программу 6, введите запросы:

?-kurs(1,X).

?-kurs(N,gruppa(X,Y)).

?-kurs(N1,gruppa(X, gruppa(Y,Z))).

3адание 11. Напишите программу для определения n-го числа Фибоначчи без накопителей и с накопителями.

Числа Фибоначчи определяются следующим законом: первые два числа равны единице, а каждое последующее равно сумме двух предыдущих. То есть получим ряд 1,1,2,3,5,8,13,21,34,...

Задание 12. Напишите программу для определение суммы нечетных (четных) чисел из n первых чисел Фибоначчи.

Задание 13. Дано число. Проверить, является ли оно суммой нечетных (четных) чисел из n первых чисел Фибоначчи. Найти число n.

Задание 14. Напишите программу для вычисления функции Аккермана, определенной на множестве пар неотрицательных чисел.

Можно ли написать эту программу с накопителями ?

ЛАБОРАТОРАТОРНАЯ РАБОТА 3

I. УПРАВЛЕНИЕ ЛОГИЧЕСКИМ ВЫВОДОМ

ЦЕЛЬ. Знакомство с механизмами управления логическим выводом в Прологе. Отсечение. Моделирование циклов в Прологе.

1. ОТСЕЧЕНИЕ (cut)

Для управления механизмом перебора используются встроенные предикаты: отсечение ("!") и неудача (fail). Предикат отсечения применяется, когда надо изменить процесс возврата.

Программа 1.

a(1,1) (1)

b(2) (2)

b(3). (3)

c(2) (4)

c(3) (5)

d(4). (6)

a(X,Y):-b(X),!,c(Y). (7)

a(X,X):-d(X) (8)

?- a(N,M).

Если бы не было предиката отсечения "!", то мы получили бы шесть ответов: N=1,M=1; N=2,M=2; N=2,M=3; N=3,M=2; N=3,M=3; N=4,M=4. При выполнении предиката отсечения ("проходе" "!" слева направо), предикаты, стоящие в правиле (7) левее "!", "замораживаются", т.е. прекращается поиск альтернативных решений для b(X), а для a(X,Y) - использование альтернативных утверждений (8), лежащих ниже правила (7). Для предиката c(Y) продолжается поиск альтернативных решений, но невозможен возврат левее "!". Получим три ответа: N=1,M=1; N=2,M=2; N=2,M=3.

Если подцель "E,F" - неуспешна, бектрекинг попадает на "!", и вся цель A - неуспешна.

1. Если при некоторых условиях какая-либо цель никогда недолжна быть успешной, комбинация cut-fail исключит выполнение

остальных правил, согласующихся с этой целью.

Например, предикат not(P) можно определить с помощью отсечения следующим образом:

not(P) :- P,!,fail.

not(_) :- true.

2. Для устранения бесконечных циклов.

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

Программа 2.

factorial(0, 1):- !. /* Условие выхода из рекурсии 0!=1 */

factorial(N,F) :- N1 is N-1,

factorial(N1, F1),

F is N*F1.

3. При программировании взаимно исключающих утверждений.

Например, sign(X,-1):- X<0,!.

sign(X,0):- X=0,!.

sign(X,1):- X>0.

Задание 1. Продолжите дерево вывода ответа на запрос

?- factorial(3,F).

Задание 2. Напишите программу для определения размера одежды, используя предикат 'размер'(Номер,Рост) и следующие критерии определения номера:

Номер 1 2 3 4 5

Интервал [158,164) [164,170) [170,176) [176,182) [182,188]

Например, второй рост можно определить правилом

'размер'(2,R):- R>=164, R<170.

Добейтесь наименьшего числа сравнений в программе, используя отсечение. Рассмотрите случай неуспешного определения роста.

2. ОРГАНИЗАЦИЯ ЦИКЛА.

2.1. Первый метод организации повторений получил название 2BAF 0-метода (Backtrack After Fail - возврат после отказа).

Предикат отказа fail используется для получения гарантированного неуспеха при доказательстве некоторой цели. Например, правило

A:- B,fail.

будет выполняться столько раз, сколько имеется альтернатив для B в этом правиле.

Программа 3.

a:- write(1).

a:- write(2).

b(X):- a,X='еще'.

c:- a.

d:- a,fail.

?-b(X).

?-c.

?-d.

Задание 3. Выполните программу 3 с данными запросами. Объясните результаты и нарисуйте деревья вывода.

Задание 4. Используя предикат fail, напишите правило, которое позволило бы распечатать столицы всех стран из базы.

country('England','London').

country('Russia','Moscow').

country('France','Paris').

country('China','Pekin').

country('Japan','Tokyo').

country('Italy','Rome').

2.2. Второй способ организации повторений получил название UDR-метода (User Defined Repeat - повторение, управляемое пользователем). Встроенный предикат repeat позволяет генерировать альтернативные решения с помощью механизма бектрекинга, причем это возможно для целей, которые не всегда успешно согласовываются при первом обращении, либо которые могут иметь много решений. Всякий раз, когда при бектрекинге происходит возврат write_list([]) к repeat, этот предикат успешно согласовывается, и при последующем согласовании предикатов, стоящих правее repeat, переменные могут конкретизироваться различными значениями.

Предикат repeat определяется следующим образом:

repeat.

repeat:- repeat.

Задание 5. Выполните программу 3 с запросом

?- repeat,a,fail.

Постройте дерево вывода и объясните результат.

Программа 4.

/* ввод с клавиатуры слов и вывод их на экран до тех пор, пока не будет введено слово stop (в конце терма, вводимого read, необходимо поставить точку и нажать клавишу Enter) */

r:- repeat, read(X), write(X), nl, X=stop.

?- r.

Дерево вывода:

Задание 6. Выполните программу 4 в режиме трассировки. (Не забывайте ставить точки в конце вводимых слов.)

Можно предложить более общую схему организации цикла с помощью предиката repeat при выполнении некоторого условия.

Задание 7. Напишите программу для организации меню, исполь-зуя встроенные предикаты Пролога:

Характеристики

Список файлов лабораторной работы