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.


 

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

36487. Древняя Греция – основные достижения в экономической, политической и духовной сферах 42 KB
  Формируется теоритеческая база науки. Процесс становления древнегреческой науки шел через отделение научного элемента от фантастического. Итак появление науки в Древней Греции способствовал ряд предпосылок: У греков отсутствовала каста жрецов и поэтому научные знание были доступны любому гражданину; Демократическая форма правления в государстве что гарантировало гражданские права и необходимость их отстаивания с помощью риторики основанной на аргументации и убеждении оппонента. Развиваются такие науки как математика геометрия...
36488. Українська мова. Відповіді на екзаменаційні питання 5.99 MB
  рикметники, у яких є закінчення, називаються повними: добрий, вільна, славне, зелені, батькового, материна. Ці форми є звичайними для сучасної української мови.У народній творчості та в поезії вживаються також нестягнені повні прикметники: вірная (замість: вірна), вечірнюю (замість: вечірню), синєє (замість: синє), молодії (замість: молоді).
36489. Співвідношення між ентропією та імовірністю, формула Больцмана 170.77 KB
  В теорії Дебая зміщення атомів представляється як система поздовжніх та поперечних хвиль суцільного однорідного твердого тіла. Система хвиль має широкий спектр частот. Всі хвилі з будьякими частотами малої швидкості відповідають поперечним і поздовжнім хвилям у твердому тілі тобто нехтуємо дисперсією хвиль. Система хвиль таким чином складається із поздовжніх та поперечних хвиль.
36490. Розподіли Гаусса і Пуассона як частинні випадки біноміального розподілу 210.63 KB
  Для кожного тіла можна записати термічне рівняння стану та його внутрішню енергію як функцію параметрів які визначають його стан наприклад . Як називається це рівняння Це калоричне рівняння. Обидва ці рівняння не можуть бути отримані методами формальної термодинаміки. Якщо відомо відоме термічне рівняння стану то теорема Карно дозволяє в загальному вигляді розвязати питання залежності внутрішньої енергії від обєму.
36491. Середня довжина вільного пробігу молекул, її залежність від тиску і температури 242.26 KB
  Середня довжина вільного пробігу молекул її залежність від тиску і температури. Розглянемо молекулу яка рухається із деякою середньою швидкістю і при зіткненнях не змінює швидкості. Будемо вважати що рухається тільки одна молекула за якою ми спостерігаємо а решта нерухомі. Виберемо проміжок часу рівний одній секунді тобто будемо розглядати шлях молекули за одиницю часу.
36492. Розподіл середньої кінетичної енергії за ступенями вільності для обертального руху 189.71 KB
  Кількість молекул всі вони незалежні. Кожна молекула характеризується у просторі кругових частот величинами . Імовірність потрапити молекулам у елементарний обєм має вигляд . Знайдемо середню кінетичну енергію обертального руху виділеної молекули що припадає на один ступінь вільності при обертанні навколо осі навіщо нам чіплятись до осі вісь нічим не гірша.
36493. Термічна ефузія 238 KB
  Кількість зіткнень з нею за одиницю часу становить за законом косинусу . Повна кількість молекул у такому обємі становить . Цей простір буде також необмежений тому ми можемо вважати кількість комірок у ньому нескінченною. Скористаємось формулою Больцмана де у нашому випадку у знаменнику немає обмеження оскільки кількість комірок є нескінченною .
36494. Основи вакуумної техніки 120.78 KB
  Мірою кількості газу що переміщується у системі є величина яка згідно із рівнянням стану ідеального газу може бути записана як . Вакуумники люди консервативні тому міра газу визначається у несистемних одиницях : лмм рт. або лтор а всі розрахунки кількості газу ми будемо вести на одиницю часу. Швидкістю відкачки насосу будемо називати такий обєм газу який входить за одиницю часу до насосу і виміряний при тискові який має місце біля його входу .
36495. Термічна дифузія 233.6 KB
  Перший доданок являє собою потік взаємної дифузії молекул 1 газу а другий термодифузійний потік. На рисунку вихідні сталі відносні концентрації змінились і набули вигляду концентрація молекул першого газу біля першої пластини; концентрація молекул першого газу біля другої пластини; концентрація молекул другого газу біля першої пластини; концентрація молекул другого газу біля другої пластини. В результаті такої конвекції нагріта частина газу рухається відносно холодної створюючи провиток. Очевидно що температура газу поблизу проволоки...