Государственный комитет Российской Федерации

по высшему и среднеспециальному образованию

Красноярский Государственный Технический Университет

Курсовая работа

по курсу
Математическая логика и теория алгоритмов

Выполнил студент гр. ВТ27-4

Попов А.В.
Проверила:

                                                                             Пестунова Т.М.
1998



Содержание.



1.    
Постановка задачи (стр.3).

2.    
Построение модели (стр.3). 

3.    
Описание алгоритма (стр.4).

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

5.    
Блок-схема алгоритма (стр.8).

6.    
Описание переменных и программа (стр.9).

7.    
Расчёт вычислительной сложности (стр.11).

8.    
Тестирование (стр.11).

9.    
Список литературы (стр.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;

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

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

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

(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;

  {ОНЛН, Робот в корне => все вершины обработаны}


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

Под "обработано ниже и левее" будем понимать "ниже обработано по разу, слева обработано полностью (листья по  разу, остальные по два)". Под "обработано ниже, левее и над" будем понимать "ниже обработано по разу, левее и над - полностью".
Программа будет такой:
  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 <= 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_up := (k > 0);

    end;

    procedure up; {вверх_налево}

    begin {k < n}

      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.











Расчёт вычислительной сложности.

Емкостная сложность:

В программе используется одномерный массив размерности n, поэтому объём входа и объём выхода совпадают и равны n. Количество пременных равно 3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.

С(n)=n+4

Временная сложность:

Если рассматривать обработку каждого листа, без проверки на пути к нему, то временная сложность T(n) = n⁰+n¹+n²+n³+…+nⁿ .

Но в случае, когда каждая вершина проверяется, временная сложность T(n) = o(n⁰+n¹+n²+n³+…+nⁿ). И это тем вернее, чем больше n. Данный вывод получен на основе приведённых ниже статистических данных:

	1	2	3	4	5	6	7
Общее кол-во листьев	2	7	40	341	3906	55987	960800
Кол-во  вершин построенного дерева.	2	3	4	17	54	153	552
Время построения(сек)	<0.01	<0.01	<0.01	<0.01	<0.01	<0.01	<0.01

	8	9	10	11	12	13
Общее кол-во листьев
Кол-во  вершин построенного дерева.	2057	8394	35539	166926	856189	4674890
Время построения(сек)	<0.01	0.21	1.20	6.48	37.12	231.29

Тестирование.

Построенная по описанному алгоритму программа при различных n выдаёт следующие данные:

n=4

<1,2><2,4><3,1><4,3>

<1,3><2,1><3,4><4,2>

Т.е. количество расстановок равно 2. Ниже приведена таблица зависимости от n количества решений (R).

n =	1	2	3	4	5	6	7	8	9	10	11	12	13
R=	1	0	0	2	10	4	40	92	352	724	2680	14200	73712

Cписок литературы.

1)         Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.

2)         Евстигнеев В.А. Применение теории графов в программировании. – М.:Наука, 1984.

3)         Основной алгоритм находился на BBS “Master of Univercity” в файле shen.rar в файловой области “Bardak” (тел. 43-27-03; время работы 21.00 – 7.00; FTN адрес – 2:5090/58).