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.


 

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

19012. Движение в кулоновском поле притяжения (задача Кеплера). Классификация орбит при финитном и инфинитном движении 281 KB
  Лекция 10. Движение в кулоновском поле притяжения задача Кеплера. Классификация орбит при финитном и инфинитном движении В предыдущей лекции мы выяснили при каких значениях энергии движение будет инфинитным финитным а так же определили условия при которых траект
19013. Кинематика и динамика упругого столкновения частиц. Переход в Ц-систему. Импульсные диаграммы. Связь углов рассеяния в Л- и Ц-системах 1.06 MB
  Лекция 11. Кинематика и динамика упругого столкновения частиц. Переход в Цсистему. Импульсные диаграммы. Связь углов рассеяния в Л и Цсистемах Столкновение двух частиц называется упругим если оно не сопровождается изменением их внутреннего состояния в том числе не ...
19014. Дифференциальное сечение рассеяния частиц. Формула Резерфорда 2.55 MB
  Лекция 12. Дифференциальное сечение рассеяния частиц. Формула Резерфорда Для изучения характера взаимодействия частиц друг с другом обычно проводятся эксперименты по рассеянию целого пучка одинаковых частиц которые падают из бесконечности с одинаковой начальной с...
19015. Малые одномерные колебания (свободные и вынужденные). Вынужденные колебания под действием произвольной силы 2.55 MB
  Лекция 13. Малые одномерные колебания свободные и вынужденные. Вынужденные колебания под действием произвольной силы. Вынужденные колебания под действием гармонической силы. Резонанс. Затухающие колебания Распространенным движением в природе являются колебания те
19016. Малые колебания системы со многими степенями свободы. Собственные частоты и нормальные координаты 459.5 KB
  Лекция 14. Малые колебания системы со многими степенями свободы. Собственные частоты и нормальные координаты Рассмотрим случай малых колебаний системы частиц имеющей степеней свободы. Самый общий вид функции Лагранжа такой системы таков: 1 2 Устойч
19017. Уравнения Гамильтона (канонические уравнения). Функция Гамильтона. Скобки Пуассона и их свойства 750 KB
  Лекция 15. Уравнения Гамильтона канонические уравнения. Функция Гамильтона. Скобки Пуассона и их свойства Одна из форм уравнения движения это уравнения Лагранжа когда задается функция Лагранжа как функция независимых обобщенных координат и обобщенных скоростей
19018. Канонические преобразования. Производящие функции. Временная эволюция механической системы как каноническое преобразование 901 KB
  Лекция 15. Канонические преобразования. Производящие функции. Временная эволюция механической системы как каноническое преобразование Выбор обобщенных координат не ограничен никакими условиями ими могут быть любые величин однозначно определяющие положение сис
19019. Место квантовой механики в современной физической науке. Основные экспе-риментальные факты, лежащие в основе квантовой механики 318 KB
  Лекция 1. Место квантовой механики в современной физической науке. Основные экспериментальные факты лежащие в основе квантовой механики В современной науке квантовая механика занимает важнейшее место поскольку формирует основные идеи современного подхода к описа
19020. Принципы построения и постулаты квантовой механики. Операторы физических величин 285 KB
  Лекция 2 Принципы построения и постулаты квантовой механики. Операторы физических величин Как следует из опытов по дифракции микрочастиц в квантовой механике отсутствует понятие траектории т.е. состояние квантовой частицы не описывается заданием координаты и имп