[Закрыть]
 
popoff.donetsk.ua
Нет хорошего, есть лишь только то, что нравится. Нет плохого, есть лишь только то, что не нравится.
Начало | Новости | Статьи | Форум | Опросы | Карта сайта | Обо мне
popoff.donetsk.ua - Статьи - ДонНТУ - Функциональное и логическое программирование - Пролог: Поиск максимума без использования списков
Я это делаю
Персональное меню
Голосование
Деньги, либо любимое занятие? Постоянный адрес этого вопроса
Деньги, но неинтересная работа и невозможность уделить время семье
Интересная работа, возможность саморазвиваться, но нищенский заработок
Ваш возраст (не обязательно)
Почему? (не обязательно)

Голосование закрыто.

Поиск по сайту
Реклама
Обмен электронных валют
money.dn.ua
Статистика

Пролог: Поиск максимума без использования списков

Постоянный адрес статьи

Очень часто в Прологе данные заданы набором фактов.

Чтобы найти максимум среди значений, которые заданы фактами, обычно все эти значения собирают в один список при помощи встроенного предиката findall и уже после этого ищут максимум или минимум в полученном списке.

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

Идея поиска максимума состоит в том, что мы перебираем все возможные значения и для каждого значения проверяем, есть ли значение, которое больше текущего. Если такое значение есть, значит текущее значение - не максимум. Если такого значения нет - значит текущее значение - это и есть максимум.

Для поиска минимума используются аналогичные рассуждения.

Теперь рассмотрим пример реализации поиска максимума на Прологе:

domains
  i=integer
predicates
  data(i)
  ismax(i)
  max(i)
clauses
  data(1).
  data(3).
  data(5).
  data(4).
  data(2).

  ismax(X):-data(Y),Y>X,!,fail.
  ismax(_).

  max(X):-data(X),ismax(X),!.

В приведённом выше примере вспомогательный предикат ismax проверяет, существует ли среди данных значение, которое больше заданного. Если существует, то этот предикат будет ложен, а если такого значения нет - истинен.

Предикат ismax отвечает на вопрос: «Может ли X являться максимумом?» или, упрощённо, «Является ли X максимумом?». Считаем, что X может являться максимумом если нет такого значения, которое было бы больше X.

Предикат ismax будет ложен, если значение найдено, благодаря использованному предикату fail. Отсечение перед fail необходимо для того, чтобы fail не включило механизм возврата и Пролог не перешёл ко второму утверждению для предиката ismax. Если среди данных нет такого значения, которое было бы больше, чем значение X, то все проверки Y>X будут ложными, до отсечения и, следовательно, до fail очередь никогда не дойдёт и, поэтому, благодаря второму утверждению для предиката ismax, сам этот предикат будет истинен.

Предикат max перебирает все возможные значения и для каждого значения проверяет, есть ли какое-нибудь другое значение, которое было бы больше, чем текущее. Эта проверка осуществляется при помощи предиката ismax.

Когда для очередного (например, самого первого) значения предикат ismax указывает на то, что «Нет, это текущее значение не является максимумом!», то включается механизм возврата и передоказывается первая подцель для предиката max (следует помнить, что отсечение внутри предиката ismax действует только на ismax и не действует на max). В этом основное отличие этого предиката от того, который обрабатывает списки - при обработке списков перебор значений осуществляется за счёт рекурсии, а здесь перебор значений осуществляется за счёт использования механизма возврата.

Когда для очередного значения предикат ismax истинен (то есть, он говорит, что «Да, текущее значение является максимумом!»), то и предикат max тоже считается доказанным и текущее значение возвращается как результат.

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

Смотрите также

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

Благодарности

Первый, черновой вариант реализации поиска максимума на Прологе без использования промежуточных списков выполнил студент потока ПС-05 Александр Чередниченко.

Последняя модификация: 13.12.07 16:25

Не проходите мимо! Оставьте Ваш комментарий в форуме! >>>