Нахождение всех комбинаций расстановки n ферзей на доске n X n

| Категория реферата: Рефераты по математике
| Теги реферата: доклад на тему, реферати українською мовою
| Добавил(а) на сайт: Grebnev.

и проверки, соответствующие возможности выполнить каждую из команд, называемые "есть_сверху", "есть_справа", "есть_снизу" (последняя истинна всюду, кроме корня). Обратите внимание, что команда "вправо" позволяет перейти лишь к "родному брату", но не к "двоюродному".

Будем считать, что у Робота есть команда "обработать" и что его задача
- обработать все листья (вершины, из которых нет стрелок вверх, то есть где условие "есть_сверху" ложно). Для нашей шахматной задачи команде обработать будет соответствовать проверка и печать позиции ферзей.

Доказательство правильности приводимой далее программы использует такие определения. Пусть фиксировано положение Робота в одной из вершин дерева.
Тогда все листья дерева разбиваются на три категории: над Роботом, левее
Робота и правее Робота. (Путь из корня в лист может проходить через вершину с Роботом, сворачивать влево, не доходя до нее и сворачивать вправо, не доходя до нее.) Через (ОЛ) обозначим условие "обработаны все листья левее
Робота", а через (ОЛН) - условие "обработаны все листья левее и над
Роботом".

Нам понадобится такая процедура:

procedure вверх_до_упора_и_обработать

{дано: (ОЛ), надо: (ОЛН)} begin

{инвариант: ОЛ} while есть_сверху do begin вверх_налево end

{ОЛ, Робот в листе} обработать;

{ОЛН} end;

Основной алгоритм:

дано: Робот в корне, листья не обработаны надо: Робот в корне, листья обработаны

{ОЛ} вверх_до_упора_и_обработать
{инвариант: ОЛН} while есть_снизу do begin if есть_справа then begin {ОЛН, есть справа} вправо;

{ОЛ} вверх_до_упора_и_обработать; end else begin

{ОЛН, не есть_справа, есть_снизу} вниз; end; end;
{ОЛН, Робот в корне => все листья обработаны}

Осталось воспользоваться следующими свойствами команд Робота (сверху записаны условия, в которых выполняется команда, снизу - утверждения о результате ее выполнения):

1) {ОЛ, не есть_сверху} обработать {ОЛН}

2) {ОЛ} вверх_налево {ОЛ}

3) {есть_справа, ОЛН} вправо {ОЛ}

4) {не есть_справа, ОЛН} вниз{ОЛН}

Теперь решим задачу об обходе дерева, если мы хотим, чтобы обрабатывались все вершины (не только листья).

Решение. Пусть x - некоторая вершина. Тогда любая вершина y относится к одной из четырех категорий. Рассмотрим путь из корня в y. Он может: а) быть частью пути из корня в x (y ниже x); б) свернуть налево с пути в x (y левее x); в) пройти через x (y над x); г) свернуть направо с пути в x (y правее x);

В частности, сама вершина x относится к категории в). Условия теперь будут такими:

(ОНЛ) обработаны все вершины ниже и левее;

(ОНЛН) обработаны все вершины ниже, левее и над.

Вот как будет выглядеть программа: