state := WL;
while есть_снизу or (state <> WLU) do begin
| if (state = WL) and есть_сверху then begin
| | вверх;
| end else if (state = WL) and not есть_сверху then begin
| | обработать; state := WLU;
| end else if (state = WLU) and есть_справа then begin
| | вправо; state := WL;
| end else begin {state = WLU, not есть_справа, есть_снизу}
| | вниз;
| end;
end;
Решение. Инвариант цикла:
state = WL => ОЛ
state = WLU => ОЛН
Доказательство завершения работы: переход из состояния ОЛ в ОЛН
возможен только при обработке вершины, поэтому если программа
работает бесконечно, то с некоторого момента значение state не
меняется, что невозможно.
3.1.4. Решить задачу об обходе дерева, если мы хотим, чтобы
обрабатывались все вершины (не только листья).
Решение. Пусть x - некоторая вершина. Тогда любая вершина y
относится к одной из четырех категорий. Рассмотрим путь из корня
в y. Он может:
(а) быть частью пути из корня в x (y ниже x);
(б) свернуть налево с пути в x (y левее x);
(в) пройти через x (y над x);
(г) свернуть направо с пути в x (y правее x);
В частности, сама вершина x относится к категории (в). Условия
теперь будут такими:
(ОНЛ) обработаны все вершины ниже и левее;
(ОНЛН) обработаны все вершины ниже, левее и над.
Вот как будет выглядеть программа:
procedure вверх_до_упора_и_обработать
| {дано: (ОНЛ), надо: (ОНЛН)}
begin
| {инвариант: ОНЛ}
| while есть_сверху do begin
| | обработать
| | вверх_налево
| end
| {ОНЛ, Робот в листе}
| обработать;
| {ОНЛН}
end;
Основной алгоритм:
дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать
{инвариант: ОНЛН}
while есть_снизу do begin
| if есть_справа then begin {ОНЛН, есть справа}
| | вправо;
| | {ОНЛ}
| | вверх_до_упора_и_обработать;
| end else begin
| | {ОЛН, не есть_справа, есть_снизу}
| | вниз;
| end;
end;
{ОНЛН, Робот в корне => все вершины обработаны}
3.1.5. Приведенная только что программа обрабатывает верши-
ну до того, как обработан любой из ее потомков. Как изменить ее,
чтобы каждая вершина, не являющаяся листом, обрабатывалась дваж-
ды: один раз до, а другой раз после всех своих потомков? (Листья
по-прежнему обрабатываются по разу.)
Решение. Под "обработано ниже и левее" будем понимать "ниже
обработано по разу, слева обработано полностью (листья по разу,
останые по два)". Под "обработано ниже, левее и над" будем пони-
мать "ниже обработано по разу, левее и над - полностью".
Программа будет такой:
procedure вверх_до_упора_и_обработать
| {дано: (ОНЛ), надо: (ОНЛН)}
begin
| {инвариант: ОНЛ}
| while есть_сверху do begin
| | обработать
| | вверх_налево
| end
| {ОНЛ, Робот в листе}
| обработать;
| {ОНЛН}
end;
Основной алгоритм:
дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать
{инвариант: ОНЛН}
while есть_снизу do begin
| if есть_справа then begin {ОНЛН, есть справа}
| | вправо;
| | {ОНЛ}
| | вверх_до_упора_и_обработать;
| end else begin
| | {ОЛН, не есть_справа, есть_снизу}
| | вниз;
| | обработать;
| end;
end;
{ОНЛН, Робот в корне => все вершины обработаны полностью}
3.1.6. Доказать, что число операций в этой программе по по-
рядку равно числу вершин дерева. (Как и в других программах, ко-
торые отличаются от этой лишь пропуском некоторых команд "обра-
ботать".)
Указание. Примерно каждое второе действие при исполнении
этой программы - обработка вершины, а каждая вершина обрабатыва-
ется максимум дважды.
Теперь реализуем операции с деревом позиций. Позицию будем
представлять с помощью переменной k: 0..n (число ферзей) и мас-
сива c: array [1..n] of 1..n (c [i] - координаты ферзя на i-ой
горизонтали; при i > k значение c [i] роли не играет). Предпола-
гается, что все позиции допустимы (если убрать верхнего ферзя,
остальные не бьют друг друга).
program queens;
| const n = ...;
| var
| k: 0..n;
| c: array [1..n] of 1..n;
|
| procedure begin_work; {начать работу}
| begin
| | k := 0;
| end;
|
| function danger: boolean; {верхний ферзь под боем}
| | var b: boolean; i: integer;
| begin
| | if k <= 1 then begin
| | | danger := false;
| | end else begin
| | | b := false; i := 1;
| | | {b <=> верхний ферзь под боем ферзей с номерами < i}
| | | while i <> k do begin
| | | | b := b or (c[i]=c[k]) {вертикаль}
| | | | or (abs(c[[i]-c[k]))=abs(i-k)); {диагональ}
| | | | i := i+ 1;
| | | end;
| | | danger := b;
| | end;
| end;
|
| function is_up: boolean {есть_сверху}
| begin
| | is_up := (k < n) and not danger;
| end;
|
| function is_right: boolean {есть_справа}
| begin
| | is_right := (k > 0) and (c[k] < n);
| end;
| {возможна ошибка: при k=0 не определено c[k]}
|
| function is_down: boolean {есть_снизу}
| begin
| | is_up := (k > 0);
| end;
|
| procedure up; {вверх_налево}
| begin {k < n}
| | k := k + 1;
| | c [k] := 1;
| end;
|
| procedure right; {вправо}
| begin {k > 0, c[k] < n}
| | c [k] := c [k] + 1;
| end;
|
| procedure down; {вниз}
| begin {k > 0}
| | k := k - 1;
| end;
|
| procedure work; {обработать}
| | var i: integer;
| begin
| | if (k = n) and not danger then begin
| | | for i := 1 to n do begin
| | | | write ('<', i, ',' , c[i], '> ');
| | | end;
| | | writeln;
| | end;
| end;
|
| procedure UW; {вверх_до_упора_и_обработать}
| begin
| | while is_up do begin
| | | up;
| | end
| | work;
| end;
|
begin
| begin_work;
| UW;
| while is_down do begin
| | if is_right then begin
| | | right;
| | | UW;
| | end else begin
| | | down;
| | end;
| end;
end.
3.1.7. Приведенная программа тратит довольно много времени
на выполнение проверки есть_сверху (проверка, находится ли
верхний ферзь под боем, требует числа действий порядка n). Изме-
нить реализацию операций с деревом позиций так, чтобы все три
проверки есть_сверху/справа/снизу и соответствующие команды тре-
бовали бы количества действий, ограниченного не зависящей от n
константой.
Решение. Для каждой вертикали, каждой восходящей и каждой
нисходящей диагонали будем хранить булевское значение - сведения
о том, находится ли на этой линии ферзь (верхний ферзь не учиты-
вается). (Заметим, что в силу допустимости позиции на каждой из
линий может быть не более одного ферзя.).
3.2. Обход дерева в других задачах.
3.2.1. Использовать метод обхода дерева для решения следу-
ющей задачи: дан массив из n целых положительных чисел
a[1]..a[n] и число s; требуется узнать, может ли число s быть
представлено как сумма некоторых из чисел массива a. (Каждое
число можно использовать не более чем по одному разу.)
Решение. Будем задавать k-позицию последовательностью из k
булевских значений, определяющих, входят ли в сумму числа
a[1]..a[k] или не входят. Позиция допустима, если ее сумма не
превосходит s.
Замечание. По сравнению с полным перебором всех (2 в степе-
ни n) подмножеств тут есть некоторый выигрыш. Можно также пред-
варительно отсортировать массив a в убывающем порядке, а также
считать недопустимыми те позиции, в которых сумма отброшенных
членов больше, чем разность суммы всех членов и s. Последний
приём называют "методом ветвей и границ". Но принципиального
улучшения по сравнению с полным перебором тут не получается (эта
задача, как говорят, NP-полна, см. подробности в книге Ахо,
Хопкрофта и Ульмана "Построение и анализ вычислительных алгорит-
мов"). Традиционное название этой задачи - "задача о рюкзаке"
(рюкзак общей грузоподъемностью s нужно упаковать под завязку,
располагая предметами веса a[1]..a[n]). См. также в главе 7
(раздел о динамическом программировании) алгоритм её решения,
полиномиальный по n+s.
3.2.2. Перечислить все последовательности из n нулей, еди-
ниц и двоек, в которых никакая группа цифр не повторяется два
раза подряд (нет куска вида XX).
3.2.3. Аналогичная задача для последовательностей нулей и
единиц, в которых никакая группа цифр не повторяется три раза
подряд (нет куска вида XXX).
К этой же категории относятся задачи типа "можно ли сложить
данную фигуру из пентамино" и им подобные. В них важно умелое
сокращение перебора (вовремя распознать, что имеющееся располо-
жение фигурок уже противоречит требованиям, и по этой ветви по-
иск не продолжать).
Глава 4. Сортировка.
4.1. Квадратичные алгоритмы.
4.1.1. Пусть a[1], ..., a[n] - целые числа. Требуется
построить массив b[1], ..., b[n], содержащий те же числа, для
которых b[1] <= ... <= b[n].
Замечание. Среди чисел a[1]...a[n] могут быть равные. Тре-
буется, чтобы каждое целое число входило в b[1]...b[n] столько
же раз, сколько и в a[1]...a[n].
Решение. Удобно считать, что числа a[1]..a[n] и b[1]..b[n]
представляют собой начальное и конечное значения массива x. Тре-
бование "a и b содержат одни и те же числа" будет заведомо вы-
полнено, если в процессе работы мы ограничимся перестановками
элементов x.
...
k := 0;
{k наименьших элементов массива x установлены на свои места}
while k <> n do begin
| s := k + 1; t := k + 1;
| {x[s] - наименьший среди x[k+1]...x[t] }
| while t<>n do begin
| | t := t + 1;
| | if x[t] < x[s] then begin
| | | s := t;
| | end;
| end;
| {x[s] - наименьший среди x[k+1]..x[n] }
| ... переставить x[s] и x[k+1];
| k := k + 1;
end;
4.1.2. Дать другое решение задачи сортировки, использующее
инвариант {первые k элементов упорядочены: x[1] <= ... <= x[k]}
Решение.
k:=1
{первые k элементов упорядочены}
while k <> n do begin
| {k+1-ый элемент продвигается к началу, пока не займет
| надлежащего места }
| t := k+1;
| {x[1] <= ... <= x[t-1] и x[t-1], x[t] <= ... <= x[k+1] }
| while (t > 1) and (x[t] < x[t-1]) do begin
| | ... поменять x[t-1] и x[t];
| | t := t - 1;
| end;
end;
Замечание. Дефект программы: при ложном выражении (t > 1)
проверка x[t] < x[t-1] требует несуществующего значения x[0].
Оба предложенных решения требуют числа действий, пропорци-
онального n*n. Существуют более эффективные алгоритмы.
4.2. Алгоритмы порядка n log n.
4.2.1. Предложить алгоритм сортировки, число действий кото-
рого было бы порядка n log n, то есть не превосходило бы
C*n*log(n) для некоторого C и для всех n.
Мы предложим два решения.
Решение 1. (сортировка слиянием).
Пусть k - положительное целое число. Разобьем массив
x[1]..x[n] на отрезки длины k. (Первый - x[1]..x[k], затем
x[k+1]..x[2k] и т.д.) Последний отрезок будет неполным, если n
не делится на k. Назовем массив k-упорядоченным, если каждый из
этих отрезков упорядочен. Любой массив 1-упорядочен. Если массив
k-упорядочен и n<=k, то он упорядочен.
Мы опишем, как преобразовать k-упорядоченный массив в
2k-упорядоченный (из тех же элементов). С помощью этого преобра-
зования алгоритм записывается так:
k:=1;
{массив x является k-упорядоченным}
while k < n do begin
| .. преобразовать k-упорядоченный массив в 2k-упорядоченный;
| k := 2 * k;
end;
Требуемое преобразование состоит в том,что мы многократно
"сливаем" два упорядоченных отрезка длины не больше k в один
упорядоченный отрезок. Пусть процедура слияние (p,q,r: integer)
при p <=q <= r сливает отрезки x[p+1]..x[q] и x[q+1]..x[r] в
