Помощь школьнику

МАТЕМАТИЧНА ЛОГІКА Й ТЕОРІЯ АЛГОРИТМІВ

Очевидно, на кожній з 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 обробити


Смотрите также:




Категории: Сочинения на свободную тему

Комментарии: 0

Комментарии закрыты.