Программирование на языке пролог

Клоксин У.

вклюсорт([Х|L],М,О):- вклюсорт(L,N,О),вклюсорт2(Х,N,М,О).

вклюсорт2(Х,[А|L],[А|М],0):-Р=..[O,А,Х], call(P),! ,вклюсорт2(Х,L,М,O).

вклюсорт2(Х,L,[Х|L],О).

Теперь мы можем использовать такие цели как вклюсорт(А,В,'‹') и вклюсорт(А,В,меньше),т. е. отпадает необходимость в предикате упорядочено.Этот метод может быть распространен.и на другие алгоритмы сортировки данного раздела.

При сортировке методом пузырькав списке ищется пара соседних элементов, расположенных не по порядку следования. Если такие элементы находятся, то они меняются местами. Этот процесс продолжается до тех пор, пока перестановки станут ненужными. Если при сортировке

включением выбранный элемент как бы «тонет», попадая на нужное место, то сортировка методом пузырька названа так потому, что здесь элементы, подобно пузырькам воздуха, постепенно «всплывают», занимая соответствующее место.

пусорт(L,S):-присоединить(Х,[А,В|Y],L),упорядочено(В,А),присоединить(Х, [В, А|Y],M),пусорт(M,S).

пусорт(L,L).

присоединить([],L,L).

присоединить([Н|Т],L[Н|V]):- присоединить(Т,L,V).

Заметим, что здесь применяется тот же самый предикат присоединить, с которым мы встречались ранее. Этот пример отличается от предыдущих необходимостью возвратного хода после каждого найденного решения. Поэтому в первом правиле в определении пусорт«отсечение» не используется. Эта программа еще один пример «недетерминированного» программирования,- для выбора элементов списка L здесь используется предикат присоединить. При этом контроль полноты выполненных перестановок целиком возложен на присоединить.

Быстрая сортировка– это более сложный метод сортировки, предложенный Хоором и применимый для сортировки больших списков. Для реализации быстрой сортировки на Прологе мы должны сначала разделить список, состоящий из головы Ни хвоста Т, на два списка Lи Мтакие, что:

• все элементы Lменьше или равны Н;

• все элементы Мбольше чем Н;

• порядок следования элементов в Lи Мтакой же как в [Н |Т].

После того, как мы разделили список, применяем быструю сортировку к каждому из полученных списков (это рекурсивная часть), и присоединяем Мк LЦель разбить(H,T,L,M)разделяет список [Н |Т]на списки Lи М, как сказано выше:

paзбить(H,[A|X],[A|Y],Z):- А=‹ Н, разбить(Н,Х,Y,Z).

разбить(Н,[А|Х],Y,[А|Z]):- А › Н, разбить(Н,Х,Y,Z).

разбить(_,[], [],[]).

Тогда программа быстрой сортировки примет вид:

бысорт([],[]).

бысорт([H|T],S):-разбить(Н,Т,А,В),бысорт(А,А1),бысорт(В,В1), присоединить(А1, [H|B1],S).

Предикат присоединитьможно встроить внутрь программы сортировки. Тогда получается другой предикат

бысорт2 ([H|T], S,X):-разбить(Н,T,А,В), бысорт2(А,S,[Н|Y]), бысорт2(B,Y,X).

бысорт2([],Х,Х).

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

Более подробные сведения о методах сортировки можно найти в книге D. Knuth, The Art of Computer Programming,v. 3 (Sort and Searching), Addison-Wesley, 1973 (Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, т. 3 (Сортировка и поиск). М.: Мир, 1978.- Перев.)Метод быстрой сортировки Хоора описан в его статье в Computer Journal n. 5 (1962), стр. 10-15.

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

эти решения?

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

7.8. Использование базы данных: random, генатом, найтивсе

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

Генератор случайных чисел (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, нужно задать следующий вопрос: