Программирование игр и головоломок - [71]
Разобранный пример хорошо иллюстрирует тесную связь между рекурсивностью и рекуррентностью, которые представляют собою не что иное, как две немного отличающиеся реализации одного и того же рассуждения.
Игра 33.
Предположите, что в Н (n − 1, d, а) диск 1 перемещается всегда в одном и том же направлении. Для Н (n, d, а) вы должны выполнить
Н (n − 1, d, 3 − а − d)
Н (n − 1, 3 − а − d, а).
Вместо того, чтобы непосредственно переходить от d к а, вы осуществляете этот переход с помощью стержня 3 − а − d, иначе говоря, вы делаете два перемещения в обратном направлении. Диск 1 продолжает перемещаться всегда в одном и том же направлении, но это направление меняется при переходе от n − 1 к n. Для n = 1 этот диск перемещается в направлении от d к а. Это всегда будет так для всех нечетных n, в то время как для четных n он будет перемещаться в направлении от а к d.
Простое итеративное решение имеет следующий вид: исходя ив четности n определите направление перемещения диска 1. Начните с 2>n − 1 число ходов, которые осталось сделать:
>s := ЕСЛИ четно (n) ТО 2 ИНАЧЕ 1 КОНЕЦ_ЕСЛИ
>d := 0; k:= 2>n − 1
>ВЫПОЛНЯТЬ
> а := d + s; ЕСЛИ a > 2 ТО а := а − 8
> КОНЕЦ_ЕСЛИ
> переместить диск 1 с d на а;
> d : = a; k := k − 1
> ЕСЛИ k = 0 TO КОНЧЕНО КОНЕЦ_ЕСЛИ
> переместить единственный диск, который можно переместить, кроме диска 1
> k := k − 1
>ВЕРНУТЬСЯ
Все диски имеют общее свойство: нечетные диски перемещаются в том же направлении, что и диск 1, а четные диски — в другом направлении.
В вышеприведенной программе стратегия совершенна с точки зрения исполнения вручную, потому что в каждый данный момент сразу видно, какой диск нужно переместить, если это не самый маленький диск (меньший из двух остальных дисков перемещается на больший). В нашей программе вам нужно вычислить это движение. Один из наиболее простых способов состоит в том, чтобы представить игру с помощью вектора, дающего для диска i номер стержня, на котором он находится. Диск, подлежащий перемещению — это наименьший Диск, который находится не на том же стержне, что и диск 1, следовательно, номер стержня которого отличается от d. Этот самый диск перемещается со стержня, на котором он находится — с номером x — на стержень 3 − x − d.
Обозначим первое перемещение через 1. Поскольку диск 1 перемещается один раз в каждой паре ходов (точнее, перемещается через ход), то он перемещается в каждый нечетный ход. По индукции покажите, что диск p перемещается в ходы с номерами, которые делятся на 2>р−1, но не делятся на 2>p (т. е. являются нечетными кратными числа 2>p−1).
Номер k любого хода может быть единственным способом представлен в виде
k = (2r + 1)2>р-1.
Перемещаемый на этом ходе диск есть диск с номером p, и это — его (r + 1)-е перемещение. Так как он начинает движение со стержня 0 и перемещается в направлении s>p (1, если р нечетно, и 2 в противном случае), то на этом ходе диск перемещается с rs>p-го на (r + 1)s>р-й стержень, где эти числа берутся по модулю 3.
Игра 34.
Попытаемся охарактеризовать значение р, дающее игре оптимум для данного n. Нам известно, что f>3(n − p)= 2>n-p − 1.
Должно выполняться
2f>4(p − 1) + 2>n-p+1 − 1 ≥ 2f>4(р) + 2>n-p − 1,
2f>4(p + 1) + 2>n-p-1 − 1 ≥ 2f>4(р) + 2>n-p − 1.
Удобно пользоваться первыми разностями для функции f>4:
d(р) = f>4(p + 1) − f>4(p).
Два приведенных выше соотношения могут быть переписаны следующим образом:
d(p − 1) < 2>n-p-1, d(р) ≥ 2>n-p-2.
Интересно рассматривать даже не d(р), а скорее 2>pd(р) = g(р):
g(р − 1) ~ 2>n-2 ≤ g(р).
Можно еще упростить запись, беря не g(р), а величину
h(р) = log>2(g(р)) = р + Iog>2(d(р)).
Тогда получаем
h(р − 1) < n − 1 ≤ h(р).
При данном n величина р — наименьшее целое, для которого h больше или равно n − 2.
Приведем здесь первые из полученных таким образом значений:
| n | q | f>4 | p | d | h |
| 0 | 0 | 0 | 1 | 0 | |
| 1 | 1 | 1 | 2 | 2 | |
| 2 | 3 | 2 | 3 | ||
| 3 | 2 | 5 | 1 | 4 | 5 |
| 4 | 9 | 1 | 4 | 6 | |
| 5 | 13 | 1 | 4 | 7 | |
| 6 | 3 | 17 | 3 | 8 | 9 |
| 7 | 25 | 3 | 8 | 10 | |
| 8 | 33 | 4 | 8 | 11 | |
| 9 | 41 | 5 | 8 | 12 | |
| 10 | 4 | 49 | 6 | 16 | 14 |
| 11 | 65 | 6 | 16 | 15 |
Мы добавили в таблицу переменное q, связанное с «треугольными» числами. Для n = q(q + 1)/2 действительно убеждаемся, что
h(р) = h(р − 1) + 2
в то время как для других n
h(p) = h(p − 1) + 1.
Исходя из n, можно вычислить q:
q = целая_часть ((
Имеем
h(n) = n + целая_часть ((
Покажите это по индукции. Исходя отсюда, вычисляется все. Таким образом, если n дано, то р — наименьшее целое, большее или равное
(2n − 1 −
Игра 35.
Возьмем, например, игру с 50 дисками. Она реализуется переносом сначала 40 дисков на запасной стержень, а затем 10 последних дисков со стержня 0 на стержень 1, с использованием при этом только трех свободных стержней. Наконец, остается перенести начальные 40 самых маленьких дисков с запасного стержня на первый стержень, используя все 4 стержня.
Чтобы переместить 40 дисков с 4 стержнями, сводим задачу к перемещению 31 диска с 4 стержнями, а затем 9 с 3 стержнями…
Таким образом, дело сводится к разбиению 50 дисков на 8 сегментов:
Каждый сегмент перемещается с использованием 3 стержней, в чем мы следуем итеративной стратегии, которая уже описана выше. Единственный вопрос — это правильный выбор запасных стержней.
Договоримся работать с тремя стержнями 0, 1, 2, так что стержень 3 остается пустым и служит запасным стержнем при любом перемещении какого-либо сегмента. Более точно, перемещение сегмента
