2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 [Пролог] интересная сортировка списка
Сообщение06.01.2007, 14:03 
Аватара пользователя
Отсортировать элементы списка, кратные Х, по возрастанию(остальные элементы остаются на своих местах)

Я написал вот это.
bubble(A,L1,L2):-change(A,L1,L3),!,bubble(A,L3,L2).
bubble(A,L,L).

change(A,[X,Y|T],[Y,X|T]):-
Temp is X mod A,
Temp is 0,
X>Y,!.
change(A,[X|T],[X|T1]):-change(A,T,T1).

Сортируются нужные элементы методом пузырька, только некратные элементы у меня тоже сдвигаются Подскажите, please

 
 
 
 
Сообщение06.01.2007, 21:51 
Аватара пользователя
Ваша ошибка в том, что в предикате change Вы меняете два соседних элемента, вне зависимости от того, сравним второй элемент по модулю или нет.
Правильный код может выглядеть так (здесь переставляются все четные - т.е. нужно будет немного поработать самому :lol: )
Код:
domains
list=integer*

predicates
nondeterm choice(list,integer,integer)
nondeterm add(integer, integer, list, list)
nondeterm sort_bubble(list, list)
nondeterm permutation(list, list)

clauses

add(A,N,[_|T],[A|T]):-N=1,!.
add(A,N,[H|T],[H|L]):-N1=N-1,add(A,N1,T,L).


choice([H|_],H,1):- (H mod 2)=0,!.
choice([H|T],H1,N):- (H mod 2)<>0,choice(T,H1,N1),N=N1+1.


permutation([H|T],[H1|T1]):-(H mod 2)=0, choice(T,H1,N), H>H1, add(H,N,T,T1),!.
permutation([X|T],[X|T1]):-permutation(T,T1).
                             
sort_bubble(L,L1):- permutation(L,LL),!,sort_bubble(LL,L1).
sort_bubble(L,L).

goal

sort_bubble([3,5,4,2,8,7,6,5,1,2,3,20,10],L).

 
 
 
 
Сообщение07.01.2007, 02:40 
Аватара пользователя
я нашел алгоритм. я сформировал 2 списка: один список исходный, второй список состоих из элементов кратных Х. Третий список формируется так: если элемент из первого списка кратен Х, то берем в третий список элемент их 2 списка, иначе - из первого списка.

Код
% удалить из списка элементы кратные Х
sublist([],[],A).
sublist([X|T],[X|T1],A):-Temp is X mod A,Temp =:= 0,sublist(T,T1,A).
sublist([X|T],T1,A):-sublist(T,T1,A).
%%%%%%%%%%%%%%%%%%
%по возрастанию упорядочиваем элементы в субсписке L2 состоящих из элеметтов кратныйх Х
sort(L1,L2,A):-sublist(L1,Lnew,A),change(Lnew,L3),!,sort(L3,L2,A).
sort(L,L,A).
change([X,Y|T],[Y,X|T]):-X>Y,!.
change([X|T],[X|T1]):-change(T,T1).
%%%%%%%%%%%%%%%%%%%%
Теперь проблема с постоением третьего списка из двух.... :oops:

 
 
 
 
Сообщение07.01.2007, 10:35 
Аватара пользователя
Эта плохая идея.
Я же дал Вам работоспособный код, только немного изменил, чтобы сами подумали. Разберитесь в нем.
Предикат add - добавляет заданный элемент на заданное место в списке.
Предикат choice - выбирает из списка первый четный и находит его номер.
Все остальное относится к пузырьковой сортировке.

Добавлено
Хотя я неправ. Ваша идея тоже работает. Только возни больше - Вы формируете промежуточный список из кратных, в моем алгоритме просто переставляются ближайшие кратные (т.е. как будто других нет).

 
 
 
 
Сообщение07.01.2007, 20:07 
Аватара пользователя
Артамонов Ю.Н. писал(а):
Хотя я неправ. Ваша идея тоже работает. Только возни больше - Вы формируете промежуточный список из кратных, в моем алгоритме просто переставляются ближайшие кратные (т.е. как будто других нет).

у меня проблема со вставкой элементов:(

 
 
 
 
Сообщение07.01.2007, 21:38 
Аватара пользователя
Попробуйте такой код:
Код:
insert([],_,[]):-!.
insert([H1|T1],[H2|T2],[H2|L]):- (H1 mod 2)=0,insert(T1,T2,L). 
insert([H1|T1],X,[H1|L]):- (H1 mod 2)<>0, insert(T1,X,L).

Здесь первый список - искомый, второй - из кратных, третий - результат.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group