А. шень Издание шестое, дополненное Москва

• Название: А. шень Издание шестое, дополненное Москва
• Дата: 17.09.2022
• Размер: 1.62 Mb.
• Имя файла: shen-progbook.pdf
• Тип: Книга; #681926
• страница: 4 из 19

если нет, то последний член надо разбить на слагаемые, равные преды- дущему, и остаток, не меньший его.]

2.4.4. Представляя разбиения как неубывающие последовательно- сти, перечислите их в порядке, обратном лексикографическому. При- мер для n=4: 4, 2+2, 1+3, 1+1+2, 1+1+1+1.
[Указание. Чтобы элемент x[s] можно было уменьшить, необходи- мо, чтобы s=1 или x[s-1]
2.5. Коды Грея и аналогичные задачи
Иногда бывает полезно перечислять объекты в таком порядке, что- бы каждый следующий минимально отличался от предыдущего. Рас- смотрим несколько задач такого рода.
2.5.1. Перечислите все последовательности длины n из чисел 1..k в таком порядке, чтобы каждая следующая отличалась от предыдущей в единственной цифре, причём не более, чем на 1.
Решение. Рассмотрим прямоугольную доску ширины n и высоты k.
На каждой вертикали будет стоять шашка. Таким образом, положе- ния шашек соответствуют последовательностям из чисел 1..k длины n
(s-й член последовательности соответствует высоте шашки на s-й вер- тикали). На каждой шашке нарисуем стрелочку, которая может быть направлена вверх или вниз. Вначале все шашки поставим на нижнюю горизонталь стрелочкой вверх. Далее двигаем шашки по такому прави- лу: найдя самую правую шашку, которую можно подвинуть в направле- нии (нарисованной на ней) стрелки, двигаем её на одну клетку в этом

50 2. Порождение комбинаторных объектов направлении, а все стоящие правее неё шашки (они упёрлись в край)
разворачиваем кругом.
Ясно, что на каждом шаге только одна шашка сдвигается, т. е. один член последовательности меняется на 1. Докажем индукцией по n, что проходятся все последовательности из чисел 1..k. Случай n=1 очевиден.
Пусть n>1. Все ходы поделим на те, где двигается последняя шашка,
и те, где двигается не последняя. Во втором случае последняя шашка стоит у стены, и мы её поворачиваем, так что за каждым ходом второ- го типа следует k-1 ходов первого типа, за время которых последняя шашка побывает во всех клетках. Если мы теперь забудем о послед- ней шашке, то движения первых n-1 по предположению индукции про- бегают все последовательности длины n-1 по одному разу; движения же последней шашки из каждой последовательности длины n-1 делают k последовательностей длины n.
В программе, помимо последовательности x[1]..x[n], будем хра- нить массив d[1]..d[n] из чисел +1 и -1 (+1 соответствует стрелке вверх, -1 | стрелке вниз).
Начальное состояние: x[1]=...=x[n]=1; d[1]=...=d[n]=1.
Приведём алгоритм перехода к следующей последовательности (од- новременно выясняется, возможен ли переход | ответ становится зна- чением булевской переменной p).
{если можно, сделать шаг и положить p := true, если нет,
положить p := false }
i := n;
while (i > 1) and
(((d[i]=1) and (x[i]=n)) or ((d[i]=-1) and (x[i]=1)))
do begin i:=i-1;
end;
if (d[i]=1 and x[i]=n) or (d[i]=-1 and x[i]=1) then begin p:=false;
end else begin p:=true;
x[i] := x[i] + d[i];
for j := i+1 to n do begin d[j] := - d[j];
end;
end;

Замечание. Для последовательностей нулей и единиц возможно дру- гое решение, использующее двоичную систему. (Именно оно связыва- ется обычно с названием «коды Грея».)

2.5. Коды Грея и аналогичные задачи
51
Запишем подряд все числа от 0 до 2
𝑛
−
1 в двоичной системе. На- пример, для 𝑛 = 3 напишем:
000 001 010 011 100 101 110 111
Затем каждое из чисел подвергнем преобразованию, заменив каждую цифру, кроме первой, на её сумму с предыдущей цифрой (по модулю 2).
Иными словами, число 𝑎
1
, 𝑎
2
, . . . , 𝑎
𝑛
преобразуем в 𝑎
1
,𝑎
1
+ 𝑎
2
,𝑎
2
+ 𝑎
3
,. . .
. . . , 𝑎
𝑛−1
+ 𝑎
𝑛
(сумма по модулю 2). Для 𝑛 = 3 получим:
000 001 011 010 110 111 101 100
Легко проверить, что описанное преобразование чисел обратимо
(и тем самым даёт все последовательности по одному разу). Кроме то- го, двоичные записи соседних чисел отличаются заменой конца 011 . . . 1
на конец 100 . . . 0, что | после преобразования | приводит к измене- нию единственной цифры.
Применение кода Грея. Пусть есть вращающаяся ось, и мы хотим поставить датчик угла поворота этой оси. Насадим на ось барабан,
выкрасим половину барабана в чёрный цвет, половину в белый и уста- новим фотоэлемент. На его выходе будет в половине случаев 0, а в половине 1 (т. е. мы измеряем угол «с точностью до 180»).
Развёртка барабана:
0 1
←
склеить бока
Сделав рядом другую дорожку из двух чёрных и белых частей и по- ставив второй фотоэлемент, получаем возможность измерить угол с точностью до 90
∘
:
0 0
1 1
0 1
0 1
Сделав третью,
0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1

52 2. Порождение комбинаторных объектов мы измерим угол с точностью до 45
∘
и т. д. Эта идея имеет, однако, не- достаток: в момент пересечения границ сразу несколько фотоэлементов меняют сигнал, и если эти изменения произойдут не совсем одновре- менно, на какое-то время показания фотоэлементов будут бессмыслен- ными. Коды Грея позволяют избежать этой опасности. Сделаем так,
чтобы на каждом шаге менялось показание лишь одного фотоэлемента
(в том числе и на последнем, после целого оборота).
0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0
Написанная нами формула позволяет легко преобразовать данные от фотоэлементов в двоичный код угла поворота.
Заметим также, что геометрически существование кода Грея озна- чает наличие «гамильтонова цикла» в 𝑛-мерном кубе (возможность обойти все вершины куба по разу, двигаясь по рёбрам, и вернуться в исходную вершину).
2.5.2. Напечатайте все перестановки чисел 1..n так, чтобы каждая следующая получалась из предыдущей перестановкой (транспозицией)
двух соседних чисел. Например, при n=3 допустим такой порядок:
3.2 1 → 2 3.1 → 2.1 3 → 1 2.3 → 1.3 2 → 3 1 2
(между переставляемыми числами вставлены точки).
Решение. Наряду с множеством перестановок рассмотрим множе- ство последовательностей y[1]..y[n] целых неотрицательных чисел,
для которых y[1] 6 0, . . . , y[n] 6 n-1. В нём столько же элементов,
сколько в множестве всех перестановок, и мы сейчас установим между ними взаимно однозначное соответствие. Именно, каждой перестановке поставим в соответствие последовательность y[1]..y[n], где y[i] |
количество чисел, меньших i и стоящих левее i в этой перестановке.
Взаимная однозначность вытекает из такого замечания. Перестанов- ка чисел 1..n получается из перестановки чисел 1..n-1 добавлением числа n, которое можно вставить на любое из n мест. При этом к сопо- ставляемой с ней последовательности добавляется ещё один член, при- нимающий значения от 0 до n-1, а предыдущие члены не меняются.
При этом оказывается, что изменение на единицу одного из членов по- следовательности y соответствует транспозиции двух соседних чисел,

2.5. Коды Грея и аналогичные задачи
53
если все следующие числа последовательности y принимают максималь- но или минимально возможные для них значения. Именно, увеличение y[i] на 1 соответствует транспозиции числа i с его правым соседом,
а уменьшение | с левым.
Теперь вспомним решение задачи о перечислении всех последова- тельностей, на каждом шаге которого один член меняется на единицу.
Заменив прямоугольную доску доской в форме лестницы (высота i-й вертикали равна i) и двигая шашки по тем же правилам, мы перечи- слим все последовательности y, причём i-й член будет меняться как раз только если все следующие шашки стоят у края. Надо ещё уметь параллельно с изменением y корректировать перестановку. Очевидный способ требует отыскания в ней числа i; это можно облегчить, если помимо самой перестановки хранить функцию i ↦→ позиция числа i в перестановке,
т. е. обратное к перестановке отображение, и соответствующим обра- зом её корректировать. Вот какая получается программа:
program test;
const n=...;
var x: array [1..n] of 1..n; {перестановка}
inv_x: array [1..n] of 1..n; {обратная перестановка}
y: array [1..n] of integer; {y[i] < i}
d: array [1..n] of -1..1; {направления}
b: boolean;
procedure print_x;
var i: integer;
begin for i:=1 to n do begin write (x[i], ’ ’);
end;
writeln;
end;
procedure set_first;{первая: y[i]=0 при всех i}
var i : integer;
begin for i := 1 to n do begin x[i] := n + 1 - i;
inv_x[i] := n + 1 - i;
y[i]:=0;

54 2. Порождение комбинаторных объектов d[i]:=1;
end;
end;
procedure move (var done : boolean);
var i, j, pos1, pos2, val1, val2, tmp : integer;
begin i := n;
while (i > 1) and (((d[i]=1) and (y[i]=i-1)) or
((d[i]=-1) and (y[i]=0))) do begin i := i-1;
end;
done := (i>1); {упрощение: первый член нельзя менять}
if done then begin y[i] := y[i]+d[i];
for j := i+1 to n do begin d[j] := -d[j];
end;
pos1 := inv_x[i];
val1 := i;
pos2 := pos1 + d[i];
val2 := x[pos2];
{pos1, pos2 - номера переставляемых элементов;
val1, val2 - их значения; val2 < val1}
tmp := x[pos1];
x[pos1] := x[pos2];
x[pos2] := tmp;
tmp := inv_x[val1];
inv_x[val1] := inv_x[val2];
inv_x[val2] := tmp;
end;
end;
begin set_first;
print_x;
b := true;
{напечатаны все перестановки до текущей включительно;
если b ложно, то текущая - последняя}
while b do begin move (b);
if b then print_x;
end;
end.


2.6. Несколько замечаний
55 2.6. Несколько замечаний
Посмотрим ещё раз на использованные нами приёмы. Вначале уда- валось решить задачу по такой схеме: определяем порядок на подле- жащих перечислению объектах и явно описываем процедуру перехода от данного объекта к следующему (в смысле этого порядка). В задаче о кодах Грея потребовалось хранить, помимо текущего объекта, и неко- торую дополнительную информацию (направления стрелок). Наконец,
в задаче о перечислении перестановок (на каждом шаге допустима одна транспозиция) мы применили такой приём: установили взаимно одно- значное соответствие между перечисляемым множеством и другим, бо- лее просто устроенным. Таких соответствий в комбинаторике известно много. Мы приведём несколько задач, связанных с так называемыми
«числами Каталана».
2.6.1. Перечислите все последовательности длины 2n, составленные из n единиц и n минус единиц, у которых сумма любого начального от- резка неотрицательна, т. е. число минус единиц в нём не превосходит числа единиц. (Число таких последовательностей называют числом Ка- талана; формулу для чисел Каталана см. в следующем разделе.)
Решение. Изображая единицу вектором (1,1), а минус единицу век- тором (1,-1), можно сказать, что мы ищем пути из точки (0,0) в точ- ку (n,0), не опускающиеся ниже оси абсцисс.
Будем перечислять последовательности в лексикографическом по- рядке, считая, что -1 предшествует 1. Первой последовательностью будет «пила»
1, -1, 1, -1, ...
а последней | «горка»
1, 1, 1,..., 1, -1, -1,..., -1.
Как перейти от последовательности к следующей? До некоторого места они должны совпадать, а затем надо заменить -1 на 1. Место за- мены должно быть расположено как можно правее. Но заменять -1 на 1
можно только в том случае, если справа от неё есть единица (которую можно заменить на -1). После замены -1 на 1 мы приходим к такой за- даче: фиксирован начальный кусок последовательности, надо найти ми- нимальное продолжение. Её решение: надо приписывать -1, если это не нарушит условия неотрицательности, а иначе приписывать 1. Получаем

56 2. Порождение комбинаторных объектов такую программу:
type array2n = array [1..2n] of integer;
procedure get_next (var a: array2n; var last: Boolean);
{в a помещается следующая последовательность, если}
{она есть (при этом last:=false), иначе last:=true}
var k, i, sum: integer;
begin k:=2*n;
{инвариант: в a[k+1..2n] только минус единицы}
while a[k] = -1 do begin k:=k-1; end;
{k - максимальное среди тех, для которых a[k]=1}
while (k>0) and (a[k] = 1) do begin k:=k-1; end;
{a[k] - самая правая -1, за которой есть 1;
если таких нет, то k=0}
if k = 0 then begin last := true;
end else begin last := false;
i:=0; sum:=0;
{sum = a[1]+...+a[i]}
while i<>k do begin i:=i+1; sum:= sum+a[i];
end;
{sum = a[1]+...+a[k], a[k]=-1}
a[k]:= 1; sum:= sum+2;
{вплоть до a[k] всё изменено, sum=a[1]+...+a[k]}
while k <> 2*n do begin k:=k+1;
if sum > 0 then begin a[k]:=-1
end else begin a[k]:=1;
end;
sum:= sum+a[k];
end;
{k=2n, sum=a[1]+...+a[2n]=0}
end;
end;

2.6.2. Перечислите все расстановки скобок в произведении n сомно- жителей. Порядок сомножителей не меняется, скобки полностью опре-

2.7. Подсчёт количеств
57
деляют порядок действий. Например, для n=4 есть 5 расстановок:
((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).
[Указание. Каждому порядку действий соответствует последова- тельность команд стекового калькулятора, описанного на с.
144
.]

2.6.3. На окружности задано 2n точек, пронумерованных от 1 до 2n.
Перечислите все способы провести n непересекающихся хорд с верши- нами в этих точках.

2.6.4. Перечислите все способы разрезать n-угольник на треуголь- ники, проведя n-2 его диагонали.

(Мы вернёмся к разрезанию многоугольника в разделе о динамиче- ском программировании, с.
137
.)
Ещё один класс задач на перечисление всех элементов заданного множества мы рассмотрим ниже, обсуждая метод поиска с возвратами
(backtracking).
2.7. Подсчёт количеств
Иногда можно найти количество объектов с тем или иным свой- ством, не перечисляя их. Классический пример: 𝐶
𝑘
𝑛
| число всех 𝑘-эле- ментных подмножеств 𝑛-элементного множества | можно найти, за- полняя таблицу по формулам
𝐶
0
𝑛
= 𝐶
𝑛
𝑛
= 1
(𝑛 > 1)
𝐶
𝑘
𝑛
= 𝐶
𝑘−1
𝑛−1
+ 𝐶
𝑘
𝑛−1
(𝑛 > 1, 0 < 𝑘 < 𝑛)
или по формуле
𝐶
𝑘
𝑛
=
𝑛!
𝑘! · (𝑛 − 𝑘)!
(Первый способ эффективнее, если нужно сразу много значений 𝐶
𝑘
𝑛
.)
Приведём другие примеры.
2.7.1. (Число разбиений; предлагалась на Всесоюзной олимпиаде по программированию 1988 года) Пусть 𝑃 (𝑛) | число разбиений целого положительного 𝑛 на целые положительные слагаемые (без учёта по- рядка, 1 + 2 и 2 + 1 | одно и то же разбиение). При 𝑛 = 0 положим
𝑃 (𝑛) = 1 (единственное разбиение не содержит слагаемых). Постройте алгоритм вычисления 𝑃 (𝑛) для заданного 𝑛.

58 2. Порождение комбинаторных объектов
Решение. Можно доказать (это нетривиально) такую формулу для
𝑃 (𝑛):
𝑃 (𝑛)=𝑃 (𝑛−1)+𝑃 (𝑛−2)−𝑃 (𝑛−5)−𝑃 (𝑛−7)+𝑃 (𝑛−12)+𝑃 (𝑛−15)+. . .
(знаки у пар членов чередуются, вычитаемые в одной паре равны
(3𝑞
2
−
𝑞)/2 и (3𝑞
2
+ 𝑞)/2; сумма конечна | мы считаем, что 𝑃 (𝑘) = 0
при 𝑘 < 0).
Однако и без её использования можно придумать способ вычисле- ния 𝑃 (𝑛), который существенно эффективнее перебора и подсчёта всех разбиений.
Обозначим через 𝑅(𝑛, 𝑘) (для 𝑛 > 0, 𝑘 > 0) число разбиений 𝑛 на це- лые положительные слагаемые, не превосходящие 𝑘. (При этом 𝑅(0, 𝑘)
считаем равным 1 для всех 𝑘 > 0.) Очевидно, 𝑃 (𝑛) = 𝑅(𝑛, 𝑛). Все разби- ения 𝑛 на слагаемые, не превосходящие 𝑘, разобьём на группы в зави- симости от максимального слагаемого (обозначим его 𝑖). Число 𝑅(𝑛, 𝑘)
равно сумме (по всем 𝑖 от 1 до 𝑘) количеств разбиений со слагаемыми не больше 𝑘 и максимальным слагаемым, равным 𝑖. А разбиения 𝑛 на слагаемые не более 𝑘 с первым слагаемым, равным 𝑖, по существу пред- ставляют собой разбиения 𝑛 − 𝑖 на слагаемые, не превосходящие 𝑖 (при
𝑖 6 𝑘). Так что
𝑅(𝑛, 𝑘) =
𝑘
∑︁
𝑖=1
𝑅(𝑛 − 𝑖, 𝑖)
при 𝑘 6 𝑛,
𝑅(𝑛, 𝑘) = 𝑅(𝑛, 𝑛)
при 𝑘 > 𝑛,
что позволяет заполнять таблицу значений функции 𝑅.

2.7.2. (Счастливые билеты; предлагалась на Всесоюзной олимпиа- де по программированию 1989 года.) Последовательность из 2𝑛 цифр
(каждая цифра от 0 до 9) называется счастливым билетом, если сумма первых 𝑛 цифр равна сумме последних 𝑛 цифр. Найдите число счаст- ливых последовательностей данной длины.
Решение. (Сообщено одним из участников олимпиады; к сожалению,
не могу указать фамилию, так как работы проверялись зашифрован- ными.) Рассмотрим более общую задачу: найти число последователь- ностей, где разница между суммой первых 𝑛 цифр и суммой послед- них 𝑛 цифр равна 𝑘 (𝑘 = −9𝑛, . . . , 9𝑛). Пусть 𝑇 (𝑛, 𝑘) | число таких последовательностей.
Разобьём множество таких последовательностей на классы в зависи- мости от разницы между первой и последней цифрами. Если эта разни- ца равна 𝑡, то разница между суммами групп из оставшихся 𝑛 − 1 цифр

2.7. Подсчёт количеств
59
равна 𝑘 − 𝑡. Учитывая, что пар цифр с разностью 𝑡 бывает 10 − |𝑡|, по- лучаем формулу
𝑇 (𝑛, 𝑘) =
9
∑︁
𝑡=−9
(10 − |𝑡|)𝑇 (𝑛 − 1, 𝑘 − 𝑡).
(Некоторые слагаемые могут отсутствовать, так как 𝑘 − 𝑡 может быть слишком велико.)

В некоторых случаях ответ удаётся получить в виде явной формулы.
2.7.3. Докажите, что число Каталана (количество последовательно- стей длины 2𝑛 из 𝑛 единиц и 𝑛 минус единиц, в любом начальном отрез- ке которых не меньше единиц, чем минус единиц) равно 𝐶
𝑛
2𝑛
/(𝑛 + 1).
[Указание. Число Каталана есть число ломаных, идущих из (0, 0)
в (2𝑛, 0) шагами (1, 1) и (1, −1), не опускающихся в нижнюю полуплос- кость, т. е. разность числа всех ломаных (которое есть 𝐶
𝑛
2𝑛
) и числа ло- маных, опускающихся в нижнюю полуплоскость. Последние можно опи- сать также как ломаные, пересекающие прямую 𝑦 = −1. Отразив их ку- сок справа от самой правой точки пересечения относительно указанной прямой, мы установим взаимно однозначное соответствие между ними и ломаными из (0, 0) в (2𝑛, −2). Остаётся проверить, что 𝐶
𝑛
2𝑛
−
𝐶
𝑛+1 2𝑛
=
= 𝐶
𝑛
2𝑛
/(𝑛 + 1).]


3. ОБХОД ДЕРЕВА.
ПЕРЕБОР С ВОЗВРАТАМИ
3.1. Ферзи, не бьющие друг друга:
обход дерева позиций
В предыдущей главе мы рассматривали несколько задач одного и то- го же типа: «перечислить все элементы некоторого множества 𝐴». Схе- ма решения была такова: на множестве 𝐴 вводился порядок и описы- валась процедура перехода от произвольного элемента множества 𝐴
к следующему за ним (в этом порядке). Такую схему не всегда удаётся реализовать непосредственно, и в этой главе мы рассмотрим другой полезный приём перечисления всех элементов некоторого множества.
Его называют «поиск с возвратами», «метод ветвей и границ», «back- tracking». На наш взгляд, наиболее точное название этого метода |
обход дерева.
3.1.1. Перечислите все способы расстановки 𝑛 ферзей на шахмат- ной доске 𝑛 × 𝑛, при которых они не бьют друг друга.
Решение. Очевидно, на каждой из 𝑛 горизонталей должно стоять по ферзю. Будем называть 𝑘-позицией (для 𝑘 = 0, 1, . . . , 𝑛) произволь- ную расстановку 𝑘 ферзей на 𝑘 нижних горизонталях (ферзи могут бить друг друга). Нарисуем «дерево позиций»: его корнем будет един- ственная 0-позиция, а из каждой 𝑘-позиции выходит 𝑛 стрелок вверх в (𝑘 + 1)-позиции. Эти 𝑛 позиций отличаются положением ферзя на
(𝑘 + 1)-й горизонтали. Будем считать, что расположение их на рисун- ке соответствует положению этого ферзя: левее та позиция, в которой ферзь расположен левее.
Среди позиций этого дерева нам надо отобрать те 𝑛-позиции, в ко- торых ферзи не бьют друг друга. Программа будет «обходить дерево»
и искать их. Чтобы не делать лишней работы, заметим вот что: если в какой-то 𝑘-позиции ферзи бьют друг друга, то ставить дальнейших

3.1. Ферзи, не бьющие друг друга: обход дерева позиций
61
P
P
P
P
P
i





1
@
@
I

@
@
I

∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
Дерево позиций для 𝑛 = 2
ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в этом направлении.
Точнее, назовём 𝑘-позицию допустимой, если после удаления верх- него ферзя оставшиеся не бьют друг друга. Наша программа будет рассматривать только допустимые позиции.
P
P
P
P
P
P
P
P
i








1 6
B
B
B
M




6
B
B
B
M




6
B
B
B
M




6
B
B
B
M




6
B
B
B
M




6
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
Дерево допустимых позиций для 𝑛 = 3
Разобьём задачу на две части: (1) обход произвольного дерева и (2)
реализацию дерева допустимых позиций.

62 3. Обход дерева. Перебор с возвратами
Сформулируем задачу обхода произвольного дерева. Будем счи- тать, что у нас имеется Робот, который в каждый момент находится в одной из вершин дерева (вершины изображены на рисунке кружоч- ками). Он умеет выполнять команды:
∙
вверх налево (идти по самой левой из выходящих вверх стрелок)
∙
вправо (перейти в соседнюю справа вершину)
∙
вниз (спуститься вниз на один уровень)
(На рисунках стрелками показано, какие перемещения соответствуют этим командам.)
вверх налево q
@
@
@
q q
A
A
A






q






q q q q
@
@
@
A
A
A






q q q q q q
@
@
@
I
A
A
A
K
6
@
@
@
I
вправо q
@
@
@
q q
A
A
A






q






q q q q
@
@
@
A
A
A






q q q q q q
-
-
- -
- -
- - - вниз q
q
@
@
@
R
q
?
q q
A
A
A
U
q
?
q






q
?
q






q q
@
@
@
R
q
A
A
A
U
q
?
q






@
@
@
A
A
A












@
@
@
A
A
A






Кроме того, в репертуар Робота входят проверки (соответствующие возможности выполнить каждую из команд):
∙
есть сверху;
∙
есть справа;
∙
есть снизу;
(последняя проверка истинна всюду, кроме корня). Обратите внимание,
что команда вправо позволяет перейти лишь к «родному брату», но не к «двоюродному».
q
@
@
@
I

q
A
A
A
K







q
A
A
A
K







q q
q q
-
@
@
Так команда вправо не действует!
Будем считать, что у Робота есть команда обработать и что его задача | обработать все листья (вершины, из которых нет стрелок

3.1. Ферзи, не бьющие друг друга: обход дерева позиций
63
вверх, то есть где условие есть сверху ложно). Для нашей шахматной задачи команде обработать будет соответствовать проверка и печать позиции ферзей.
Доказательство правильности приводимой далее программы ис- пользует такие определения. Пусть фиксировано положение Робота в одной из вершин дерева. Тогда все листья дерева разбиваются на три категории: над Роботом, левее Робота и правее Робота. (Путь из корня в лист может проходить через вершину с Роботом, сворачивать влево, не доходя до неё и сворачивать вправо, не доходя до неё.) Через
(ОЛ) обозначим условие «обработаны все листья левее Робота», а через
(ОЛН) | условие «обработаны все листья левее и над Роботом».
q q
@
@
@
@
@
@




@
@
@






Левее
Над Правее
Нам понадобится такая процедура:
procedure вверх_до_упора_и_обработать;
{дано: (ОЛ), надо: (ОЛН)}
begin
{инвариант: ОЛ}
while есть_сверху do begin вверх_налево;
end
{ОЛ, Робот в листе}
обработать;
{ОЛН}
end;
Основной алгоритм:
дано: Робот в корне, листья не обработаны надо: Робот в корне, листья обработаны
{ОЛ}
вверх_до_упора_и_обработать;
{инвариант: ОЛН}

64 3. Обход дерева. Перебор с возвратами while есть_снизу do begin if есть_справа then begin {ОЛН, есть справа}
вправо;
{ОЛ}
вверх_до_упора_и_обработать;
end else begin
{ОЛН, не есть_справа, есть_снизу}
вниз;
end;
end;
{ОЛН, Робот в корне => все листья обработаны}
Осталось воспользоваться следующими свойствами команд Робота
(в каждой строке в первой фигурной скобке записаны условия, в кото- рых выполняется команда, во второй | утверждения о результате её
выполнения):
(1)
{
ОЛ, не есть сверху} обработать {ОЛН}
(2)
{
ОЛ, есть сверху} вверх налево {ОЛ}
(3)
{
есть справа, ОЛН} вправо {ОЛ}
(4)
{
не есть справа, есть снизу, ОЛН} вниз {ОЛН}
3.1.2. Докажите, что приведённая программа завершает работу (на любом конечном дереве).
Решение. Процедура вверх до упора и обработать завершает рабо- ту (высота Робота не может увеличиваться бесконечно). Если програм- ма работает бесконечно, то, поскольку листья не обрабатываются по- вторно, начиная с некоторого момента ни один лист не обрабатывается.
А это возможно, только если Робот всё время спускается вниз. Проти- воречие. (Об оценке числа действий см. далее.)

3.1.3. Докажите правильность такой программы обхода дерева:
var state: (WL, WLU);
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;

3.1. Ферзи, не бьющие друг друга: обход дерева позиций
65
Решение. Инвариант цикла:
state = WL ⇒ ОЛ
state = WLU ⇒ ОЛН
Доказательство завершения работы: переход из состояния ОЛ в ОЛН
возможен только при обработке вершины, поэтому если программа ра- ботает бесконечно, то с некоторого момента значение state не меня- ется, что невозможно.

3.1.4. Напишите программу обхода дерева, использующую процеду- ру перехода в следующий лист (с выходным параметром, сообщающим,
удалось ли это сделать или лист оказался последним).

3.1.5. Решите задачу об обходе дерева, если мы хотим, чтобы об- рабатывались все вершины (не только листья).
Решение. Пусть 𝑥 | некоторая вершина. Тогда любая вершина 𝑦
относится к одной из четырёх категорий. Рассмотрим путь из корня в 𝑦. Он может:
(а) быть частью пути из корня в 𝑥 (𝑦 ниже 𝑥);
(б) свернуть налево с пути в 𝑥 (𝑦 левее 𝑥);
(в) пройти через 𝑥 (𝑦 над 𝑥);
(г) свернуть направо с пути в 𝑥 (𝑦 правее 𝑥);
В частности, сама вершина 𝑥 относится к категории (в). Условия теперь будут такими:
(ОНЛ) обработаны все вершины ниже и левее;
(ОНЛН) обработаны все вершины ниже, левее и над.
Вот как будет выглядеть программа:
procedure вверх_до_упора_и_обработать;
{дано: (ОНЛ), надо: (ОНЛН)}
begin
{инвариант: ОНЛ}
while есть_сверху do begin обработать;
вверх_налево;
end
{ОНЛ, Робот в листе}
обработать;
{ОНЛН}
end;

66 3. Обход дерева. Перебор с возвратами
Основной алгоритм:
дано: Робот в корне, ничего не обработано надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать;
{инвариант: ОНЛН}
while есть_снизу do begin if есть_справа then begin {ОНЛН, есть справа}
вправо;
{ОНЛ}
вверх_до_упора_и_обработать;
end else begin
{ОЛН, не есть_справа, есть_снизу}
вниз;
end;
end;
{ОНЛН, Робот в корне => все вершины обработаны}

3.1.6. Приведённая только что программа обрабатывает вершину до того, как обработан любой из её потомков. Как изменить програм- му, чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды: один раз до, а другой раз после всех своих потомков? (Ли- стья по-прежнему обрабатываются по разу.)
Решение. Под «обработано ниже и левее» будем понимать «ниже об- работано по разу, слева обработано полностью (листья по разу, осталь- ные по два)». Под «обработано ниже, левее и над» будем понимать «ниже обработано по разу, левее и над | полностью».
Программа будет такой:
procedure вверх_до_упора_и_обработать;
{дано: (ОНЛ), надо: (ОНЛН)}
begin
{инвариант: ОНЛ}
while есть_сверху do begin обработать;
вверх_налево;
end
{ОНЛ, Робот в листе}
обработать;
{ОНЛН}
end;

3.1. Ферзи, не бьющие друг друга: обход дерева позиций
67
Основной алгоритм:
дано: Робот в корне, ничего не обработано надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать;
{инвариант: ОНЛН}
while есть_снизу do begin if есть_справа then begin {ОНЛН, есть справа}
вправо;
{ОНЛ}
вверх_до_упора_и_обработать;
end else begin
{ОЛН, не есть_справа, есть_снизу}
вниз;
обработать;
end;
end;
{ОНЛН, Робот в корне => все вершины обработаны полностью}

3.1.7. Докажите, что число операций в этой программе по поряд- ку равно числу вершин дерева. (Как и в других программах, которые отличаются от этой лишь пропуском некоторых команд обработать.)
[Указание. Примерно каждое второе действие при исполнении этой программы | обработка вершины, а каждая вершина обрабатывается максимум дважды.]

Вернёмся теперь к нашей задаче о ферзях (где из всех программ обработки дерева понадобится лишь первая, самая простая). Реализу- ем операции с деревом позиций. Позицию будем представлять с по- мощью переменной 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;

68 3. Обход дерева. Перебор с возвратами 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_down := (k > 0);
end;
procedure up; {вверх_налево}
begin {k < n, not danger}
k := k + 1;
c [k] := 1;
end;

3.1. Ферзи, не бьющие друг друга: обход дерева позиций
69
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.


70 3. Обход дерева. Перебор с возвратами
3.1.8. Приведённая программа тратит довольно много времени на выполнение проверки есть сверху (проверка, находится ли верхний ферзь под боем, требует числа действий порядка n). Измените ре- ализацию операций с деревом позиций так, чтобы все три провер- ки есть сверху/справа/снизу и соответствующие команды требова- ли бы количества действий, ограниченного не зависящей от n конс- тантой.
Решение. Для каждой вертикали, каждой восходящей и каждой нис- ходящей диагонали будем хранить булевское значение | сведения о том, находится ли на этой линии ферзь (верхний ферзь не учитывает- ся). (Заметим, что в силу допустимости позиции на каждой из линий может быть не более одного ферзя.)

3.2. Обход дерева в других задачах
3.2.1. Используйте метод обхода дерева для решения следующей за- дачи: дан массив из n целых положительных чисел a[1] . . . a[n] и чи- сло s; требуется узнать, может ли число s быть представлено как сумма некоторых из чисел массива a. (Каждое число можно использовать не более чем по одному разу.)
Решение. Будем задавать k-позицию последовательностью из k бу- левских значений, определяющих, входят ли в сумму числа a[1] . . . a[k]
или не входят. Позиция допустима, если её сумма не превосходит s. 
Замечание. По сравнению с полным перебором всех 2n подмножеств тут есть некоторый выигрыш. Можно также предварительно отсорти- ровать массив a в убывающем порядке, а также считать недопусти- мыми те позиции, в которых сумма отброшенных членов больше, чем разность суммы всех членов и s. Последний приём называют «методом ветвей и границ». Но принципиального улучшения по сравнению с пол- ным перебором тут не получается (эта задача, как говорят, 𝑁𝑃 -пол- на, подробности см. в книге Ахо, Хопкрофта и Ульмана «Построение и анализ вычислительных алгоритмов», Мир, 1979, а также в книге Гэ- ри и Джонсона «Вычислительные машины и труднорешаемые задачи»,
Мир, 1982). Традиционное название этой задачи | «задача о рюкза- ке» (рюкзак общей грузоподъёмностью s нужно упаковать под завяз- ку, располагая предметами веса a[1] . . . a[n]). См. также в главе
8
(Как обойтись без рекурсии) алгоритм её решения, полиномиальный по n + s
(использующий «динамическое программирование»).

3.2. Обход дерева в других задачах
71 3.2.2. Перечислите все последовательности из 𝑛 нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд
(нет куска вида 𝑋𝑋).

3.2.3. Аналогичная задача для последовательностей нулей и единиц,
в которых никакая группа цифр не повторяется три раза подряд (нет куска вида 𝑋𝑋𝑋).

К этой же категории относятся задачи типа «можно ли сложить данную фигуру из пентамино» и им подобные. В них важно умелое со- кращение перебора (вовремя распознать, что имеющееся расположение фигурок уже противоречит требованиям, и по этой ветви поиск не про- должать).

4. СОРТИРОВКА
4.1. Квадратичные алгоритмы
4.1.1. Пусть a[1], . . . , a[n] | целые числа. Требуется построить массив b[1], . . . , b[n], содержащий те же числа, для которого b[1] 6 . . .
. . . 6 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 наименьших элементов массива установлены на свои места}
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] 6 . . . 6 x[k]).

