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.


 

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

34641. Школа человеческих отношений (1930 – 1950) и поведенческих наук (1950 – наше время) 17.02 KB
  Школа поведенческих наук Макгрегор – повышение эффективности организации за счет повышения эффективности её человеческих ресурсов. Решения выбора альтернативы Управленческое решение – обдуманный вывод о необходимости осуществить какието действия связанные с достижением цели организации либо наоборот воздержаться от них. Эффективным организационным решением будет то которое будет на самом деле реализовано и внесет наибольший вклад в достижение целей организации.
34642. Типы организаций 21.39 KB
  Процесс принятия рационального решения Состоит из 7 основных этапов Диагностика или определение проблемы Существует 2 способа рассмотрения проблемы: Проблемой считается ситуация когда поставленные цели не достигнуты. Проблема как потенциальная возможность для этого необходима релевантная информация это данные касающиеся только конкретной проблемы человека цели в определенный период времени Все проблемы имеют: Определенное лицо Что Связанный с какимто конкретным местом Где Время возникновения и частота повторяемости...
34643. Общие характеристики организаций 40.73 KB
  Необходимость управления практическая реализация Факторы влияющие на процесс принятия решений Личностная оценка руководителя – субъективное ранжирования важности качества или блага. Среда принятия решений Все решения принимаются в разных обстоятельствах по отношению к риску и выделяют: Условие определенности когда точно известен результат каждого из альтернативного варианта выбора Условие риска – результаты этих решений не являются определенными но вероятность каждого результата известна. Негативные последствия – принятие...
34644. Личность. Методы принятия решений 22.49 KB
  ЯОбраз – какими мы видим себя Идеальное Я – какими нам хотелось бы быть Зеркальное Я – какими по нашему мнению нас видят другие Реальное Я –каковы мы в действительности Методы принятия решений При принятии решений вне зависимости от применяемых моделей существует правило принятия решений. Соответственно существуют следующие методы принятия решений: Платежная матрица – оказывает помощь руководителю в выборе одного из нескольких вариантов решений. Методы прогнозирования – в них используется как накопленный опыт так и текущие допущения на...
34645. Понятие алгоритма. Свойства, способы описания 90 KB
  Понятие алгоритма и способы его описания; Типы алгоритмов; Блоксхемы; Базовые структуры применяемые при создании алгоритмов. Иначе говоря блоксхема служит для графического изображения структуры алгоритма. Последовательность действий в соответствии с блоксхемой указывается с помощью стрелок соединяющих отдельные блоки и показывающих какой блок и вслед за каким должен выполняться. В ходе изучения данной дисциплины будут рассматриваться алгоритмы описанные при помощи языка программирования и при помощи специальных схем...
34646. Процедуры и функции 85.5 KB
  Пользовательские функции. В Паскале имеется два вида подпрограмм: процедуры PROCEDURE и функции FUNCTION. В программе процедуры и функции описываются после раздела описания переменных программы но до начала ее основной части то есть до оператора Begin начинающего эту часть.
34647. Рекурентные выражения. Рекурсия 73.5 KB
  При первом вызове функции fib5 определяется через fib4fib3; вычисление fib4 осуществляется через fib3 fib2 fib3 через fib2 fibl fib2 через fib1 fib0. Согласно условию прекращения рекурсии fibl и fib0 равно 1. Соответствующий рекурсивный процесс должен быть осуществлен и для fib4 и т. Решение: Vr n:byte; function fibk:byte :longint; begin if k = 1 then fib : = 1 else fib: =fibk l fibk 2 {рекурсивный вызов} end; BEGIN redlnn; writelnn 'e число Фибоначчи'...
34648. Сортировка. Усовершенствованные алгоритмы сортировки 142.5 KB
  Усовершенствованные алгоритмы сортировки. Имеется два вида алгоритмов сортировки. Изза этих отличий методы сортировки существенно отличаются для этих двух видов сортировки. В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки который используется в сравнениях.
34649. Страница Dialogs 227.84 KB
  Пусть ваше приложение включает окно редактирования Memo1 в которое по команде меню Открыть вы хотите загружать текстовый файл а после какихто изменений сделанных пользователем сохранять по команде Сохранить текст в том же файле а по команде Сохранить как.FileNme; Memo1.FileNme сохраняется в переменной FNme и файл загружается в текст Memo1 методом LodFromFile. Обработка команды Сохранить выполняется оператором Memo1.