на то, что дерево высоты 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. В паскалевских программах бывают также строки, зак-
люченные в кавычки. Если фигурная скобка стречается внутри стро-
ки, то она не означает начала или конца комментария. В свою оче-
редь, кавычка в комментарии не означает начала или конца строки.
Как изменить программу, чтобы это учесть?
Указание. Состояний будет три: основное, внутри коммента-
рия, внутри строки.
5.1.5. Еще одна возможность многих реализаций паскаля - это
комментарии вида
i:=i+1; (* here i is increased by 1 *)
при этом закрывающая скобка должна соответствовать открываюшей
(то есть { ... *) не разрешается). Как удалять такие коммента-
рии?
5.2. Ввод чисел
Пусть десятичная запись числа подается на вход программы
символ за символом. Мы хотим "прочесть" это число (поместить в
переменную типа real его значение). Кроме того, надо сообщить об
ошибке, если число записано неверно.
Более конкретно, представим себе такую ситуацию. Последова-
тельность символов на входе делится на прочитанную и оставшуюся
части. Мы можем пользоваться функцией Next:char, которая возвра-
щает первый символ оставшей части, а также функцией Move, кото-
рая перводит забирает первый символ из оставшейся части, перево-
дя его в категорию прочитанных.
---------------------|--------------------------
прочитанная часть | Next | ? | ? | ? |
---------------------|--------------------------
Будем называть десятичной записью такую последовательность сим-
волов:
<0 или более пробелов> <1 или более цифр>
а также такую:
<0 или более пробелов> <1 или более цифр>.<1 или более цифр>
Заметим, что согласно этому определению '1.', '.1', '1. 1',
'-1.1' не являются десятичными записями. Сформулируем теперь за-
дачу точно:
5.2.1. Прочесть из входной строки максимальную часть, кото-
рая может быть началом десятичной записи. Определить, является
ли эта часть десятичной записью или нет.
Решение. Запишем программу на паскале (используя "перечис-
лимый тип" для наглядности записи: переменная state может прини-
мать одно из значений, указанных в скобках).
var state:
(Accept, Error, Initial, IntPart, DecPoint, FracPart);
state := Initial;
while (state <> Accept) or (state <> Error) do begin
| if state = Initial then begin
| | if Next = ' ' then begin
| | | state := Initial; Move;
| | end else if Digit(Next) then begin
| | | state := IntPart; {после начала целой части}
| | | Move;
| | end else begin
| | | state := Error;
