Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа №7
Тема : повторение и рекурсия.
Цель: навыками программирования повторяющихся операций в Прологе.
.
.
Теоретические сведения.
Очень часто в программах необходимо выполнить одну и ту же задачу несколько раз. В программах на Прологе повторяющиеся операции обычно выполняются при помощи правил, которые используют откат и рекурсию. В этой лабораторной работе рассматриваются итеративные и рекурсивные правила, а так же общие способы их построения. Вводятся ЧЕТЫРЕ ВАЖНЫХ МЕТОДА: метод отката после неудачи, метод отсечения и отката, правило повтора, определяемое пользователем, и обобщенное рекурсивное правило.
Правила повтора и рекурсии должны содержать средства управления их выполнением с тем, чтобы их использование было удобным. Встроенные предикаты Турбо-Пролога fail и cut используются для управления откатами, а условия завершения используются для управления рекурсией.
Программирование повторяющихся операций.
Цели управляют программой на Прологе, обеспечивая выполнение последовательности определенных задач. Цели могут содержать подцели и могут содержать правила. Правила часто требуют, чтобы такие задачи, как поиск элементов в базе данных или вывод данных на экран выполнялись несколько раз.
Существуют два способа реализации правил, выполняющих одну и туже задачу многократно. Первый их них будем называть ПОВТОРЕНИЕМ, а второй - РЕКУРСИЕЙ. Правила Пролога, выполняющие повторения, используют откат, а правила, выполняющие рекурсию используют самовызов.
Вид правила, выполняющего ПОВТОРЕНИЕ, следующий:
repetitive_rule :- /* правило повторения */
<предикаты и правила>,
fail. /* неудача */
Конструкция <предикаты и правила> в теле правила обозначает предикаты, содержащие несколько утверждений, а так же правила, определенные в программе. Встроенный предикат fail (неудача) вызывает откат, так что предикаты и правила выполняются еще раз.
Вид правила, выполняющего РЕКУРСИЮ, следующий:
recursive_rule :- /* правило рекурсии */
<предикаты и правила>,
recursive_rule.
Последним правилом в теле данного правила является само правило recursive_rule. Правила рекурсии содержат в теле правила сами себя.
Правила повтора и рекурсии могут обеспечивать одинаковый результат, хотя алгоритмы их выполнения не одинаковы. Каждый из них в конкретной ситуации имеет свои преимущества.
Рекурсия, например, может потребовать больше системных ресурсов. Так всякий раз при рекурсивном вызове новые копии используемых значений помещаются в стек. Стек представляет собой область памяти, используемую в основном для передачи значений между правилами. Значения сохраняются пока правило не завершиться либо успешно, либо неуспешно. В некоторых ситуациях такое использование стека может быть оправдано, если промежуточные значения должны храниться в определенном порядке для дальнейшего использования.
Повторение и откат
Обычно цель программы на Турбо-Прологе содержит одну или несколько подцелей, которые могут быть либо фактами, либо правилами. Факт вычисляется немедленно. Результат будет либо успешным, либо неуспешным в зависимости от того, сопоставим ли факт в программе с фактом в правиле. Правило, являясь связкой подправил, вычисляется путем вычисления подправил. Если подправило не может быть успешно вычислено, то Турбо-Пролог выполняет откат, что бы найти другие возможные пути вычисления этого под правила.
Проанализируем понятие отката на примере простой базы данных о спортивных увлечениях, содержащей следующие факты:
plays(tom,football) /* Том играет в американский */
/* футбол */
plays(john,soccer) /* Джон играет в европейский */
/* футбол */
plays(john,volleyball) /* Джон играет в волейбол */
plays(tom,basketball) /* Том играет в баскетбол */
plays(tom,volleyball) /* Том играет в волейбол */
plays(john,baseball) /* Джон играет в бейсбол */
Задача программы определить в какую игру одновременно играют Джон и Том.
Утверждение цели следующее:
plays(john,G),plays(tom,G).
Заметьте, что эта цель есть связка двух подцелей. Каждая подцель содержит переменную G. Задача заключается в нахождении значения для G, удовлетворяющего обеим подцелям. Чтобы вычислить первую подцель plays(john,G), Пролог ищет в базе данных сопоставимое утверждение. Первый объект утверждения plays(john,soccer) сопоставим с первым объектом первой подцели, так что подцель успешно вычисляется и переменная G получает значение soccer. Существуют другие утверждения для plays, которые могут быть использованы для вычисления этой же подцели. По этому Пролог должен сохранить след этих утверждений на случай неуспешного вычисления второй подцели со значением G равным soccer. Для этого внутренние унификационные подпрограммы устанавливают указатель отката на точку, с которой могут быть продолжены усилия по вычислению первой подцели.
Теперь Пролог пытается вычислить вторую подцель. Так как G имеет значение soccer, то эта подцель есть plays(tom,soccer). Турбо-Пролог просматривает базу данных в поиске утверждения, сопоставимого с этой подцелью. Сопоставимых утверждений нет, поэтому подцель неуспешна.
Так как вторая подцель вычислена неуспешно, то Пролог вновь должен начать просмотр с первой подцели. После того, как попытка вычислить вторую подцель оказалась неуспешной, переменная G освобождается и Пролог снова начинает поиск утверждения для вычисления подцели plays(john,G).
Поиск начинается с указателя отката. Следующее сопоставляемое утверждение - это plays(john, volleyball).
Переменная G получает значение volleyball. Снова указатель отката помещается на следующее утверждение. Пролог пытается вычислить вторую подцель plays(tom,volleyball). Во время этой попытки удается найти сопоставимое утверждение. Присвоение переменной G значения volleyball приводит к успеху. Обе подцели удовлетворены. Больше подцелей нет, поэтому вся исходная цель оказывается успешно вычисленной.
Если бы цель в этом примере была внутренней, то процесс вычисления остановился бы после первого ее успешного вычисления. Однако цель здесь внешняя, поэтому процесс повторяется до тех пор, пока не будут найдены все успешные способы вычисления цели. Но информация, содержащаяся в данных утверждениях, дает только одно допустимое значение для G, которое удовлетворяет обеим подцелям, т.е. результат вычисления подцели есть
G=volleyball.
ОТКАТ является автоматически инициируемым системой процессом, если не используются средства управления им. Для управления процессом отката в Прологе предусмотрены два встроенных предиката fail (НЕУДАЧА) и cut (ОТСЕЧЕНИЕ).
Во время выполнения программы Пролог создает необходимые внутренние структуры данных (такие как списки и деревья) для выполнения обработки программы. Эта обработка включает такие процессы как поиск, сопоставление с образцом, создание экземпляра, означивание и освобождение переменных, откаты.
МЕТОД ОТКАТА ПОСЛЕ НЕУДАЧИ
Метод отката после неудачи (ОПН) может быть использован для управления вычислением внутренней цели при поиске всех возможных ее решений. Метод ОПН использует предикат fail. Программа о городах должна продемонстрировать использование этого предиката.
Назначение программы о городах состоит в перечислении названий десяти городов США.
domains
name=symbol
predicates
cities(name)
show_cities
goal
write("Here are the cities:"),nl
show_cities
clauses
cities("ANN ARBOR ").
cities("ATLANTA").
cities("NEW HAVEN").
cities("INDIANAPOLIS").
cities("BOSTON").
cities("MESA").
cities("MINEAPOLIS").
cities("SAN ANTONIO").
cities("SAN DIEGO").
cities("TAMPA").
show_cities :-
cities(City),
write(" ", City), nl,
fail.
Утверждение первой подцели выдает заголовок Here are the cities (Это названия городов). Вторая подцель является правилом для перечисления названий городов. Подправило cities(City) означивает переменную City (город) названием города. Затем это значение выдается на экран. Предикат fail вызывает откат к следующему утверждению, которое может обеспечить вычисление цели.
Мы написали в программе 10 предикатов, каждый из которых является альтернативным утверждением для предиката cities(name). Во время попытки вычислить цель, внутренние унификационные подпрограммы означивают переменную City объектом первого утверждения, который есть ANN ARBOR (название города в США). Т.к. существует следующее утверждение, которое может обеспечить вычисление подцели cities(City), то указатель отката помещается в эту точку, а значение ANN ARBOR выводится на экран.
Предикат fail вызывает неуспешное завершение правила, внутренние унификационные подпрограммы выполняют откат в эту точку , и процесс повторяется до тех пор, пока последнее утверждение не будет обработано.
Программа о городах показывает, что использование метода ОПН позволяет извлекать данные из каждого утверждения базы данных. Если в программе содержатся утверждения для 10 вариантов, то результат так же содержит 10 строк. Данные извлекаются из каждого утверждения, так как каждый вариант удовлетворяет под цели cities(City).
1. Запустите программу о городах США.
2. Модифицируйте программу таким образом, что бы результатом была выдача на экран целых чисел 66, 46, 32, 93, 44, 98, 37, 16, 12. Выдавайте только одно число в строке.
3. Какие необходимы модификации для выдачи целых чисел в одну строку так, что бы они были разделены двумя пробелами?
Содержание отчета.
1. Цель работы.
2. Задания .
3.Программы и результат их выполнения.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Какие методы существуют для организации повторяющихся
операций в Прологе?
2. Какой вид имеет правило повторения ?
3. Какой вид имеет правило рекурсии ?
4. Опишите, как работает метод ОПН ?