Государственный комитет Российской Федерации
по высшему и среднеспециальному образованию
Красноярский Государственный Технический Университет
Курсовая работа
по курсу
Математическая логика и теория алгоритмов
Выполнил студент гр. ВТ27-4
Попов А.В.
Проверила:
Пестунова Т.М.
1998
Содержание.
Постановка задачи (стр.3).
Построение модели (стр.3).
Описание алгоритма (стр.4).
Доказательство правильности алгоритма (стр.7).
Блок-схема алгоритма (стр.8).
Описание переменных и программа (стр.9).
Расчёт вычислительной сложности (стр.11).
Тестирование (стр.11).
Список литературы (стр.12).
Постановка задачи.
Перечислить все способы расстановки n ферзей на шахматной доске n на n,
при которых они не бьют друг друга.
Построение модели.
Очевидно, на каждой из n горизонталей должно стоять по ферзю. Будем
называть k-позицией (для k = 0, 1,…,n) произвольную расстановку k
ферзей на k нижних горизонталях (ферзи могут бить друг друга). Нарисуем
“дерево позиций”: его корнем будет единственная 0-позиция, а из каждой
k-позиции выходит n стрелок вверх в (k+1)-позиции. Эти n позиций
отличаются положением ферзя на (k+1)-ой горизонтали. Будем считать, что
расположение их на рисунке соответствует положению этого ферзя: левее та
позиция, в которой ферзь расположен левее.
Дерево позиций для n = 2
Данное дерево представлено только для наглядности и простоты
представления для n=2.
Среди позиций этого дерева нам надо отобрать те n-позиции, в которых
ферзи не бьют друг друга. Программа будет “обходить дерево” и искать
их. Чтобы не делать лишней работы, заметим вот что: если в какой-то
k-позиции ферзи бьют друг друга, то ставить дальнейших ферзей смысла
нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в
этом направлении.
Точнее, назовем k-позицию допустимой, если после удаления верхнего ферзя
оставшиеся не бьют друг друга. Наша программа будет рассматривать только
допустимые позиции.
Описание алгоритма.
Разобьем задачу на две части: (1) обход произвольного дерева и (2)
реализацию дерева допустимых позиций.
Сформулируем задачу обхода произвольного дерева. Будем считать, что у
нас имеется Робот, который в каждый момент находится в одной из вершин
дерева. Он умеет выполнять команды:
вверх_налево (идти по самой левой из выходящих вверх стрелок)
вправо (перейти в соседнюю справа вершину)
вниз (спуститься вниз на один уровень)
вверх_налево
вправо
вниз
и проверки, соответствующие возможности выполнить каждую из команд,
называемые “есть_сверху”, “есть_справа”, “есть_снизу” (последняя истинна
всюду, кроме корня). Обратите внимание, что команда “вправо” позволяет
перейти лишь к “родному брату”, но не к “двоюродному”.
Будем считать, что у Робота есть команда “обработать” и что его задача –
обработать все листья (вершины, из которых нет стрелок вверх, то есть
где условие “есть_сверху” ложно). Для нашей шахматной задачи команде
обработать будет соответствовать проверка и печать позиции ферзей.
Доказательство правильности приводимой далее программы использует такие
определения. Пусть фиксировано положение Робота в одной из вершин
дерева. Тогда все листья дерева разбиваются на три категории: над
Роботом, левее Робота и правее Робота. (Путь из корня в лист может
проходить через вершину с Роботом, сворачивать влево, не доходя до нее
и сворачивать вправо, не доходя до нее.) Через (ОЛ) обозначим условие
“обработаны все листья левее Робота”, а через (ОЛН) – условие
“обработаны все листья левее и над Роботом”.
Нам понадобится такая процедура:
procedure вверх_до_упора_и_обработать
{дано: (ОЛ), надо: (ОЛН)}
begin
{инвариант: ОЛ}
while есть_сверху do begin
вверх_налево
end
{ОЛ, Робот в листе}
обработать;
{ОЛН}
end;
Основной алгоритм:
дано: Робот в корне, листья не обработаны
надо: Робот в корне, листья обработаны
{ОЛ}
вверх_до_упора_и_обработать
{инвариант: ОЛН}
while есть_снизу do begin
if есть_справа then begin {ОЛН, есть справа}
вправо;
{ОЛ}
вверх_до_упора_и_обработать;
end else begin
{ОЛН, не есть_справа, есть_снизу}
вниз;
end;
end;
{ОЛН, Робот в корне => все листья обработаны}
Осталось воспользоваться следующими свойствами команд Робота (сверху
записаны условия, в которых выполняется команда, снизу – утверждения о
результате ее выполнения):
{ОЛ, не есть_сверху} обработать {ОЛН}
{ОЛ} вверх_налево {ОЛ}
{есть_справа, ОЛН} вправо {ОЛ}
{не есть_справа, ОЛН} вниз{ОЛН}
Теперь решим задачу об обходе дерева, если мы хотим, чтобы
обрабатывались все вершины (не только листья).
Решение. Пусть 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;
{ОНЛН, Робот в корне => все вершины обработаны}
Приведенная только что программа обрабатывает вершину до того, как
обработан любой из ее потомков. Теперь изменим ее, чтобы каждая вершина,
не являющаяся листом, обрабатывалась дважды: один раз до, а другой раз
после всех своих потомков. Листья по-прежнему обрабатываются по разу:
Под “обработано ниже и левее” будем понимать “ниже обработано по разу,
слева обработано полностью (листья по разу, останые по два)”. Под
“обработано ниже, левее и над” будем понимать “ниже обработано по разу,
левее и над – полностью”.
Программа будет такой:
procedure вверх_до_упора_и_обработать
{дано: (ОНЛ), надо: (ОНЛН)}
begin
{инвариант: ОНЛ}
while есть_сверху do begin
обработать
вверх_налево
end
{ОНЛ, Робот в листе}
обработать;
{ОНЛН}
end;
Основной алгоритм:
дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать
{инвариант: ОНЛН}
while есть_снизу do begin
if есть_справа then begin {ОНЛН, есть справа}
вправо;
{ОНЛ}
вверх_до_упора_и_обработать;
end else begin
{ОЛН, не есть_справа, есть_снизу}
вниз;
обработать;
end;
end;
{ОНЛН, Робот в корне => все вершины обработаны полностью}
Доказательство правильности алгоритма.
Докажем, что приведенная программа завершает работу (на любом конечном
дереве).
Доказательство. Процедура вверх_налево завершает работу (высота Робота
не может увеличиваться бесконечно). Если программа работает бесконечно,
то, поскольку листья не обрабатываются повторно, начиная с некоторого
момента ни один лист не обрабатывается. А это возможно, только если
Робот все время спускается вниз. Противоречие.
Блок-схема алгоритма.
Описание переменных и программа.
Теперь реализуем операции с деревом позиций. Позицию будем представлять
с помощью переменной 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;
procedure begin_work; {начать работу}
begin
k := 0;
end;
function danger: boolean; {верхний ферзь под боем}
var b: boolean;
i: integer;
begin
if k верхний ферзь под боем ферзей с номерами 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 0) and (c[k] 0);
end;
procedure up; {вверх_налево}
begin {k 0, c[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 (‘ ‘);
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.
Расчёт вычислительной сложности.
Емкостная сложность:
Возьмём любую доску размерности n, и расставим на ней n ферзей по одной
из главных диагоналей, таким образом мы получим такую расстановку, при
которой на каждой вертикали и горизонтали стоит по одному ферзю. Тогда
емкостная сложность будет равна количеству перестановок из n чисел (в
нашем случае вертикалей, или горизонталей), т. е. (n!).
Временная сложность:
Если рассматривать обработку каждого листа, без проверки на пути к нему,
то временная сложность T(n) = nn. Но так как проверка идет на каждой
вершине, то T(n) уменьшается в n раз, т.е. T(n)=nn-1.
Тестирование.
Построенная по описанному алгоритму программа при различных n выдаёт
следующие данные:
n=4
т.е. количество расстановак равно 2. Ниже приведена таблица зависимости
от n количества решений (С).
n = 1 2 3 4 5 6 7 8 9 10 11 12 13
С= 1 0 0 2 10 4 40 92 352 724 2680 14200 8176
Список литературы.
Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера.
– М.: Энергоатомиздат, 1988.
Евстигнеев В.А. Применение теории графов в программировании. – М.:Наука,
1984.
Основной алгоритм находился на BBS “Master of Univercity” в файле
shen.rar (тел. 43-27-03; время работы 21.00 – 7.00; FTN адрес –
2:5090/58).
PAGE 1
PAGE 12
Нашли опечатку? Выделите и нажмите CTRL+Enter
