67459

Условная компиляция

Лекция

Информатика, кибернетика и программирование

Не ставить коня на заблокированное поле при каждом ходе, кроме последнего (64-го). Заблокированным называется поле, на которое конь, казалось бы, может встать, но выйти из него не сможет, поскольку все возможные для последующего хода поля уже посещены.

Русский

2014-09-10

51 KB

0 чел.

Лекция 7

Условная компиляция

{$define <Имя режима>}  // Режим “<Имя режима>” включен

{$undef <Имя режима>}   // Режим “<Имя режима>” выключен

{$ifdef <Имя режима>}

  <Фрагмент кода 1>  

// Выполняется только если режим “<Имя режима>” включен

{$else}

  <Фрагмент кода 2>

// Выполняется только если режим “<Имя режима>” выключен

{$endif}

{$ifndef <Имя режима>}

  <Фрагмент кода 2>

// Выполняется только если режим “<Имя режима>” выключен

{$else}

  <Фрагмент кода 1>

// Выполняется только если режим “<Имя режима>” включен

{$endif}

Пример применения условной компиляции приведен в проекте, реализующем поиск оптимального пути по элементам матрицы (архив OptPathRD.arj).
Рекурсивные алгоритмы (продолжение)

Пример. Задача о ходе коня.

Требуется организовать обход конём всех полей шахматной доски (), начиная с заданного поля. Каждое поле конь должен посетить только один раз. Постановка на первое заданное поле, для удобства, считается первым ходом.

Существует два эвристических принципа выбора очередного хода коня.

1. Не ставить коня на заблокированное поле при каждом ходе, кроме последнего (64-го). Заблокированным называется поле, на которое конь, казалось бы, может встать, но выйти из него не сможет, поскольку все возможные для последующего хода поля уже посещены.

2. Критерий Варнсдорфа. Из всех полей, на которые конь может перейти из текущего поля, следует выбирать то, из которого есть наименьшее количество вариантов последующего хода. Это количество положительно, поскольку постановка коня на заблокированное поле исключена. Если полей с одинаковыми наименьшими количествами последующих ходов несколько, следует испытать каждое из них. Если испытать только одно, «любое» поле (как рекомендовал Варнсдорф), есть опасность зайти в тупик (найдены примеры). Действенность критерия Варнсдорфа строго не доказана, но проверена на практике.

Замкнутым называется маршрут, при котором последнее, 64-е посещенное поле находится в одном ходе коня от начального поля маршрута. Количество всех замкнутых маршрутов коня без учёта направления обхода равно 13267364410532 (количество замкнутых маршрутов с учётом направления в два раза больше). В то же время задача подсчёта всех возможных незамкнутых маршрутов значительно сложнее и не решена до сих пор. Известно, что количество незамкнутых маршрутов не превышает числа сочетаний .

Реализация решения поставленной задачи содержится в проекте KnightTurns (архив KnightTurns.rar).

В основе проекта лежит процедура

NextTurn(iRow, iCol, iNumber: integer),

которая вызывается рекурсивно. iRow, iCol – координаты поля, на которое ставится конь при совершении хода с номером iNumber.

Пример. Найти наиболее «дешевый» путь от элемента  матрицы  размера   до элемента . Все элементы матрицы неотрицательны. В отличие от предыдущей постановки родственной задачи, в данном случае разрешено на каждом шаге двигаться и вправо, и вниз, и влево, и вверх. Таким образом, оптимальный путь может иметь вид «змейки». На рисунке этот путь проложен по единичкам.

Метод динамического программирования к этой задаче неприменим.

Приходится вернуться к рекурсивной функции

function BestPathRecoursive(i, j: integer): integer;

Каждый следующий экземпляр функции совершает ход на элемент с координатами (i, j), а затем пытается выбрать направление для очередного хода по элементам матрицы. Поскольку возможных направлений дальнейшего движения может быть до четырёх, приходится выбирать из них одно, лучшее, самое дешевое.

В функции BestPathRecoursive предусмотрено недопущение циклических путей. Действительно, оптимальный путь не может содержать цикла (петли), так как устранение петли из пути как минимум укорачивает путь, как максимум, удешевляет его (если петлевой участок проходит через положительные элементы матрицы).

Проект, реализующий решение поставленной задачи, содержится в архиве OptPatrRDLU.arj.


 

А также другие работы, которые могут Вас заинтересовать

