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.


 

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

35560. Доменные фурмы. Снижение потерь тепла от горячего дутья через внутренний конус (стакан) фурмы 616.5 KB
  В работах сообщается об успешной эксплуатации фурм с внутренними конусами из углеродистых и легированных сталей. О снижении теплопотерь от стальных конусов говорит тот факт [30] что замена материала внутреннего конуса толщина стенки 10 мм с меди на углеродистую и легированную сталь приводит к повышению температуры поверхности конуса со стороны горячего дутья со 108 до 300 и 5600С соответственно. Но со временем сложилось мнение [5] что конструкции фурм со стальными внутренними конусами недолговечны так как испытывая ударные...
35561. Профилактика зависимости от ПСИХОАКТИВНЫХ ВЕЩЕСТВ 2.45 MB
  Представленные в пособии материалы позволят тренеру составить детальный план тренинговых занятий с учетом потребностей целевой группы различного опыта и знаний подростков о вреде наркотиков. Основные понятия В ходе тренинга с участниками группы происходят изменения. Развитие или движение группы во времени обусловленное взаимодействием и взаимоотношениями членов группы между собой и с ведущим называют групповой динамикой. Групповая сплоченность формирование у участников чувства принадлежности к группе группового единства необходимое...
35562. ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ, СИСТЕМЫ И СЕТИ 4.47 MB
  В учебном пособии изложены основные принципы схемотехнической и программной организации современных ЭВМ. Основное внимание уделено задачам организации ЭВМ на основе микропроцессоров фирмы Intel.
35563. ОБОРУДОВАНИЕ ДЛЯ ВТОРИЧНОЙ ОБРАБОТКИ МЕТАЛЛОВ И СПЛАВОВ 1.87 MB
  Рассмотрены источники образования и классификация вторичных отходов металлов описаны операции разделки и компактирования сепарации лома и отходов металлов приведены конструктивные схемы установок и оборудования для вторичной обработки металлов и сплавов. Источники образования и структура вторичных сырьевых ресурсов Ресурсы отходов цветных металлов и сплавов  это часть фонда металлов и сплавов перешедшая в категорию отходов к моменту на который определяется фонд. Оборотные отходы  часть отходов металлов и сплавов...
35564. Высокие технологии в металлургии. ч.1 Производство цветных металлов 1.14 MB
  Кратко изложена теория и практика современной металлургии меди никеля алюминия магния и титана. Металлургия меди 5 1.2 Свойства меди и области её применения 8 1.3 Сырье для получения меди 9 1.
35565. ТЕОРИЯ ПЕРЕХОДНЫХ ПРОЦЕССОВ. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЭЛЕКТРОТЕХНИКИ 9.56 MB
  21 Операторные схемы замещения элементов цепи22 Законы Ома и Кирхгофа в операторной форме.38 Численное решение уравнения состояния явный метод Эйлера40 ЛЕКЦИЯ 5 Линейные электрические цепи при импульсных воздействиях Расчет реакции цепи на одиночный импульс воздействия метод наложения.42 Расчет реакции цепи на периодическое импульсное воздействия метод сопряжения интервалов . Дальнейшее состояние цепи называют установившимся процессом.
35566. ЭКСПЛУАТАЦИОННЫЕ СВОЙСТВА АВТОМОБИЛЕЙ 3.43 MB
  АТС и его эксплуатационные свойства4 Вопрос 2. Условия эксплуатации АТС. Тяговоскоростные свойства АТС ТСС АТС. Силы действующие на АТС9 Вопрос 5.
35567. Металлургия черных металлов 1.51 MB
  Дан расчет количества МНЛЗ обращено внимание на выбор типа и основных проектных характеристик МНЛЗ. Типы МНЛЗ и их применение. Расчет количества МНЛЗ для рассматриваемого примера. На обоих предприятиях установлена и внедрена в производство установка внепечной очистки сталей АКВОС на ОАО Электросталь строится 5й СПЦ который планируется оборудовать двумя ДСП20 агрегатами внепечной очистки стали и МНЛЗ.
35568. ТЕХНОЛОГИЯ ПРОИЗВОДСТВА СТАЛИ В ЭЛЕКТРИЧЕСКИХ ПЕЧАХ 1.01 MB
  Курс лекций Технология производства стали в электрических печах ГОУ СПО Красносулинский металлургический колледж г. Данное методическое пособие является кратким курсом лекций по дисциплине Технология производства стали в электрических печах для студентов 3 курса специальности 150108 Порошковая металлургия композиционные материалы покрытия СОДЕРЖАНИЕ АННОТАЦИЯ. ТЕХНОЛОГИЧЕСКИЕ ПРОЦЕССЫ ПРОИЗВОДСТВА СТАЛИ.