Автор работы: Пользователь скрыл имя, 20 Января 2013 в 16:15, курсовая работа
Курсовой проект “Сортировка данных” разработан на языке программирования ТурбоПролог, учитывая всю специфику данного языка, а особенно работа со списками и рекурсия.
Сила Турбо-Пролога заключается в его возможностях поиска и сопоставления. Внутренние унификационные процедуры бесстрастно перебирают все возможные комбинации правил, пытаясь удовлетворить заданную программистом цель. Пролог, как видим, базируется на естественных для человека логических принципах, и поэтому, чем больше вы им занимаетесь, тем он становится все более привлекательным.
fusion_sort(List,_,Nf,'n'),
write(" Количество рекуссий при сортировке перестановкой = ",Np),nl,
write(" Количество рекуссий при сортировке вставкой = ",Nv),nl,
write(" Количество рекуссий при быстрой сортировке = ",Nq),nl,
write(" Количество рекуссий при сортировке слиянием = ",Nf),nl,
q_sort(Np,Nv,Nq,Nf,Sort),
write(" Самая быстрая сортировка
- ",Sort,"."),nl,write("Нажмите
клавишу..."),nl,nl,
readchar(_),!.
process(27):-!.
process(_):-
write("Ошибка при вводе."),nl,write("Нажмите любую клавишу..."),nl,
readchar(_),!.
repeat.
repeat:-repeat.
read_list([H|T]):-
readln(H),
H<>"",
read_list(T).
read_list([]).
write_list([]).
write_list([H|T]):-
write(H),nl,
write_list(T).
sort_p(List,List_s,N,C):-
perest(List,List1,Np),!,
write_s(List1,C),
sort_p(List1,List_s,N1,C),
N=N1+Np+1.
sort_p(List_s,List_s,1,_).
perest([X,Y|T],[Y,X|T],1):-X>
perest([H|T1],[H|T2],N):-
sort_v([],[],1,_).
sort_v([H|T],L_posle,N,C):-
sort_v(T,L_do,N1,C),
insert(H,L_do,L_posle,Nv),
write_s(L_posle,C),
N=N1+Nv+1.
insert(E,[],[E],1).
insert(E,[H|T1],[H|T2],N):-
E>H,
insert(E,T1,T2,N1),N=N1+1.
insert(E,[H|T],[E,H|T],1):-
E<=H.
sort_q1([],[],1,_).
sort_q1([H|T],List_s,N,C):-
devide(H,T,Mal,Bol,Nd),
sort_q1(Mal,Mal_s,N1,C),
sort_q1(Bol,Bol_s,N2,C),
connect(Mal_s,[H|Bol_s],
write_s(List_s,C),
N=Nc+Nd+N1+N2+1.
devide(_,[],[],[],1).
devide(X,[Y|T],[Y|Mal],Bol,N):
X>Y,!,
devide(X,T,Mal,Bol,N1),N=N1+
devide(X,[Y|T],Mal,[Y|Bol],N):
connect([],L,L,1).
connect([H|L1],L2,[H|L3],N):-
q_sort(Np,Nv,Nq,Nf,Sort):-Np<=
q_sort(Np,Nv,Nq,Nf,Sort):-Nv<=
q_sort(Np,Nv,Nq,Nf,Sort):-Nq<=
q_sort(Np,Nv,Nq,Nf,Sort):-Nf<=
write_s(List,'y'):-
write(" Полученный список:"),nl,
write_list(List),nl,
readchar(_),!.
write_s(_,_).
fusion(L1,[ ],L1,1):-!.
fusion([ ],L2,L2,1):-!.
fusion([H1|T1],[H2|T2],[H1|T],
H1<H2,!,
fusion(T1, [H2|T2],T,N1),N=N1+1.
fusion(L1, [H2|T2],[H2|T],N):-fusion(L1,
splitting([],[],[],1).
splitting([H],[H],[],1).
splitting([H1,H2|T],[H1|T1],[
splitting(T,T1,T2,N1),N=N1+1.
fusion_sort([],[],1,_):-!.
fusion_sort([H],[H],1,_):-!.
fusion_sort(L,L_s,N,C):-
splitting(L,L1,L2,Ns),
fusion_sort(L1,L1_s,N1,C),
fusion_sort(L2,L2_s,N2,C),
fusion(L1_s,L2_s,L_s,Nf),
N=Ns+N1+N2+Nf.
GOAL
begin_work.
Первоначальное меню, появляющееся при запуске программы.
Рис. 6.1. – Меню программы
При выборе с первого по четвертый пункт меню программа предоставляет пользователю ввести список который надо отсортировать с помощью одной из четырех видов сортировки:
«1. Сортировка перестановкой»
«2. Сортировка вставкой»
«3. Быстрая сортировка»
«4. Сортировка слиянием»
Рис. 6.2. – Сортировка перестановкой
Рис. 6.3. – Сортировка вставкой
Рис. 6.4. – Быстрая сортировка
Рис. 6.5. – Сортировка слиянием
При выборе пятого пункта меню «5. Оценка алгоритма на быстродействие» программа предоставляет пользователю ввести список, который будет отсортирован четырьмя сортировками и выдаст наиболее эффективную из них, то есть по наименьшему количеству рекурсий.
Рис. 6.6. – Оценка алгоритма на быстродействие
При вводе цифры, не соответствующей ни одному из пунктов меню, отображается сообщение об ошибке и предложение ввести цифру снова.
Рис. 6.7. – Сообщение об ошибке ввода данных
Для выхода из программы следует нажать кнопку ESC.
Рис. 6.8. – Выход
Данная программа выполняется на любом ЭВМ под управлением операционной системы семейства Windows.
При запуске программы появляется главное меню. Для дальнейшей работы необходимо выбрать один из пунктов меню:
1)Сортировка перестановкой;
2) Сортировка вставкой;
3) Быстрая сортировка;
4) Сортировка слиянием;
5) Оценка алгоритма на быстродействие;
После выбора соответствующего пункта меню, нужного для пользователя, будет представлена дальнейшая информация по работе с программой, в частности будет предложено ввести список для его дальнейшей сортировки. В целом интерфейс программы понятен любому пользователю.
Выводы
Данный курсовой проект был разработан с целью получения навыков программирования на языке ТурбоПролог при работе c сортировкой списков и анализе полученных сортировок. Разработанный интерфейс позволяет легко выбрать любой пункт меню для демонстрации одной из четырех реализованных сортировок. Готовую полученную программу можно использовать для демонстрации и решения поставленных задач. А также по отдельности можно использовать разработанный интерфейс программы и предикаты при реализации других программ.
Были рассмотрены четыре вида сортировки:
Был продемонстрирован поэтапно каждый вид сортировки.
По производительности сортировок
можно сделать следующие выводы
Литература
1. Братко Иван. Алгоритмы искусственного интеллекта на языке PROLOG, 3-е издание.: Пер. с англ. — М.: Издательский дом "Вильяме", 2004. — 640 с.: ил.
2. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. — СПб.: —"БХВ-Петербург", 2003. — 992 c.