Практикум по теме

Составить и отладить программу, реализующую обработку множеств по предложенному заданию.

1. Уточнить задание: записать его в виде формулы для получения пятого множества по заданным четырём, используя знаки операций над множествами. Результат может выглядеть так:

E = A B ⋂ C \ D

2. Предложить контрольный тест в соответствии с заданным типом универсума

A = {1, 2, 3, 4, 5}

B = {2, 4, 6}

C = {4, 6, 7, 8}

D = {1, 3, 9}

E =? (вычислить результат!)

3. Составить программу для вычисления пятого множества по четырём заданным, используя для представления множеств в памяти массивы символов. Для задания исходных множеств использовать инициализацию. Добиться прохождения теста.

4. Добавить в программу ввод исходных множеств и протестировать её на нескольких тестах: на пустых, полных, не пересекающихся, совпадающих множествах и т. п. Рекомендуется использовать для ввода символов функцию gets(), а для определения мощности множества — функцию strlen().

5. Дополнить программу так, чтобы исходные множества из массивов преобразовывались в линейные списки, и получение результата достигалась обработкой этих списков.

1.1.2. Варианты индивидуальных заданий к теме «Множества»

№ варианта	Универсум	Что надо вычислить
	Десятичные цифры	Множество, содержащее цифры, общие для мно­жеств A и B, а также все цифры из множества C и из множества D

Продолжение таблицы

№ варианта	Универсум	Что надо вычислить
	Прописные латинские буквы	Множество, содержащее все символы из множества A, за исключением символов, содержащихся в B или в C, а также все символы мно­жества D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры, имеющиеся в любом из множеств A, B, C, и D
	Строчные латинские буквы	Множество, содержащее все буквы, общие для мно­жеств A и B, за исключением букв, содержащихся в C, а также все буквы из D
	Десятичные цифры	Множество, содержащее все цифры мно­жества A, за ис­ключением цифр из B и C, а также все цифры из D
	Русские буквы	Множество, содержащее все буквы мно­жеств A и B, за исключением букв, содержащихся в C, а также все буквы из D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры, имеющиеся в каждом из мно­жеств A, B, C, а также все цифры из D
	Латинские буквы	Множество, содержащее буквы, имеющиеся во мно­же­стве A, но не являющихся общими для B и C, и все буквы из D
	Десятичные цифры	Множество, содержащее все цифры из A, все цифры, общие для множеств B и C, а также все цифры из D
	Прописные латинские буквы	Множество, содержащее буквы, имеющиеся в A или B, но отсутствующие в C, кроме того, обязательно встречающиеся также и в D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры, имеющиеся во мно­же­ствах A или C, но отсутствующие в B или D
	Строчные латинские буквы	Множество, содержащее буквы, имеющиеся в любом из множеств A, B, C, но отсутствующие в D
	Десятичные цифры	Множество, содержащее цифры, общие для мно­жеств A и B, но не встречающиеся ни в C, ни в D
	Прописные русские буквы	Множество, содержащее все буквы множества A, которых нет во множествах B, C или D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры, имеющиеся в A или B, но отсутствующие и в C, и в D
	Строчные русские буквы	Множество, содержащее буквы, общие для множеств A, B, C и не встречающиеся D
	Десятичные цифры	Множество, содержащее цифры из A, не являющиеся об­щими для множеств B и C и не встречающиеся в D
	Русские буквы	Множество, содержащее буквы, имеющиеся в A или об­щие для B и C, но не встречающиеся в D

Продолжение таблицы

№ варианта	Универсум	Что надо вычислить
	Шестнадца­те­ричные цифры	Множество, содержащее все цифры, общие для A и B, а также все цифры, являющиеся общими для C и D
	Латинские буквы	Множество, содержащее буквы из множества A, не содержащиеся в B, а также все общие для C и D
	Десятичные цифры	Множество, содержащее цифры, имеющиеся в A или B или являющиеся общими для C и D
	Прописные русские буквы	Множество, содержащее буквы, общие для A и B, но не являющиеся общими для C и D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры из A, не встречающиеся в B и не являющиеся общими для C и D
	Строчные русские буквы	Множество, содержащее все буквы из A и B, но не содержащее букв, являющихся общими для C и D
	Десятичные цифры	Множество, содержащее цифры, имеющиеся в каж­дом из множеств A, B, C, и D
	Прописные латинские буквы	Множество, содержащее все буквы из A, не яв­ля­ю­щи­е­ся общими для B, C и D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры, имеющиеся в A, и все цифры, являющиеся общими для B, C и D
	Строчные латинские буквы	Множество, содержащее буквы, общие для множества A и любого из множеств B, C и D
	Десятичные цифры	Множество, содержащее цифры, общие для цифр из A, не встречающихся в B, с одной стороны, и любых цифр из C и D – с дру­гой
	Цвета радуги	Множество, содержащего цвета, имеющиеся в A, также од­новременно в B и C, и все цвета из D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры, имеющиеся во мно­же­ствах A или C, но отсутствующие в B или D
	Русские буквы	Множество, содержащее буквы, имеющиеся в любом из множеств A, B, C, но отсутствующие в D
	Десятичные цифры	Множество, содержащее цифры, общие для мно­жеств A и B, но не встречающиеся ни в C, ни в D
	Латинские буквы	Множество, содержащее все буквы множества A, которых нет во множествах B, C или D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры, имеющиеся в A или B, но отсутствующие и в C, и в D

Окончание таблицы

№ варианта	Универсум	Что надо вычислить
	Строчные русские буквы	Множество, содержащее буквы, общие для множеств A, B, C и не встречающиеся в D
	Десятичные цифры	Множество, содержащее цифры из A, не являющиеся об­щими для множеств B и C и не встречающиеся в D
	Прописные русские буквы	Множество, содержащее буквы, имеющиеся в A или об­щие для B и C, но не встречающиеся в D
	Шестнадца­те­ричные цифры	Множество, содержащее все цифры, общие для A и B, а также все цифры, являющиеся общими для C и D
	Латинские буквы	Множество, содержащее буквы из множества A, не содержащиеся в B, а также все общие для C и D
	Десятичные цифры	Множество, содержащее цифры, имеющиеся в A или B или являющиеся общими для C и D
	Русские буквы	Множество, содержащее буквы, общие для A и B, но не являющиеся общими для C и D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры из A, не встречающиеся в B и не являющиеся общими для C и D
	Латинские буквы	Множество, содержащее все буквы из A и все буквы из B, но не содержащее букв, являющихся общими для C и D
	Десятичные цифры	Множество, содержащее цифры, имеющиеся в каж­дом из указанных множеств
	Строчные латинские буквы	Множество, содержащее все буквы из A, не яв­ля­ю­щи­е­ся общими для B, C и D
	Шестнадца­те­ричные цифры	Множество, содержащее цифры, имеющиеся в A и все цифры, являющиеся общими для B, C и D
	Прописные латинские буквы	Множество, содержащее буквы, общие для множества A и любого из множеств B, C и D
	Десятичные цифры	Множество, содержащее цифры, общие для цифр из A, не встречающихся в B, с одной стороны, и любые цифры из C и D — с дру­гой
	Цвета радуги	Множество, содержащее цвета, имеющиеся в A, также од­новременно в B и C, и все цвета из D

Контрольные вопросы

1. Какой объём памяти нужно выделить под массив-результат?

2. Можно ли сэкономить память, если обрабатывать множества не попарно, а все четыре сразу?

3. Какова временная сложность получения результата одновременной обработкой четырёх множеств?

4. Какая временная сложность получилась у вас? Можно ли считать ваш алгоритм оптимальным?