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

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

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

1. изучить словесную постановку задачи;
2. выбрать метод сортировки, который лучше всего подходит для решения поставленной задачи;
3. разработать программу, решающую поставленную задачу;
4. оттестировать и отладить программу;
5. написать и представить к защите отчет по работе.

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

1. Титульный лист.
2. Словесная постановка задачи.
3. Алгоритм решения задачи в текстуальном виде.
4. Обоснование правильности работы алгоритма и правильности выбора метода сортировки исходя из постановки задачи.
5. Листинг программы.
6. Ответы на контрольные вопросы по согласованию с преподавателем.

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

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

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

Задача 1. Найти количество различных чисел среди элементов данного массива. Обеспечить число действий порядка n*log n.

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

Задача 2. Найти k-ое по порядку число среди элементов данного массива. Обеспечить число действий порядка n*log n.

Указание. Отсортировать массив, а затем взять число, хранящееся в элементе массива с индексом k.

Задача 3. Дано n отрезков [A[i], B[i]] на прямой (i=1..n), где A[i] – одномерная координата начала отрезка, а B[i] – конца отрезка.

Найти максимальное k, для которого существует точка прямой, покрытая k отрезками (" максимальное число слоев"). Обеспечить число действий - порядка n*log n.

Указание. Упорядочим все левые и правые концы отрезков вместе (при этом левый конец считается меньше правого конца, расположенного в той же точке прямой). Далее двигаемся слева направо, считая число слоев. Встреченный левый конец увеличивает число слоев на 1, правый - уменьшает. Отметим, что примыкающие друг к другу отрезки обрабатываются правильно: сначала идет левый конец (правого отрезка), а затем - правый (левого отрезка).

Задача 4. Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Обеспечить число действий порядка n*log n.

Указание. Упорядочим точки по x-координате, а при равных x-координатах - по y-координате. В таком порядке и можно проводить ломаную.

Задача 5. Та же задача, если ломаная должна быть замкнутой.

Указание. Возьмем самую левую точку (т.е. точку с наименьшей x-координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи, а точки на одном луче поместим в порядке увеличения расстояния от начала луча.

Задача 6. Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Форму выпуклой оболочки примет резиновое колечко, если его натянуть на гвозди, вбитые в точках.) Обеспечить число операций порядка n*log n.

Указание. Упорядочим точки - годится любой из порядков, использованных в двух предыдущих задачах. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек. (Для хранения выпуклой оболочки полезно использовать дек – смотрите главу «Стеки, очереди, деки»)

Задача 7. Дан массив, состоящий из чисел 0, 1 и 2. Переместить все 0 в начало массива, а 2 – в конец. Обеспечить число действий порядка n.

Указание. Воспользоваться вырожденной сортировкой распределением.

Задача 8. В неупорядоченном массиве А могут быть совпадающие элементы. Из каждой группы одинаковых элементов оставить только один, удалив остальные и «поджав» массив к его началу. Обеспечить число операций порядка n*log n.

Указание. Можно сначала отсортировать массив, а затем произвести его «поджатие» с удалением повторяющихся. При удалении очередного повтора не надо сразу сдвигать весь массив (это может привести к сложности T(n²)) – достаточно, рассматривая массив поэлементно и помня последний рассмотренный элемент, либо пропускать очередной, либо приписывать его к уже просмотренной части.

Задача 9. Турнирная таблица соревнований представлена квадратной матрицей A, каждый элемент которой a_ij есть число голов, забитых i-ой командой в ворота j-ой команды. По диагонали расположить место каждой команды (по числу побед за вычетом числа поражений; в случае равенства – по разности забитых и пропущенных голов).

Задача 10. В целочисленном массиве найти наибольшее число одинаковых элементов.

Указание. Удобно предварительно отсортировать массив.

Задача 11. Отсортировать список по неубыванию. Гарантировать число действий порядка n. Элементы списка могут содержать числа от 1 до 1000000000.

Указание. Воспользоваться сортировкой распределением.