4.2. Алгоритмы порядка 𝑛 log 𝑛
73
Решение.
k:=1;
{первые k элементов упорядочены}
while k <> n do begin t := k+1;
{k+1-ый элемент продвигается к началу, пока не займёт надлежащего места, t - его текущий номер}
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
2
. Существуют более эффективные алгоритмы.
4.2. Алгоритмы порядка 𝑛 log 𝑛
4.2.1. Предложите алгоритм сортировки за время 𝑛 log 𝑛 (число опе- раций при сортировке 𝑛 элементов не больше 𝐶𝑛 log 𝑛 для некоторого 𝐶
и для всех 𝑛).
Мы приведём два решения.
Решение 1 (сортировка слиянием).
Пусть k | положительное целое число. Разобьём массив x[1] . . . x[n]
на отрезки длины k. (Первый | x[1] . . . x[k], затем x[k+1] . . . x[2k]
и так далее.) Последний отрезок будет неполным, если n не делится на k. Назовём массив k-упорядоченным, если каждый из этих отрезков в отдельности упорядочен. Любой массив 1-упорядочен. Если массив k-упорядочен и n 6 k, то он упорядочен.
Мы опишем, как преобразовать k-упорядоченный массив в 2k-упо- рядоченный (из тех же элементов). С помощью этого преобразования алгоритм записывается так:
k:=1;
{массив x является k-упорядоченным}
while k < n do begin
...преобразовать k-упорядоченный массив в 2k-упорядоченный;
k := 2 * k;
end;

