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

Если представить игру в виде 3 строк с помощью последовательностей чисел, то, таким образом, достаточно снять крайнее правое число со строки н и присоединить его справа к строке к.

Если вы хотите представить стержни вертикально, создайте, кроме того, внутреннее представление с помощью трех цепочек символов и составьте процедуру вывода на экран. Это, как кажется, проще всего. Если вы не любите цепочек символов, используйте три таблицы, но вы не выиграете в легкости.

Игра 33.

Если ваш компьютер допускает рекурсию, заставьте работать рекурсивную процедуру и понаблюдайте за движением дисков. В противном случае выполните вручную рекурсивную процедуру для маленького n (например 4), что поможет вам наглядно увидеть то, что уже доказано: два диска одинаковой четности не могут оказаться друг на друге.

Вы должны заметить, что

— диск с номером 1 перемещается один раз за любые два хода,

— он перемещается циклически, причем всегда в одном направлении, а именно

либо 0 — 1 1 — 2 2 — 0…

либо 0 — 2 2 — 1 1 — 0…

Следующий ход, перемещающий диск с номером 1, полностью определен. Недостаточно проверить это, это нужно доказать. После этого итеративное решение тривиально. Можете ли вы априори определить перемещение диска с номером 1 в зависимости от четности числа дисков?

Можете ли вы сказать что-нибудь о движении остальных дисков?

Пронумеруйте ходы. Диск с номером 1 перемещается в ходах с нечетными номерами. Проверьте, а затем докажите, что диск с номером 2 перемещается в ходах с номерами 2, 6, 10, …, т. е. в ходах, номер которых кратен двум, но не кратен четырем. Обобщите. Исходя отсюда, вы можете сказать, зная номер хода, какой диск будет перемещаться, с какого стержня он уйдет и куда придет.

Красиво, не правда ли?

Игра 34.

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

f4(р) — число ходов для перемещения р дисков, используя 4 стержня;

f3(р) — число ходов для перемещения р дисков, используя 3 стержня (известное число, см. игру 31).

Тогда наша стратегия дает

f4(n) = f4(р) + f3(n−p) + f4(р).

Нужно выбрать значение р, которое минимизирует эту сумму.

Первые несколько значений для /4 получить легко:

f4(1) = 1, f4(2) = 3, f4(3) = 5.

В этих случаях на самом деле есть только один способ действовать. Вычислите сначала на руках следующие значения. Воспользуйтесь вашим компьютером, чтобы составить таблицу, дающую последовательные значения для f4(n), вместе с оптимальным значением р для каждого n (оно не всегда однозначно определено. Вы по своему произволу можете выбирать из них наименьшее).

Игра 35.

Итеративная программа для игры с 4 стержнями есть обобщение итеративной программы для игры с 3 стержнями. Это видно по рекурсивной форме. Она не идеально проста…

Это замечание позволит вам перейти к любому числу стержней.

Игра 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 = 28 (см. рис. 38). Он пересекает точку с нулевым значением на вертикали 21 = 28 − 7. Значит, нужно ограничить число k шестью, задавая g = 3 при p = 28.

Для 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]. Стратегия очень проста:

— мы пробегаем все поля на строке k,

— если поле свободно (т. е. не бьется уже поставленными ранее ферзями), то мы ставим на него ферзя k и решаем ту же задачу для k + 1.

При k = 8 задача проще всего. Не может быть более одного свободного столбца. Если он есть, то мы ставим туда последнего ферзя и записываем полученное таким образом решение. Если свободного столбца нет, то нет и решения.