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

средневековой игре? — Позицией является состав выложенных на стол карт, а также их значения: сколько карт на столе имеет значение 1, сколько карт имеет значение 2, и т. д. Сумма, набранная игроками в данный момент, равна 84 минус сумма значений карт на столе. Что же имеет в виду автор книги, когда он пишет SG(50)? Почему он приписывает число Спрага-Грюнди не позиции, а сумме карт этой позиции? Дело в том, что для всех позиций с набранной суммой 50 число Спрага-Грюнди одинаково и равно 0. Это и позволяет написать равенство SG(50) = 0. А что могло бы значить SG(49)? Если бы все позиции с суммой 49 имели одинаковое число SG, мы бы обозначили его SG(49). Но, увы! Разные позиции с суммой 49 имеют разные числа Спрага-Грюнди. Так что автор книги дальше рассуждает о несуществующих вещах. Я из этих рассуждений ничего полезного извлечь не смог (кроме подозрения, что у автора нет работающей программы, играющей в 24 карты). — Примеч. ред.

(обратно)

21

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

(обратно)

22

В частном случае, когда в каждой кучке игра идет по правилам игры Нима, число Спрага-Грюнди каждой кучки равно просто числу спичек. — Примеч. ред.

(обратно)

23

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

(обратно)

24

Маленькая головоломка для знающих французский (или хотя бы имеющих словарь): откуда это обозначение? — Примеч. ред.

(обратно)

25

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

(обратно)

26

Если разрешить перемещать каждый элемент вектора не один раз, а два, то можно найти изящное и простое решение, в котором и речи нет ни о каких общих делителях. Представим себе элементы вектора расположенными по окружности на равных расстояниях друг от друга. Нам нужно повернуть эти векторы на угол. Используйте тот факт, что всякий поворот окружности можно получить, выполнив подряд две осевые симметрии. — Примеч. ред.

(обратно)

27

См. головоломку 29. — Примеч. пер.

(обратно)

28

В математике для решения этой задачи есть полезная формула Ньютона-Лейбница:

где F —функция, определяемая условием F(x) = f(x), x ∊ [p, q]. Впрочем, все эти интегралы нам не понадобятся, так как у этой формулы есть гораздо более простой аналог для сумм: ai + ai+1 + … + aj = bj − bi−1, где последовательность {b} определяется условием, что bk − bk−1 = аk для любого k от 1 до n. Последовательность {b} легко построить: b0 = 0, bk+1 = bk + ak+1. Для последовательности {b} задача ставится так: найти такие i < j, что разность bj − bi максимальна. С этой задачей уже легче справиться. — Примеч. ред.

(обратно)

29

Вот пара условий, которая не обладает этим свойством: t: x ≠ 0; u: sin(1/x) > 0. — Примеч. ред.

(обратно)

30

Прочтя весь этот ужас, я решил провести решение, основанное на методике из курса программирования механико-математического факультета МГУ.

Каждой последовательности чисел {a1, а2, …, ai} (i ≥ 1) сопоставим число lmax, равное максимальной длине равнинного участка этой последовательности. Очевидно, что lmax ({a1}) = 1. Пусть мы знаем lmax ({a1, а2, …, ai}). Как вычислить величину lmax ({a1, …, ai, ai+1})? Добавление элемента ai+1 к последовательности {a1, а2, …, ai} не затрагивает равнинных участков этой последовательности, кроме, быть может, последнего. Если ai+1 = ai, то длина этого последнего участка — назовем ее llast ({a1, …, ai}) — увеличивается на единицу. Если величина llast ({a1, …, ai, ai+1}) окажется при этом больше величины lmax ({a1, а2, …, ai}), то это значит, что последний равнинный участок --">