Списки на Прологе (часть 2) Лекция 7

План Сумма, среднее арифметическое элементов списка, поиск минимального значения Сортировка списка (простого обмена, вставками, выбором, быстрая, слияниями)

Сумма элементов списка sum([], 0). /* сумма элементов пустого списка равна нулю */ sum([H|T], S) :– sum(T, S_T), /* S_T - сумма элементов хвоста */ S = S_T + H. /* S - сумма элементов исходного списка */

Сумма элементов списка sum_list([],S,S). /* список стал пустым, значит в накопителе – сумма элементов списка */ sum_list([H|T],N,S) :– N_T=H+N, /* N_T - результат добавления к сумме, находящейся в накопителе, первого элемента списка */ sum_list(T,N_T,S). /* вызываем предикат от хвоста T и _T */ sum2(L,S):– sum_list(L,0,S).

Среднее арифметическое элементов списка avg(L,A):– summa(L,S), /* помещаем в переменную S сумму элементов списка */ length(L,K), /* переменная K равна количеству элементов списка */ A=S/K. /* вычисляем среднее как отношение суммы к количеству */ avg([],0):–!.

Минимальный элемент списка min_list([X],X). min_list([H|T],M):– min_list(T,M_T), min(H,M_T,M).

Сортировка: метод прямого обмена permutation([X,Y|T],[Y,X|T]):– X>Y,!. permutation([X|T],[X|T1]):– permutation(T,T1). bubble(L,L1):– permutation(L,LL), !, bubble(LL,L1). bubble(L,L).

Сортировка вставкой ins_sort([ ],[ ]). ins_sort([H|T],L):– ins_sort(T,T_Sort), insert(H,T_Sort,L). insert(X,[],[X]). insert(X,[H|T],[H|T1]):– X>H,!, insert(X,T,T1). insert(X,T,[X|T]).

Сортировка выбором choice([ ],[ ]). choice(L,[X|T]):– min_list(L,X), delete_one(X,L,L1), choice(L1,T).

Быстрая сортировка quick_sort([],[]). quick_sort([H|T],O):– partition(T,H,L,G), quick_sort(L,L_s), quick_sort(G,G_s), conc(L_s,[H|G_s],O). partition([],_,[],[]). partition([X|T],Y,[X|T1],Bs):– X

Объединение отсортированных списков fusion(L1,[ ],L1):–!. fusion([ ],L2,L2):–!. fusion([H1|T1],[H2|T2],[H1|T]):– H1

Сортировка слияниями splitting([],[],[]). splitting([H],[H],[]). splitting([H1,H2|T],[H1|T1],[H2|T2]):– splitting(T,T1,T2). fusion_sort([],[]):–!. fusion_sort([H],[H]):–!. fusion_sort(L,L_s):– splitting(L,L1,L2), fusion_sort(L1,L1_s), fusion_sort(L2,L2_s), fusion(L1_s,L2_s,L_s).

Проверка упорядоченности списка sorted([ ]). sorted([_]). sorted([X,Y|T]):– X