npak
|
|
« Ответ #2 : 25-05-2006 08:47 » |
|
Katya,
неужели пока зачёт не грянул, вы не читали учебник по Prolog? Возмите книгу Ивана Братко "Программирование на языке ПРОЛОГ для искусственного интеллекта" и прочтите главы 1 и 3. Этого будет достаточно, чтобы понять программу quicksort.
C другой стороны, в упомянутых главах 60 страниц, "многа букоф, ниасилить", поэтому кратко объясню программу. Но заранее предупреждаю, если с этим описанием вы пойдёте программу сдавать, без знания языка, то рискуете не ответить на элементарные дополнительные вопросы.
Сначала небольшое введение. Язык пролог описывает отношения между объектами. В приведённой программе определяются два отношения - quicksort и split. Отношение quicksort двухместное, split - четырёхместное.
quicksort(X, Y) даёт ответ yes, если список Y является результатом сортировки списка Y. Например, если в интерактивной сессии Prolog задать вопрос ?- quicksort([2,1], [1,2]). то система ответит yes, а на вопрос ?- quicksort([2,1], [2,1]). ответит no
Однако пролог может не только отвечать на вопросы "Объект Х находится в отношении quicksort с объектом Y", но и самостоятельно искать ответ на вопрос "Найди объект Y, который находится в отношении quicksort с объектом X". Например, если задать вопрос ?- quicksort([2,1], Y). то система ответит "Y = [1, 2]". Как пролог-система ищет ответ - см. учебники.
Вернёмся к программе. Предложение "quicksort([],[])." обозначает, что пустому списку соответствует пустой список". Дальше определяется отношение quicksort для непустого списка на первом месте. Предложение начинается с "quicksort([X|Tail], Sorted) :-", которое читается так: список Sorted quicksort-соответствует списку, у которого первый элемент X, а остальные элементы обозначаются как Tail, если 1. Есть такие объекты Small и Big, которые находятся в отношении split с объектами X и Tail, и 2. Есть такой объект SortedSmall, который находится в отношении quicksort с объектом Small, и 3. Есть такой объект SortedBig, который находится в отношении quicksort с объектом Big, и 4. Объект Sorted находится в отношении append с объектом SortedSmall и списком, полученным добавлением объекта X в голову объекта (из операции следует, что это список) SortedBig.
|