Если представить игру в виде 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.
Головоломка 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 задача проще всего. Не может быть более одного свободного столбца. Если он есть, то мы ставим туда последнего ферзя и записываем полученное таким образом решение. Если свободного столбца нет, то нет и решения.
![И Печальный - Геймер[СИ]](/uploads/posts/books/no-image.jpg)
