У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

Упражнение 7.5.Проверьте, что предикат перестановка (L1, L2)строит все перестановки заданного списка L1(причем каждую по одному разу) и выдает их как альтернативные значения списка L2. В каком порядке строятся эти решения?

Упражнение 7.6.Быстрая сортировка лучше всего работает ка больших списках, поскольку там она обеспечивает более быструю сходимость к решению. В то же время объем работы, выполняемой на каждом уровне рекурсии быстрой сортировки, превышает то, что делается в других методах, из-за использования разбить. Поэтому, при сортировке небольших списков рекурсивные вызовы бысорт,видимо, можно заменить обращениями к другим методам сортировки, например, к сортировке включением. Разработайте «гибридную» программу, которая использует быструю сортировку для обработки больших подсписков (списков, полученных с помощью предиката разбить),но переключается на другой метод (сортировка включением) при значительном уменьшении длины подсписка. Подсказка: поскольку разбитьдолжен просмотреть все элементы списка, то он может заодно подсчитать и длину списка.

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

Цель random(R, N)конкретизирует Nцелым числом, случайно выбранным в диапазоне от 1до R. Метод выбора случайного числа основан на конгруэнтном методе с использованием начального числа («затравки») инициализируемого произвольным целым числом. Каждый раз, когда требуется случайное число, ответ вычисляется на основе существующего начального значения, и при этом порождается новое начальное число, которое сохраняется до тех пор, пока вновь не потребуется вычислить случайное число. Для хранения начального числа между вызовами randomмы используем базу данных. После того как начальное число использовано, мы убираем (с помощью retract)из базы данных старую информацию о начальном числе, вычисляем его новое значение, и засылаем в базу данных новую информацию (с помощью asserta).Исходное начальное значение – это просто факт в базе данных, с функтором seedимеющим одну компоненту – целое значение начального числа.

seed(13).

random (R,N):-seed(S),N is (S mod R) + 1,retract(seed(S)),NewSeed is (125 * S + 1) mod 4096,asserta(seed(NewSeed)),!.

Используя семантику retractможно упростить определение randomследующим образом:

random(R,N):-retract(seed(S)),N is (S mod R)+1,NewSeed is (125 * S +1) mod 4096,asserta(seed(NewSeed)),!.

Для того, чтобы напечатать последовательность случайных чисел, расположенных в диапазоне между 1 и 10, которая обры-вается после того, как будет порождено значение 5, нужно задать следующий вопрос:

?- repeat, random(10,X), write(X), nl, X=5.

Предикат генатомпозволяет порождать новые атомы Пролога. Если у нас есть программа, которая воспринимает информацию об окружающем мире (например, путем анализа описывающих его предложений на английском языке), то в случае появления в этом мире нового объекта возникают трудности с его обозначением. Естественно представлять объект атомом Пролога. Если объект ранее не встречался, мы должны убедиться в том, что тот атом, который мы ему сопоставляем, случайно не совпал с другим атомом, уже представляющим какой-то другой объект. Иными словами, нам необходимо иметь возможность формировать новые атомы. Мы можем также потребовать, чтобы созданный атом имел также некоторое мнемоническое значение: это облегчит понимание информации выводимой нашей программой. Если бы атомы представляли, скажем, студентов, то целесообразно было бы назвать первого студента – студент1,второго – студент2, третьего – студентЗи т. д. Если к тому же нам нужно было бы работать с объектами представляющими еще и преподавателей, то можно было бы выбрать для их представления атомы преподаватель1, преподаватель2, преподавательЗи т. д.