Описание переменных и программа.

Теперь реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной 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).