| Дано множество из n камней одинакового внешнего вида. Можно сравнивать их по весу с помощью чашечных весов без гирь (на каждую чашку помещается ровно один камень). Камни в произвольном порядке подаются через входное окошко в комнату, в которой находится Сортировщик. От него требуется выдать через выходное окошко все поданные ему на входное окошко камни, о в порядке неубывания веса. У сортировщика имеются весы и стол, на котором он может выкладывать камни, делать на них и на столе пометки мелом и т.п. Кроме входного и выходного окон других отверстий в комнате нет. |
1.
Сколько взвешиваний понадобится сортировщику, чтобы найти
2.
Сортировщик. утверждает, что один из камней – самый тяжелый. Он хочет убедить в этом скептиков при помощи нескольких взвешиваний.
3.
Отсортируйте пять (заведомо попарно разных) камней за семь взвешиваний.
4.
Докажите, что при некоторых порядках входа камней Сортировщику понадобится не менее log n! взвешиваний.
Указание. Пусть все камни разные – сколько разных перестановок?
Вопрос: Как вы думаете, в каких случаях выгоднее использовать каждый из этих алгоритмов?
5.
Напишите сортировку исключениями, используя массив размера n для хранения камней. Количество операций взвешивания не должно превышать n (n – 1) / 2.
6.
7.
Напишите сортировку включениями, используя массив для хранения постепенно растущего упорядоченного множества. Количество операций взвешивания меньше n log n.
В задаче 6 количество операций взвешивания имеет порядок теоретического минимума из задачи 4 (докажите!), но количество операций перемещения камней имеет порядок n2. Однако, «цена» этих операций ниже (см. 7).
8.
9.
Пусть во всех камнях есть дырки, и первоначально их разделили поровну и надели как бусы на две веревки. Крайний камень можно снимать с левого конца веревки и надевать на правый. Есть еще две запасных веревки.
10.
Пусть дан массив длины n. Предположим, что элемент 1 является вершиной некоего дерева, ее потомки 2 и 3, в общем случае для элемента i потомки 2i и 2i+1 (если они существуют). Дерево называется регулярным, если любая вершина больше всех потомков, и почти регулярным, если это правило нарушается только в корне. Высота такого дерева приблизительно равна log n (докажите!) Важная лемма. Почти регулярное дерево можно превратить в регулярное, совершив количество перестановок в массиве, пропорциональное высоте дерева.
Реализовать сортировку, используя тот факт, что нижние два слоя дерева представляют собой «лес» почти регулярных деревьев (постепенно повышая высоту). После получения регулярного дерева удаляем вершину, на ее место ставим последний элемент массива, массив укорачиваем, далее в цикле. Алгоритм имеет время работы
порядка n log n и память n.
11.
Цифровая сортировка Имеется массив целых чисел размера N, сами числа от 1 до M. Отсортировать их за время N + M, с таким же расходом памяти. Как вы думаете, почему «нарушается» результат задачи 4?
12.
На почте имеется алгоритм для сортировки писем по шестизначному индексу. Используется 10 коробок размером n, время работы
примерно 6 n. Воспроизведите алгоритм, напишите программу.