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.


 

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

23322. Защита от быстрых нейтронов 209 KB
  ЦЕЛЬЮ НАСТОЯЩЕЙ РАБОТЫ является исследование железоводной защиты от быстрых нейтронов и измерение величины сечения выведения для железного поглотителя. ОСНОВНЫЕ ТОРЕТИЧЕСКИЕ СВЕДЕНИЯ При проектировании защиты от нейтронного излучения необходимо что процесс захвата и поглощения эффективен для тепловых медленных и резонансных нейтронов благодаря большому десятки сотни барн сечению их взаимодействия с веществом см. Энергетический спектр нейтронов деления ядра тепловыми нейтронами.
23323. Установка отношений между базами данных 86 KB
  Лабораторная работа №4: Установка отношений между базами данных По дисциплине: Базы данных. Цели работы: освоить технологию установки отношений между 2–3мя базами данных; выполнить просмотр связанных баз данных. Задание: Проверьте проект базы данных на предмет проектирования связей ключи первичные вторичные. В проекте базы данных предметной области выделите 2–3 связанные таблицы родственные таблицы.
23324. Поиск информации в базах данных. Установка фильтров 88.5 KB
  Лабораторная работа №5: Поиск информации в базах данных. Установка фильтров По дисциплине: Базы данных. Цели работы: освоить технологию поиска данных в базах данных в среде FoxPro Seek Find Locate; научиться составлять выражения логического типа для поиска; научиться фильтровать данные в базах данных set filter с помощью простого и индексного фильтра; ознакомиться с синтаксисом генерируемых команд. Задание: Составьте не менее 10 логических выражений для поиска данных в базе данных.
23325. Обработка запросов 95.5 KB
  Отчет по работе: Исходные базы данных: Простые запросы для одной базы данных: SELECT Table1.зарплата Table1.фамилия; FROM db6table1; WHERE Table1.зарплата 20000; SELECT Table1.
23326. Создание отчетов 143 KB
  Лабораторная работа №7: Создание отчетов По дисциплине: Базы данных. Цели работы: научиться быстро составлять отчет на основе стандартного; освоить технику разработки отчетов вывода отчетов на экран в файл; изучить все особенности работы в диалоговых окнах генерации отчетов; составить отчеты по теме самостоятельного проектирования. Отчет по работе: Контрольные вопросы: Объяснить структуру выполненных отчетов. Назначение инструментов для конструирования отчетов.
23327. Проектирование этикеток 76.5 KB
  Лабораторная работа №8: Проектирование этикеток По дисциплине: Базы данных. Цели работы: научиться быстро проектировать этикетки; освоить технику разработки этикеток вывода этикеток на экран в файл; составить этикетку по теме самостоятельного проектирования. Задание: Определите структуру этикетки: база данных для этикетки; название этикетки; порядок размещения полей в этикетке; порядок размещения этикеток на листе; размер этикеток.
23328. Локальные сети. Структура стандартов IEEE 802.x 158.5 KB
  Стандарты семейства IEEE 802.х охватывают только два нижних уровня семиуровневой модели OSI — физический и канальный. Это связано с тем, что именно эти уровни в наибольшей степени отражают специфику локальных сетей. Старшие же уровни, начиная с сетевого, в значительной степени имеют общие черты, как для локальных, так и для глобальных сетей.
23329. Макросы. Создание макросов 36.5 KB
  Отчет по работе: Открыть таблицу CtrlF1: USE{SPACEBAR}table1{SPACEBAR}AGAIN{SPACEBAR}IN{SPACEBAR}0{ENTER} SELECT{SPACEBAR}Table1{ENTER} BROWSE{SPACEBAR}LAST{ENTER} Удалить таблицу CtrlF2: Remove{SPACEBAR}Table{SPACEBAR}table1{ENTER} Установить отношение между таблицами CtrlR: SET{SPACEBAR}RELATION{SPACEBAR}TO{SPACEBAR}фамилия{SPACEBAR}INTO{SPACEBAR}Table2{SPACEBAR}ADDITIVE{ENTER} Модифицировать отчёт CtrlM: MODIFY{SPACEBAR}REPORT{SPACEBAR} c: artamonov базы данных visual foxpro9 save artlab10 report1.frx {SPACEBAR}NOENVIRONMENT{ENTER}...
23330. Генератор прикладных программ 91 KB
  Цель работы: научиться создавать стандартные приложения с помощью генератора FoxApp. Задание: Перед началом работы создать отдельный каталог для файлов приложения. Выполните генерацию стандартного приложения создавая или указывая базу данных на шаге 1. Проверьте работу стандартного приложения: стандартный экран форма ввода кнопки управления; меню стандартного приложения.