Головоломка «Отшельник». Реализации решения «выигрывающих стратегий»::Журнал СА 10.2014
www.samag.ru
     
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
Журнал "Системный администратор"
Журнал «БИТ»
Подписка
Архив номеров
Где купить
Наука и технологии
Авторам
Рекламодателям
Контакты
   

  Опросы
  Статьи

Дата-центры  

Дата-центры: есть ли опасность утечки данных?

Российские компании уже несколько лет испытывают дефицит вычислительных мощностей. Рост числа проектов,

 Читать далее...

Книжная полка  

Защиты много не бывает

Среди книжных новинок издательства «БХВ» есть несколько изданий, посвященных методам социальной инженерии

 Читать далее...

Событие  

В банке рассола ждет сисадмина с полей фрактал-кукумбер

Читайте впечатления о слете ДСА 2024, рассказанные волонтером и участником слета

 Читать далее...

Организация бесперебойной работы  

Бесперебойная работа ИТ-инфраструктуры в режиме 24/7 Как обеспечить ее в нынешних условиях?

Год назад ИТ-компания «Крок» провела исследование «Ключевые тренды сервисного рынка 2023». Результаты

 Читать далее...

Книжная полка  

Читайте и познавайте мир технологий!

Издательство «БХВ» продолжает радовать выпуском интересных и полезных, к тому же прекрасно

 Читать далее...

СУБД PostgreSQL  

СУБД Postgres Pro

Сертификация по новым требованиям ФСТЭК и роль администратора без доступа к данным

 Читать далее...

Критическая инфраструктура  

КИИ для оператора связи. Готовы ли компании к повышению уровня кибербезопасности?

Похоже, что провайдеры и операторы связи начали забывать о требованиях законодательства

 Читать далее...

Архитектура ПО  

Архитектурные метрики. Качество архитектуры и способность системы к эволюционированию

Обычно соответствие программного продукта требованиям мы проверяем через скоуп вполне себе понятных

 Читать далее...

Как хорошо вы это знаете  

Что вам известно о разработках компании ARinteg?

Компания ARinteg (ООО «АРинтег») – системный интегратор на российском рынке ИБ –

 Читать далее...

Графические редакторы  

Рисование абстрактных гор в стиле Paper Cut

Векторный графический редактор Inkscape – яркий представитель той прослойки open source, с

 Читать далее...

День сисадмина  

Учите матчасть! Или как стать системным администратором

Лето – время не только отпусков, но и хорошая возможность определиться с профессией

 Читать далее...

День сисадмина  

Живой айтишник – это всегда движение. Остановка смерти подобна

Наши авторы рассказывают о своем опыте и дают советы начинающим системным администраторам.

 Читать далее...

Виртуализация  

Рынок решений для виртуализации

По данным «Обзора российского рынка инфраструктурного ПО и перспектив его развития», сделанного

 Читать далее...

Книжная полка  

Как стать креативным и востребованным

Издательский дом «Питер» предлагает новинки компьютерной литературы, а также книги по бизнесу

 Читать далее...

1001 и 1 книга  
19.03.2018г.
Просмотров: 6311
Комментарии: 0
Машинное обучение с использованием библиотеки Н2О

 Читать далее...

12.03.2018г.
Просмотров: 7020
Комментарии: 0
Особенности киберпреступлений в России: инструменты нападения и защита информации

 Читать далее...

12.03.2018г.
Просмотров: 4302
Комментарии: 0
Глубокое обучение с точки зрения практика

 Читать далее...

12.03.2018г.
Просмотров: 3056
Комментарии: 0
Изучаем pandas

 Читать далее...

12.03.2018г.
Просмотров: 3852
Комментарии: 0
Программирование на языке Rust (Цветное издание)

 Читать далее...

19.12.2017г.
Просмотров: 3868
Комментарии: 0
Глубокое обучение

 Читать далее...

19.12.2017г.
Просмотров: 6359
Комментарии: 0
Анализ социальных медиа на Python

 Читать далее...

19.12.2017г.
Просмотров: 3211
Комментарии: 0
Основы блокчейна

 Читать далее...

19.12.2017г.
Просмотров: 3502
Комментарии: 0
Java 9. Полный обзор нововведений

 Читать далее...

16.02.2017г.
Просмотров: 7322
Комментарии: 0
Опоздавших не бывает, или книга о стеке

 Читать далее...

17.05.2016г.
Просмотров: 10685
Комментарии: 0
Теория вычислений для программистов

 Читать далее...

30.03.2015г.
Просмотров: 12409
Комментарии: 0
От математики к обобщенному программированию

 Читать далее...

18.02.2014г.
Просмотров: 14050
Комментарии: 0
Рецензия на книгу «Читаем Тьюринга»

 Читать далее...

13.02.2014г.
Просмотров: 9172
Комментарии: 0
Читайте, размышляйте, действуйте

 Читать далее...

12.02.2014г.
Просмотров: 7119
Комментарии: 0
Рисуем наши мысли

 Читать далее...

10.02.2014г.
Просмотров: 5428
Комментарии: 3
Страна в цифрах

 Читать далее...

18.12.2013г.
Просмотров: 4660
Комментарии: 0
Большие данные меняют нашу жизнь

 Читать далее...

