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.


 

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

73834. Выбор вариантов схем базирования 40.5 KB
  Для создания возможности повышения уровня концентрации обработки в операции и снижения разнообразия технологической оснастки лучше принять в качестве базы для обработки всех поверхностей детали одну и туже базу Е. Синтез маршрута обработки заготовки Первый шаг синтеза маршрута обработки заготовки распределение отобранных переходов обработки типовых поверхностей заготовки по этапам типовой схемы изготовления деталей соответствующего класса или подкласса. Типовая схема обработки является вариантом полного типового решения. Причиной...
73835. Проектирование маршрутных технологических процессов механической обработки 52 KB
  Маршрутное описание ТП заключается в сокращенном описании всех технологических операций в маршрутной карте в последовательности их выполнения без переходов и технологических режимов. Операционное описание ТП характеризуется полным описанием всех технологических операций в последовательности их выполнения с указанием переходов и технологических режимов. Маршрутнооперационным описанием ТП называют сокращенное описание технологических операций в маршрутной карте в последовательности их выполнения с полным описанием отдельных операций в других...
73836. Особенности проектирования технологических процессов обработки заготовок на автоматизированных участках и автоматических линиях 51.5 KB
  В необходимых случаях подготовку технологических баз при обработке на автоматической линии или при установке заготовки в приспособлениеспутник производят на отдельных операциях вне автоматической линии; маршрутный технологический процесс разрабатывают с учетом максимальной концентрации операций соблюдения принципа единства баз выполнения чистовых и отделочных операций в конце технологического процесса; при проектировании автоматических операций анализируют возможность совмещения технологических и вспомогательных переходов во времени. Для...
73837. Особенности проектирования технологических процессов для станков с ЧПУ и ГПС 58 KB
  Особенности проектирования технологических процессов для станков с ЧПУ и ГПС При проектировании технологических операций для станков с ЧПУ необходимо учитывать ряд особенностей обработки. Порядок обработки поверхностей заготовок для деталей типа валов следующий. Черновая и чистовая обработка дополнительных форм поверхности если имеются дополнительные формы требующие черновой обработки. Обработка дополнительных форм поверхности не требующих черновой обработки.
73838. Технология изготовления втулок 80.5 KB
  Технологические задачи Отличительной технологической задачей является обеспечение концентричности наружных поверхностей с отверстием и перпендикулярности торцов к оси отверстия. Диаметры наружных поверхностей выполняют по h6 h7; отверстия по H7 реже по H8 для ответственных сопряжений по Н6.015 мм; перпендикулярность торцовых поверхностей к оси отверстия 02 мм на радиусе 100 мм при осевой нагрузке на торцы отклонение от перпендикулярности не должно превышать 002. Заготовками для втулок с диаметром отверстия до 20 мм служат...
73839. Технология изготовления корпусных деталей 1.63 MB
  Обрабатывают направляющие начерно резцами на продольнострогальных станках торцевыми фрезами и наборами фрез на продольнофрезерных станках. Обрабатывают начерно поверхности расположенные перпендикулярно направляющим на продольнофрезерных станках если станина по длине проходит между колонами станка; на горизонтальнорасточных станках фрезой или на торцефрезерных станках если станина длинная. Обрабатывают отверстия начерно на горизонтальнорасточных станках в приспособлении. Чистовую обработку лучше выполнять на продольнофрезерных...
73840. Процессы обработки деталей типа некруглые стержни 191.5 KB
  Технология изготовления рычагов. Характеристика рычагов К деталям класса рычагов относятся собственно рычаги тяги серьги вилки балансиры шатуны. Детали класса рычагов имеют два отверстия или больше оси которых расположены параллельно или под прямым углом.
73841. Процессы обработки деталей «круглые стержни» 58.5 KB
  В зависимости от типа производства операцию производят: в единичном производстве подрезку торцов и центрование выполняют на универсальных токарных станках последовательно за два установа; в серийном производстве подрезку торцов выполняют раздельно от центрования на продольнофрезерных или горизонтальнофрезерных станках а центрование на одностороннем или двустороннем центровальном станке. В зависимости от типа производства операцию выполняют: в единичном производстве на токарновинторезных станках; в мелкосерийном на...
73842. Технико-экономические показатели разрабатываемых ТП 72 KB
  На завершающим этапе разработки ТП проводят полную оценку вариантов путем сравнения себестоимости обработки заготовок отражающей затраты живого и овеществленного труда. Существует два основных метода определения себестоимости: бухгалтерский и метод прямого калькулирования поэлементный. Цеховые расходы при калькулировании себестоимости определяют в процентах от заработной платы основных рабочих цеха: тогда себестоимость текущие затраты можно выразить так: где ц процент цеховых накладных расходов. Его можно использовать при приближенном...