3 темы: Множества, Деревья, Графы

Задания:

На множества

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

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

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. Дополнить программу так, чтобы исходные множества из массивов преобразовывались в линейные списки, и получение результата достигалась обработкой этих списков.

На Деревья

№ вари- анта	Вид дерева	Разметка	Способ обхода	Что надо вычислить
15	Троичное	Прямая	Внутрен­ний	Количество вершин, имеющих не более двух потомков

1. Написать и отладить программу для работы с деревьями по предложенному преподавателем варианту индивидуального задания. Программа должна выводить на экран изображение дерева с разметкой его вершин, сделанной заданным способом, а под ним — последовательность меток вершин при обходе дерева и результат вычисления заданного параметра. Можно взять за основу учебный пример.

2. Сделать узел дерева и дерево в целомобъектамисоответствующих классов, а обходы дерева — методами для этого класса.

3. Объявить в классе «дерево» деструктор и все конструкторы, поддерживаемые по умолчанию. Сделать невозможным использование тех конструкторов, которые на самом деле не нужны. Сделать в тексте программы временные дополнения и убедиться, что это действительно так.

На графы

№ вари- анта	Алгоритм для исследования
15	Построение эйлерова пути в неориентированном графе

Выбрать оптимальную структуру данных для представления графа в памяти ЭВМ. Реализовать граф как объект, а обработку — как метод для него. Результат обработки может быть или не быть частью объекта, способ его представления выбирается особо.

Для объекта должны быть объявлены все вспомогательные методы (методы по умолчанию) — конструкторы, деструктор и т. п. Использование ненужных методов блокируется на уровне компиляции или выполнения.

---

Стек и очередь (если нужны) реализуются как вспомогательные объекты. Рекомендуется использовать шаблоны классов.

Интерфейс программы должен быть удобен для испытаний алгоритма. Следует предусмотреть ввод заранее заготовленных и генерацию произвольных тестовых данных.

Дополнительное требование: оценить возможный объём исходных данных для решения поставленной задачи для следующих ограничений:

— возможность вывода данных на экран;

— доступный объём памяти;

— получение решения за разумное время.

---

Смотрите также файлы

• Задание 1 цифровые бизнес-модели.docx

• Задание графические системы (заочное).docx

• Транспортные задачи для самостоятельного решения.docx

• Лабораторная работа на тему Выявление тренда во временном ряду.docx

• Лабораторная работа на тему Выявление и подбор тренда для временного ряда.docx