74 4. Сортировка
Требуемое преобразование состоит в том,что мы многократно «сли- ваем» два упорядоченных отрезка длины не больше k в один упорядо- ченный отрезок. Пусть процедура слияние (p,q,r: integer)
при p 6 q 6 r сливает отрезки x[p+1] . . . x[q] и x[q+1] . . . x[r] в упоря- доченный отрезок x[p+1] . . . x[r] (не затрагивая других частей масси- ва x).
упорядоченный упорядоченный упорядоченный
↓
p q
r
Тогда преобразование k-упорядоченного массива в 2k-упорядоченный осуществляется так:
t:=0;
{t кратно 2k или t = n, x[1]..x[t] является
2k-упорядоченным; остаток массива x не изменился}
while t + k < n do begin p := t;
q := t+k;
r := min (t+2*k, n);
{min(a,b) - минимум из a и b}
слияние (p,q,r);
t := r;
end;
Слияние требует вспомогательного массива для записи результатов слияния | обозначим его b. Через p0 и q0 обозначим номера последних элементов участков, подвергшихся слиянию, s0 | последний записан- ный в массив b элемент. На каждом шаге слияния производится одно из двух действий:
b[s0+1]:=x[p0+1];
p0:=p0+1;
s0:=s0+1;

4.2. Алгоритмы порядка 𝑛 log 𝑛
75
или b[s0+1]:=x[q0+1];
q0:=q0+1;
s0:=s0+1;
(Любители языка C написали бы в этом случае b[++s0]=x[++p0] и b[++s0]=x[++q0].)
Первое действие (взятие элемента из первого отрезка) может про- изводиться при одновременном выполнении двух условий:
(1) первый отрезок не кончился (p0 < q);
(2) второй отрезок кончился (q0 = r) или не кончился, но эле- мент в нём не меньше очередного элемента первого отрезка [(q0 < r)
и(x[p0+1] 6 x[q0+1])].
Аналогично для второго действия. Итак, получаем p0 := p; q0 := q; s0 := p;
while (p0 <> q) or (q0 <> r) do begin if (p0 < q) and ((q0 = r) or ((q0 < r) and
(x[p0+1] <= x[q0+1]))) then begin b [s0+1] := x [p0+1];
p0 := p0+1;
s0 := s0+1;
end else begin
{(q0 < r) and ((p0 = q) or ((p0(x[p0+1] >= x[q0+1])))}
b [s0+1] := x [q0+1];
q0 := q0 + 1;
s0 := s0 + 1;
end;
end;
(Если оба отрезка не кончены и первые невыбранные элементы в них равны, то допустимы оба действия; в программе выбрано первое.)
Остаётся лишь переписать результат слияния обратно в массив x.
(Предупреждение. Если обратное копирование выполняется вне проце- дуры слияния, то не забудьте про последний отрезок.)
Программа имеет привычный дефект: обращение к несуществую- щим элементам массива при вычислении булевских выражений.
Решение 2 (сортировка деревом).
Нарисуем «полное двоичное дерево» | картинку, в которой снизу один кружок, из него выходят стрелки в два других, из каждого |

76 4. Сортировка в два других и так далее:
r r
r r
r r
r r r r r r r r r
@
@
@
I

A
A
A
K







A
A
A
K







B
B
M



B
B
M



B
B
M



B
B
M



Будем говорить, что стрелки ведут «от отцов к сыновьям»: у каждо- го кружка два сына и один отец (если кружок не в самом верху или низу). Предположим для простоты, что количество подлежащих сорти- ровке чисел есть степень двойки, и они могут заполнить один из рядов целиком. Запишем их туда. Затем заполним часть дерева под ними по правилу:
число в кружке = минимум из чисел в кружках-сыновьях
Тем самым в корне дерева (нижнем кружке) будет записано минималь- ное число во всём массиве.
Изымем из сортируемого массива минимальный элемент. Для этого его надо вначале найти. Это можно сделать, идя от корня: от отца пе- реходим к тому сыну, где записано то же число. Изъяв минимальный элемент, заменим его символом +∞ и скорректируем более низкие яру- сы (для этого надо снова пройти путь к корню). При этом считаем, что min(𝑡, +∞) = 𝑡. Тогда в корне появится второй по величине элемент, мы изымаем его, заменяя бесконечностью и корректируя дерево. Так по- степенно мы изымем все элементы в порядке возрастания, пока в корне не останется бесконечность.
При записи этого алгоритма полезно нумеровать кружки числами
1, 2, . . . | при этом сыновьями кружка номер n являются кружки 2n и 2n + 1. Подробное изложение этого алгоритма мы опустим, поскольку мы изложим более эффективный вариант, не требующий дополнитель- ной памяти, кроме конечного числа переменных (в дополнение к сор- тируемому массиву).
Мы будем записывать сортируемые числа во всех вершинах де- рева, а не только на верхнем уровне. Пусть x[1] . . . x[n] | мас- сив, подлежащий сортировке. Вершинами дерева будут числа от 1
до n; о числе x[i] мы будем говорить как о числе, стоящем в вер- шине i. В процессе сортировки количество вершин дерева будет сокращаться. Число вершин текущего дерева будем хранить в пе-

4.2. Алгоритмы порядка 𝑛 log 𝑛
77
ременной k. Таким образом, в процессе работы алгоритма массив x[1] . . . x[n] делится на две части: в x[1] . . . x[k] хранятся числа на дереве, а в x[k+1] . . . x[n] хранится уже отсортированная в порядке возрастания часть массива | элементы, уже занявшие своё законное место.
На каждом шаге алгоритм будет изымать максимальный элемент дерева и помещать его в отсортированную часть, на освободившееся в результате сокращения дерева место.
Договоримся о терминологии. Вершинами дерева считаются числа от 1 до текущего значения переменной k. У каждой вершины s могут быть сыновья 2s и 2s+1. Если оба этих числа больше k, то сыновей нет;
такая вершина называется листом. Если 2s = k, то вершина s имеет ровно одного сына (2s).
Для каждого s из 1 . . . k рассмотрим «поддерево» с корнем в s: оно содержит вершину s и всех её потомков (сыновей, внуков и так да- лее | до тех пор, пока мы не выйдем из отрезка 1 . . . k). Вершину s будем называть регулярной, если стоящее в ней число | максималь- ный элемент s-поддерева; s-поддерево назовём регулярным, если все его вершины регулярны. (В частности, любой лист образует регуляр- ное одноэлементное поддерево.)
Заметим, что истинность утверждения «s-поддерево регулярно» за- висит не только от s, но от текущего значения k.
Схема алгоритма такова:
k:= n
...Сделать 1-поддерево регулярным;
{x[1],...,x[k] <= x[k+1] <=..<= x[n]; 1-поддерево регулярно,
в частности, x[1] - максимальный элемент среди x[1]..x[k]}
while k <> 1 do begin
...обменять местами x[1] и x[k];
k := k - 1;
{x[1],...,x[k-1] <= x[k] <=...<= x[n]; 1-поддерево регулярно везде, кроме, возможно, самого корня }
...восстановить регулярность 1-поддерева всюду end;
В качестве вспомогательной процедуры нам понадобится процедура восстановления регулярности s-поддерева в корне. Вот она:
{s-поддерево регулярно везде, кроме, возможно, корня}
t := s;
{s-поддерево регулярно везде, кроме, возможно, вершины t}

78 4. Сортировка while ((2*t+1 <= k) and (x[2*t+1] > x[t])) or
((2*t <= k) and (x[2*t] > x[t])) do begin if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin
...обменять x[t] и x[2*t+1];
t := 2*t + 1;
end else begin
...обменять x[t] и x[2*t];
t := 2*t;
end;
end;
Чтобы убедиться в правильности этой процедуры, посмотрим на неё повнимательнее. Пусть в s-поддереве все вершины, кроме разве что вершины t, регулярны. Рассмотрим сыновей вершины t. Они ре- гулярны, и потому содержат наибольшие числа в своих поддеревьях.
Таким образом, на роль наибольшего числа в t-поддереве могут пре- тендовать число в самой вершине t и числа в её сыновьях. (В первом случае вершина t регулярна, и всё в порядке.) В этих терминах цикл можно записать так:
while наибольшее число не в t, а в одном из сыновей do begin if оно в правом сыне then begin поменять t с её правым сыном; t:= правый сын end else begin {наибольшее число - в левом сыне}
поменять t с её левым сыном; t:= левый сын end end
После обмена вершина t становится регулярной (в неё попадает макси- мальное число t-поддерева). Не принявший участия в обмене сын оста-
ётся регулярным, а принявший участие может и не быть регулярным.
В остальных вершинах s-поддерева не изменились ни числа, ни подде- ревья их потомков (разве что два элемента поддерева переставились),
так что регулярность не нарушилась.
Эта же процедура может использоваться для того, чтобы сделать
1-поддерево регулярным на начальной стадии сортировки:
k := n; u := n;
{все s-поддеревья с s>u регулярны }
while u<>0 do begin
{u-поддерево регулярно везде, кроме разве что корня}
...восстановить регулярность u-поддерева в корне;
u:=u-1;
end;

4.2. Алгоритмы порядка 𝑛 log 𝑛
79
Теперь запишем процедуру сортировки на паскале (предполагая,
что n | константа, x имеет тип arr = array [1..n] of integer).
procedure sort (var x: arr);
var u, k: integer;
procedure exchange(i, j: integer);
var tmp: integer;
begin tmp := x[i];
x[i] := x[j];
x[j] := tmp;
end;
procedure restore (s: integer);
var t: integer;
begin t:=s;
while ((2*t+1 <= k) and (x[2*t+1] > x[t])) or
((2*t <= k) and (x[2*t] > x[t])) do begin if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin exchange (t, 2*t+1);
t := 2*t+1;
end else begin exchange (t, 2*t);
t := 2*t;
end;
end;
end;
begin k:=n;
u:=n;
while u <> 0 do begin restore (u);
u := u - 1;
end;
while k <> 1 do begin exchange (1, k);
k := k - 1;
restore (1);
end;
end;

Несколько замечаний.
Метод, использованный при сортировке деревом, бывает полезным в других случаях. (См. в главе
6
(Типы данных) об очереди с приори- тетами.)

80 4. Сортировка
Сортировка слиянием хороша тем, что она на требует, чтобы весь сортируемый массив помещался в оперативной памяти. Можно сначала отсортировать такие куски, которые помещаются в памяти (например,
с помощью дерева), а затем сливать полученные файлы.
Ещё один практически важный алгоритм сортировки (быстрая сор- тировка Хоара) таков: чтобы отсортировать массив, выберем случай- ный его элемент 𝑏, и разобьём массив на три части: меньшие 𝑏, равные 𝑏
и большие 𝑏. (Эта задача приведена в главе
1
.) Теперь осталось отсор- тировать первую и третью части: это делается тем же способом. Время работы этого алгоритма | случайная величина; можно доказать, что в среднем он работает не больше 𝐶𝑛 log 𝑛. На практике | он один из самых быстрых. (Мы ещё вернёмся к нему, приведя его рекурсивную и нерекурсивную реализации.)
Наконец, отметим, что сортировка за время порядка 𝐶𝑛 log 𝑛 мо- жет быть выполнена с помощью техники сбалансированных деревьев
(см. главу
14
), однако программы тут сложнее и константа 𝐶 довольно велика.
4.3. Применения сортировки
4.3.1. Найдите количество различных чисел среди элементов дан- ного массива. Число действий порядка 𝑛 log 𝑛. (Эта задача уже была в главе
1
.)
Решение. Отсортируйте числа, а затем посчитайте количество раз- личных, просматривая элементы массива по порядку.

4.3.2. Дано n отрезков [a[i], b[i]] на прямой (i = 1 . . . n). Найди- те максимальное k, для которого существует точка прямой, покрытая k отрезками («максимальное число слоёв»). Число действий | порядка n log n.
Решение. Упорядочим все левые и правые концы отрезков вместе
(при этом левый конец считается меньше правого конца, расположен- ного в той же точке прямой). Далее двигаемся слева направо, считая число слоёв. Встреченный левый конец увеличивает число слоёв на 1,
правый | уменьшает. Отметим, что примыкающие друг к другу от- резки обрабатываются правильно: сначала идёт левый конец (правого отрезка), а затем | правый (левого отрезка).

4.3.3. Дано 𝑛 точек на плоскости. Укажите (𝑛 − 1)-звенную неса- мопересекающуюся незамкнутую ломаную, проходящую через все эти

4.3. Применения сортировки
81
точки. (Соседним отрезкам ломаной разрешается лежать на одной пря- мой.) Число действий порядка 𝑛 log 𝑛.
Решение. Упорядочим точки по 𝑥-координате, а при равных 𝑥-ко- ординатах | по 𝑦-координате. В таком порядке и можно проводить ломаную.

4.3.4. Та же задача, если ломаная должна быть замкнутой.
Решение. Возьмём самую левую точку (то есть точку с наименьшей
𝑥-координатой) и проведём из неё лучи во все остальные точки. Теперь упорядочим эти лучи снизу вверх, а точки на одном луче упорядочим по расстоянию от начала луча (это делается для всех лучей, кроме нижнего и верхнего). Ломаная выходит из выбранной (самой левой) точки по нижнему лучу, затем по всем остальным лучам (в описанном порядке)
и возвращается по верхнему лучу.

4.3.5. Дано 𝑛 точек на плоскости. Постройте их выпуклую оболоч- ку | минимальную выпуклую фигуру, их содержащую. (Резиновое ко- лечко, натянутое на вбитые в доску гвозди | их выпуклая оболочка.)
Число операций порядка 𝑛 log 𝑛.
[Указание. Упорядочим точки | годится любой из порядков, ис- пользованных в двух предыдущих задачах. Затем, рассматривая точ- ки по очереди, будем строить выпуклую оболочку уже рассмотрен- ных точек. (Для хранения выпуклой оболочки полезно использовать дек, см. главу
6
. Впрочем, при упорядочении точек по углам это из- лишне.)]

4.3.6. На прямой дано 𝑛 точек. Найдите минимальное число отрез- ков длины 1, которые покрывают все эти точки. Число операций по- рядка 𝑛 log 𝑛.
[Указание. Упорядочим все точки; один из отрезков должен покры- вать последнюю 𝑥[𝑛], поскольку справа ничего нет, его правый конец можно считать равным 𝑥[𝑛], и задача сводится к меньшему числу точек
(выбросим те, которые покрыты). ]

4.3.7. На прямой дано n отрезков [a[i], b[i]] (i = 1, . . . , n). Какое наибольшее число непересекающихся (и не имеющих общих концов) от- резков можно выбрать среди них? Число операций порядка 𝑛 log 𝑛.
[Указание. Можно упорядочить правые концы отрезков и рассмо- треть два случая: последний отрезок выбран или нет.]


82 4. Сортировка
4.4. Нижние оценки для числа сравнений при сортировке
Пусть имеется 𝑛 различных по весу камней и весы, которые по- зволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем до- ступ к функции тяжелее(i,j:1..n):boolean.) Надо упорядочить кам- ни по весу, сделав как можно меньше взвешиваний (вызовов функции тяжелее).
Разумеется, число взвешиваний зависит не только от выбранного нами алгоритма, но и от того, как оказались расположены камни. Слож- ностью алгоритма назовём число взвешиваний при наихудшем распо- ложении камней.
4.4.1. Докажите, что сложность произвольного алгоритма сорти- ровки 𝑛 камней не меньше log
2
𝑛! (где 𝑛! = 1 · 2 · . . . · 𝑛).
Решение. Пусть имеется алгоритм сложности не более 𝑑. Для каждо- го из 𝑛! возможных расположений камней запротоколируем результа- ты взвешиваний (обращений к функции тяжелее); их можно записать в виде последовательности из не более чем 𝑑 нулей и единиц. Для еди- нообразия дополним последовательность нулями, чтобы её длина стала равной 𝑑. Тем самым у нас имеется 𝑛! последовательностей из 𝑑 нулей и единиц. Все эти последовательности разные | иначе наш алгоритм дал бы одинаковые ответы для разных порядков (и один из ответов был бы неправильным). Получаем, что 2
𝑑
> 𝑛! | что и требовалось доказать.

