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.


 

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

1242. Административное право, ответы к экзамену 1.31 MB
  Понятие и правовое регулирование в административном праве. Понятие и основные черты административно-правовых отношений. Административно-правовые гарантии реализации прав граждан. Обращения граждан. Основные принципы построения и функционирования системы государственной службы: понятие, система и виды.
1243. Информационные системы в экономике 438 KB
  Объективность процесса информатизации, направления ее развития. Основные понятия экономической информатики. Информационный бизнес, рынок, менеджмент. Структура и схема функционально-позадачных информационных систем. Основные направления в развитии инфокоммуникационных технологий. Этапы компьютерного решения экономических задач.
1244. Шпаргалка по логике: Ответы на экзаменационные билеты 531.08 KB
  МЫШЛЕНИЕ КАК ПРЕДМЕТ ЛОГИКИ. ВЗАИМОСВЯЗЬ ЛОГИКИ И ЯЗЫКА. ОСОБЕННОСТИ ЛОГИЧЕСКИХ ЗАКОНОВ И ИХ СВЯЗЬ С ПРИНЦИПАМИ МЫШЛЕНИЯ. ЗАКОН ИСКЛЮЧЕННОГО ТРЕТЬЕГО. ПОНЯТИЕ КАК ФОРМА МЫШЛЕНИЯ. ОБОБЩЕНИЕ И ОГРАНИЧЕНИЕ ПОНЯТИЯ. ОПРЕДЕЛЕНИЕ ПОНЯТИЯ КАК ЛОГИЧЕСКАЯ ОПЕРАЦИЯ.
1245. Место и роль Фонда социального страхования РФ в обеспечении социальной защиты населения 626 KB
  Сущность и особенности функционирования фонда социального страхования РФ. Понятие, функции и принципы социальной защиты населения. Роль Фонда социального страхования в системе социальной защиты населения. Анализ деятельности фонда социального страхования РФ (на примере калужского регионального отделения).
1246. Право собственности в гражданском праве 389.5 KB
  Понятие и содержание права собственности по законодательству РФ. Проблема соотношения видов и форм права собственности. Классификации собственности на виды. Первоначальные и производные основания приобретения права собственности. Проблема определения момента приобретения права собственности на выморочное имущество (коллизии судебной практики).
1247. Проектирование одноцепной ВЛ 110 кВ ПС Березники 883.5 KB
  Определение расчетных климатических условий. Электрический расчет проводов. Определение единичных нагрузок на провод АС 150/24. Определение единичных нагрузок на трос ТК – 50. Поддерживающее неизолированное крепление для троса ТК – 50 (с заземлением) для ВЛ 110 кВ. Схема дополнительного заземления для промежуточных железобетонных опор. Определение срока монтажа ВЛ.
1248. Проектування токарно-револьверного верстата 761.5 KB
  Вибір компонування і визначення основних технічних характеристик верстата і приводів. Вибір базової моделі й обґрунтування принципової конструкції верстата. Проектний розрахунок приводу у автоматизованій системі PRIVOD. Розрахунок кількості зубів шестерень привода та оцінювання точності кінематичного розрахунку. Проектний розрахунок міцності деталей та механізмів привода головного руху.
1249. Проектирование предприятия пищевой промышленности 1.03 MB
  Компоновка и анализ помещений. Расчет фундаментной площади и болтов для крепления экстрактора НД-1250. Расчет фундаментных болтов для экстрактора. Расчет кинетостатики экстрактора НД-1250. Расчет сетевого графика монтажа.
1250. Пошук і використання альтернативних джерел палива 876.5 KB
  Аналіз основних напрямків розвитку альтернативного палива у світі. Використання газових та водневих вдигунів. Індикаторна діаграма циклу Отто. Паралельна схема роботи гібридів. Схема роботи двигуна Civic Hybrid. Функціональні системи автомобіля Toyota Prius. Аналіз схемних рішень електрозапалювання робочої суміші. Мікропроцесорна система запалювання.