каждой из групп). Число действий порядка 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;
| | end;
| end else if state = IntPart then begin
| | if Digit (Next) then begin
| | | state := IntPart; Move;
| | end else if Next = '.' then begin
| | | state := DecPoint; {после десятичной точки}
| | | Move;
| | end else begin
| | | state := Accept;
| | end;
| end else if state = DecPoint then begin
| | if Digit (Next) then begin
| | | state := FracPart; Move;
| | end else begin
| | | state := Error; {должна быть хоть одна цифра}
| | end;
| end else if state = FracPart then begin
| | if Digit (Next) then begin
| | | state := FracPart; Move;
| | end else begin
| | | state := Accept;
| | end;
| end else if
| | {такого быть не может}
| end;
end;
Заметьте, что присваивания state:=Accept и state:=Error не соп-
ровождаются сдвигом (символ, который не может быть частью числа,
не забирается).
Приведенная программа не запоминает значение прочитанного
числа.
5.2.2. Решить предыдущую задачу с дополнительным требовани-
ем: если прочитанный кусок является десятичной записью, то в пе-
ременную val:real следует поместить ее значение.
Решение. При чтении дробной части используется переменная
step - множитель при следующей десятичной цифре.
state := Initial; val:= 0;
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; {после начала целой части}
| | | val := DigitValue (Next);
| | | Move;
| | end else begin
| | | state := Error;
| | end;
| end else if state = IntPart then begin
| | if Digit (Next) then begin
| | | state := IntPart; val := 10*val + DigitVal(Next);
| | | Move;
| | end else if Next = '.' then begin
| | | state := DecPoint; {после десятичной точки}
| | | step := 0.1;
| | | Move;
| | end else begin
| | | state := Accept;
| | end;
| end else if state = DecPoint then begin
| | if Digit (Next) then begin
| | | state := FracPart;
| | | val := val + DigitVal(Next)*step; step := step/10;
| | | Move;
| | end else begin
| | | state := Error; {должна быть хоть одна цифра}
