Учебная работа № 341447. Тема: Операции над множествами

Учебная работа № 341447. Тема: Операции над множествами

Выдержка из похожей работы

…

Множества и операции над ними (2)

…….редством текстового
меню, вводом определенного символа в
ответ на запрос – выбор по желанию
автора). Операции: вхождение
A
B, A
B, A
B, A\B (дополнительно:
B\A, A
B, B
A).

Программа посредством алгоритма
типа слияния определяет результат
выбранной операции и выдает его на
экран с необходимыми пояснениями.
Одновременно с результатом на экране
должны присутствовать и исходные
множества.

Возврат на п.2 (выбор операции).

Завершение работы
программы – из п.2 (например,
по ESC).

Дополнительно:
предусмотреть возможность возврата не
только к выбору операции (п.2), но и к
вводу новых множеств (п.1). Выход в таком
случае должен быть возможен из любого
пункта (1 или 2).

Замечание: Исходные
множества не должны содержать повторяющихся
элементов (при обработке входных данных
такие элементы следует удалять). Если
исходные множества не упорядочены,
нужно отсортировать их по возрастанию.
Только после такой обработки над
множествами возможно выполнять требуемые
операции.

Решение.
Множества
будем хранить как массив с нумерацией
элементов, начинающейся с единицы.
Объединение
множеств.
Обозначим
через i номер текущего
рассматриваемого элемента в множестве
A, через j –
номер текущего рассматриваемого элемента
множества B. Будем получать
множество U, представляющее
собой объединение множеств A
и B. Через k
обозначим мощность множества U.
Также k будет и номером
последнего добавленного элемента в U.
Алгоритм
решения.

Положить i
= j =1, k = 0.
Если ещё не
просмотрены все элементы множеств A,
B выполнить:

Если в A
ещё есть элементы, и в B
есть элементы и A[i]
= B[j], то

Добавить A[i]
в U, то есть k
:= k + 1 и U[k]
:= A[i]
Перейти к следующим
элементам в A и B,
то есть i := i
+ 1 и j := j
+ 1

Если в B
уже все элементы были просмотрены или
же A[i]

Добавить A[i]
в U, то есть k
:= k + 1 и U[k]
:= A[i]
Перейти к следующему
элементу множества A,
то есть i := i
+ 1

Во всех остальных
случаях (то есть когда в A
уже все элементы просмотрены или же
если A[i] >
B[j])
выполнить:

Добавить B[j]
в U, то есть k
:= k + 1 и U[k]
:= B[j];
Перейти к следующему
элементу множества B,
то есть j := j
+ 1

Перейти к пункту
2.

Как видно,
на каждом шаге мы добавляем в U
минимальный элемент из A[i]
и B[j] и
переходим к рассмотрению следующе
…