50858

Рекурсия и итерация в языке Пролог

Лабораторная работа

Информатика, кибернетика и программирование

Что обеспечивает предикат repet Предикат repet обеспечивает дополнительную возможность для порождения множественных решений в процессе возврата. Этот предикат можно определить следующим образом...

Русский

2014-01-31

38 KB

24 чел.

Министерство образования и науки молодежи и спорта Украины

ОДЕССКИЙ НАЦИОНАЛЬНЫЙ МОРСКОЙ УНИВЕРСИТЕТ

Кафедра «Информационные технологии»

ОТЧЕТ ПО

ЛАБОРАТОРНОЙ РАБОТЕ №2

 

«Рекурсия и итерация в языке Пролог»

Выполнил:

студент 4к., 4гр. КСФ

Мельников В.Е.

Проверил:

Бодарев А.Д.


Одесса - 2013

Цель работы

Изучить возможности использования рекурсивных и итерационных алгоритмов в языке Пролог.

Контрольные вопросы

  1.  Что такое рекурсивная процедура?

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

  1.  Отличие итерации от рекурсии?

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

  1.  Принцип работы управления поиском с возвратом?

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

- fail (неудача) – осуществляет вынужденное неудачное завершение выполнение предиката и, таким образом, инициирует процесс возврата.

- Cut или ! (отсечение) – используется для предотвращения поиска с возвратом.

  1.  Что обеспечивает предикат repeat ?

Предикат repeat обеспечивает дополнительную возможность для порождения множественных решений в процессе возврата. Этот предикат можно определить следующим образом:

repeat.

repeat :- repeat.

Первый repeat является утверждением, объявляющим предикат repeat истинным. Первый repeat не создает подцелей, поэтому данное правило всегда успешно. Однако, поскольку имеется еще один вариант правила repeat, то указатель возврата устанавливается на первый repeat. Второй repeat – это правило, которое использует само себя как компоненту (третий repeat). Второй repeat вызывает третий repeat, и этот вызов вычисляется успешно, так как первый repeat всегда успешен. Поскольку для доказательства третьего repeat имеется два правила, точка возврата устанавливается на первый repeat, и т. д.  Предикат repeat будет вычисляться успешно при каждой новой попытке его вызвать после возврата. Факт (первое утверждение) будет использоваться для выполнения всех подцелей программы. Таким образом, repeat – это рекурсивное правило, которое никогда не бывает неуспешным.

5. Условия оптимизацией остатка рекурсии.

Метод реализации, приводящий к подобной экономии памяти, называется оптимизацией остатка рекурсии или, точнее, оптимизацией последнего обращения. Для выполнения оптимизации остатка рекурсии необходимо, чтобы соблюдались следующие условия:

- Вызов рекурсивно-определенного предиката должен являться самой последней подцелью предложения.

-   Ранее в предложении не должно быть точек возврата


 

А также другие работы, которые могут Вас заинтересовать

29472. Признак коши (радикальный) 15.45 KB
  Радикальный признак Коши: Рассмотрим положительный числовой ряд .в При признак не дает ответа. Нужно использовать другой признак.
29474. Накочередующиеся ряды, признак Лейбница 18.25 KB
  Теорема Лейбница о сходимости знакочередующихся рядов Признак Лейбница признак сходимости знакочередующегося ряда установлен Готфридом Лейбницем. Формулировка теоремы: Пусть для знакочередующегося ряда выполняются следующие условия: монотонное убывание. Тогда этот ряд сходится.
29476. ЧЕЛОВЕК ПРИСПОСОБЛЕННЫЙ 152.5 KB
  Проблема приспособления человека к изменившейся социальной среде становится предельно острой и общезначимой в условиях крутых общественных переломов когда практически все общественные слои и группы оказываются перед выбором вынужденного приспособления или самораспада. период перестройки общества и человека оказался более долгим располагал более массированными средствами включая тотальный террор и последствия двух мировых войн притом объектом воздействия оказывался расшатанный ранее тип социального человека. Ориентируясь на идеологию...
29477. ЧЕЛОВЕК НЕДОВОЛЬНЫЙ: ПРОТЕСТ И ТЕРПЕНИЕ 114.5 KB
  Чтобы преодолеть видимый парадокс нужно определить те социальные условия и структуры которые формируют и поддерживают такое сочетание а точнее взаимодействие недовольства и терпения в обществе. или к неэффективности современного социального недовольства фонового констатируют бесспорные факты но не объясняют их. Состояние общественно значимого недовольства возникает как реакция на сравнение то ли с лучшим по крайней мере более спокойным прошлым то ли с неосуществленным светлым будущим точнее с иллюзией такого будущего...
29478. ЧЕЛОВЕК ЛУКАВЫЙ: ДВОЕМЫСЛИЕ ПО-РОССИЙСКИ 150 KB
  Он приспосабливается к социальной действительности ища допуски и лазейки в ее нормативной системе то есть способы использовать в собственных интересах существующие в ней правила игры и в то же время что не менее важно постоянно пытаясь в какойто мере обойти эти правила. Успех этой системы на долгие десятилетия по крайней мере был бы невозможен если бы она опиралась только на массовое принуждение и массовый обман. Практическое отсутствие общеобязательных авторитетов создает многополярную структуру нормативного поля где...
29479. «ЧЕЛОВЕК ОГРАНИЧЕННЫЙ»: УРОВНИ И РАМКИ ПРИТЯЗАНИЙ 107.5 KB
  Стабильность притязаний На протяжении ряда лет данные ВЦИОМ охватывают как реальные так и воображаемые приписанные показатели положения человека: данные о полученном и желаемом нормальном по мнению опрошенных доходе и т. При этом 72 опрошенных считали что они получают намного меньше или несколько меньше чем заслуживают; 19 что они получают столько сколько заслуживают; 8 что получают больше чем того заслуживают. Если бы в распоряжении опрошенных исследование типа Мониторинг март 1997 г. При сходной формулировке...
29480. НАШИ ДЕСЯТЬ ЛЕТ: ИТОГИ И ПРОБЛЕМЫ (околоюбилейные размышления) 128 KB
  было подписано Постановление Президиума ВЦСПС и Госкомтруда СССР О создании Всесоюзного центра изучения общественного мнения по социальноэкономическим вопросам формальная дата появления на свет ВЦИОМ. Первое десятилетие жизни и работы ВЦИОМ можно рассматривать под разными углами зрения перебирать опросы отчеты оценивать кадры вспоминать конфликты и т. Что такое ВЦИОМ Условия и время создания нашего центра естественно наложили свой отпечаток на характер ВЦИОМ как организации или даже как своеобразного организма. Вопервых...