Нахождение всіх комбінацій розстановки n ферзів на дошці n X n
Вочевидь, з кожної з n горизонталей має стояти по ферзю. Будемо називати k-позицией (для k = 0, 1,…, n) довільну розстановку k ферзів на k нижніх горизонталях (ферзі можуть бити одне одного). Намалюємо «дерево позицій «: його коренем єдина 0-позиция, та якщо з кожної k-позиции виходить n стрілок угору меча у (k+1)-позиции. Ці n позицій відрізняються становищем ферзя на (k+1)-ой горизонталі… Читати ще >
Нахождение всіх комбінацій розстановки 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 | |Час построения (сек) |.