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.


 

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

46104. Характеристика системы специальных учреждений для детей с нарушениями речи 42 KB
  Характеристика системы специальных учреждений для детей с нарушениями речи. дошкольные учреждения для детей с нарушениями речи. Первоначально в д с открывали группы для детей только с легкими нарушениями речи затем организованы группы для детей с более сложными заикание ОНР. Д с яслисады для детей с нарушениями речи и соответствующие дошкольные группы при детских садах и ясляхсадах общего типа комплектуются непосредственно теми отделами народного образования в ведении которых находятся указанные дошкольные учреждения.
46105. Обучение и воспитание детей с фонетико-фонематическим недоразвитием 21.5 KB
  Признаком фонематического недоразвития является незаконченность процесса формирования звуков отличающихся тонкими артикуляционными или акустическими признаками. Состояние фонематического развития детей влияет на овладение звуковым анализом. При первичном нарушении фонематического восприятия предпосылки к овладению звуковым анализом и уровень сформированности действия звукового анализа ниже чем при вторичном. Недостатки звукопроизношения могут быть сведены к следующим характерным проявлениям: замена звуков более простыми по...
46106. Общее недоразвитие речи у детей. Характеристика уровней речевого недоразвития 30 KB
  Общее недоразвитие речи у детей. Общее недоразвитие речи ОНР различные сложные речевые расстройства при которых у детей нарушено формирование всех компонентов речевой системы относящихся к ее звуковой и смысловой стороне при нормальном слухе и интеллекте.Левиной была разработана периодизация проявлений ОНР: от полного отсутствия средств общения до развернутых форм связной речи с элементами фонетикофонематического и лексикограмматического недоразвития. Переход с одного уровня на другой определяется появлением новых языковых...
46107. Обучение и воспитание детей с общим недоразвитие речи 32.5 KB
  Обучение и воспитание детей с общим недоразвитие речи. Предусматривает: развитие понимания речи; развитие самостоятельной речи на основе подражательной деятельности; формирование двусоставного простого предложения на основе усвоения элементарных словообразований. Логопедические занятия с безречевыми детьми проводятся небольшими подгруппами в форме игровых ситуаций что помогает постепенно формировать мотивационную основу речи. Задачи: вызвать подражательную речевую деятельность детей в форме любых звуковых проявлений; расширение объема...
46108. Предупреждение речевых нарушений. Формы и методы профилактического воздействия в системе общегосударственных мероприятий 25 KB
  Одним из важных направлений развития логопедической помощи населению является предупреждение речевых нарушений и последствий речевой патологии. Своевременное генетическое консультирование будущих родителей с целью предупреждения развития тех или иных отклонений в нервопсихическом и в частности речевом развитии ребенка. Для своевременного развития речи мать и другие лица окружающие ребенка должны постоянно общаться с ним стремясь вызвать ответную реакцию. Стимуляция формирования речевой функции имеет большое значение для развития...
46109. Анализ условий нормального речевого развития ребенка. Этапы нормального речевого онтогенеза 17.5 KB
  Речь ребенка формируется под влиянием речи взрослого и в огромной степени зависит от достаточной речевой практики от нормального окружения и от воспитания и обучения которое начинается с первых дней его жизни. Этапы становления речи детей Леонтьев. В это же время путем подражания ребенок постепенно перенимает элементы звучащей речи.Преддошкольный от 1года до 3 лет Характеристика: этап становления активной речи.
46110. Теоретические основы логопсихологии. Психологическая характеристика детей с нарушениями речи 20.5 KB
  Психологическая характеристика детей с нарушениями речи. Объект психика лиц с патологией речи. Психологическая характеристика детей с нарушениями речи. Ранний возраст 13 года Этот возраст является сензитивным чувствительным периодом становления речи.
46111. Характеристика педагогических систем воспитания детей с речевыми нарушениями. Проблемы интеграции детей дошкольного возраста с речевыми нарушениями 23.5 KB
  Характеристика педагогических систем воспитания детей с речевыми нарушениями. Проблемы интеграции детей дошкольного возраста с речевыми нарушениями.подготовка к обучению грамоте и овладение элементами грамоты Системы логопедического и педагогического обследования детей дошкольного возраста с речевыми нарушениями В целом проводится комплексное психологопедагогическое обследование психолог педагоги логопед Цель: выявить отклонения направить ребенка в соответствующее образовательное учреждение Задачи обследования: 1....
46112. Семейное воспитание детей с нарушениями речи: содержание, формы, и стили семейного воспитания 14 KB
  Семейное воспитание детей с нарушениями речи: содержание формы и стили семейного воспитания. Семья основная на браке или кровном родстве малая группа члены которой связаны общностью быта взаимной моральной ответственностью в ней вырабатываются совокупность нормы и образцов регламентирущих взаимодействий между супругами детьми детей между собой. детоцентрическая все интересы подчинены ребенку детей формируется высокая самооценка 3.сексуальноэротическая Специфические функции семей имеющих детей с нарушениями в развитии 1.