3.1.1. Перечислить все способы расстановки n ферзей на
шахматной доске , при которых они не бьют друг друга.
Среди позиций этого дерева нам надо отобрать те n -позиции, в которых ферзи не бьют друг друга. Программа будет << обходить дерево>> и искать их. Чтобы не делать лишней работы, заметим вот что: если в какой-то k -позиции ферзи бьют друг друга, то ставить дальнейших ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в этом направлении.
Точнее, назовем k -позицию допустимой, если после удаления верхнего ферзя оставшиеся не бьют друг друга. Наша программа будет рассматривать только допустимые позиции.
Разобьем задачу на две части: (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 не меняется, что невозможно.
3.1.4. Решить задачу об обходе дерева, если мы хотим, чтобы
обрабатывались все вершины (не только листья).
(а) быть частью пути из корня в 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-ой горизонтали; при значение 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_down := (k > 0); | end; | | procedure up; {вверх_налево} | begin {k < n, not danger} | | 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;`
0есть_сверху 1есть_сверху
3.1.7. Приведенная программа тратит довольно много времени на
выполнение проверки 0 (проверка,
находится ли верхний ферзь под боем, требует числа действий
порядка n). Изменить реализацию операций с деревом позиций
так, чтобы все три проверки
1/справа/снизу и
соответствующие команды требовали бы количества действий,
ограниченного не зависящей от n константой.