TURBO PROLOG. Терёхин В.В. - 112 стр.

UptoLike

ВУЗ: 

НФИ КемГУ | Новокузнецк

Составители: 

Рубрика: 

112
Три метода обычно применяются для сортировки списков: метод пе-
рестановки, метод вставки и метод выборки. Сортировку можно произвести
любым из трех названных методов или их комбинацией. Первый из пере-
численных методов заключается в перестановке элементов списка до тех пор,
пока они не выстроятся в нужном порядке. Второй осуществляется при
помощи
неоднократной вставки элементов в список до тех пор, пока он не
будет упорядочен. Третий включает в себя многократную выборку и пере-
мещение элементов списка.
Второй из методов, метод вставки, особенно удобен для реализации
на Турбо-Прологе. Сейчас мы зададимся целью написать правило, реали-
зующее этот метод.
Рассмотрим список [4,7,3,9], элементы которого
расположены случай-
ным образом. Мы хотим получить список [3,4,7,9], упорядоченный по поряд-
ку возрастания элементов.
Опишем предикат, производящий нужную сортировку списка методом
вставки.
insert_sort(source_list,target_list)
Внешней целью в задаче сортировки списка [4,7,3,9] будет утвержде-
ние
insert_sort([4,7,3,9],S).
В этом утверждении отсортированный список обозначен переменной S. Для
того, чтобы воспользоваться преимуществами мощного средства Турбо-
Пролога - внутренней унификацией, мы проделаем то, что обычно называет-
ся сортировкой хвоста. Напомним, что список всегда можно разбить на голо-
ву и хвост. Перед тем, как первый элемент списка будет присвоен голове
списка, его хвост в действительности содержит весь список целиком. Сле-
довательно, сортировка хвоста есть не что иное, как сортировка
самого спи-
ска.
Правила, реализующие этот способ сортировки, имеют следующую
структуру:
insert_sort([],[]).
insert_sort([X|Tail],Sorted_list) :-
insert_sort(Tail,Sorted_Tail),
in-sert(X,Sorted_Tail,Sorted_list).
insert(X,[Y|Sorted_list],[Y|Sorted_list1]) :-
asc_order(X,Y), !,
insert(X,Sorted_list,Sorted_list1).
insert(X,Sorted_list,[X|Sorted_list]).
asc_order(X,Y) :- X>Y.
Дальнейшее обсуждение продемонстрирует работу правил на примере
списка [4,7,3,9].
Вначале Турбо-Пролог применяет приведенные правила к исходному
списку, выходной список в этот момент еще не определен.
insert_sort([4,7,3,9],_). 
      Три метода обычно применяются для сортировки списков: метод пе-
рестановки, метод вставки и метод выборки. Сортировку можно произвести
любым из трех названных методов или их комбинацией. Первый из пере-
численных методов заключается в перестановке элементов списка до тех пор,
пока они не выстроятся в нужном порядке. Второй осуществляется при
помощи неоднократной вставки элементов в список до тех пор, пока он не
будет упорядочен. Третий включает в себя многократную выборку и пере-
мещение элементов списка.
      Второй из методов, метод вставки, особенно удобен для реализации
на Турбо-Прологе. Сейчас мы зададимся целью написать правило, реали-
зующее этот метод.
      Рассмотрим список [4,7,3,9], элементы которого расположены случай-
ным образом. Мы хотим получить список [3,4,7,9], упорядоченный по поряд-
ку возрастания элементов.
      Опишем предикат, производящий нужную сортировку списка методом
вставки.
      insert_sort(source_list,target_list)
      Внешней целью в задаче сортировки списка [4,7,3,9] будет утвержде-
ние
      insert_sort([4,7,3,9],S).
В этом утверждении отсортированный список обозначен переменной S. Для
того, чтобы воспользоваться преимуществами мощного средства Турбо-
Пролога - внутренней унификацией, мы проделаем то, что обычно называет-
ся сортировкой хвоста. Напомним, что список всегда можно разбить на голо-
ву и хвост. Перед тем, как первый элемент списка будет присвоен голове
списка, его хвост в действительности содержит весь список целиком. Сле-
довательно, сортировка хвоста есть не что иное, как сортировка самого спи-
ска.
      Правила, реализующие этот способ сортировки, имеют следующую
структуру:
      insert_sort([],[]).
      insert_sort([X|Tail],Sorted_list) :-
                                insert_sort(Tail,Sorted_Tail),
                                in-sert(X,Sorted_Tail,Sorted_list).
      insert(X,[Y|Sorted_list],[Y|Sorted_list1]) :-
                                asc_order(X,Y), !,
                                insert(X,Sorted_list,Sorted_list1).
                                insert(X,Sorted_list,[X|Sorted_list]).
      asc_order(X,Y) :- X>Y.
      Дальнейшее обсуждение продемонстрирует работу правил на примере
списка [4,7,3,9].
      Вначале Турбо-Пролог применяет приведенные правила к исходному
списку, выходной список в этот момент еще не определен.
      insert_sort([4,7,3,9],_).



                                                                       112

Страницы