Решение. Возьмем самую левую точку (т.е. точку с наименьшей
x-координатой) и проведем из нее лучи во все остальные точки.
Теперь упорядочим эти лучи, а точки на одном луче поместим в по-
рядке увеличения расстояния от начала луча.
4.3.5. Дано n точек на плоскости. Построить их выпуклую
оболочку - минимальную выпуклую фигуру, их содержащую. (Форму
выпуклой оболочки примет резиновое колечко, если его натянуть на
гвозди, вбитые в точках.) Число операций не более n*log n.
Указание. Упорядочим точки - годится любой из порядков, ис-
пользованных в двух предыдущих задачах. Затем, рассматривая точ-
ки по очереди, будем строить выпуклую оболочку уже рассмотренных
точек. (Для хранения выпуклой оболочки полезно использовать дек,
см. главу 6 о типах данных.)
4.4. Нижние оценки для числа сравнений при сортировке.
Пусть имеется n различных по весу камней и весы, которые
позволяют за одно взвешивание определить, какой из двух выбран-
ных нами камней тяжелее. (В программистских терминах: мы имеем
доступ к функции тяжелее(i,j:1..n):boolean.) Надо упорядочить
камни по весу, сделав как можно меньше взвешиваний (вызовов
функции "тяжелее").
Разумеется, число взвешиваний зависит не только от выбранно-
го нами алгоритма, но и от того, как оказались расположены кам-
ни. Сложностью алгоритма назовем число взвешиваний при наихудшем
расположении камней.
4.4.1. Доказать, что сложность любого алгоритма сортировки n
камней не меньше log (n!). (Логарифм берется по основанию 2, n!
- произведение чисел 1..n.)
Решение. Пусть имеется алгоритм сложности не более d. Для
каждого из n! возможных расположений камней запротоколируем ре-
зультаты взвешиваний (обращений к функции "тяжелее"); их можно
записать в виде последовательности из не более чем d нулей и
единиц. Для единообразия дополним последовательность нулями,
чтобы ее длина стала равной d. Тем самым у нас имеется n! после-
довательностей из d нулей и единиц. Все эти последовательности
разные - иначе наш алгоритм дал бы одинаковые ответы для разных
порядков (и один из ответов был бы неправильным). Получаем, что
2 в степени d не меньше n! - что и требовалось доказать.
Другой способ объяснить то же самое - рассмотреть дерево
вариантов, возникающее в ходе выполнения алгоритма, и сослаться
на то, что дерево высоты d не может иметь более (2 в степени d)
листьев.
Это рассуждение показывает, что любой алгоритм сортировки,
использующий только сравнения элементов массива и их перестанов-
ки, требует не менее C*n*log n действий, так что наши алгоритмы
близки к оптимальным. Однако алгоритм сортировки, использующий
другие операции, может действовать быстрее. Вот один из приме-
ров.
4.4.2. Имеется массив целых чисел a[1]..a[n], причем все
числа неотрицательны и не превосходят m. Отсортировать этот мас-
сив; число действий порядка m+n.
Решение. Для каждого числа от 0 до m подсчитываем, сколько
раз оно встречается в массиве. После этого исходный массив можно
стереть и заполнить заново в порядке возрастания, используя све-
дения о кратности каждого числа.
Отметим также, что этот алгоритм не переставляет числа в масси-
ве, как большинство других, а "записывает их туда заново".
Есть также метод сортировки, в котором последовательно проводится
ряд "частичных сортировок" по отдельным битам. Начнём с такой
задачи:
4.4.3. В массиве a[1]..a[n] целых чисел переставить элемен-
ты так, чтобы чётные шли перед нечётными (не меняя взаимный по-
рядок в каждой из групп).
Решение. Сначала спишем (во вспомогательный массив) все
чётные, а потом - все нечётные.
4.4.4. Имеется массив из n чисел от 0 до (2 в степени k) -
1, каждое из которых мы будем рассматривать как k-битовое слово.
Используя проверки "i-ый бит равен 0" и "i-ый бит равен 1" вмес-
то сравнений, отсортировать все числа за время порядка n*k.
Решение. Отсортируем числа по последнему биту (см. предыду-
щую задачу), затем по предпоследнему и так далее. В результате
они будут отсортированы. В самом деле, индукцией по i легко до-
казать, что после i шагов любые два числа, отличающиеся только в
i последних битах, идут в правильном порядке. (Вариант: после i
шагов i-битовые концы чисел идут в правильном порядке.)
Аналогичный алгоритм может быть применен для m-ичной систе-
мы счисления вместо двоичной. При этом полезна такая вспомога-
тельная задача:
4.4.5. Даны n чисел и функция f, принимающая (на них) зна-
чения 1..m. Требуется переставить числа в таком порядке, чтобы
значения функции f не убывали (сохраняя притом порядок внутри
каждой из групп). Число действий порядка m+n.
Указание. Завести m списков суммарной длины n (как это сде-
лать, смотри в главе 6 о типах данных) и помещать в i-ый список
числа, для которых значение функции f равно i. Вариант: посчи-
тать для всех i, сколько имеется чисел x c f(x)=i, после чего
легко определить, с какого места нужно начинать размещать числа
с f(x)=i.
4.5. Родственные сортировке задачи.
4.5.1. Какова минимально возможная сложность (число сравне-
ний в наихудшем случае) алгоритма отыскания самого легкого из n
камней?
Решение. Очевидный алгоритм с инвариантом "найден самый
легкий камень среди первых i" требует n-1 сравнений. Алгоритма
меньшей сложности нет. Это вытекает из следующего более сильного
утверждения.
4.5.2. Эксперт хочет докать суду, что данный камень - самый
легкий среди n камней, сделав менее n-1 взвешиваний. Доказать,
что это невозможно. (Веса камней неизвестны суду, но известны
эксперту.)
Решение. Изобразим камни точками, а взвешивания - линиями
между ними. Получим граф с n вершинами и менее чем n-1 ребрами.
Такой граф несвязен (добавление каждого следующего ребра
уменьшает число компонент не более чем на 1). Поэтому суд ничего
не знает относительно соотношения весов камней в двух связных
компонентах и может допустить, что самый легкий камень - в любой
из них.
Разница между этой задачей и предыдущей в том, что n-1
взвешиваний не достаточно не только для нахождения самого легко-
го, но даже для того, чтобы убедиться, что данный камень являет-
ся самым легким - если предположительный ответ известен. (В слу-
чае сортировки, зная предположительный ответ, мы можем убедиться
в его правильности, сделав всего n-1 сравнений: каждый сравнива-
ем со слеследующим по весу.)
4.5.3. Дано n различных по весу камней и число k (от 1 до
n). Требуется найти k-ый по весу камень, сделав не более C*n
взвешиваний, где C - некоторая константа, не зависящая от k.
Замечание. Сортировка позволяет сделать это за C*n*log n
взвешиваний. Указание к этой (трудной) задаче приведено в главе
про рекурсию.
Следующая задача имеет неожиданно простое решение.
4.5.4. Имеется n одинаковых на вид камней, некоторые из ко-
торых на самом деле различны по весу. Имеется прибор, позволя-
ющий по двум камням определить, одинаковы они или различны (но
не говорящий, какой тяжелее). Известно, что среди этих камней
большинство (более n/2) одинаковых. Сделав не более n взвешива-
ний, найти хотя бы один камень из этого большинства.
Предостережение. Если два камня одинаковые, это не гаранти-
рует их принадлежности к большинству.
Указание. Если найдены два различных камня, то их оба можно
выбросить - хотя бы один из них плохой и большинство останется
большинством.
Решение. Программа просматривает камни по очереди, храня в
переменной i число просмотренных камней. (Считаем камни пронуме-
рованными от 1 до n.) Помимо этого программа хранит номер "теку-
щего кандидата" c и его "кратность" k. Смысл этих названий
объясняется инвариантом:
если к непросмотренным камням (с номерами i+1..n) до-
бавили бы k копий c-го камня, то наиболее частым среди (И)
них был бы такой же камень, что и для исходного массива
Получаем такую программу:
k:=0; i:=0
{(И)}
while i<>n do begin
| if k=0 then begin
| | k:=1; c:=i+1; i:=i+1;
| end else if i+1-ый камень одинаков с c-ым then begin
| | i:=i+1; k:=k+1;
| | {заменяем материальный камень идеальным}
| end else begin
| | i:=i+1; k:=k-1;
| | {выкидываем один материальный и один идеальный камень}
| end;
end;
искомым является c-ый камень
Замечание. Поскольку во всех трех вариантах выбора стоит
команда i:=i+1, ее можно вынести наружу.
Следующая задача не имеет на первый взгляд никакого отноше-
ния к сортировке.
4.5.5. Имеется квадратная таблица a[1..n, 1..n]. Известно,
что для некоторого i строка с номером i заполнена одними нулями,
а столбец с номером i - одними единицами (за исключением их пе-
ресечения на диагонали, где стоит неизвестно что). Найти такое i
(оно, очевидно, единственно). Число действий не превосходит C*n.
(Заметим, что это существенно меньше числа элементов в таблице).
Указание. Рассмотрите a[i][j] как результат "сравнения" i с
j и вспомните, что самый тяжелый из n камней может быть найден
за n сравнений. (Не забудьте, впрочем, что таблица может не быть
"транзитивной".)
Глава 5. Конечные автоматы в задачах обработки текстов
5.1. Составные символы, комментарии и т.п.
5.1.1. В тексте возведение в степень обозначалось двумя
идущими подряд звездочками. Решено заменить это обозначение на
'^' (так что, к примеру, 'x**y' заменится на 'x^y'). Как это
проще всего сделать? Исходный текст разрешается читать символ за
символом, получающийся текст требуется печатать символ за симво-
лом.
Решение. В каждый момент программа находится в одном из
двух состояний: "основное" и "после звездочки"
Состояние Очередной Новое Действие
входной символ состояние
основное * после нет
основное x <> '*' основное печатать x
после * основное печатать '^'
после x <> '*' основное печатать *, x
Замечание. При этом '***' заменится на '^*' (но не на '*^'). В
условии задачи мы не оговаривали деталей, как это часто делается
- предполагается, что программа "должна действовать разумно". В
данном случае, пожалуй, самый простой способ объяснить, как
программа действует - это описать ее состояния и действия в них.
5.1.2. Написать программу, удалающую из текста подслова ви-
да 'abc'.
5.1.3. В паскале комментарии заключаются в фигурные скобки:
begin {начало цикла}
i:=i+1; {увеличиваем i на 1}
Написать программу, которая удаляла бы комментарии и вставляла
бы вместо исключенного комментария пробел (чтобы '1{один}2'
превратилось бы не в '12', а в '1 2').
Решение. Программа имеет два состояния: "основное" и "внут-
ри комментария".
Состояние Очередной Новое Действие
входной символ состояние
основное { внутри нет
основное x <> '{' основное печатать x
внутри } основное печатать пробел
внутри x <> '}' внутри нет
Замечание. Эта программа не воспринимает вложенные коммен-
тарии: строка вроде
'{{комментарий внутри} комментария}'
превратится в
' комментария}'
(в начале стоят два пробела). Обработка вложенных комментариев
конечным автоматом невозможна (нужно "помнить число скобок" - а
произвольное натуральное число не помещается в конечную память).
5.1.4. В паскалевских программах бывают также строки, зак-
люченные в кавычки. Если фигурная скобка стречается внутри стро-
ки, то она не означает начала или конца комментария. В свою оче-
редь, кавычка в комментарии не означает начала или конца строки.
