с вершинами в этих точках.
2.6.4. Перечислить все способы разрезать n-угольник на тре-
угольники, проведя n - 2 его диагонали.
Еще один класс задач на перечисление всех элементов задан-
ного множества мы рассмотрим ниже, обсуждая метод поиска с
возвратами (backtracking).
2.7. Подсчет количеств.
Иногда можно найти количество объектов с тем или иным
свойством, не перечисляя их. Классический пример: C(n,k) - число
всех k-элементных подмножеств n-элементного множества - можно
найти, заполняя таблицу значений функции С по формулам:
C (n,0) = C (n,n) = 1 (n >= 1)
C (n,k) = C (n-1,k-1) + C (n-1,k) (n > 1, 0 < k < n);
или по формуле n!/((k!)*(n-k)!). (Первый способ эффективнее, ес-
ли надо вычислить много значений С(n,k).)
Приведем другие примеры.
2.7.1 (Число разбиений). (Предлагалась на всесоюзной олим-
пиаде по программированию 1988 года.) Пусть P(n) - число разби-
ений целого положительного n на целые положительные слагаемые
(без учета порядка, 1+2 и 2+1 - одно и то же разбиение). При n=0
положим P(n) = 1 (единственное разбиение не содержит слагаемых).
Построить алгоритм вычисления P(n) для заданного n.
Решение. Можно доказать (это нетривиально) такую формулу
для P(n):
P(n) = P(n-1)+P(n-2)-P(n-5)-P(n-7)+P(n-12)+P(n-15) +...
(знаки у пар членов чередуются, вычитаемые в одной паре равны
(3*q*q-q)/2 и (3*q*q+q)/2).
Однако и без ее использования можно придумать способ вычис-
ления P(n), который существенно эффективнее перебора и подсчета
всех разбиений.
Обозначим через R(n,k) (при n >= 0, k >= 0) число разбиений
n на целые положительные слагаемые, не превосходящие k. (При
этом R(0,k) считаем равным 1 для всех k >= 0.) Очевидно, P(n) =
R(n,n). Все разбиения n на слагаемые, не превосходящие k, ра-
зобьем на группы в зависимости от максимального слагаемого
(обозначим его i). Число R(n,k) равно сумме (по всем i от 1 до
k) количеств разбиений со слагаемыми не больше k и максимальным
слагаемым, равным i. А разбиения n на слагаемые не более k с
первым слагаемым, равным i, по существу представляют собой раз-
биения n - i на слагаемые, не превосходящие i (при i <= k). Так
что
R(n,k) = сумма по i от 1 до k чисел R(n-i,i) при k <= n;
R(n,k) = R(n,n) при k >= n,
что позволяет заполнять таблицу значений функции R.
2.7.2 (Счастливые билеты). (Задача предлагалась на Всесоюз-
ной олимпиаде по программированию 1989 года). Последовательность
из 2n цифр (каждая цифра от 0 до 9) называется счастливым биле-
том, если сумма первых n цифр равна сумме последних n цифр. Най-
ти число счастливых последовательностей данной длины.
Решение. (Сообщено одним из участников олимпиады; к сожале-
нию, не могу указать фамилию, так как работы проверялись зашиф-
рованными.) Рассмотрим более общую задачу: найти число последо-
вательностей, где разница между суммой первых n цифр и суммой
последних n цифр равна k (k = -9n,..., 9n). Пусть T(n, k) - чис-
ло таких последовательностей.
Разобьем множество таких последовательностей на классы в
зависимости от разницы между первой и последней цифрами. Если
эта разница равна t, то разница между суммами групп из оставших-
ся n-1 цифр равна k-t. Учитывая, что пар цифр с разностью t бы-
вает 10 - (модуль t), получаем формулу
T(n,k) = сумма по t от -9 до 9 чисел (10-|t|) * T(n-1, k-t).
(Некоторые слагаемые могут отсутствовать, так как k-t может быть
слишком велико.)
Глава 3. Обход дерева. Перебор с возвратами.
3.1. Ферзи, не бьющие друг друга: обход дерева позиций
В предыдущей главе мы рассматривали несколько задач одного
и того же типа: "перечислить все элементы некоторого множества
A". Схема решения была такова: на множестве A вводился порядок и
описывалась процедура перехода от произвольного элемента мно-
жества A к следующему за ним (в этом порядке). Такую схему не
всегда удается реализовать непосредственно, и в этой главе мы
рассмотрим другой полезный прием перечисления всех элементов не-
которого множества. Его называют "поиск с возвратами", "метод
ветвей и границ", "backtracking". На наш взгляд наиболее точное
название этого метода - обход дерева.
3.1.1. Перечислить все способы расстановки n ферзей на шах-
матной доске n на n, при которых они не бьют друг друга.
Решение. Очевидно, на каждой из n горизонталей должно сто-
ять по ферзю. Будем называть k-позицией (для k = 0, 1,...,n)
произвольную расстановку k ферзей на k нижних горизонталях (фер-
зи могут бить друг друга). Нарисуем "дерево позиций": его корнем
будет единственная 0-позиция, а из каждой k-позиции выходит n
стрелок вверх в (k+1)-позиции. Эти n позиций отличаются положе-
нием ферзя на (k+1)-ой горизонтали. Будем считать, что располо-
жение их на рисунке соответствует положению этого ферзя: левее
та позиция, в которой ферзь расположен левее.
Дерево позиций для
n = 2
Среди позиций этого дерева нам надо отобрать те n-позиции, в ко-
торых ферзи не бьют друг друга. Программа будет "обходить дере-
во" и искать их. Чтобы не делать лишней работы, заметим вот что:
если в какой-то k-позиции ферзи бьют друг друга, то ставить
дальнейших ферзей смысла нет. Поэтому, обнаружив это, мы будем
прекращать построение дерева в этом направлении.
Точнее, назовем k-позицию допустимой, если после удаления
верхнего ферзя оставшиеся не бьют друг друга. Наша программа бу-
дет рассматривать только допустимые позиции.
Дерево допустимых
позиций для n = 3
Разобьем задачу на две части: (1) обход произвольного дере-
ва и (2) реализацию дерева допустимых позиций.
Сформулируем задачу обхода произвольного дерева. Будем счи-
тать, что у нас имеется Робот, который в каждый момент находится
в одной из вершин дерева (вершины изображены на рисунке кружоч-
ками). Он умеет выполнять команды:
вверх_налево (идти по самой левой
из выходящих вверх стрелок)
вправо (перейти в соседнюю справа
вершину)
вниз (спуститься вниз на один уро-
вень)
вверх_налево
вправо
вниз
и проверки, соответствующие возможности выполнить каждую из ко-
манд, называемые "есть_сверху", "есть_справа", "есть_снизу"
(последняя истинна всюду, кроме корня). Обратите внимание, что
команда "вправо" позволяет перейти лишь к "родному брату", но не
к "двоюродному".
Так команда "вправо"
НЕ действует!
Будем считать, что у Робота есть команда "обработать" и что
его задача - обработать все листья (вершины, из которых нет
стрелок вверх, то есть где условие "есть_сверху" ложно). Для на-
шей шахматной задачи команде обработать будет соответствовать
проверка и печать позиции ферзей.
Доказательство правильности приводимой далее программы ис-
пользует такие определения. Пусть фиксировано положение Робота в
одной из вершин дерева. Тогда все листья дерева разбиваются на
три категории: над Роботом, левее Робота и правее Робота. (Путь
из корня в лист может проходить через вершину с Роботом, свора-
чивать влево, не доходя до нее и сворачивать вправо, не доходя
до нее.) Через (ОЛ) обозначим условие "обработаны все листья ле-
вее Робота", а через (ОЛН) - условие "обработаны все листья ле-
вее и над Роботом".
Нам понадобится такая процедура:
procedure вверх_до_упора_и_обработать
| {дано: (ОЛ), надо: (ОЛН)}
begin
| {инвариант: ОЛ}
| while есть_сверху do begin
| | вверх_налево
| end
| {ОЛ, Робот в листе}
| обработать;
| {ОЛН}
end;
Основной алгоритм:
дано: Робот в корне, листья не обработаны
надо: Робот в корне, листья обработаны
{ОЛ}
вверх_до_упора_и_обработать
{инвариант: ОЛН}
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;
Решение. Инвариант цикла:
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. Приведенная только что программа обрабатывает верши-
ну до того, как обработан любой из ее потомков. Как изменить ее,
чтобы каждая вершина, не являющаяся листом, обрабатывалась дваж-
ды: один раз до, а другой раз после всех своих потомков? (Листья
