Жак Арсак - Программирование игр и головоломок

Здесь есть возможность читать онлайн «Жак Арсак - Программирование игр и головоломок» весь текст электронной книги совершенно бесплатно (целиком полную версию без сокращений). В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Город: Москва, Год выпуска: 1990, ISBN: 1990, Издательство: Наука. Гл. ред. физ.-мат. лит., Жанр: Программирование, на русском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.

Программирование игр и головоломок: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Программирование игр и головоломок»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

Рассматриваются способы программирования различных занимательных игр и головоломок с числами, геометрическими фигурами и др. Изложение большинства игр и головоломок ведется в несколько этапов. Сначала разъясняется сама постановка задачи и требования, предъявляемые к алгоритму ее решения.
В следующем разделе книги обсуждается сам алгоритм и возможные пути его реализации.
В конце книга по многим играм и головоломкам даются наброски их программной реализации. Используемый при этом язык типа Паскаля допускает перевод на другие широко распространенные языки программирования.
Для начинающих программистов, студентов вузов и техникумов.

Программирование игр и головоломок — читать онлайн бесплатно полную книгу (весь текст) целиком

Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «Программирование игр и головоломок», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Попытаемся охарактеризовать числа с помощью их цифрового представления. Изменить число — значит, изменить представляющие его цифры. Если использовать десятичное представление, то у нас в наличии 10 возможных цифр и их изучение затруднительно. Возьмем двоичное представление, для которого есть только две возможные цифры: 0 и 1. Уменьшение числа изменяет по крайней мере одну цифру этого числа, так что есть по крайней мере одна цифра 1, замененная на 0, или 0, замененный на 1. Этого должно хватить для того, чтобы заставить перейти от выигрывающего положения к проигрывающему положению. Число 0 встречаться не должно, поскольку пустые кучки, характеризующиеся нулевыми значениями, просто не считаются кучками. Характеризация выигрывающего положения должна быть поэтому связана с единицами различных чисел, записанных в двоичной системе.

Если есть две кучки с одинаковым числом спичек, то ситуация является выигрывающей. Следовательно, каково бы ни было число единиц в двоичном представлении каждого числа, положение является выигрывающим, если в каждом разряде наши два числа имеют либо 0, либо две цифры 1.

Первые выигрывающие комбинации с тремя кучками имеют вид

1, 2, 3, или в двоичной записи 01 10 11,

1, 4, 5, или в двоичной записи 001 100 101

Опять в каждом разряде наши три числа имеют либо 0, либо две цифры 1. Я разобрал достаточно случаев, чтобы подвести вас к результату К. Бутона (1902): положение является выигрывающим, если в каждом двоичном разряде суммарное число 1 двоичных представлений числа спичек в каждой кучке четно.

Совершенно очевидно, что нужно совершить прыжок для перехода от случая двух куч или первых примеров в случае трех куч к Наиболее общему случаю. Тут требуется выдумка или изобретение. Следует, иметь мужество признать, что некоторые люди имеют настоящий талант изобретать или открывать то, что совершенно не очевидно, и не всегда можно потом сказать: да никакой заслуги в этом нет, это было очевидно. Нет, это остается тайной, и преподавателя раздражает, если он оказывается вынужден давать результат, который нельзя легко «переоткрыть».

Назовем Ним-суммой двух целых чисел p и q число, которое вычисляется следующим образом:

p и q записываются в двоичной системе;

сложение выполняется поразрядно, по следующему правилу:

0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 0

(сложение без переноса в следующий разряд).

Рассмотрим игру, образованную объединением n независимых игр, каждая со своими собственными правилами. Игра проходит в кучке 1 но правилам R 1, в кучке 2 — по правилам R 2, … в кучке n — по правилам Rn . В каждой кучке мы располагаем числом Спрага-Грюнди, зависящим от числа спичек в этой кучке. Число Спрага-Грюнди есть Ним-сумма чисел Спрага-Грюнди в каждой кучке… [22] В частном случае, когда в каждой кучке игра идет по правилам игры Нима, число Спрага-Грюнди каждой кучки равно просто числу спичек. — Примеч. ред. Красиво, не правда ли?

Обратимся к программированию обычной игры города Нима (одно и то же правило для всех кучек: можно брать столько спичек, сколько пожелаешь, но не меньше одной). Вам нужно вычислить Ним-сумму данной ситуации. Если она равна нулю, то у вас нет шансов: ситуацию придется изменить и она перестанет быть выигрывающей. Вы можете, например, взять одну спичку из самой большой кучи: это — способ замедлить конец, и вы всегда можете ожидать, что ваш противник допустит ошибку…

Если же эта сумма не равна нулю, то это в точности означает, что есть разряды, в которых при двоичном представлении единицы встречаются нечетное число раз. Рассмотрим крайний левый из таких разрядов. Нужно уменьшить число единиц в этом разряде. Выберите кучку, содержащую единицу в этом разряде (все равно какую: взять ли самую большую, первую или последнюю…). Нужно уменьшить эту кучку на «эту» единицу. Кроме того, в любом другом (расположенном правее) разряде, где стоит нечетное число единиц, нужно

если в данной кучке в этом разряде стоит 1, удалить ее;

если в данной кучке в этом разряде стоит 0, заменить его на 1.

Это дает вам новое число спичек в этой кучке.

Я видел в некоторых книгах программы для игры Нима, в которых после обнаружения ситуации с ненулевой Ним- суммой испытывались все возможные конфигурации, чтобы найти конфигурацию с нулевой Ним-суммой. Над кем они смеются?

В игре Нима вам нужно для каждого хода, делаемого компьютером, получить двоичное представление числа спичек в каждой кучке. Вам следует решить, будете ли вы пересчитывать его при каждом ходе или вы будете сохранять различные представления, так как имея единственное представление, вы после каждого хода должны изменять его…

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Похожие книги на «Программирование игр и головоломок»

Представляем Вашему вниманию похожие книги на «Программирование игр и головоломок» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё непрочитанные произведения.


Отзывы о книге «Программирование игр и головоломок»

Обсуждение, отзывы о книге «Программирование игр и головоломок» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.

x