18.12.2013г.
Просмотров: 3465
Комментарии: 0
Компьютерные технологии – корень зла для точки роста

 Читать далее...

04.12.2013г.
Просмотров: 3191
Комментарии: 0
Паутина в облаках

 Читать далее...

03.12.2013г.
Просмотров: 3434
Комментарии: 0
Рецензия на книгу «MongoDB в действии»

 Читать далее...

02.12.2013г.
Просмотров: 3063
Комментарии: 0
Не думай о минутах свысока

 Читать далее...

Друзья сайта  

 Головоломка «Отшельник». Реализации решения «выигрывающих стратегий»

Архив номеров / 2014 / Выпуск №10 (143) / Головоломка «Отшельник». Реализации решения «выигрывающих стратегий»

Рубрика: Карьера/Образование /  Пятая пара

Кирилл Ткаченко КИРИЛЛ ТКАЧЕНКО, аспирант, Севастопольский национальный технический университет, tkachenkokirillstanislavovich@gmail.com

Головоломка «Отшельник»
Реализации решения «выигрывающих стратегий»

Существует определенный класс головоломок, который можно назвать «выигрывающие стратегии» [1] – их суть состоит в нахождении выигрышной стратегии. Широко известна головоломка «Отшельник» или «English peg solitaire» [2] с 32 колышками (фишками)

Правила головоломки таковы: на крестообразном игровом поле (см. рис. 1) в начале игры находится 32 колышка (обозначенные символом «х») и одно свободное место (обозначенное символом «-»).

Рисунок 1. Начальное состояние игрового поля

Рисунок 1. Начальное состояние игрового поля

Все возможные ходы состоят в том, что колышек может «съесть» другой колышек, «перепрыгнув» через него на свободное место либо по горизонтали, либо по вертикали. Так, два последовательных хода из начальной позиции изображены на рис. 2, 3.

Рисунок 2. Состояние игрового поля после первого хода

Рисунок 2. Состояние игрового поля после первого хода

Рисунок 3. Состояние игрового поля после второго хода

Рисунок 3. Состояние игрового поля после второго хода

При этом игра (решение головоломки) может заканчиваться, когда на доске остается один колышек (см. рис. 4).

Рисунок 4. Вероятное последнее состояние игрового поля

Рисунок 4. Вероятное последнее состояние игрового поля

Одной из существующих программных реализаций является [3] пример использования возможностей языка программирования Go. Укрупненный и упрощенный алгоритм функционирования [3] следующий:

  • 1. Начальная позиция рассматривается как текущее поле.
  • 2. Для каждой позиции поля выполняются пп.3-8.
  • 3. Если в рассматриваемой позиции поля нет колышка, то п.2.
  • 4. Для всех возможных направлений выполняются пп.5-8.
  • 5. Если возможно выполнить съедение колышка колышком в указанном направлении, то пп.6-8.
  • 6. Выполняется «перескок колышка со съедением».
  • 7. Рекурсивно вызывается 2.
  • 8.1. Происходит отмена «перескока колышка со съедением».
  • 8.2. Если вызов прошел с успехом, то выводится состояние поля и происходит возврат с успехом.
  • 9. Если остался один колышек, то вывод состояния поля и возврат с успехом, иначе возврат с неуспехом.

Далее будет рассматриваться модифицированный алгоритм, для которого схема основной рекурсивной функции выбора хода приводится на рис. 5. При этом используются паскале-подобные обозначения (некоторые отклонения от норм и требований к схемам алгоритмов обусловлены предельными значениями журнальной страницы).

На рис. 5 и в нижеследующих листингах используются обозначения переменных (полей), сведенные в таблицу 1.

Рисунок 5. Алгоритм функционирования рекурсивной функции выбора хода

Рисунок 5. Алгоритм функционирования рекурсивной функции выбора хода

Таблица 1. Переменные (поля)

Название Описание
1. PEG Символ, обозначающий колышек на игровой доске
2. HOLE Символ, обозначающий пустое место на игровой доске
3. line Длина строки игрового поля, включая символ-терминатор
4. directions Массив, содержащий разницу между целевым полем и текущим для направлений
5. board Строковая (или подобная ей) переменная, хранящая игровое поле
6. noOfTests Число проведенных проверок возможности хода
7. position Текущая рассматриваемая позиция поля
8. direction Текущее рассматриваемое направление поля
9. idir Номер текущего рассматриваемого направления поля
10. isSolved Факт успешности рекурсивного вызова
11. pegsOnBoard Количество колышков на доске
12. canMove Возможно ли выполнить съедение в заданном направлении

Перед реализацией на нескольких языках программирования разумно проверить, в каком порядке нужно производить обход направлений при проверке возможности совершения игрового хода. Для этих целей разрабатывается программа, приведенная в листинге 1. В дальнейшем предполагается, что массив для представления игрового поля одномерный; направление задается разницей индексов целевого и рассматриваемого полей.

Статью целиком читайте в журнале «Системный администратор», №10 за 2014 г. на страницах 82-85.

PDF-версию данного номера можно приобрести в нашем магазине.


Комментарии отсутствуют

Добавить комментарий

Комментарии могут оставлять только зарегистрированные пользователи

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-45
E-mail: sa@samag.ru