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.


 

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

44945. Александр Николаевич Самохвалов 24.39 KB
  Александр Николаевич Самохвалов 21 августа 1894 Бежецк Тверская губерния Российская империя 20 августа 1971 Ленинград СССР крупнейший советский художник живописец график прикладник монументалист Заслуженный деятель искусств Российской Федерации член Ленинградской организации Союза художников РСФСР. Самохвалов Александр Николаевич родился 8 21 августа 1894 года в городе Бежецк Тверской губернии. Его отец Николай Дмитриевич Самохвалов занимался мелкой торговлей умер в 1917 году. Мать Самохвалова Елена Фёдоровна в девичестве...
44946. Организация вычисляемого перехода 41.46 KB
  Вычисляемый переход осуществляется при помощи команды ddwf PCF которая формально описывается так: сложить содержимое регистров W и PC с сохранением результата сложения в регистре PC имеется ввиду младший байт счетчика команд с названием PCL. Для вычисляемого перехода адрес в PC на момент исполнения команды ddwf PCF является как бы начальной точкой отсчета т. число находящееся в регистре W на момент исполнения команды ddwf PCF которое и будет приращением счетчика команд PC.
44947. Динамическая индикация 59.87 KB
  Для краткости эти регистры обозначим под названиями LED с соответствующей нумерацией. Например если результат измерения подсчета нужно вывести на индикацию как 4 разрядное десятичное число то двоичный результат измерения “прогоняется†через двоично-десятичное преобразование о нем позднее в итоге которого результат измерения помещается в младшие полубайты 4х регистров LED от LED0 до LED3.0 MHz ; DtL equ 0Ch DtH equ 0Dh D_H equ 0Eh D_L equ 0Fh Step equ 1Bh Led0 equ 1Ch Led1...
44949. Работа с EEPROM памятью данных 61.93 KB
  Поставим перед собой достаточно простую и конкретную задачу (что-то типа задания на первоначальную разработку). Допустим, что в ходе исполнения программы нужно изменить (модифицировать) содержимое пяти ячеек EEPROM памяти, начиная с адреса 7. Для простоты модификации (и для обеспечения наглядности наблюдения за происходящими в EEPROM памяти изменениями) к первому числу (по адресу 7) необходимо добавить 1...
44950. Однокристальные микроконтроллеры серии PIC 231 KB
  Микроконтроллеры семейств PIC (Peripheral Interface Controller) компании Microchip, обладающие особой популярностью, построены на основе передовых технологий микроконтроллеров. Им свойственны следующие особенности: электрически программируемые пользователем ППЗУ, минимальное энергопотребление, высокая производительность, хорошо развитая RISC-архитектура
44952. Автоколебательный мультивибратор 33.87 KB
  Проанализируем нашу программу, реализующую функцию автоколебательного мультивибратора, с одним выходом. Форма сигнала меандр (скважность, т.е. отношение периода к длительности импульса – 2). Под этот выход можно назначить любой из выводов порта А или В...
44953. Устройство формирования сигнала тонального вызова 87.52 KB
  Полупериоды формируем используя €œзакольцовку рабочей точки программы в подпрограммах задержки по аналогии с программой Multi. К моменту начала составления текста программы желательно определиться с как можно большим количеством исходных данных. Так как программа должна исполняться непрерывно то в случае нахождения устройства в режиме ожидания включения на передачу рабочая точка программы должна €œзакольцеваться€ до последующего нажатия на кнопку в какой-нибудь подпрограмме. Часто такого рода закольцовки осуществляют в...