Другой способ объяснить то же самое | рассмотреть дерево вари- антов, возникающее в ходе выполнения алгоритма, и сослаться на то,
что дерево высоты 𝑑 не может иметь более 2
𝑑
листьев.
Несложно заметить, что log
2
𝑛! > 𝑐𝑛 log 𝑛 при подходящем 𝑐 > 0, по- скольку в сумме log 𝑛! = log 1 + log 2 + log 3 + . . . + log 𝑛
вторая половина слагаемых не меньше log
2
(𝑛/2) = log
2
𝑛 − 1 каждое.
Тем самым любой алгоритм сортировки, использующий только срав- нения элементов массива и их перестановки, требует не менее 𝑐𝑛 log 𝑛
действий, так что наши алгоритмы близки к оптимальным. Однако ал- горитм сортировки, использующий другие операции, может действо- вать и быстрее. Вот один из примеров.

4.4. Нижние оценки для числа сравнений при сортировке
83 4.4.2. Имеется массив целых чисел a[1] . . . a[n], причём все числа неотрицательны и не превосходят m. Отсортируйте этот массив; число действий порядка m + n.
Решение. Для каждого числа от 0 до m подсчитываем, сколько раз оно встречается в массиве. После этого исходный массив можно сте- реть и заполнить заново в порядке возрастания, используя сведения о кратности каждого числа.

