50858

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

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

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

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

Русский

2014-01-31

38 KB

27 чел.

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

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

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

ОТЧЕТ ПО

ЛАБОРАТОРНОЙ РАБОТЕ №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. Условия оптимизацией остатка рекурсии.

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

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

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


 

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

17478. Автоматизированные информационные системы (АИС), структура и классификация 127 KB
  Лекция №2 Автоматизированные информационные системы АИС структура и классификация АИС комплекс автоматизированных информационных технологий предназначенный для информационного обслуживания организованного непрерывного технологического процесса подготовк...
17479. Организационное обеспечение и пользователи АИС 36.5 KB
  Организационное обеспечение и пользователи АИС В состав организационного обеспечения АИС принято включать структурные подразделения организации осуществляющие управление технологическими процессами и поддержку работоспособности системы а также совокупность док
17480. Некоторые поисковые возможности и характеристики систем Yandex и Rambler 392.5 KB
  Некоторые поисковые возможности и характеристики систем Yandex и Rambler. Стандартный поиск Yandex. Рассмотрим общий вид стандартной поисковой формы Yandex рис. 2.20. 1. Основная поисковая форма. Главный ее элемент строка запроса. При желании можно искать только в результатах пр
17481. Структура и классификация автоматизированных информационных систем 103.5 KB
  Структура и классификация автоматизированных информационных систем Цели изучения темы: общеобразовательная прочное усвоение знаний о составе и структуре АИС; развивающая развитие логического мышления; воспитательная формирование представлений об осн...
17482. АИС. Автоматизированные информационные системы 114 KB
  Введение. Ни одно современное предприятие не обходится без систем сбора и обработки информации. Чем больше стадий производства чем оно сложнее чем больше и разнообразнее спектр производимых продаваемых изделий или предлагаемых услуг тем больше потребность в автомат...
17483. Формати і правила роботи з командами організації циклів і роботи з ланцюгами мікропроцесора i8086 31.55 KB
  Лабораторна робота №6 З дисципліни СПіОС на тему: Формати і правила роботи з командами організації циклів і роботи з ланцюгами мікропроцесора i8086 Мета: Ознайомитись з правилами роботи команд організації циклів і роботи з ланцюгами мікропроцесора i8086. Вивчити осн
17484. Ввід інформації із клавіатури 27.12 KB
  Лабораторна робота №7 З дисципліни СПіОС на тему: Ввід інформації із клавіатури Мета: Ознайомитись з правилами обробки переривань для роботи із клавіатурою. Завдання: Створіть файл у який записано слово пароль. Напишіть програму яка запитує введення па
17485. Вивчення арифметичних команд мікропроцесора i8086 37.37 KB
  Лабораторна робота №2 З дисципліни СПіОС на тему Вивчення арифметичних команд мікропроцесора i8086 Лабораторна робота №2 Мета: Вивчити арифметичні команди мікропроцесора i8086 і правила їх використання. Завдання: Реалізувати можливість введення даних з клавіа...
17486. Вивчення способів адресації даних мікропроцесором i8086 і їх використання при пересиланні даних 47 KB
  Лабораторна робота №1 З дисципліни СП та ОС Мета: Вивчення способів адресації даних мікропроцесором i8086 і їх використання при пересиланні даних. Теоретичні відомості: Мікропроцесор вибирає один з семи режимів адресації за значенням поля режиму команди: регіс