Статьи / Задачи с решениями - часть вторая (Задача №1: Реализовать операции работы с множествами)
В статье рассматривается 7 задач и предлагаются детали реализации.
Автор: Потапенко В.А.
Написал: artish   Дата: 2008-09-09 20:10
Комментарии: (0)   Рейтинг:
Пока комментариев нет
Задача: Реализовать операции работы с множествами

    1. Пересечение множеств
    2. Объединение множеств
    3. Вычитание множеств
    4. Симметрическая разность


Определения:

Объединением множеств A и B называется множество

Пересечением множеств A и B называется множество

Разностью множеств A и B называется множество

Симметрической разностью множеств A и B называется множество


Решение

Для решения задачи необходимо определиться с представлением множеств. В качестве представления выберем списки. Таким образом, множество из элементов A,B,C будет представлено в виде списка (A B C). Многоуровневые списки естественным образом представляют множество
множеств.

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

Начнем с объединения множеств. Решением является функция union~ от двух аргументов a, b, которые представляют два объединяемых множества. Единственность элемента, его уникальность – вот свойство множеств, которое требует реализации. Таким образом, решение можно свести к рекурсивной обработке одного из аргументов на осове слудующих соображений:

Если a пусто, то вернуть b
Если b пусто, то вернуть a
Если (car a) принадлежит множеству b, то результат:
(cons (car a) (union~ (cdr a) b)
В противном случае результат:
(union~ (cdr a) b)

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

В силу того, что мы ограничились рассмотрением одноуровневых списков, то (car a) всегда будет элементом, атомом. Тогда понятие принадлежности можно формализовать как функцию in-predicate от двух аргументов, первый из которых атом, а второй – одноуровневый спискок, представляющий множество:
 
(defun in-predicate (a l)
(cond
((null l) nil) ; элемент не может принадлежать пустому множеству
((eq a (car l)) t) ; элемент принадлежит множеству, если в нем содержится
(t (in-predicate a (cdr l))) ; продолжаем проверку
)
)
 

Тестирование:
 
> (in-predicate 'a '(b c a))
T
> (in-predicate 'a '(b c d))
NIL
 

Формализуя, получаем решение:
 
(defun union~ (a b)
(cond ((null a) b)
((null b) a)
((in-predicate (car a) b) (union~ (cdr a) b) )
(t (cons (car a) (union~ (cdr a) b)))
)
)
 

Тестирование:
 
> (union~ '(a b c) '(b c d))
“Лисп со всех сторон” --- В.А. Потапенко --- vp@green.iis.nsk.su 2
(A B C D)
> (union~ '(a b c) 'nil)
(A B C)
> (union~ 'nil 'nil)
NIL
> (union~ '(a b) '(c d))
(A B C D)
 

По аналогии с объединением легко написать разность и пересечение, потому что их определения опираются на понятие принадлежности, которое формализовано предикатом in-predicate.

Приведем решения:

Пересечение - intersection~
 
(defun intersection~ (a b)
(cond
; nil является естественным представлением пустого множества
((null a) nil)
((null b) nil)
((in-predicate (car a) b) (cons (car a) (intersection~ (cdr a) b)) )
(t (intersection~ (cdr a) b))
)
)
 

Тестирование:
 
> (intersection~ '(a b c) '(b c d) )
(B C)
> (intersection~ '(a ) '( d) )
NIL
> (intersection~ '(a ) 'nil )
NIL
 

Разность – difference~
 
(defun difference~ (a b)
(cond
((null a) nil)
((null b) a)
((in-predicate (car a) b) (difference~ (cdr a) b))
(t (cons (car a)(difference~ (cdr a) b)))
)
)
 

Тестирование:
 
> (difference~ '(a b c) '(b c e))
(A)
> (difference~ '(a b c) '(b c e a))
NIL
> (difference~ '(a b c) 'nil)
(A B C)
> (difference~ '(a b c) '(q w e r))
(A B C)
 

Симметрическая разность symmetry-difference~ выражется через объединение и разность, а значит может быть реализовано следующим образом:
 
(defun symmetry-difference~ (a b)
(union~ (difference~ a b) (difference~ b a))
)
 

Тестирование:
 
> (symmetry-difference~ '(a b c) '(b c e))
(A E)
 

Для решения этой задачи ключевым являлось выражение формализация представления множеств и реализация концепции принадлежности. Построив более универсальную реализацию концепции принадлежности мы сразу получим реализацию пересечения, объединения и т.п. для более широкого класса множеств.
> 1 < [2] [3] [4] [5] [6] [7]


Онлайн :

0 пользователь(ей), 14 гость(ей) :




Реклама на сайте: