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.


 

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

29860. Направления совершенствования бюджетной классификации 12.67 KB
  направления совершенствования бюджетной классификации Бюджетная классификация Российской Федерации является группировкой доходов и расходов бюджетов всех уровней бюджетной системы Российской Федерации а также источников финансирования дефицитов этих бюджетов применяется при составлении проектов бюджетов и исполнении бюджетов всех уровней обеспечивает сопоставимость показателей бюджетов всех уровней бюджетной системы Российской Федерации. Бюджетная классификация Российской Федерации включает: 1 классификацию доходов бюджетов Российской...
29861. Инвестиционные риски и направления их минимизации 12.78 KB
  При управлении инвестиционными рисками используется ряд приемов: в основном они состоят из средств разрешения рисков и приемов снижения степени риска. Средствами разрешения рисков являются избежание их удержание передача снижение степени риска. Избежание риска означает простое уклонение от мероприятия связанного с риском. Однако избежание риска для инвестора чаще является отказом от прибыли.
29862. Факторный анализ динамики финансово-экономических показателей 14.31 KB
  факторный анализ динамики финансовоэкономических показателей Под факторным анализом понимается методика комплексного и системного изучения и измерения воздействия факторов на величину результативных показателей. Отбор факторов определяющих исследуемые результативные показатели. Классификация и систематизация факторов с целью обеспечения комплексного и системного подхода к исследованию их влияния на результаты хозяйственной деятельности. Расчет влияния факторов и оценка роли каждого из них в изменении величины результативного показателя.
29863. Бюджетное планирование и его совершенствование в современных условиях 12.84 KB
  Весь цикл управления процессами формирования распределения перераспределения и потребления бюджетных ресурсов осуществляется посредством бюджетного планирования объектом которого являются фонды денежных средств. Главной задачей реформирования бюджетного процесса является создание условий и предпосылок для максимально эффективного управления общественными финансами в соответствии с приоритетами государственной политики а следовательно и повышение эффективности бюджетного планирования. Одна из задач этой реформы заключается в смещении...
29864. Финансовый рынок его структура и место в системе экономических отношений 13.9 KB
  финансовый рынок его структура и место в системе экономических отношений Финансовый рынок рынок ссудных капиталовэто механизм перераспределения капитала между кредиторами и заёмщиками при помощи посредников на основе спроса и предложения на капитал. Финансовый рынок категория историческая. Финансовый рынок это категория экономическая которая выражает экономические отношения по поводу реализации стоимости и с потребительской стоимости заключённой в финансовых активах. Как и любой другой финансовый рынок предназначен для установления...
29865. Порядок формирования и финансирования венчурных,инновационных и инвестиционных фондов 46 KB
  Фактически венчурное финансирование может быть охарактеризовано как источник долгосрочных инвестиций предоставляемых обычно на 5 7 лет предприятиям находящимся на ранних этапах своего становления а также действующим предприятиям для их расширения и модернизации. Отличие венчурного финансирования от других видов финансирования Источники финансирования Банки Стратегические партнеры Венчурное финансирование Инвестиции в акционерный капитал Кредиты Долгосрочныеинвестиции Рисковый бизнес Участие инвестора в управлении...
29866. Финансовый механизм предприятия 15.5 KB
  Рассмотрим более подробно один из методов финансового механизма финансовый анализ совершенствование которого позволит снизить расходную часть бюджета предприятия и повысить доходную. Финансовое состояние предприятия характеризуется совокупностью показателей отражающих процесс формирования и использования его финансовых средств. В рыночной экономике финансовое состояние предприятия по сути дела отражает конечные результаты его деятельности.
29867. Рынок ценных бумаг РФ: структура и основныек тенденции развития 28.63 KB
  Совокупность экономических отношений между его участниками по поводу выпуска и обращения ценных бумаг. Ценные бумаги в основе которых лежат деньги как капитал и которые опосредуют отношения связанные с движением денежного капитала образуют фондовый рынок как часть рынка ценных бумаг. Ценные бумаги опосредующие товарные отношения формируют рынок товарных ценных бумаг являющийся второй составной частью рынка ценных бумаг.
29868. Бюджетная система РФ 19.67 KB
  10 бюджетная система Российской Федерации состоит из трех уровней: Федерального бюджета и бюджетов государственных внебюджетных фондов; Бюджетов субъектов Российской Федерации региональных бюджетов и бюджетов территориальных государственных внебюджетных фондов; Местных бюджетов. Бюджетная система Российской Федерации включает: федеральный бюджет 21 республиканский бюджет республик в составе РФ 55 краевых и областных бюджетов и бюджеты Москвы и СанктПетербурга один областной бюджет автономной области 10 окружных бюджетов автономных...