Sistema_operatsii_774_nad_mnozhestvami

Примеры конечных множеств
N – размер универса
универс
Подмножество А
Подмножество А
Подмножество А
Подмножество В

Размер универса N = 100
Подмножество А:
1, 5, 20, 7, 11, 75, 41, 50, 80
Подмножество В:
20, 11, 45, 13, 60, 90, 7, 10

Размер универса N = 100
Подмножество А:
1, 5, 20, 7, 11, 75, 41, 50, 80
Подмножество В:
20, 11, 45, 13, 60, 90, 7, 10
Подмножество А ᴜ В:
1, 5, 7, 10, 11, 13, 20, 41, 45, 50, 60, 75, 80, 90

Размер универса N = 100
Подмножество А:
1, 5, 20, 7, 11, 75, 41, 50, 80
Подмножество В:
20, 11, 45, 13, 60, 90, 7, 10
Подмножество А ∩ В: 7, 11,20

Размер универса N = 100
Подмножество А:
1, 5, 20, 7, 11, 75, 41, 50, 80
Подмножество В:
20, 11, 45, 13, 60, 90, 7, 10
Подмножество ~А:
2, 3, 6, 8, 9, 10, 12, …,19, 21, …, 40, 42, …, 49, 51, …, 74, …,79, 81, …, 100

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

Вариант 1
Структура хранения –
массив номеров элементов, входящих в подмножество
тип массива целый
размер массива - ??? N
сложность по памяти - ??? N*4 байт
Сложность по времени - квадратичная

Вариант 1
Структура хранения – массив номеров элементов
Сложность по времени
1. Операция объединения:

Вариант 1
Структура хранения – массив номеров элементов
Сложность по времени
1. Операция пересечения:

Вариант 1
Структура хранения – массив номеров элементов
Сложность по времени
1. Операция дополнения:

Технология разработки и тестирования класса
1.Создается проект в консольном приложении
2.Добавляется заготовка класса
#include ….
…..
Int main( …)
{
}
Class Myclass
{
}

Технология разработки и тестирования класса
3.Класс подключается к главной программе
#include ….
…..
Int main( …)
{
}
Class Myclass
{
}

Технология разработки и тестирования класса
3.В классе прописываются поля (свойства класса)
4.Обязательные методы
#include ….
…..
Int main( …)
{
}
Class Myclass
{
}

Технология разработки и тестирования класса
3.В классе прописываются поля (свойства класса)
4.Обязательные методы:
-Конструктор(ы)
-Деструктор
-Конструктор копирования
-Перегрузка оператора присваивания
5.В главной программе объявляются объекты нового класса для тестирования написанных методов

Технология разработки и тестирования класса
6. Параллельно каждый добавленный в класс метод должен быть протестирован, для этого вызывается в главной программе
#include ….
…..
Int main( …)
{
}
Class Myclass
{
}

Задание 1.
Написать и протестировать класс Set, обеспечивающий работу с множествами:
Ввод множества
Объединение 2х множеств
Пересечение 2х множеств
Дополнение к первому множеству
Вывод множества
Структура хранения – массив номеров элементов

Вариант 2
Структура хранения – битовая строка, отображенная на память компа
Пример. Размер универса – 36
Подмножество А: 6, 9, 16, 19, 20, 35
Номер элемента универса
Признак принадлежности элемента к подмножеству,
1-принадлежит, 0-отсутствует

Вариант 2
Структура хранения – битовая строка, отображенная на память компа
Пример. Размер универса – 36
Подмножество В: 2, 7, 12, 13, 22, 23, 24, 35

Вариант 2
Структура хранения – битовая строка, отображенная на память компа
Пример. Размер универса – 36
mem[0]
mem[1]
mem[2]
mem[3]
mem[4]
Отображение битовой строки подмножества А на массив mem типа char
Память компа
Битовая строка

Вариант 2
Структура хранения – битовая строка, отображенная на память компа
Пример. Размер универса – 36
mem[0]
mem[1]
mem[2]
Отображение битовой строки подмножества А на массив mem типа int16

Вариант 2
Структура хранения – битовая строка, отображенная на память компа
Пример. Размер универса – 36
mem[0]
mem[1]
Отображение битовой строки подмножества А на массив mem типа int32

Вариант 2
массив mem типа int32
массив mem типа int16
массив mem типа char

Вариант 2
Расположение 35 элемента
массив mem типа int32
массив mem типа int16
массив mem типа char
mem[1]
mem[2]
mem[4]
лишние
лишние

Вариант 2
Размер выделяемой памяти
массив mem типа int32 - size=2, количество байт 8
массив mem типа int16- size=3, количество байт 6
массив mem типа char – size=5, количество байт 5

Задание 2.
Исходные данные:
Тип массива
Размер универса
Номер элемента множества
Определить:
Размер выделяемой памяти в байтах
Номер массива mem, содержащий заданный элемент множества
Номер бита, содержащий заданный элемент множества

Оценка сложности по памяти
Для произвольного N определяем по формуле
size=N/(sizeof(тип)*8)+1
Число байт = size* sizeof(тип)

Вариант 2
Структура хранения – массив, содержащий битовую строку
Сложность по времени
1. Операция объединения:

Вариант 2
Структура хранения – массив, содержащий битовую строку
Сложность по времени
1. Операция пересечения:

Вариант 2
Структура хранения – массив, содержащий битовую строку
Сложность по времени
1. Операция дополнения:

ПримерРазмер универса – 36
Подмножество А: 6, 9, 16, 19, 20, 35
Подмножество В: 2, 7, 12, 13, 22, 23, 24, 35
Подмножество АᴜВ: 2,6,7,9,12,13,16,19,20,22,23,24,35

Операция “<<“ «сдвиг влево») и “>>” («сдвиг вправо» )
Пример 1. Int16 A= 1<<2
Результатом операции А=4
Пример 2. 910=10012 после выполнения операции int B = 9 << 5

Операция “(«сдвиг влево» <<“) и “>>” ( «сдвиг вправо»)
Пример 3. Пусть есть элемент целого массива mem[i], который в двоичном представлении имеет вид
после выполнения операции int B =mem[i]<< 4 будет иметь вид
При этом единица из 29 разряда будет потеряна

Задание на лабораторную работу
1. На WindousForm разработать интерфейс
После установки размера универса открываются остальные поля

Структура проекта с использованием WindousForm
Главная программа формируется автоматически при создании проекта
Form.h формируется и дополняется автоматически
вызов
Дополнения при появлении на форме новых инструментов
TSet
TBitField
вызов
вызов
Вызов при наступлении соответствующего события

Задание на лабораторную работу
2. Реализовать структуру классов
TBitField
TSet

Задание на лабораторную работу
3. В классе TBitField должны быть поля
-массив с битовой строкой
-размер массива
Приватные методы по номеру элемента множества
-вычисление номера бита
-вычисление номера элемента массива

Задание на лабораторную работу
4. В классе TBitField кроме обязательных должны быть реализованы методы:
- добавить элемент
удалить элемент
перегружены операции «и», «или», «отрицание»
преобразование содержимого массива в строку с параметром размера универса

Задание на лабораторную работу
5. В классе TSet должны быть поля
- объект класса TBitField
-размер универса

Задание на лабораторную работу
6. В классе TSet кроме обязательных должны быть реализованы методы:
- добавить элемент с контролем
удалить элемент
перегружены операции «и», «или», «отрицание»
ввод подмножества с контролем
возврат строки с номерами элементов