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.


 

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

25457. Теория социальной работы как наука. Механизмы взаимодействия теории и практики социальной работы 15.18 KB
  Теория социальной работы как наука. Механизмы взаимодействия теории и практики социальной работы Теоретическое обоснование соц. Вопервых определяется место соц.работы как науки среди таких дисциплин как соц.
25459. Основные группы категорий социальной работы 11.87 KB
  основные группы категорий социальной работы Любая гуманитарная наука в том числе теория социальной работы отражает изменчивые тесно переплетающиеся друг с другом многообразные социальные явления например взаимодействие человекчеловек человексреда обобщая и интерпретируя которые ученые выдвигают понятия краткие но всеобъемлющие определения способные объяснить особенности того или иного явления не позволяющие его толковать двояко. Категориально понятийный аппарат социальной работы. В теории социальной работы сложился...
25460. Февральский переворот 1917 г 12.75 KB
  В ходе боев формируется убеждение что земля не может не перейти крестьянам в награду за страдания жертвы и гибель за Царя тем более что община провожая солдат на войну говорила : Защитите землю и отвоюйте ее в руки крестьянские Вера в победоносное и непременно скорое окончание войны побуждало солдат безропотно нести свой крест и выполнять свой долг перед Царем и Отечеством. Объективно особых причин для этого не было но традиционное сознание ориентировано на то что правдивую информацию поставляет ближайшее окружение то есть солдат при...
25461. Взаимосвязь процесов в обществе социальной политики и социальной работы 12.45 KB
  Решение соц. проблем через личностные потребности и интерес клиентов Зависимость результативности ср от профессионализма нравственных Закономерности соц работы носят объективный характер Жуков 2 группы: 1 законодат функц и разв системы СР 2 законод отраж существ связи между С и О соц дти и их диалектика полит обусловл СР взаимосвязь соц пол госва и сод СР объем и финанс соц прогр: стрра соц служб кат нас все завис от соц пол госва детермин сод и форм СР с социокульт услми ее сущя проф компетентность и ориентир соц служб ...
25462. Вторая половина 1918 г. 12.51 KB
  в стране насчитывалось до 10 типов изданий проводивших политику правящей партии. Но самым примечательным стал выход 28 новых центральных изданий. Среди центральных изданий возникших в годы гражданской войны следует назвать газету Жизнь национальностей орган Народного Комиссариата по делам национальностей. они выпустили около 500 различных изданий.
25463. Принципы и методы профессиональной социальной работы 15.61 KB
  Принципы и методы профессиональной социальной работы Принципы соц. Именно через применение принципов осуществляется непосредственное соотнесение теоретических положений воплощенныхв категориях и закономерностях с практикой соц. Теория соц.рты выявляет и описывает основные тенденции закономерности разя и функционирования всего комплекса взаимосвязанных компонентов соц.