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.


 

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

3862. Философия как дисциплина научного познания. Генезис философии 470 KB
  Генезис философии. Нужно отметить, что генезис является проблемой для самой философии, развиваясь, она постоянно сталкивается с проблемой собственного возникновения, ибо, только решив ее, философия сможет в полной мере осознать свою сущность. Сущест...
3863. Контрольна робота. Механіка матеріальної точки 86.01 KB
  Механіка матеріальної точки За заданими рівняннями руху х=х(t), у=у(y) (та z=z(t) для 2 рівня складності) матеріальної точки масою т =1кг встановити: Рівняння та вид траєкторії точки побудувати графік. Вектори переміщення, середньої швидкості та їх...
3864. Управляющие операторы или принятие решений в VB6 428.5 KB
  Управляющие операторы или принятие решений в VB6. Операторы, которые могут изменить последовательность выполнения операторов процедуры. Основанием для принятия решений в управляющих операторах являются условные (логические) выражения. Логические вы...
3865. Основні поняття та закони хімії. Конспект лекцій 3.89 MB
  ВСТУП Без знання основ хімії неможливе успішне вивчення технічних і технологічних дисциплін. Метою курсу є оволодіння студентами знань, необхідних їм для розуміння хімічних та технологічних явищ, які лежать в основі перетворень процесів зварювання...
3866. Работа с листом. Выделение объектов 3.16 MB
  Работа с листом. Выделение объектов Ячейка, блок ячеек, строка, диапазон строк, столбец, диапазон столбцов, лист, книга - это основные объекты, с которыми работает пользователь Excel. Принцип робот с объектами одинаков для всех программ Windows: на...
3867. Запуск Excel. Основные понятия 830.33 KB
  Запуск Excel. Основные понятия Запустить электронную таблицу Excel можно из главного меню, пункт Программы. При частом обращении к этой программе удобно поместить ее ярлык на рабочий стол, и пользоваться им для запуска Excel. Кроме того, двойное щел...
3868. Моделирование решения уравнений в среде электронных таблиц MS Excel 74.9 KB
  Моделирование решения уравнений в среде электронных таблиц MS Excel Основная задача нашего сегодняшнего урока - это научиться решать уравнения различными методами, а также моделировать процесс решения определенного вида уравнений в зависимости от зн...
3869. Формулы в Microsoft Excel 407.37 KB
  Формулы в Microsoft Excel Общие сведения Excel - программируемый табличный калькулятор. Все расчеты в Excel выполняют формулы. Формулой Excel считает все, что начинается со знака "=". Если в ячейке написать просто "1+1", Excel не будет вычислять это...
3870. Формат представления данных в ячейках 182.39 KB
  Формат представления данных в ячейках По умолчанию после создания документа все ячейки находятся в формате "Общий". Этот формат имеет ряд хитростей: числа выравниваются по правому краю, а текст — по левому если, изменяя ширину столбца, сделать...