Программирование игр и головоломок
Шрифт:
Нужно выбрать значение р, которое минимизирует эту сумму.
Первые несколько значений для /4 получить легко:
f4(1) = 1, f4(2) = 3, f4(3) = 5.
В этих случаях на самом деле есть только один способ действовать. Вычислите сначала на руках следующие значения. Воспользуйтесь вашим компьютером, чтобы составить таблицу, дающую последовательные значения для f4(n), вместе с оптимальным значением р для каждого n (оно не всегда однозначно определено. Вы по своему произволу можете выбирать из них наименьшее).
Игра 35.
Итеративная
Это замечание позволит вам перейти к любому числу стержней.
Игра 36.
Нужно снова взять все, что было нами оставлено в игре 23. Предположите, что для некоторого р существует такое значение q, что
SG(p, q) = 0.
Покажите, что в этом случае SG(р, q') = 0 для всех q' < q. Следовательно, если р таково, что SG(р, 1) = 0, то должно существовать некоторое g такое, что SG(р, g) = 0, но SG(р, g + 1) /= 0; g — наибольшее из значений q, дающих равенство SG(р, q) = 0.
Нужно построить последовательность pi, gi.
Вы можете показать, что если gi = 1, то pi+1 = pi + 2, в то время как если gi > 1, то pi+1 = pi + 3.
Хороший способ действия состоит в том, чтобы опереться на геометрические рассмотрения. Числа Спрага-Грюнди интересуют нас только с одной стороны— равны они нулю или нет (у нас нет намерения играть несколько игр одновременно, что избавляет нас от вычисления Ним-сумм и, следовательно, от заботы о значениях ненулевых чисел Спрага-Грюнди). Число Спрага-Грюнди равно нулю тогда и только тогда, когда невозможен никакой переход к нулевому числу. Но положение р, q допускает переходы к p– k, для k <= 2q. Следовательно, мы получим SG(p, q) = 0 тогда и только тогда, когда
SG(p– k, k) /= 0 для всех k от 1 до 2q.
Нарисуйте на плоскости две перпендикулярные оси, p как абсциссу и q как ординату. Обозначьте точки с нулевыми значениями SG.
Рассмотрите те прямые, которые проходят через точки p c SG(p, 1) = 0. Нужно изучить прямые p– k, k, где меняется от 1, т. е. те, которые параллельны биссектрисе второго и четвертого координатного угла и проходят через точку p– 1, 1.
Мы представили отрезок такой прямой
Для p = 34 диагональ, проходящая через 33, 1 проходит над всеми отрезками с 0 для p /= 0 и пройдет поэтому, пересекая ось q при q = 34. Поэтому нужно ограничить число k тридцатью тремя и, следовательно, взять g = 33 : 2 = 16.
У вас есть также некоторое число таких pi, что диагональ, выходящая из pi– 1, 1, не пересекает никакого отрезка нулей перед осью q, что дает gi = (pi– 1) : 2.
Исходя отсюда, следующие числа p определяются диагоналями, которые перерезают вертикальный отрезок, выходящий из pi так, что p– pi <= gi = (pi– 1) : 2. Тогда можно восстановить первоначальную последовательность, несущую нули, вплоть до (pi– 1) : 2.
Теперь вы легко сможете доказать, что интересующая нас последовательность pi есть последовательность чисел Фибоначчи.
Составьте программу, перечисляющую pi, gi.
6. Комбинаторные задачи
Головоломка 20. Полное решение.
Поскольку эта задача всюду решена, предложим также и здесь решение: это избавит вас от поисков других решений; и, кроме того, я буду уверен, что вы посмотрели на все существенные места этой задачи. Есть книги, которые… Но это — совсем другая история.
Заметим сначала, что два ферзя не могут находиться на одной строке (горизонтали) и, поскольку нужно поставить 8 ферзей на 8 строк, то на каждой строке есть ферзь. Поэтому я буду говорить «ферзь k» вместо «ферзь, стоящий на строке k».
Точно также, есть только один ферзь в каждом столбце. Но совершенно ясно, что я не могу управлять в одно и то же время размещением и по строкам и по столбцам — собственно, это от меня в задаче и требуется. Я собираюсь поэтому размещать ферзей на последовательных строках, начиная сверху.
Чтобы начать, я помещаю ферзя в первый столбец на первой строке. Тогда мне остается решить меньшую задачу; разместить 7 ферзей на 7 последних строках шахматной доски, учитывая, что ферзь стоит на первом поле первой строки. Я получу тогда все решения с ферзем 1 в столбце 1. Затем я поставлю ферзя 1 в столбец 2 и разрешу задачу с 7 ферзями, и т. д. — 8 раз.
Обобщим. Мы собираемся решить частную, но нужную задачу: полагая, что уже есть ферзи, правильно размещенные на строках от 1 до k– 1, и зная их положение, найти все возможные решения, размещая подходящим образом ферзей с номерами от k до 8. Обозначим программу, которая это делает, через HR(k) [24] . Стратегия очень проста:
24
Маленькая головоломка для знающих французский (или хотя бы имеющих словарь): откуда это обозначение? — Примеч. ред.