Отметим, что этот алгоритм не переставляет числа в массиве, как большинство других, а «записывает их туда заново».
Есть также метод сортировки, в котором последовательно прово- дится ряд «частичных сортировок» по отдельным битам. Начнём с та- кой задачи.
4.4.3. В массиве a[1] . . . a[n] целых чисел переставьте элементы так, чтобы чётные числа шли перед нечётными (не меняя взаимный порядок в каждой из групп).
Решение. Сначала спишем (во вспомогательный массив) все чётные,
а потом | все нечётные.

4.4.4. Имеется массив из 𝑛 чисел от 0 до 2
𝑘
−
1, каждое из кото- рых мы будем рассматривать как 𝑘-битовое слово из нулей и единиц.
Используя проверки «𝑖-й бит равен 0» и «𝑖-й бит равен 1» вместо срав- нений, отсортируйте все числа за время порядка 𝑛𝑘.
Решение. Отсортируем числа по последнему биту (см. предыдущую задачу), затем по предпоследнему и так далее. В результате они будут отсортированы. В самом деле, индукцией по 𝑖 легко доказать, что после
𝑖 шагов любые два числа, отличающиеся только в 𝑖 последних битах,
идут в правильном порядке. (Вариант: после 𝑖 шагов 𝑖-битовые концы чисел идут в правильном порядке.)

Аналогичный алгоритм может быть применён для 𝑚-ичной системы счисления вместо двоичной. При этом полезна такая вспомогательная задача:
4.4.5. Даны 𝑛 чисел и функция 𝑓, принимающая (на них) значения
1 . . . 𝑚. Требуется переставить числа в таком порядке, чтобы значения функции 𝑓 не убывали (сохраняя порядок для чисел с равными значе- ниями 𝑓). Число действий порядка 𝑚 + 𝑛.
[Указание. Завести 𝑚 списков суммарной длины 𝑛 (как это сделать,
см. в главе
6
о типах данных) и помещать в 𝑖-й список числа, для кото- рых значение функции 𝑓 равно 𝑖. Вариант: посчитать для всех 𝑖, сколько

84 4. Сортировка имеется чисел 𝑥 с 𝑓(𝑥) = 𝑖, после чего легко определить, с какого места нужно начинать размещать числа 𝑥 с 𝑓(𝑥) = 𝑖.]

4.4.6. Даны 𝑛 целых чисел в диапазоне от 1 до 𝑛
2