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.


 

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

20014. Технологии работы с графической информацией. Растровая и векторная графика. Аппаратные средства ввода и вывода графических изображений 96.5 KB
  Создавать и хранить графические объекты в компьютере можно в виде Растрового изображения Векторного изображения Растровые изображения Растровые изображения очень хорошо передают реальные образы. Такие изображения легко выводить на монитор или принтер поскольку эти устройства тоже основаны на растровом принципе. Одной из главных проблем растровых файлов является масштабирование: при существенном увеличении изображения появляется зернистость ступенчатость картинка может превратиться в набор неряшливых квадратов увеличенных пикселей ....
20015. Табличные базы данных (БД): основные понятия (поле, запись, первичный ключ записи); типы данных 42 KB
  Табличные базы данных БД: основные понятия поле запись первичный ключ записи; типы данных. Системы управления базами данных и принципы работы с ними. Поиск удаление и сортировка данных в БД. Любой из нас начиная с раннего детства многократно сталкивался с базами данных .
20016. Технология обработки информации в электронных таблицах (ЭТ). Структура электронной таблицы. Типы данных: числа, формулы, текст 38 KB
  Типы данных: числа формулы текст. Графическое представление данных. Электронные таблицы Электронная таблица это программа обработки числовых данных хранящая и обрабатывающая данные в прямоугольных таблицах. Можно вводить и изменять данные одновременно на нескольких рабочих листах а также выполнять вычисления на основе данных из нескольких листов.
20017. Интернет. Информационные ресурсы и сервисы компьютерных сетей: Всемирная паутина, файловые архивы, интерактивное общение. Назначение и возможности электронной почты. Поиск информации в Интернете 72 KB
  Адресация в Интернет Для того чтобы связаться с некоторым компьютером в сети Интернет Вам надо знать его уникальный Интернет адрес. Существуют два равноценных формата адресов которые различаются лишь по своей форме: IP адрес и DNS адрес. IP адрес IP адрес состоит из четырех блоков цифр разделенных точками. Благодаря такой организации можно получить свыше четырех миллиардов возможных адресов.
20018. Виды информационных моделей (на примерах). Реализация информационных моделей на компьютере. Пример применения электронной таблицы в качестве инструмента математического моделирования 55.5 KB
  Понятие модели. Пример применения электронной таблицы в качестве инструмента математического моделирования. Моделирование Человечество в своей деятельности научной образовательной постоянно созадет и использует модели окружающего мира. Строгие правила построения моделей сформулировать невозможно однако человечество накопило богатый опыт моделирования различных объектов и процессов.
20019. Язык как способ представления информации: естественные и формальные языки. Основные информационные процессы: хранение, передача и обработка информации 48 KB
  Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей. Язык как способ представления информации: естественные и формальные языки.
20020. Измерение информации: содержательный и алфавитный подходы. Единицы измерения информации 39 KB
  Измерение информации: содержательный и алфавитный подходы. Единицы измерения информации. Определить понятие количество информации довольно сложно. один из основоположников кибирнетиеи американский математик Клож Шенон развил вероятностный подход к измерению количества информации а работы по созданию ЭВМ привели к объемному подходу .
20021. Дискретное представление информации: двоичные числа; двоичное кодирование текста в памяти компьютера. Информационный объем текста 40.5 KB
  Дискретное представление информации: двоичные числа; двоичное кодирование текста в памяти компьютера. Кодирование информации Представление информации происходит в различных формах в процессе восприятия окружающей среды живыми организмами и человеком в процессах обмена информацией между человеком и человеком человеком и компьютером компьютером и компьютером и так далее. Преобразование информации из одной формы представления...
20022. Дискретное представление информации: кодирование цветного изображения в компьютере (растровый подход). Представление и обработка звука и видеоизображения. Понятие мультимедиа 40.5 KB
  Дискретное представление информации: кодирование цветного изображения в компьютере растровый подход. Кодирование информации в компьютере Вся информация которую обрабатывает компьютер должна быть представлена двоичным кодом с помощью двух цифр 0 и 1. Это явилось причиной того что в компьютере обязательно должно быть организовано два важных процесса: кодирование которое обеспечивается устройствами ввода при...