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

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

Блок-схема алгоритма.

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

Теперь реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной 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 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 (' '); 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) = n0+n1+n2+n3+…+nn .

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

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