23070. Поняття, предмет та структура національної безпеки 36.5 KB
  ТЕМА: Безпека як суспільна цінність. Законність своєї держави визначається не лише станом війни або миру є ще пріоритетний стан безпека чітко окреслений стан суспільства США. Національна безпека стан захищеності життєво важливих інтересів особи нації суспільства і держави від внутрішніх та зовнішніх загроз. В Україні основним органом забезпечення національної безпеки є СБУ громадянська безпека забезпечення виконання і дотримання положень конституції.
23071. Сфери національних інтересів України 62.5 KB
  Сфери національних інтересів України. Конспект вельмишановного Пана Перепелиці каже про національні інтереси України ніхера тому все що є в конспекті по національним інтересам дивіться в 3 питанні національні інтереси життєво важливі матеріальні інтелектуальні і духовні цінності Українського народу як носія суверенітету і єдиного джерела влади в Україні визначальні потреби суспільства і держави реалізація яких гарантує державний суверенітет України та її прогресивний розвиток; Стаття 6. Пріоритети національних інтересів Пріоритетами...
23072. Поняття національного інтересу 40 KB
  Сфери національних інтересів України. Формується з інтересів кожної конкретної особистості кожного соціального прошарку. Завдання еліти продукування інтересів в суспільство. Еліта має мобілізувати націю на реалізацію національних інтересів.
23073. Поняття загроза та небезпека національним інтересам України. Види загроз національній безпеці України 38.5 KB
  ТЕМА: Загрози національній безпеці. Потенційні загрози це становище при якому існують певні зазіхання але при цьому відсутні умови при яких вони переходять в намагання завдати шкоду національним інтересам України. Вимоги до органів мають упереджувати загрози: ефективно виявляти загрози та ефективно на них реагувати; адекватно реагувати на виникнення загрози; Методика: визначення чинників що спричиняють загрозу національним інтересам України; класифікувати загрози звідкіля виходять і в якій сфері знаходяться: політика економіка...
23074. Суб`єкти національної безпеки 37.5 KB
  Суб`єкти національної безпеки З конспекту. ТЕМА: Система національної безпеки України. Суб`єкти національної безпеки. Вимоги до системи національної безпеки.
23075. Вимоги до системи національної безпеки 33 KB
  Вимоги до системи національної безпеки З конспекту Кожна країна створює певну систему органів які могли б реагувати на загрози така система називається системою національної безпеки. Система забезпечення національно міжнародної безпеки включає певну діяльність органів по підтримці стану захищеності. Наявність механізмів які забезпечують стан безпеки. Система національної безпеки наявність певних органів тільки обмежена територією певної країни.
23076. Роль та повноваження органів спеціальної компетенції в системі забезпечення національної безпеки України 69.5 KB
  Роль та повноваження органів спеціальної компетенції в системі забезпечення національної безпеки України. Національний банк України відповідно до основних засад грошовокредитної політики визначає та проводить грошовокредитну політику в інтересах національної безпеки України; міністерства Служба безпеки України та інші центральні органи виконавчої влади в межах своїх повноважень забезпечують виконання передбачених Конституцією і законами України актами Президента України Кабінету Міністрів України завдань здійснюють...
23077. Вимірювання напруг при механічних деформаціях поляризаційним методом 447 KB
  Різницю фаз Δ що виникає між двома взаємно перпендикулярними лінійнополяризованими хвилями визначають за формулою 16 де λ довжина хвилі; σ1 σ2 головні нормальні напруги; d товщина деталі; с стала фотопружності яка залежить від матеріалу деталі. Таким чином при постійній товщині зразка лінії однакового зсуву фаз відповідають лініям однакових різниць нормальних напруг або лініям рівних максимальних дотичних напруг оскільки максимальна дотична напруга τmax пов'язана з...
23078. Дослідження анізотропних кристалів під поляризаційним мікроскопом 458 KB
  Прилади: поляризаційний мікроскоп клин або компенсатор Берека набір шліфів і пластинок з одновісних та двовісних кристалів вирізаних під різними кутами до оптичної осі. Різниця яку вносить пластинка залежить від її товщини матеріалу зразка та орієнтації оптичної осі відносно зрізу. Форма і розміщення ізохромат залежать від напряму оптичної осі відносно зрізу товщини зразка і довжини хвилі Форма і розміщення ізогір залежать від орієнтації осі відносно зрізу і взаємного положення поляризатора та аналізатора. Для пластинки вирізаної...