Методические указания

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

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

При выполнении индивидуального задания придерживаться следующей последовательности действий:

• изучить словесную постановку задачи;

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

• доказать, что для всех операций гарантируется требуемая в постановке задачи сложность.

• разработать программу, решающую поставленную задачу;

• протестировать и отладить программу;

• написать и представить к защите отчет по работе.

Содержание отчета

1. Словесная постановка задачи.

2. Алгоритм решения задачи в виде блок-схемы.

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

4. Листинг программы.

5. Протокол выполнения программы.

6. Ответы на контрольные вопросы.

Варианты индивидуальных заданий

Задача 1. Используя память, пропорциональную n, хранить подмножества множества {1..n}.

Операции	Число действий
Сделать пустым	T(n)
Проверить принадлежность	T(1)
Добавить	T(1)
Удалить	T(1)
Минимальный элемент	T(n)
Проверка пустоты	T(n)

Указание. Хранить множество как A: array [1..n] of boolean, где A[i]=true, если i принадлежит множеству.

Задача 2. Условия те же, что в задаче 1, но проверка пустоты должна требовать T(1) действий.

Указание. Действуем как в задаче 1. Дополнительно храним число элементов множества.

Задача 3. Используя память, пропорциональную n, хранить подмножества множества {1..n}.

Операции	Число действий
Сделать пустым	T(n)
Проверить принадлежность	T(1)
Добавить	T(1)
Удалить	T(n)
Минимальный элемент	T(1)
Проверка пустоты	T(1)

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

Задача 4. Используя память, пропорциональную n, хранить подмножества множества {1..n}.

Операции	Число действий
Сделать пустым	T(n)
Проверить принадлежность	T(1)
Добавить	T(n)
Удалить	T(1)
Минимальный элемент	T(1)
Проверка пустоты	T(1)

Указание. Хранить множество как A: array [1..n] of boolean, где A[i]=true, если i принадлежит множеству. Дополнительно храним минимальный элемент, а для каждого – следующий и предыдущий по величине.

Задача 5. Число элементов множества не превосходит n. Элементами множества являются произвольные целые числа. Используя память, пропорциональную n, организовать такое хранение множества, что

Операции	Число действий
Сделать пустым	T(1)
Число элементов	T(1)
Проверить принадлежность	T(n)
Добавить новый (заведомо отсутствующий)	T(1)
Удалить	T(n)
Минимальный элемент	T(n)
Взять произвольный элемент	T(1)

Указание. Представим множество в виде двух переменных: A: array [1..n] of integer; Count: 0..n. Множество содержит Count элементов A[1], A[2], … , A[Count] и все они различны. По существу, множество будет храниться в стеке с произвольным доступом (чтение возможно не только из вершины стека).

Задача 6. Число элементов множества не превосходит n. Элементами множества являются произвольные целые числа. Используя память, пропорциональную n, организовать такое хранение множества, что

Операции	Число действий
Сделать пустым	T(1)
Проверить пустоту	T(1)
Проверить принадлежность	T(Log (n))
Добавить	T(n)
Удалить	T(n)
Минимальный элемент	T(1)
Взять произвольный элемент	T(1)

Указание. Действуем как в предыдущей задаче, но каждая операция должна сохранять упорядоченность массива, а при проверке принадлежности следует использовать дихотомический поиск.

8