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

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

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

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

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

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

{ОНЛН} end;

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

дано: Робот в корне, ничего не обработано надо: Робот в корне, все вершины обработаны

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

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

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

Приведенная только что программа обрабатывает вершину до того, как обработан любой из ее потомков. Теперь изменим ее, чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды: один раз до, а другой раз после всех своих потомков. Листья по-прежнему обрабатываются по разу:

Под "обработано ниже и левее" будем понимать "ниже обработано по разу, слева обработано полностью (листья по разу, остальные по два)". Под
"обработано ниже, левее и над" будем понимать "ниже обработано по разу, левее и над - полностью".

Программа будет такой:

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

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

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

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

{ОНЛН} end;

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

дано: Робот в корне, ничего не обработано надо: Робот в корне, все вершины обработаны

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

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

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

Доказательство правильности алгоритма.

Докажем, что приведенная программа завершает работу (на любом конечном дереве).
Доказательство. Процедура вверх_налево завершает работу (высота Робота не может увеличиваться бесконечно). Если программа работает бесконечно, то, поскольку листья не обрабатываются повторно, начиная с некоторого момента ни один лист не обрабатывается. А это возможно, только если Робот все время спускается вниз. Противоречие.

Поделитесь этой записью или добавьте в закладки