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

Державного комітету Російської Федерації за найвищим і среднеспециальному образованию.

Красноярський Державний Технічний Университет.

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

по курсу.

Математична і теорія алгоритмов.

Виконав студент грн. ВТ27−4.

Попов А.В.

Проверила:

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

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 (число ферзів) і масиву з: array [1.n] of 1. n (з [і] - координати ферзя на i-ой горизонталі; при і > k значення з [і] ролі не грає). Передбачається, що це позиції припустимі (якщо прибрати верхнього ферзя, інші не б’ють друг друга).

program queens; const n = …; var k: 0. n; з: array [1.n] of 1. n;

procedure begin_work; {розпочати роботу} begin k := 0; end;

function danger: boolean; {верхній ферзь під боєм} var b: boolean; і: 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; з [k] := 1; end;

procedure right; {вправо} begin {k > 0, c[k] < n} з [k] := з [k] + 1; end;

procedure down; {вниз} begin {k > 0} k := k — 1; end;

procedure work; {обробити} var і: integer; begin if (k = n) and not danger then begin for і := 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 |55 987 |960 800 | |У вершин побудованого дерева. |2 |3 |4 |17 |54 |153 |552 | |Час построения (сек) |.