Читаем Программирование на языке пролог полностью

Заметим, что здесь применяется тот же самый предикат присоединить, с которым мы встречались ранее. Этот пример отличается от предыдущих необходимостью возвратного хода после каждого найденного решения. Поэтому в первом правиле в определении пусорт«отсечение» не используется. Эта программа еще один пример «недетерминированного» программирования,- для выбора элементов списка 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.Быстрая сортировка лучше всего работает ка больших списках, поскольку там она обеспечивает более быструю сходимость к решению. В то же время объем работы, выполняемой на каждом уровне рекурсии быстрой сортировки, превышает то, что делается в других методах, из-за использования разбить. Поэтому, при сортировке небольших списков рекурсивные вызовы бысорт,видимо, можно заменить обращениями к другим методам сортировки, например, к сортировке включением. Разработайте «гибридную» программу, которая использует быструю сортировку для обработки больших подсписков (списков, полученных с помощью предиката разбить),но переключается на другой метод (сортировка включением) при значительном уменьшении длины подсписка. Подсказка: поскольку разбитьдолжен просмотреть все элементы списка, то он может заодно подсчитать и длину списка.

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

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

Генератор случайных чисел (random)
Перейти на страницу:

Похожие книги

Основы программирования в Linux
Основы программирования в Linux

В четвертом издании популярного руководства даны основы программирования в операционной системе Linux. Рассмотрены: использование библиотек C/C++ и стан­дартных средств разработки, организация системных вызовов, файловый ввод/вывод, взаимодействие процессов, программирование средствами командной оболочки, создание графических пользовательских интерфейсов с помощью инструментальных средств GTK+ или Qt, применение сокетов и др. Описана компиляция программ, их компоновка c библиотеками и работа с терминальным вводом/выводом. Даны приемы написания приложений в средах GNOME® и KDE®, хранения данных с использованием СУБД MySQL® и отладки программ. Книга хорошо структурирована, что делает обучение легким и быстрым. Для начинающих Linux-программистов

Нейл Мэтью , Ричард Стоунс , Татьяна Коротяева

ОС и Сети / Программирование / Книги по IT
Программист-прагматик. Путь от подмастерья к мастеру
Программист-прагматик. Путь от подмастерья к мастеру

Находясь на переднем крае программирования, книга "Программист-прагматик. Путь от подмастерья к мастеру" абстрагируется от всевозрастающей специализации и технических тонкостей разработки программ на современном уровне, чтобы исследовать суть процесса – требования к работоспособной и поддерживаемой программе, приводящей пользователей в восторг. Книга охватывает различные темы – от личной ответственности и карьерного роста до архитектурных методик, придающих программам гибкость и простоту в адаптации и повторном использовании.Прочитав эту книгу, вы научитесь:Бороться с недостатками программного обеспечения;Избегать ловушек, связанных с дублированием знания;Создавать гибкие, динамичные и адаптируемые программы;Избегать программирования в расчете на совпадение;Защищать вашу программу при помощи контрактов, утверждений и исключений;Собирать реальные требования;Осуществлять безжалостное и эффективное тестирование;Приводить в восторг ваших пользователей;Формировать команды из программистов-прагматиков и с помощью автоматизации делать ваши разработки более точными.

А. Алексашин , Дэвид Томас , Эндрю Хант

Программирование / Книги по IT
97 этюдов для архитекторов программных систем
97 этюдов для архитекторов программных систем

Успешная карьера архитектора программного обеспечения требует хорошего владения как технической, так и деловой сторонами вопросов, связанных с проектированием архитектуры. В этой необычной книге ведущие архитекторы ПО со всего света обсуждают важные принципы разработки, выходящие далеко за пределы чисто технических вопросов.?Архитектор ПО выполняет роль посредника между командой разработчиков и бизнес-руководством компании, поэтому чтобы добиться успеха в этой профессии, необходимо не только овладеть различными технологиями, но и обеспечить работу над проектом в соответствии с бизнес-целями. В книге более 50 архитекторов рассказывают о том, что считают самым важным в своей работе, дают советы, как организовать общение с другими участниками проекта, как снизить сложность архитектуры, как оказывать поддержку разработчикам. Они щедро делятся множеством полезных идей и приемов, которые вынесли из своего многолетнего опыта. Авторы надеются, что книга станет источником вдохновения и руководством к действию для многих профессиональных программистов.

Билл де Ора , Майкл Хайгард , Нил Форд

Программирование, программы, базы данных / Базы данных / Программирование / Книги по IT