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.


 

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

75526. Классификация и краткая характеристика моделей данных 172 KB
  Классификация и краткая характеристика моделей данных Одними из основополагающих в концепции баз данных являются обобщенные категории данные и модель данных. Понятие данные в концепции баз данных это набор конкретных значений параметров характеризующих объект условие ситуацию или любые другие факторы. Примеры данных: Петров Николай Степанович 30 и т. Поэтому центральным понятием в области баз данных является понятие модели.
75527. Последовательность действий при разработке проекта в ИС Project Expert 25 KB
  Последовательность действий при разработке проекта в ИС Project Expert Раздел Проект состоит из шести модулей. В этом диалоге отображается информация введенная присоздании проекта в диалоге Новый проект . Информация введенная в диалоге Список продуктов будет использована программой в модулях раздела Операционный план при планировании стратегии производства и сбыта сформированного перечня продуктов услуг проекта а также в модуле Стартовый баланс раздела Компания при описании активов и пассивов действующего предприятия. Текстовое...
75528. Основные требования к организации и формированию БД 26 KB
  Основные требования к организации и формированию БД База данных БД именованная совокупность данных отражающая состояние объектов и их отношений в рассматриваемой предметной области. К таким требованиям можно отнести...
75529. Хозяйственные операции и их регистрация в системе 1С 21 KB
  Ведение финансово-хозяйственных операций неразрывно связан с регистрацией первичных документов и формированию на их основ бухгалтерских проводок. Документы одного вида группируются в журнал. Кроме обычных журналов объединяющих все документы определенного вида видов существует общий журнал в который попадет все документы. Документ может находиться в двух состояниях не проведен и проведен.
75530. Характеристика и принципы построения сетевых (распределенных) БД 35.5 KB
  Характеристика и принципы построения сетевых распределенных БД Под распределенными базами данных РБД понимаются БД применяемые в вычислительной компьютерной сети. По типологии РБД делятся на: РБД централизованного хранения РБД распределенного хранения. При централизованном хранении вся РБД хранится на одном компьютере сервере а программы с остальных компьютеров клиентов обращаются к нему. Проектирование структуры такой РБД ничем не отличается от проектирования структуры обычных БД.
75531. Основные понятия и принципы инфологического моделирования 39.5 KB
  Основными конструктивными элементами инфологических моделей являются сущности связи между ними и их свойства атрибуты. Необходимо различать такие понятия как тип сущности и экземпляр сущности. Понятие тип сущности относится к набору однородных личностей предметов событий или идей выступающих как целое. Экземпляр сущности относится к конкретной вещи в наборе.
75532. Відвідування театру. Враження від вистави. План-конспект уроку з англійської мови для учнів 9-х класів 55 KB
  Т: The topic of our lesson is Going to the thetre Describing performnce . By the end of the lesson you should be ble: to review nd ctivize the words nd wordcombintions to the topic Going to th thetre nd Describing performnce ; to predict fcts nd events from the newspper rticle by its hedline; to understnd the gist nd detils of the newspper rticle despite the nturl difficulties; to express your opinions bout performnce. I went to the thetre lst Sundy. Do you often go to the thetre Why Cn you sy wht the thetre is Where re the best sets in...
75533. Великий Кобзар, Тарас Шевченко, відомий у всьому світі 66.5 KB
  Т: Wht is this rticle bout Look t the newspper hedline of ex. Predict wht is this rticle bout 2 WhileReding ctivities. Wht kind of the text is it Wht kind of newspper is it tken from Wht is this rticle bout б Scnning. Where do monuments to gret poets of the world literture Ukrinin Trs Shevchenko Russin lexnder Pushkin Byelorussin Ynk Kupl nd mericn Wlt Whitmn stnd nerby on one lwn In wht town is rrow Prk situted Wht poem by Trs Shevchenko resounded in the prk on tht dy Who lid flowers t the monuments to the luminries of...
75534. Кіно в Україні 58 KB
  Т: The topic of our lesson is Cinem in Ukrine Describing film . By the end of the lesson you should be ble: to review the words nd wordcombintions to the topic Going to the cinem Describing film ; to understnd the gist nd detils of the text for reding; to express your opinion bout film you hve recently seen. Т: Red the quottion bout films find Ukrinin equivlent. Повторення ЛО теми Going to the cinem Describing film .