Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Объединение N множеств
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Finogenov Finogenov вне форума
Member
 
Сообщений: 29
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.10.2007
По умолчанию 22.11.2007, 00:18

Почитал темы про множества про объединиия их, свою задачу решить не смог, а точнее вообще не понимаю, как это "Объединение N множеств"
Условия те же, под множеством понимается - список, который не содержит повторных вхождений элементов. Другими словами, во множестве любое значение не может встречаться более одного раза.
Вот кусок из лекций по обединению двух множеств:

Код:
union([ ],S2,S2). /* результатом объединения  
               пустого множества со множеством S2  
               будет множество S2 */
union([H|T],S2,S):–
            member3(H,S2), 
                /* если голова первого 
                  множества H принадлежит второму 
                  множеству S2, */
            !,
            union(T,S2,S). 
                /* то результатом S будет  
                 объединение хвоста первого 
                 множества T и второго 
                 множества S2 */
union([H  |T],S2,[H|S]):–
            union(T,S2,S). 
                /* в противном случае результатом 
                  будет множество, образованное 
                  головой первого множества H 
                  и хвостом, полученным объединением 
                  хвоста первого   множества T 
                  и второго множества S2 */
помогите заточить эту прогу под объединение N множеств.
Допустим ввел количество списков с клавы, а прога сгенерила их длинну, допустим 3-7, чтоб не особо длинные списки были. А потом на выходе список полученный объединением этих множеств
Ответить с цитированием
  (#2 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 22.11.2007, 21:47

Вот простой декларативный способ, этот код надо добавить к Вашей программе:
Код:
union_sets([],[]).
union_sets([Set|SetList],Union):- 
    union_sets(SetList,Union1), 
    union(Set,Union1,Union).
Цель: union_sets([[1,2],[2,3],[3,4,5]],Union).
Решение: Union=[1,2,3,4,5]
Ответить с цитированием
  (#3 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 22.11.2007, 23:36

Вот более эффективный вариант с тем же результатом:
Код:
union_sets(Sets,Union):- union_sets1(Sets,[],Union).

union_sets1([[A|Set]|Sets],Stack,Union):-
    member(A,Stack),
    !,
    union_sets1([Set|Sets],Stack,Union).
union_sets1([[A|Set]|Sets],Stack,[A|Union]):- !,
    union_sets1([Set|Sets],[A|Stack],Union).
union_sets1([_|Sets],Stack,Union):- 
    union_sets1(Sets,Stack,Union).
union_sets1([],_,[]).
Можно, конечно, сделать еще эффективнее (особенно в VIP7 с красно-черными деревьями).
Ответить с цитированием
  (#4 (permalink)) Старый
Finogenov Finogenov вне форума
Member
 
Сообщений: 29
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.10.2007
По умолчанию 24.11.2007, 12:04

Помогие всё это собрать мне вместе. Начну попорядку:
Задать множество, чтобы не было повторных вхождений
Код:
 domains
il=integer*
predicates
delete_all(il,il,il).
clauses
delete_all(_,[],[]).
delete_all(X,[X|L],L1):-delete_all(X,L,L1).
delete_all(X,[Y|L],[Y|L1]):-X<>Y,delete_all(X,L,L1).
В качестве операции принадлежности элемента множеству, нужно использовать предикат:
Код:
member3(X,[X|_]):–!.
member3(X,[_|T]):–member3(X,T).
затем используя эту идею:
Код:
union([ ],S2,S2). /* результатом объединения  
               пустого множества со множеством S2  
               будет множество S2 */
union([H|T],S2,S):–
            member3(H,S2), 
                /* если голова первого 
                  множества H принадлежит второму 
                  множеству S2, */
            !,
            union(T,S2,S). 
                /* то результатом S будет  
                 объединение хвоста первого 
                 множества T и второго 
                 множества S2 */
union([H  |T],S2,[H|S]):–
            union(T,S2,S). 
                /* в противном случае результатом 
                  будет множество, образованное 
                  головой первого множества H 
                  и хвостом, полученным объединением 
                  хвоста первого   множества T 
                  и второго множества S2 */
добавить Ваше рассуждение:
Код:
union_sets([],[]).
union_sets([Set|SetList],Union):- 
    union_sets(SetList,Union1), 
    union(Set,Union1,Union).
не получаеться собрать всё вместе, куча мелких ошибок.
Ответить с цитированием
  (#5 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,955
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 24.11.2007, 16:57

А Вы на каком Прологе пишете?
Если на ISO-Прологах, то надо убрать декларативную часть:
Код:
domains
il=integer*
predicates
delete_all(il,il,il).
clauses
и всё должно заработать.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Finogenov Finogenov вне форума
Member
 
Сообщений: 29
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.10.2007
По умолчанию 25.11.2007, 00:01

На Turbo Prolog. Еслиб я знал что еще такое "декларативная часть". Пожалуйста помогите собрать всё вместе в готовый код.
Ответить с цитированием
  (#7 (permalink)) Старый
Finogenov Finogenov вне форума
Member
 
Сообщений: 29
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.10.2007
По умолчанию 27.11.2007, 20:28

Код:
domains
il = integer*
predicates
member3(il,il).
union(il,il,il).
union_sets(il,il).
clauses
member3(X,[X|_]):-!.
member3(X,[_|T]):-member3(X,T).
union([ ],S2,S2).
union([H|T],S2,S):-member3(H,S2),!,union(T,S2,S). 
union([H|T],S2,[H|S]):-union(T,S2,S). 
union_sets([],[]).
union_sets([Set|SetList],Union):-
union_sets(SetList,Union1),
union(Set,Union1,Union).
пока без предиката delete_all решил попробовать, пишет ошибку missing на строчку member3(X,[X|_]):-!.
Ответить с цитированием
  (#8 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,955
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 28.11.2007, 00:00

У Вас должен быть ещё один домен: список списков. Это необходимо для определения первого аргумента в предикате union_sets(ill,il).
Код:
ill = il*
Ответить с цитированием
  (#9 (permalink)) Старый
Finogenov Finogenov вне форума
Member
 
Сообщений: 29
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.10.2007
По умолчанию 28.11.2007, 19:54

Вот такой код есть, выкладываю его специально для тех у кого может встретиться такая же задача, чтоб не парились

Код:
domains
ListS=integer*
predicates
list_set(ListS,ListS).
delete_all(integer,ListS,ListS).
union(ListS,ListS,ListS).
member(integer,ListS).
start(integer,ListS,ListS).
clauses
member(X,[X|_]) :- !.
member(X,[_|T]) :- member(X,T).
delete_all(_,[],[]).
delete_all(X,[X|L],L1) :- delete_all(X,L,L1).
delete_all(X,[Y|L],[Y|L1]) :- X<>Y, delete_all(X,L,L1).
list_set([],[]).
list_set([H|T],[H|T1]) :- delete_all(H,T,T2), list_set(T2,T1).
union([],S2,S2).
union([H|T],S2,S) :- member(H,S2),!, union(T,S2,S).
union([H|T],S2,[H|S]) :- union(T,S2,S).
start(0,A,B):-union(A,[],B),!.
start(N,A,B):-N1=N-1,write("Введите следующее множество:"),
              readterm(ListS,M2),list_set(M2,M1),start(N1,M1,M),union(A,M,B).
goal
write("Введите количество объединяемых множеств:"),
readint(N1),
N=N1-1,
write("Введите первое множество:"),
readterm(ListS,A),
start(N,A,B),
write("Полученное множество:",B).
всем спасибо за советы и помощь
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите с задачей про включение множеств Barso4ka Prolog 3 05.12.2010 23:42
Хвостовая рекурсия для пересечения множеств alt_1111111 Prolog 10 29.11.2010 18:25
Пересечение множеств pasha51113 Prolog 6 30.04.2010 15:54
Cимметpичная pазность множеств glyc Lisp 2 29.04.2010 11:17
Пересечение множеств Пальмира Prolog 3 29.07.2009 19:45
Написать функцию UNION, которая вычисляет объединение двух множеств Horror Lisp 22 06.01.2008 11:08
Написать функцию UNION, которая вычисляет объединение двух множеств Serg13 Lisp 3 13.09.2007 14:22
Написать функцию UNION,которая вычисляет объединение множеств compadre_sai Lisp 1 24.05.2007 02:11
Результат симметричной разности множеств в Паскале Колобок Вопросы начинающих программистов 1 19.02.2007 18:58
Оптимизация разницы множеств Bogdan1024 MSSQL Server 1 17.08.2006 08:07
Алгебра множеств как ее понять Richard С/С++ 26 16.01.2006 16:54
Пересечение множеств NetSlow Prolog 6 22.05.2005 18:59



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов