1. Случайные числа

Головоломка 1.

Первая стратегия. Нужно сравнить u2 i и u i . Они равны, если 2i = i + kp для целого k, следовательно, если i делится на p. Кроме того, i должно превосходить r. Следовательно, нужно искать наименьшее кратное p, большее или равное r.

Положим v i = u2 i . Тогда

v i +1 = u2 i +2 = f(f(u2 i )) = f(f(v i )).

Если вы начинаете u с u1 = a, то вы начинаете v с v1 = f(а).

Таким образом, получаем начало программы:

u := a ; v := f ( а )

ПОКА u ≠ v ВЫПОЛНЯТЬ

   u := f ( u ); v := f ( f ( v ))

ВЕРНУТЬСЯ

Теперь вы получили два равных элемента. Чтобы получить период, нужно пройти интервал между полученными числами — например, начиная с u — считая число элементов:

p := 1; w := f ( u )

ПОКА w ≠ u ВЫПОЛНЯТЬ

   w := f ( w ); p := p + 1

ВЕРНУТЬСЯ

Мне пришлось рассказать вам все…

Вторая стратегия. Начните с d = 1 и h = 1. Если вы не находите периодичности в интервале от d + 1 до d + h (сравнивая u на этом интервале со значением u на элементе d, сохраняемым в некоторой переменной, например, x), возьмите значение u в d + h в качестве нового значения x, d + h в качестве нового d, и удвойте k.

Вы непосредственно получаете период. Тщательно подсчитайте количество вычислений f в каждом из этих двух алгоритмов. Второй способ определенно лучше,

Игра 4.

Если вы представляете игровое ноле прямоугольной таблицей, то перемещение обозначается изменением координат точки: добавлением или вычитанием чисел 1 или 2. Я разместил эти добавляемые количества (целые числа со знаком) в два вектора DX, DY из 8 элементов. Одно направление перемещения задается номером поля в этой таблице, следовательно, целым числом от 1 до 8.

 

2. Игры с числами

Головоломка 3.

Остановитесь, когда вы получите 5 в качестве цифры единиц с нулем «в уме».

Головоломка 4.

Представленный здесь алгоритм эквивалентен алгоритму, который можно найти в старых книгах по арифметике, и который действует на целые числа, разбитые на куски но 2 цифры в каждом куске. Вы можете либо разыскать доказательство в этих книгах, либо посмотреть в моей книге «Основы программирования», как можно доказать, что программа, реализующая этот алгоритм, действительно вычисляет квадратный корень. Но это рассуждение слишком сложно, чтобы воспроизводить его здесь.

Лично я работаю по основанию 10. Я представляю числа цепочками цифр. Присоединить 1 справа легко: это просто конкатенация. Сдвинуть вправо легко: используется индекс, сообщающий, начиная с какой позиции нужно урезать. Именно этот индекс и изменяется. Складывать с 2 легко, так как может быть не более одного переноса. Единственная тонкая операция — вычитание, Не проводите сравнения перед вычитанием: оно стоит так же дорого, как и само вычитание. Сделайте копию той части, которая должна была бы быть изменена при вычитании, и если вы обнаружите, что вы не можете осуществить вычитание, — возьмите сохраненное значение.

Головоломка 5.

Задайте три индекса и три значения: i2, i3, i5, x2, x3, x5. Число i2 есть индекс элемента последовательности, который, будучи умноженным на 2, дает подходящего кандидата на роль ближайшего значения (иначе говоря, удвоение числа с индексом i2 − 1 дает число, которое содержится в уже сформированной части последовательности, но удвоение числа с индексом i2 дает число, которое в сформированной части не содержится). Число x2 получается удвоением числа с индексом i2. Вы определяете аналогично i3 и x3 заменяя «удвоение» на «утроение» (произведение на 3 числа с индексом i3 − 1 содержатся в построенной части последовательности, а число x3 — утроенное число с индексом i3 — в ней не содержится). Наконец, вы делаете то же самое для i5 и x5. Ближайшее число в последовательности есть наименьшее из чисел x2, x3, x5. Назовем его х. Если x = x2, то i2 увеличивается на 1 и x2 пересчитывается. То же самое для i3 и i5.

Головоломка 7.

Возьмем n = 3n' + 2. Тогда (2n − 1)/3 = 2n' + 1.

По общему правилу, непосредственно следующий за нечетным числом 2n' + 1 элемент равен (3(2n' + 1) + 1)/2 = 3n' + 2.

Если n дает n' при переходе (p, q), q > 1, т. е. если n имеет вид n = (2p(2qn' + 1)/3p ) − 1, то

n'' = (n − 1)/2 = (2p −1 (2q n ' + 1)/Зp ) − 1.

Как и следовало ожидать, это имеет в точности тот смысл, что если деление на Зp можно выполнить нацело, то в связи с этим возникает соотношение между (p, q) и n'.

Если n" увеличить на 1, а затем умножить на 3p −1 /2p −1 , то получится (2q n ' + 1)/3.

Тогда нужно уменьшить результат на 1: получим (2q n ' − 2)/3. Но это число делится на 2, так что с помощью перехода (p − 1, 1) число n" дает

(2q −1 n' − 1)/3.

По общим правилам получаем

3 ((2q −1 n' − 1)/3) + 1 = 2q −1 n',

а затем n', что и доказывает наше утверждение.

Если вы примените это правило перехода к 4k + 1, то нужно добавить 1, что дает 4k + 2, делящееся на 2, но не на 4. Делим на 2 и умножаем на 3, что дает 6k + 3. Уменьшаем на 1 и затем делим на 2, и получается Зk + 1.

Если k нечетно, то это — элемент, следующий за k; так что за числом вида 4k + 1 с k нечетным следуют те же величины, что и за k.

Если k четно, то 4k + 1 дает 3k + 1.

Если существует цикл с единственным переходом p, q, т. е.

n = (2p (2q n + 1)/3p ) − 1,

то это возможно только в случае, когда существует такая пара p, q, что число

(Зp − 2p )/(2p + q − Зp )

— целое. Мы показали, что такой пары (p, q) нет.

Головоломка 10.

9*АВСДЕ + АВСДЕ = 10*АВСДЕ, что можно записать как АВСДЕ0. Отсюда получаем зашифрованное сложение:

FGHIJ + ABCDE = ABCDE0

Это показывает, что A = 1. Далее, J + E не может быть нулем, следовательно, J + Е = 10 и для I есть кое-что «в уме». Сумма F + A дает AB с A = 1, так что сумма F + 1, к которой, может быть, добавлено что-то «в уме», должна дать число, большее 9. Это может быть только в случаях 1 + 8 + 1 = 10, 9 + 1=10 или 1 + 9 + 1 = 11. Но, так как B ≠ A, то B = 0.

Тогда в сумме G + B рассмотрим цифру C как цифру единиц. Так как В = 0, то это означает, что для G «в уме» кое-что есть (потому что G ≠ С).

Отсюда получаем схему операции сложения:

Запишем, что A + B + C + D + E + F + G + H + I + J = 45,

А = 1, B = 0.

Запишем пять операций сложения с учетом переносов в старший разряд:

J + E = 10,

1 + I + D = 10k + E,

k + H + C = 10 + D,

1 + G + В = 10k' + С,

k' + F + A = 10.

Сложим их все. Вам остается

C + D + E = 17 − 9(k + k').

Но С + D + E не может быть меньше, чем 2 + 3 + 4 = 9, и не может быть больше, чем 6 + 7 + 9 (если F = 8 и k' = 1). Не может быть, чтобы у вас одновременно выполнялись соотношения k = k' = 1 (что давало бы отрицательную сумму С + D + E). Но не может быть и равенства k + k' = 1, так как тогда было бы С + D + E = 17 − 9 = 8, что слишком мало. Следовательно, k = k' = 0. Составим окончательную систему

J + E = 10,

I + D + 1 = E,

H + C = 10 + D,

G + 1 = С,

F = 9.

Закончите вы с помощью программы.

Головоломка 11.

Обозначим через a i цифры исходного числа, b i — цифры результата, k i — цифры «в уме»:

3a i + k i = b i + 10ki +1 .

Сумма всех a i равна 45, как и сумма всех b i . Обозначим через K сумму всех k i :

3*45 + K = 45 + 10*K дает К = 10.

Мы знаем, что дает «в уме» каждая цифра:

1 дает 0, 2 дает 0, 3 дает 0 или 1 в зависимости от того, что хранится «в уме» над 3.

4 дает 1, 5 дает 1, 6 дает 1, потому что не может случиться 3*6 + 2, что давало бы «в уме» 2, но цифру единиц 0;

7, 8 и 9 дают 2.

Для того, чтобы сумма величин «в уме» была равна 10, нужно, чтобы 3 давало 1 «в уме». Так как 3*3 + 1 (с цифрой единиц, равной 0) случиться не может, то нужно, чтобы «в уме» над 3 было 2. Следовательно, 3 стоит слева от 7, 8 или 9. В частности, 3 не может стоять на правом конце.

Остальное просто, если вы будете следовать методу, указанному в разделе «Условия». Вот таблица:

Потребуем, чтобы 9 было справа; следовательно, вычеркнем 9 из этой таблицы, оставив его только в столбце, соответствующей тому, что «в уме» 0. Цифра 3 требует 2 «в уме», чтобы дать 1. Вычеркнем остальные 3 в таблице. Цифра 9 не может быть получена иначе как с помощью 6 и 1 «в уме». Другие 6 вычеркиваем. Цифра 8 получается из 2 при 2 «в уме». Нужно взять 3 числа в первом столбце, так что нужно еще одно не равное ни 2, ни 3. Их нужно 4 в среднем столбце, так что нужно еще 3 числа, ре равных 6, которые нужно взять среди цифр 7, 4, 1, 8, 5. Два последних числа должны быть взяты из столбца с нулем «в уме». Когда эти числа среди всех возможных будут выбраны, останется расположить их в соответствии с тем, что должно быть для них «в уме». Эту программу сделать легко.

Головоломка 12.

Если число a1a2…a p (представленное как последовательность цифр) кратно 3, то и a1 + а2 + … + a p кратно 3. Сумма кубов цифр равна

a13 + а23 + … + a p 3.

Нужно показать, что это число также кратно 3. Действуйте по индукции по числу слагаемых. Предположим, что для p = n − 1 членов

a13 + а23 + … + a p 3 = (a1 + … + a p )3 по модулю 3; тогда равенство

(a1 + … + a p + a n )3 = (a1 + … + a p )3 + a n 3 + 3 (…)

доказывает наше утверждение для n слагаемых.

Возьмите число с k цифрами. Сумма кубов его цифр ограничена величиной k*93. Но исходное число не может быть меньше, чем 10k−1. Следовательно, достаточно, чтобы 10k−1 было больше, чем k*729, что очевидным образом выполняется при k = 5. Но эта оценка слишком пессимистична.

Головоломка 14.

Число, полученное при обращении порядка цифр, равно

1000d + 100c + 10b + a,

и разность этих двух чисел равна

999 (a − d) + 90 (b − c).

Числа a, b, c, d были расположены в невозрастающем порядке, и они не все равны между собой, так что a строго больше d и a − d не равно нулю. Все остальное просто.

Головоломка 16.

Единственное, что до сих пор еще не сказано — это способ определять, становится» ли последовательность периодической. Метод Полларда был основан на первой стратегии. Мы выясняем, существует ли a i с a2 i = a i . Но вычисление f(x) = x2 − 1 по модулю n — дорогое вычисление. Брепт улучшил этот метод, предложив использовать вторую стратегию.

Головоломка 17.

Эта программа основана на следующих результатах:

если b нечетно, n четно, то n делится на b тогда и только тогда, когда n/2 делится на b;

нечетное n делится на b тогда и только тогда, когда n − b делится на b. Но n − b четно.

Для n = 277 − 3 и b = 7 вы получаете:

Число n нечетно. Рассматриваем n − b = 277 − 10. Оно делится на 2: получаем 276 − 5.

Это число нечетно: (276 − 5) − 7 = 276 − 12.

Делим на 4: 274 — 3.

Получаем ту же самую задачу, в которой показатель уменьшен на 3. Так как 77 = 3*25 + 2, то мы таким образом доходим до 22 — 3 = 1, которое не делится на 3. Вряд ли вас слишком утомит доказательство того, что 2n − 3 никогда не делится на 7…

Головоломка 18.

Я не в состоянии рассказать вам, как я получил эту программу, это — очень долгая история, связанная с разложением целых чисел на множители. Может быть, когда-нибудь я ее и опубликую. Следовательно, будем разбираться в том, что нам дано — в тексте программы.

Начнем с нечетного n. В соответствии с инициализацией программы n = 4p − 1, где p четно. В противном случае уже последует ответ «НЕТ». Следовательно, рассмотрите нечетное n, являющееся полным квадратом и, следовательно, квадратом нечетного числа 2k + 1;

(2k + 1)2 = 4k2 + 4k + 1 = 4k (k + 1) + 1.

Так как k (k + 1) — произведение двух последовательных целых чисел, и из двух последовательных целых чисел всегда есть хотя бы одно четное число, получаем простой, но интересный результат: любой квадрат нечетного числа сравним с 1 по модулю 8. Таким-образом, при n отличном от 1 по модулю 8 инициализирующая часть программы выводит, что n не является точным квадратом.

Посмотрим теперь, что происходит внутри цикла. Делим p на 2, и если результат четен, мы удовлетворяемся тем, что умножаем a на 2. При этом действии произведение a*p остается постоянным. Поэтому кажется вероятным, что в цикле существует инвариантная величина, запись которой содержит a*p в предположении, что p четно.

Если после деления p на 2 результат оказывается нечетным, то мы вычитаем из этого результата a/2 + b. Обозначим новые значения a, b, p через а', b', p' соответственно:

а' = 2*а, p' = p/2 − а/2 − b, b' = a + b.

Для этих значений получаем:

a'*p' = a*p − a2 − 2a*b = а*р − (а + b)2 + b2 = а*р − b'2 + b2.

Это, наконец, дает

а'*p' + b'2 = а*р + b2.

Инвариантной величиной цикла оказывается, таким образом, сумма ар + b2, причем p остается четным. Это обеспечивается тем, что в случаях, когда p/2 нечетно, мы вычитаем нечетные b из нечетного p/2. Что касается b, то он нечетен потому, что он начинается со значения 1 и к нему прибавляются только четные значения а.

В начале а = 4, p (целая часть дроби (n − 1)/4) четно, b = 1, так что ар + b2 = n.

Наконец, a, начиная с 4, умножается на 2 при каждом прохождении цикла; b начинается с 1, которое меньше соответствующего начального а = 4.

Тогда при переходе от a, b, p к a', b', p' либо

b' = b, а' = 2*а, так что если b < а, то и b' < а';

либо

b' = а + b, а' = 2*а, что также сохраняет справедливость отношения а' < b'.

Следовательно, вот ситуация, которую цикл оставляет инвариантной:

n = а*p + b2;

а — степень двойки,

p четно,

b нечетно, b < а.

Кроме того, мы знаем, что при выходе из цикла p < а.

Если p равно нулю, то n = b2. Тогда мы видим, что n — квадрат числа b, которое выводится, и все закончено.

Но n может оказаться полным квадратом и тогда, когда p не нуль. Попробуем рассмотреть все возможные случаи. Положим n = r2 (r нечетно). Соотношение

r2 = ар + b дает

r2 − b2 = ар.

Положим r + b = 2u, r − b = 2v (r и b нечетны). Отсюда получаем 4uv = ар.

Поскольку r = u + v, где r нечетно, получаем, что u и v не могут быть числами одинаковой четности, так что одно из них четно, а другое нечетно. Так как а является степенью двойки, то нечетный сомножитель относится к p. Выявим его, полагая р = s2t , где s нечетно, a t ≥ 1 (p четно).

Напомним, что а = 2k . В этих обозначениях 4uv = ар = s2k + t , uv = s2k + t −2 .

Возможные решения для пары u, v имеют вид пар

s'2k + t -2 , s''

где s's" = s.

Покажем сначала, что s" — меньший из этих двух элементов пары. Вследствие t ≥ 1 имеем k − t ≤ k + t − 2.

Вследствие p < а последовательно выводим

s2t < 2k ,

s's"2t < 2k .

s's" < 2k - t ≤ 2k + t -2 ≤ s'22k + t -2

(потому что s' нечетен и не меньше 1).

Следовательно, нужно взять u = s'2k + t -2 , v = s".

Покажем теперь, что нужно обязательно взять s' =1, s" = s. По выбору u и v

b = 2k + t −2 s' − s" < а = 2k .

Отсюда получаем:

s" > 2k + t −2 s' − 2k ,

и, так как t ≥ 1:

s" > 2k −1 s' − 2k ,

s = s's" > 2k −1 s'2 − 2k s = 2k −1 s' (s' − 2).

Вследствие р = s2t < а = 2k выводим s < 2k − t ≤ 2k −1 .

Объединим два полученных неравенства:

2k −1 s' (s' − 2) < x < 2k −1 , поэтому s' (s' − 2) < 1.

Единственное нечетное число s', удовлетворяющее этому соотношению, это s' = 1. Следовательно, у нас остается единственная возможность:

u = 2k + t -2 , v = s,

b = u − v = 2k + t -2 − s < а = 2k ,

s > 2k + t -2 − 2k .

Так как s < 2k − t , то t должно быть таким, чтобы

2k − t > 2k + t -2 − 2k .

Поскольку t должно быть строго положительно, то его единственными возможными значениями являются t = 1 и t = 2.

При t = 1 имеем

p = 2s, b = 2k − t − s = a/2 − p/2.

Следовательно, если 2b = а − p, то n — квадрат числа (а + p)/2 = а − b.

При t = 2 имеем

p = 4s, b = 2k − s = a − p/4.

Следовательно, если p = 4(a − b), то n — квадрат числа a + p/4 = 2а − b.

Этим исчерпываются случаи, когда n может быть полным квадратом.

Можно спросить себя, могут ли эти различные случаи действительно осуществляться. Заметим, что при вступлении в цикл у нас b = 1, a = 4. После этого b может быть изменено добавлением а, т. е. кратным числа 4. Следовательно, b остается сравнимым с 1 по модулю 4. В трех возможных случаях:

p = 0, r = b,

p = а − 2b, r = a − b,

p = 4 (a − b), r = 2a − b,

первый случай — единственный, в котором квадратный корень из n сравним с 1 по модулю 4; два других дают квадратный корень, сравнимый с 3 по модулю 4. При выходе из цикла равенство

b = ар + b2

с учетом соотношений p < a, b < a дает n < 2a2 и, следовательно, при выходе из цикла a2 > n/2. Равенство

ар = n − b2

дает p = (n − b2)/a < n/а.

Если окажется, что n/а < a, то непременно p < а и цикл закончен. Чтобы цикл остановился, необходимо, чтобы a2 > n/2, и цикл заведомо останавливается, если a3 > n.

Следовательно, все зависит от положения n по отношению к степеням двойки. Существует такое целое n, что

4q < n < 4q +1 .

Возможны два случая. Во-первых, может выполняться неравенство

4q = 22 q < n < 22 q +1 ,

и тогда для k = q число a2 = 22 q > n/2 может быть значением остановки, но в этом нет уверенности. С другой стороны, если

22 q +1 < n < 22 q +2 ,

то единственное значение a, удовлетворяющее условию a2 > n/2, есть a = 2q +1 , и для этого значения имеем a2 > n, что гарантирует остановку. Поскольку r = a − b, то а = r + b > r и, следовательно, a2 > n.

Во втором случае

r = 2a − b и b < а, откуда а < 2a − b = r.

Таким образом, все три распознаваемые программой случая являются единственными возможными исходами программы, и каждый из них может произойти.

Таким образом, перед нами — очень забавный алгоритм, который дает значение квадратного корня, и который определяет случай, когда n не является корнем, но в этом случае не дает никакой дополнительной информации.

Программа заведомо останавливается при а = 2q +1 , так что число шагов цикла не больше q − 1 (начиная с 4), причем q — логарифм квадратного корня из n по основанию 2. Таким образом, получилась программа порядка In n, что дает ту же сложность, что и обычный алгоритм, действующий кусками по две цифры. Но для этого последнего алгоритма нужен еще первый цикл, чтобы найти порядок величины n.

Головоломка 19.

Соотношение f(a, b) = f(b, a) следует из самой инициализации p и q:

p := max (a, b); q := min (a, b).

Эти две функции симметричны по a и b, и поэтому точно так же симметрична f. При анализе программы мы ограничены действиями, происходящими внутри цикла. Величины r и s являются вспомогательными переменными, которые не оставляют никакой проблемы. Трудность вызывают преобразования, проделываемые над p и q. Чтобы ясно увидеть эту трудность, осуществим введение новых переменных без разрушения старых. Перепишем наш цикл:

ПОКА q ≥ eps ВЫПОЛНЯТЬ

r := (q/p)2; s := r/(r + 4)

p' := (2 * s + 1) * p; q' := s * q

p := p'; q := q'

ВЕРНУТЬСЯ

Рассмотрим действия этой программы, производимые над данными a, b с одной стороны и над ac, bc с другой.

Когда мы входим в цикл, то и p, и q умножаются на с при переходе от первого вычисления ко второму.

Это не меняет величины r и, следовательно, не меняет величины s. Таким образом, p и q в этих вычислениях умножаются на одни и те же сомножители, так что значения p', q' во втором вычислении получаются из значений p, q в первом вычислении умножением их обоих на c. Следовательно, мы еще раз входим в цикл при том же соотношении между входными данными; следовательно, это соотношение будет иметь место при каждом входе в цикл, и, следовательно, также и на выходе из цикла. Отсюда получаем, что f(ac, bc) = cf(a, b).

Выполнение программы для вычисления g(x) = f(x, 1) с x = 1 и eps = 10-5 дает мне результат, равный 1.4142.

Дальше считать бесполезно, это √2.

Я немедленно изменяю программу, чтобы она выполняла вывод не только величины g, но также и g2. Я получаю:

x g2(x)

1 2

2 5

3 10

4 17

Нет возможности сомневаться: g(х) = √х2 + 1.

Перенося эту формулу в соотношение между f и g, мы видим, проделав все вычисления, что

f (a, b) = √a2 + b2.

«Осталось только» доказать это. Мы не можем доверять заверениям программистов, утверждающих, что их программа делает то-то и то-то. При входе в цикл p и q имеют значения а и b в каком-то порядке, поэтому

p2 + q2 = a2 + b2.

Что происходит с величиной p2 + q2 после изменений, которым p и q подвергаются в цикле? Вычислим p'2 + q'2:

p'2 + q'2 = (2s + 1)2p2 + s2q2 = s2 (4р2 + q2) + 4sp + р2.

Вычислим s:

r := q2/p2, s = r/(r + 4) = q2(q2 + 4p2),

откуда, наконец,

s (4р2 + q2) = q2.

Возвращаясь отсюда к предыдущему соотношению, получаем

p'2 + q'2 = sq2 + 4sp2 + р2 = s(4р2 + q2) + p2 = p2 + q2.

Таким образом, все кончено… Это соотношение гарантирует, что p2 + q2 является инвариантом цикла. При каждом входе в цикл выполняется соотношение

p2 + q2 = a2 + b2.

При выходе из цикла

p2 + q2 = a2 + b2, причем q < ерs.

Отсюда следует, что

p2 = (a2 + b2) * (1 − q2/(a2 + b2)).

Cpaey получаем, что

p = √a2 + b2

с относительной ошибкой eps2/(2 * (a2 + b2)).

Чтобы получить точность до 10-5, совершенно ненужно брать eps = 10-5; более чем достаточно eps = 0.004. Эта программа сходится очень быстро.

 

3. Игры без стратегии

Игра 13.

Задача о наиболее длинном взятии не имеет однозначного решения. Вот как ее сделал я — с учетом моих привычек в программировании и упрощений, предоставляемых моим микрокомпьютером.

Я представил всю игру одной-единственной цепочкой символов с кодами возврата каретки, расположенными надлежащим образом — так, чтобы визуализация игры сводилась к визуализации этой цепочки бее какого-либо дополнительного исследования. Куры обозначаются в этой цепочке присвоенными им буквами, лисы — буквами X, пустые игровые поля обозначаются точками. Остальные символы (пробелы или возврат каретки) не отвечают никаким используемым игровым полям. Я добавил в начале и в конце по строчке пробелов, чтобы не было необходимости изучать возможность некоторых перемещений на границе игрового поля.

Я не храню положений лис с помощью двух переменных. Я отыскиваю их положение в цепочке, представляющей игру, с помощью функции «положение» языка LSE. Это — существенная деталь. Поиск наиболее длинного взятия я осуществляю итеративно. Я образую две цепочки:

— одна из них содержит список кур, уже взятых при исследовании данного пути (это — последовательность букв взятых кур),

— вторая цепочка содержит дуплеты: положение в игре и рассматриваемое направление (мы осуществляем взятие, исходя из положения x и двигаясь в направлении, обозначенном через i).

Находясь в положении x и в направлении i я смотрю, есть ли кура на поле x + d[i]. Если ее нет, то в этом направлении никакое взятие невозможно. Если же такая кура есть, то я смотрю, не содержится ли буква этой куры в цепочке уже взятых кур. Если содержится, то в этом направлении ничего не сделаешь. Если же эта кура еще не взята, то я проверяю, действительно ли поле x + 2 * d[i] содержит именно точку — в противном случае никакого взятия нет. Действуя таким образом, я не сталкиваюсь ни с какими трудностями на краях (там есть предохранительная строка, и она не содержит ни одной куры).

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

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

 

4. Игры со стратегией

Игра 19.

И здесь тоже решение неединственно. Вот одно из них, хорошо приспособленное к используемой мною машине, на которой деления на 2 не бесплатны (на мой взгляд, выполняются слишком долго). Нам известна верхняя граница числа спичек в каждой кучке, определяемая принятым вами правилом (я взял 4 кучки с по крайней мере 16 спичками). Я рассматриваю двоичные записи числа спичек в кучке, начиная слева. Я задаюсь числом p = 8. Если число больше или равно 8, то оно содержит 1 в крайнем левом из возможных положений. Тогда я вычитаю 8 из этого числа и перехожу к p = 4.

Сначала я определяю крайнюю левую цифру для числа спичек во всех четырех кучках. Из них я удерживаю только две вещи: четность этого числа (переменная q, вначале равная 0, изменяется на 1 — q при каждой встрече с единицей; результат нечетен, если в конце получается q = 1); номер последней встреченной кучки, у которой в данном положении встретилась единица. Я исследую таким образом все положения слева направо, пока не встречаю положение, для которого сумма единиц, стоящих в этом положении, нечетна. Тогда я знаю кучку (ту, номер которой был удержан в памяти), у которой в этом положении стоит именно единица. Я убираю из этой кучки желаемое число спичек, чтобы эта единица исчезла (8, если сейчас изучается крайнее левое положение).

Тогда я аналогичным образом исследую оставшиеся положения, за исключением того, что я больше не трогаю номера кучек, из которых я уже брал спички. Для каждой оставшейся позиции, вплоть до крайней правой, я отыскиваю единицы и, если число единиц нечетно, то я изменяю число спичек в выбранной кучке. Чтобы узнать, нужно ли добавить или уменьшить, я сохраняю их число перед изменением в цикле. Если оно больше р, я вычитаю из него р, а если меньше, то я р добавляю (я ставлю 0 вместо 1 и 1 вместо 0). Все это — очень быстрое вычисление, но оно требует немного больше строк в программе. Так вы легко достигнете цели.

Игра 20.

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

Игра 22.

Вот шкала весов, предложенная А.-П. де Лоашем в книге Шварца [SCHJ:

0: отрезок замыкает проигрывающий треугольник,

1: отрезок замыкает треугольник, две стороны которого принадлежат моему противнику,

2: отрезок замыкает смешанный треугольник (одна из сторон которого — моя, а другая — моего противника),

3: отрезок соединяет две смешанных вершины (из каждой из них выходит и моя сторона, и сторона моего противника),

4: отрезок соединяет смешанную вершину и вершину, из которой выходит только одна сторона,

5: отрезок соединяет две вершины, каждая из которых принадлежит только одному отрезку, который провел именно я,

6: отрезок соединяет две вершины, каждая из которых принадлежит только одному отрезку, один из которых провел я, а другой — мой противник,

7: отрезок соединяет две вершины, которые не принадлежат проведенным мною отрезкам,

8: отрезок проходит через «чистую» (еще не использованную) вершину,

9: отрезок соединяет чистую вершину с вершиной, не принадлежащей моим отрезкам,

10: отрезок соединяет две чистые вершины.

Можно немного упростить этот список, не увеличивая сколько-нибудь серьезно опасность проиграть.

Игра 23.

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

3,1 5,2 8,3 11,1 13,6 16,1 18,2

21,10 24,1 26,2 29,3 32,1

34,16 37,1 39,2 42,3 44,1 47,6 50,1

Игра 24.

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

Для каждой новой комбинации предложение некоторого цвета в некоторой позиции ведет к следующему:

— для черных шашек вы можете осуществить сравнение с той же позицией в другой комбинации;

— для множества белых + черных шашек: вы получаете еще и другие появления этого цвета, и у вас хранится число появлений этого цвета в других комбинациях.

Поэтому вы можете немедленно остановить испытание с цветом x в положении i, если:

либо эта комбинация дает слишком много черных шашек по сравнению с другой комбинацией,

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

либо она дает слишком много белых шашек,

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

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

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

 

5. Стратегия без игры (выигрывающие стратегии)

Игра 27.

Рассмотрим игру НАДЕВАТЬ. В начале на игровом поле ничего нет. Можно играть только на поле, которое следует эа первым занятым полем, а такого поля нет. Играем на поле 1.

На следующем ходе было бы глупо снимать только что выставленную шашку. Первое занятое поле — первое. Ставим шашку на поле 2. Первое занятое поле — это снова первое поле. Было бы глупо снимать только что выставленную шашку, и поэтому нужно играть на первом поле, т. е. освобождать его. Теперь первое свободное поле — это поле 2. Было бы глупо возвращать на поле 1 только что снятую шашку. Следовательно, поставим шашку на поле 3. Никакого выбора…

Чтобы освободить игру на одно поле, очищаем поле 1.

Чтобы освободить игру на два поля, мы не можем очистить поле 1, так как тогда мы не могли бы очистить и поле 2. Первое занятое поле — поле 1. Можно очистить поле 2, а затем поле 1.

Для игры с 3 полями, мы очищаем 1, эатем ставим 3, ставим снова 1, очищаем 2, а затем 1.

Если n четно, то мы начинаем с удаления шашки 2, в противном случае мы удаляем шашку 1.

Теперь вам не составит ни малейшего труда написать итеративную программу:

место := 0; игра : = пусто

ВЫПОЛНЯТЬ

  ЕСЛИ поле (1) = пусто ТО поставить (1);

    место := место + 1

  ИНАЧЕ удалить (1);

    место := место − 1

  КОНЕЦ_ЕСЛИ

  ЕСЛИ место = n ТО КОНЧЕНО КОНЕЦ_ЕСЛИ

  искать первое занятое поле, номер которого дает число i ;

  ЕСЛИ поле ( i + 1) = пусто ТО поставить ( i + 1);

    место := место + 1

  ИНАЧЕ удалить ( i + 1);

    место := место − 1

  КОНЕЦ_ЕСЛИ

  ЕСЛИ место = n ТО КОНЧЕНО КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Для игры СНИМАТЬ вы действуете аналогично.

В том, что касается последовательностей чисел, порожденных игрой СНИМАТЬ, начнем с рассмотрения конкретного примера. Вот игра СНИМАТЬ для n = 4.

Использованы все числа, меньшие 8, а из больших или равных 8 участвуют только 12, 13 и 15. Для обобщения действуйте по индукции.

Игра 29.

Вот решение для 8 букв и 10 полей.

..абабабаб

баабаба..б

бааб..аабб

б..баааабб

ббббаааа..

Присутствие куска X не меняет последовательности изменений.

..абабХабаб

баабабХа..б

бааб..Хаабб

б..бааХаабб

ббббааХаа..

Последний перенос пары букв аа слева от X в свободные пары справа дает

бббб..Хаааа

Теперь вы можете заняться X (если для этой комбинации вам решение уже известно) и получить

ббббY ..аааа

Таким образом, остается переместить два а с крайних полей справа на свободные поля, и все закончено. Следовательно, если вы умеете исследовать комбинацию Х с р парами букв а, б, то вы умеете исследовать и комбинацию с р + 4 парами.

Я уже предложил вам решение для четырех пар. Таким образом вы получаете решение для 8, 12,…

Главные решения — это решения для 4, 5, 6, 7 пар. Вот одно из решений для строчки из 5 пар

..абабабабаб

Искомое расположение имеет вид

бббббааааа..

Можно задаться целью удалить все буквы а (особенную трудность при перемещениях вызывает то, что их число нечетно) из первой половины (первых 5 позиций, в которых букв а в исходном положении не столько же, сколько букв б).

..абабабабаб

баабабаба..б

бааб..абаабб

бааббаа..абб

б..ббааааабб

бббббааааа..

Предлагаю вам разыграть 6 и 7 пар. Совершенно бесполезно подключать к этому делу компьютер. А где же программирование, спросите вы? Я отвечу, что это упражнение вводит вас в рекурсивные или индуктивные рассуждения. Это оздоровляет Наши способы рассуждать…

Игра 30.

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

Игра имеет ту же конфигурацию, что и для лис и кур. Поле обозначается своим положением в цепочке. Перемещение в данном направлении реализуется добавлением некоторой константы к данному положению. Таблица из четырех элементов дает эти константы для всех четырех направлений. Свободное поле представляется точкой, занятое поле — крестиком ×.

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

Вы уже проделали более трудную работу для самого длинного взятия в игре с курами и лисами.

Игра 31.

Число ходов f(р) для переноса р дисков получается переносом сначала p − 1 дисков со стержня d на стержень 3 − а − d за f(р − 1) ход, затем из перемещения диска р, что требует в точности одного хода, а затем возвращения р − 1 дисков из запаса на стержень прибытия за f(р − 1) ход, откуда получаем:

f(р) = 2 * f(р − 1) + 1,

g(p) = f(p) + 1 = 2 * f(р − 1) + 2 = 2 * (f(p − 1) + 1) − 2 * g(р − 1).

По индукции g(р) = 2p g (0).

Так как f(0) = 0, g(0) = f(0) + 1 = 1, g(р) = 2p , то, наконец

f(р) = 2p − 1.

Для игры с 50 дисками нужно 250 − 1 ходов. Но 210 равно 1024, или порядка 103. Следовательно, 250 порядка 1015.

В часе 3600 секунд, в сутках 3600 × 24 = 86400 секунд, за год получаем 86400 × 365 — или порядка 3 × 107 секунд, откуда, наконец, 3 × 109 секунд за столетие. Поэтому нужно порядка 1015/3 × 109, или порядка 3 × 105 веков для игры с 50 дисками, которая, таким образом, требует около 300000 веков…

Вот другой способ доказывать свойство четности. Пусть диски обозначены их порядковыми номерами, начиная с первого — самого маленького, и нужно показать, что два диска с номерами одной четности никогда не попадают непосредственно один на другой.

Опыт показывает, что для первых значений n реализация игры Н(n, d, а) дает следующее;

— диски, попадающие в основание стержней d и а, имеют ту же четность, что и n,

— диски, попадающие в основание запасного стержня, имеют другую четность.

Предположим, что это свойство справедливо для n − 1. Для реализации Н(n, d, а) нужно выполнить сначала Н(n − 1, d, 3 − а − d). В течение этой операции диск n остается в основании начального стержня d и, следовательно, в основании диска d находится диск n и потому диск той же четности, что и n. Диски, которые при этом оказываются в основании стержня прибытия для процедуры Н(n − 1, d, 3 − а − d), имеют (по предположению индукции) ту же четность, что и n − 1. Но этот стержень прибытия является для игры Н(n, d, а) запасным стержнем, и, следовательно, в основании запасного стержня оказываются диски, имеющие ту же четность, что и n − 1. Наконец, запасной стержень для игры Н(n − 1, d, 3 − а − d) есть а, в основание которого попадают диски с четностью n − 2, следовательно, с четностью n.

Перемещение диска n со стержня d на стержень а помещает n в основание стержня а, так что при этом свойство четности для а подтверждается. Проверьте, что для стержней d и 3 − а − d оно также подтверждается. Для этого разложите Н (n, d, а) на 5 операций:

Н (n − 2, d, а) n и n − 1 на стержне d

Р (n − 1, d, 3 − а − d) n на d, n − 1 на 3 − а − d

Н (n − 2, а, 3 − а − d)

Р (n, d, а) n на а, n − 1 на 3 − а − d

Н (n − 2, 3 − a − d, d)

Р (n − 1, 3 − а − d, а) n на а, n − 1 на а

Н (n − 2, d, а).

Предположим, что искомое свойство четности выполняется для n − 1. Тогда остается заниматься только теми дисками, которые ложатся на диск n.

В первой операции диск n − 1 находится на диске n, они разной четности, и, таким образом, здесь свойство четности выполняется. Во время игры Н(n − 2, а, 3 − а − d) диск n находится на стержне, который для этой игры является запасным. Диски, которые в этой игре ложатся в основание этого стержня — и потому ложатся на диск n — имеют четность, противоположную четности числа n − 2, следовательно, четность, противоположную четности n, что и проверяет на этом этапе наше условие четности. Вы легко завершите это рассуждение.

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

Игра 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. Начните с 2n − 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 , но не делятся на 2p (т. е. являются нечетными кратными числа 2p −1 ).

Номер k любого хода может быть единственным способом представлен в виде

k = (2r + 1)2р -1 .

Перемещаемый на этом ходе диск есть диск с номером p, и это — его (r + 1)-е перемещение. Так как он начинает движение со стержня 0 и перемещается в направлении s p (1, если р нечетно, и 2 в противном случае), то на этом ходе диск перемещается с rs p -го на (r + 1)s р -й стержень, где эти числа берутся по модулю 3.

Игра 34.

Попытаемся охарактеризовать значение р, дающее игре оптимум для данного n. Нам известно, что f3(n − p)= 2n - p − 1.

Должно выполняться

2f4(p − 1) + 2n - p +1 − 1 ≥ 2f4(р) + 2n - p − 1,

2f4(p + 1) + 2n - p- 1 − 1 ≥ 2f4(р) + 2n - p − 1.

Удобно пользоваться первыми разностями для функции f4:

d(р) = f4(p + 1) − f4(p).

Два приведенных выше соотношения могут быть переписаны следующим образом:

d(p − 1) < 2n - p -1 , d(р) ≥ 2n - p- 2 .

Интересно рассматривать даже не d(р), а скорее 2p d (р) = g(р):

g(р − 1) ~ 2n -2 ≤ g(р).

Можно еще упростить запись, беря не g(р), а величину

h(р) = log2(g(р)) = р + Iog2(d(р)).

Тогда получаем

h(р − 1) < n − 1 ≤ h(р).

При данном n величина р — наименьшее целое, для которого h больше или равно n − 2.

Приведем здесь первые из полученных таким образом значений:

Мы добавили в таблицу переменное q, связанное с «треугольными» числами. Для n = q(q + 1)/2 действительно убеждаемся, что

h(р) = h(р − 1) + 2

в то время как для других n

h(p) = h(p − 1) + 1.

Исходя из n, можно вычислить q:

q = целая_часть (( − 1)/2).

Имеем

h(n) = n + целая_часть (( − 1)/2).

Покажите это по индукции. Исходя отсюда, вычисляется все. Таким образом, если n дано, то р — наименьшее целое, большее или равное

(2n − 1 − )/2.

Игра 35.

Возьмем, например, игру с 50 дисками. Она реализуется переносом сначала 40 дисков на запасной стержень, а затем 10 последних дисков со стержня 0 на стержень 1, с использованием при этом только трех свободных стержней. Наконец, остается перенести начальные 40 самых маленьких дисков с запасного стержня на первый стержень, используя все 4 стержня.

Чтобы переместить 40 дисков с 4 стержнями, сводим задачу к перемещению 31 диска с 4 стержнями, а затем 9 с 3 стержнями…

Таким образом, дело сводится к разбиению 50 дисков на 8 сегментов:

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

Договоримся работать с тремя стержнями 0, 1, 2, так что стержень 3 остается пустым и служит запасным стержнем при любом перемещении какого-либо сегмента. Более точно, перемещение сегмента р со стержня d на стержень а осуществляется с помощью изученной выше процедуры Н, в которой запасным стержнем является стержень 3.

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

Мы сохраняем предыдущую итеративную стратегию, но понимаем ее как стратегию для сегментов. На компьютере это может пройти очень быстро. Вполне вероятно, что робот может осуществить одно перемещение за несколько секунд. Тогда на всю игру потребуется не более чем несколько часов…

Игра 36.

Соотношение SG (p, q) = 0 означает, что вы не можете достичь ситуации с числом Спрага-Грюнди, равным нулю, удаляя не более 2q спичек из кучки с р спичками. Если вы исходите из SG (р, q' < q), то вы не можете удалить столько же спичек и, следовательно, нет опасности, что вы получите число SG, равное нулю.

Предположим, что SG (p i , 1) = 0.

Исходя из p i + 1, я могу удалить 1 спичку и получить пару p i , 1. Следовательно, SG (p i + 1, q) ≠ 0.

Исходя из p i + 2, я для любого q всегда могу удалить две спички, но тогда я получаю SG (p i , 2) ≠ 0, и, следовательно,

SG (p i + 2, 1) = 0.

Если в p i имеем q i > 1, то тогда мы этого не получим и SG (p i + 2, 1) ≠ 0. Но в p i + 3, удаляя единственную спичку, получаем пару p i + 2, 1 c SG ≠ 0, или же, удаляя две спички, получаем пару p i + 1, 2 с ненулевым числом SG. Следовательно, SG (p i + 3, 1) = 0.

Все оставшееся уже очень хорошо подготовлено. Рассмотрите точку р, для которой диагональ пересекает ось р = 0, не пересекая положений с нулевым SG. Эта прямая задается уравнением x + у = р. Она пересекает ось x = 0 в точке у = р. Нельзя взять в точности р спичек, — можно не больше р − 1. Следовательно, в этой точке

q = целая_часть ((р − 1)/2).

Рассмотрим теперь точку, абсцисса которой есть число Фибоначчи: р = fib (s).

Нужно показать, что прямая x + у = fib (s) не пересекает точек с ненулевыми SG, кроме x = 0. Рассмотрим сначала точку

х = fib (s − 1).

В этой точке

у = fib (s) − fib (s − 1) = fib (s − 2).

При p = fib (s − 1)

q = целая_часть ((fib (s − 1) − 1)/2).

Нужно показать, что для каждого s

целая_часть ((fib (s − 1) − 1)/2) < fib (s − 2),

или, что равносильно,

fib (s − 1) < 2 * fib (s − 2) + 1.

Но

fib (s − 1) = fib (s − 2) + fib (s − 3)

и

fib (s − 3) < fib (s − 2).

Следовательно, рассматриваемая диагональ не пересекает точек с нулевым SG в fib (s − 1). Она не может пересекать их и между s − 1 и s, поскольку эта часть воспроизводит то, что происходит в интервале от 1 до fib (s − 2), а диагональ, выходящая из fib (s − 2), не пересекает точек с нулевым SG до оси q.

Вы без труда завершите это доказательство.

 

6. Комбинаторные задачи

Головоломка 28.

Действительно ли вам что-то еще нужно сообщать? Тогда я немного уточню способ поддержания части от 1 до р в порядке неубывания. Исходим ив упорядоченного по неубыванию вектора a1, a2, …, а р . Вы последовательно заменяете элемент а р элементами а i , где i направлен по убыванию. Вы последовательно получите

a1, a2, …, ар -1 , а р ,

a1, a2, …, ар , ар -1 ,

a1, a2, …, ар -3 , ар -1 , а р , ар -2 .

По индукции, предположим, что в некоторый момент вы получили

a1, …, аi -1 , аi +1 , …, ар , аi

после перемены мест элементов с номерами i, р.

На следующем ходе вы поменяете местами аi -1 и последний член, который равен а i . Эта форма остается неизменной, и первая часть, от 1 до р − 1, остается отсортированной в неубывающем порядке. В конце вы получите

a2, a3, …, а р , a1.

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

Это вы делаете только в случае необходимости. Незачем восстанавливать порядок, когда все закончено.

Процедура работает достаточно быстро для того, чтобы в случае неудачи иметь возможность испытать наличие решения для n − 1, а затем для n + 1. Таким образом, по прошествии 45 с для каждого кандидата мы получаем в качестве результата

— решение, если оно существует,

— приближение о точностью до единицы, если это возможно.

Эта программа терпит неудачу крайне редко.

В выпуске от 8 марта 1984 года следующий розыгрыш не был найден ни кандидатами, ни Бертраном, ни кем- либо из присутствующих:

50 10 10 5 4 2 n = 767.

На моем микрокомпьютере нужно 18 с, чтобы обнаружить, что эта задача не имеет решения, а затем еще 5 с, чтобы получить

50 − 10 = 40 , 40 * 5 = 200, 10 − 2 = 8,

200 − 8 = 192, 192 * 4 = 768.

Для задачи

9 7 6 4 3 1 n = 795 через 6 с получается

4 * 9 = 36, 36 + 1 = 37, 37 * 7 = 259,

259 + 6 = 265, 265 * 3 = 795.

Наконец,

100 50 8 5 4 2 n = 631.

За менее чем 2 с получаем

50 − 4 = 46 , 46 * 2 = 92, 92 * 8 = 736,

100 + 5 = 105 , 736 − 105 = 631.

Я уже предлагал вам следующий пример:

100 75 50 25 10 10.

Для n = 370 особой трудности нет, потому что это — кратное десяти.

Компьютер сообщает мне

75/25 = 3,

50 − 3 = 47,

47 * 10 = 470,

470 − 100 = 370.

Это уже интересно, потому что это — совершенно не то решение, которое я собирался искать.

Чтобы найти 369, нужно образовать число, не кратное 5, — чего нельзя сделать с помощью какой-либо из трех операций +, −, *, сохраняющих кратность пяти. Следовательно, нужно использовать деление. Вот решение:

50/10 = 5,

5 * 75 = 375,

375 − 10 = 365,

100/25 = 4,

365 + 4 = 369.

Обе представленные здесь программы не позволяют получить это решение. Действительно, оно записывается в виде

(50/10) * 75 + 100/25 − 10.

А число 368? Вы нашли для него решение? Я не сумел. Но Жак Бейгбеде сообщил мне, что он получил его делением на 25…

10 * 100= 1000,

1000 − 75 = 925,

925 * 10 = 9250,

9250 − 50 = 9200,

9200/25 = 368.

 

7. Обо всем понемногу

Головоломка 31.

Программисты обманываются, поскольку они не берут на себя труд прояснить различные ситуации.

В строке 200 мы знаем, что цепочка а пройдена полностью, и исследованы все символы, не являющиеся пробелами. Если в цепочке b содержится еще какой-нибудь символ, не являющийся пробелом, то равенства цепочек нет. Все в порядке.

В строке 300 цепочка а пройдена вплоть до некоторого символа, не являющегося пробелом, и этот символ еще не исследован. Цепочка b пройдена полностью, и в ней не содержится более ни одного символа, не являющегося пробелом. Следовательно, эти две цепочки различны. Можно было бы сказать, что дальнейшее движение по цепочке а бесполезно, но не приводит к ошибке. Но это неверно. Вы остановились на еще не исследованном символе, который не является пробелом. Если вы перейдете к следующему символу, не являющемуся пробелом, то данный символ вы потеряете. Если, как бывает в большинстве случаев, цепочка а совпадает с цепочкой b с точностью до пробелов за исключением единственного дополнительного символа в конце цепочки, то именно по этой-то причине и должен быть остановлен пробег цепочки а. Перемещаясь и не обнаруживая больше символов, не являющихся пробелами, мы получаем сообщение, что цепочки совпадают, а это неверно. Ясно, что программисты не принимали во внимание и не изучали именно этот случай. И никаких оснований поступать так нет. В этом и состоит преимущество логических рассуждений о тексте программы по сравнению с проверкой ее правильности с помощью тестирования.

Ваша программа должна сохранять симметричную роль обеих цепочек. Не начинайте проверять результат пробега цепочки а, не пробежав цепочки b, и изучайте обе цепочки разом.

Возьмем общую ситуацию:

а пройдена вплоть до i включительно;

b пройдена вплоть до j включительно;

обе части совпадают с точностью до пробелов.

ВЫПОЛНЯТЬ

  продвинуть i на следующий символ в а , не являющийся пробелом;

  продвинуть j на следующий символ в b , не являющийся пробелом;

  ЕСЛИ таких нет в а И таких нет в b ТО

  r := ИСТИНА;

    КОНЧЕНО КОНЕЦ_ЕСЛИ;

  ЕСЛИ таких нет в a ИЛИ таких нет в b ТО

  r := ЛОЖЬ;

    КОНЧЕНО КОНЕЦ_ЕСЛИ;

  ЕСЛИ a [ i ] ≠ b [ j ] ТО r := ЛОЖЬ;

  КОНЧЕНО КОНЕЦ_ЕСЛИ;

ВЕРНУТЬСЯ

Эта программа совершенно симметрична относительно а и b…

Головоломка 33.

Нужно работать по модулю n. Удобнее всего пронумеровать элементы вектора от 0 до n − 1. Все элементы спускаются вниз на m по модулю n. Элемент, который переходит в 0, имеет номер m; элемент, который переходит в m, имеет номер 2m по модулю n; элемент, который переходит в 2m, имеет номер 3m по модулю n… Таким образом, мы получаем цепочку чисел, кратных m по модулю n. Весь вопрос в том, чтобы узнать, порождает ли последовательность чисел, кратных m по модулю n, последовательность всех целых от 0 до n − 1.

Это так, если m и n взаимно просты. В противном случае пусть с наибольший общий делитель m и n:

m = m'с, n = n'c,

n' * m = n' * m' * с = m' * n = 0 по модулю n.

Эта цепочка возвращается в 0 за n' = n/с операций. При этом пробегается не весь вектор, а только его элементы, сравнимые с 0 по модулю с.

Беря в качестве исходных элементов различных циклов последовательно целые числа от 0 до c − 1, вы разместите все элементы вектора, причем каждый из них будет перемещаться в точности один раз…

Головоломка 34.

Рассмотрите более общую задачу, что заставит вас открыть одно из этих знаменитых «преобразований программы», столь полезных, когда желательно улучшить уже существующие программы. Обозначим через t и u два условия, а через a и b — две последовательности инструкций. Вот простой цикл:

ПОКА t ВЫПОЛНЯТЬ

  ЕСЛИ u ТО a ИНАЧЕ b

КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Последовательность операций следующая:

— проверяется условие t,

— если оно истинно, то проверяется u,

— если u истинно, то выполняется a, и все возобновляется.

Допустим, что условия t и u таковы, что я имею возможность проверить u, даже если проверка условия t дает значение ЛОЖЬ. Тогда, пока условия t и u истинны, в цикле выполняется а.

Вот другая последовательность, которая может встретиться:

— проверяется условие t,

— если оно истинно, то проверяется u,

— если u ложно, то выполняется b, и все возобновляется.

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

ПОКА t ВЫПОЛНЯТЬ

  ПОКА t И u ВЫПОЛНЯТЬ а ВЕРНУТЬСЯ

  ПОКА t И НЕ u ВЫПОЛНЯТЬ b ВЕРНУТЬСЯ

ВЕРНУТЬСЯ

Мы перепишем программу для определения равнин, чтобы придать ей форму ПОКА, заключенного в скобки ЕСЛИ:

i := 1; р : = 0;

ПОКА i ≤ n ВЫПОЛНЯТЬ

  ЕСЛИ a [ i ] = a [ i − р ]

    ТО x := a [i]; р := р + 1; i := i + 1

    ИНАЧЕ i := i + 1

  КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Мы обнаруживаем, что в нашем случае мы не можем объединить два условия с помощью операции И: если i не удовлетворяет условию, что i не больше n, то нельзя поставить вопрос относительно a[i]. Обрисуем трудность подходящим образом:

— нужно либо добавить в таблицу а поле, которое содержит какую-нибудь несущественную для нас величину (мы к этой величине не обращаемся);

— либо нужно допустить, что операция И не коммутативна. Для вычисления t и u мы вычисляем t, и если результат есть ЛОЖЬ, то все кончено и притом с результатом ЛОЖЬ. В противном случае результат есть значение условия u.

Тогда можно использовать наше преобразование:

i := 1; р := 0;

ПОКА i ≤ n ВЫПОЛНЯТЬ

  ПОКА i ≤ n И а [ i ] = a [ i − р ] ВЫПОЛНЯТЬ

     x := а [ i ]; р := р + 1; i := i + 1

  ВЕРНУТЬСЯ

  ПОКА i ≤ n И а [ i ] ≠ a [ i − р ] ВЫПОЛНЯТЬ

     i : = i + 1

  ВЕРНУТЬСЯ

ВЕРНУТЬСЯ

Первый цикл движется по таблице а, пока обнаруживается, что элементы равны между собой. Более точно, р и i изменяются одинаково, так что разность i − р остается постоянной. Все элементы a[i] сравниваются с одним и тем же элементом, и величина x остается постоянной, равной этому элементу, на протяжении всего цикла.

Второй цикл изменяет i до тех пор, пока не обнаружится пара элементов, отстоящих на р + 1.

Уточним ситуацию выхода из первого внутреннего цикла. Мы собираемся найти конец равнины, которая лучше всех предыдущих, мы фиксируем ее длину р и ее значение х, a i обозначает первый элемент после этой равнины. Мы можем надеяться найти пару j, j − р с

a[j] = a[j − р]

только пока j − р остается на равнине, которую мы собираемся пройти. Наименьшее соответствующее i значение j удовлетворяет условию j − р = i, или j = i + р.

Следовательно, можно увеличивать i от р в обоих циклах, не меняя действия программы, что ускоряет ее работу.

Чтобы ускорить и первый внутренний цикл, мы присвоим переменной x ее значение перед циклом и сохраним ее начальное значение в j. Так как i − р остается постоянным, то можно вычислить значение р также и после выхода из цикла. Начальные значения суть i = j и р = р0, а конечные значения i и р удовлетворяют соотношениям i − р = j − р0, откуда р = i + р0 − j:

i := 1; р := 0

ПОКА i ≤ n ВЫПОЛНЯТЬ

x := а [ i ]; j := i

  ПОКА i ≤ n И а [ i ] = x ВЫПОЛНЯТЬ

     i := i + 1

  ВЕРНУТЬСЯ

   р := i + р − j ; i := i + p

  ПОКА i ≤ n И а [ i ] ≠ a [ i − р ] ВЫПОЛНЯТЬ

     i := i + 1

  ВЕРНУТЬСЯ

ВЕРНУТЬСЯ

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

Может быть, это связано с ходом мыслей, который я приобрел, преподавая.

Головоломка 35.

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

Покажем сначала, что u i < ui +1 . Предположим, что это не так: пусть существует такая последовательность длины i + 1, у которой последний элемент не больше u i . Так как эта последовательность возрастает, то ее предпоследний элемент меньше ui +1 и потому меньше u i . Тогда, удаляя последний элемент этой последовательности, мы получили бы последовательность длины i с последним членом, меньшим u i , что противоречило бы предположению, что u i — последний элемент последовательности длины i с наименьшим возможным последним элементом.

Рассмотрим теперь следующий элемент x нашего вектора. Разместим его в упорядоченной таблице u. Может случиться, что x > u m . Тогда элемент x можно присоединить к концу последовательности длины m; тем самым получилась бы (впервые) возрастающая последовательность длины m + 1, которая вследствие своей единственности была бы оптимальна.

Если x меньше u1, то им следует заменить для построения новой наилучшей последовательности с длиной 1. Если же, наконец, оказывается, что u i < x < ui +1 , то x можно присоединить к концу последовательности с длиной i + 1, чтобы получить последовательность с длиной i + 1, которая лучше уже известной, и поэтому ui +1 следует заменить на х. Так как и упорядочена, то вы можете разместить в ней x с помощью дихотомического поиска.

Эта операция требует порядка log2 m действий для m, не превосходящих n. Так как вам требуется n обращений к таблице, то вы получаете верхнюю границу числа действий порядка n log2 n, что чрезмерно завышено.

Головоломка 36.

Предположим, что вы уже прошли первую цепочку вплоть до индекса i − 1 и получили наилучшие слова длины р, меняющейся от 1 до m. Вы рассматриваете символ в положении i и ищете его в другой цепочке. Его первое положение j1 может быть поставлено в конце некоторого слова — скажем, слова длины р1 — и даст слово длины р1 + 1, которое окажется лучшим, чем предыдущее: действительно, если j1 можно поставить после слова длины p1, то это значит, что его значение больше положения последнего символа в наилучшем слове длины р1, но меньше положения последнего символа в слове длины p1 + 1, Рассмотрим теперь второе появление того же символа во второй цепочке: j2 > j1. Его нельзя поставить в конце елова длины p1 + 1, хотя j2 и больше j1, потому что это — другое появление того же символа, и их не нужно смешивать. Поэтому достаточно ограничиться по поводу этого появления символа обращением к таблице в ее части от p1 + 2 до m.

Головоломка 37.

Рассмотрим прямоугольник пробелов, вертикальная граница которого расположена в столбце j и располагающийся вправо от этого столбца в строках от i1 до i2. Его основание равно inf (l[i1 : i2]), а его площадь есть произведение этого основания на его высоту i2 − i1 + 1.

Для столбца j нужно найти максимум этой величины, когда i1 меняется от 1 до n − 1 (n — число строк), а i2 — от i1 + 1 до n.

Когда вы переходите к следующему столбцу, то каждое l уменьшается на 1. В строке, в которой стояла единица, оно становится нулем. Там, где l было равно 0, его нужно вычислить заново. Вы можете попробовать схитрить при вычислении величины inf (l).

В центральном цикле любое введение нового члена может только уменьшить значение минимума.

Головоломка 39.

Рассмотрим значения S для строк i и i' > i. Очевидно

S (i, j) = S (i, i' − 1) + S (i', j).

Если S (i, i' − 1) положительно, то S (i, j) > S (i', j) и строка i остается строкой, которая может содержать максимум.

Но если S (i, i' − 1) < 0, то S (i, j) < S (i', j).

Максимум нужно тогда искать либо среди S (i, j) для j < i', либо среди S (i', j) для j ≥ i'.

Заметим, что S (i', i') = а[i'].

Мы собираемся пробежать строку S (1, …) вплоть до первого индекса i1 , для которого S становится отрицательным. Тогда мы начнем пробегать строку S (i1 + 1, …), и т. д.

Отсюда следует, что в каждый данный момент нужно знать максимальную подпоследовательность в уже пройденной части; эта подпоследовательность задается номером начала r, номером конца q и своей суммой m. С другой стороны, нужно знать наилучшую заключительную подпоследовательность S (k, i − 1), предполагая, что вектор пройден вплоть до поля i − 1. Обозначим через s значение суммы этой заключительной подпоследовательности. Пусть k — номер отроки, дающий этой сумме максимальное значение, а s — сумма всех членов, начиная с k.

Если сумма s положительна, то она и образует максимум на строке с номером k. При переходе к i число a[i] добавляется к s. Если s отрицательно, то новый элемент с номером i и становится оптимальной строчкой, и нужно взять s = а[i].

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

Предположим, что вектор пройден от элемента 1 до элемента с номером i − 1 включительно. Мы знаем лучшую подпоследовательность в этой части: она идет от индекса r до индекса q включительно, и ее сумма равна m: m = S (r, q). С другой стороны, мы внаем наилучшую заключительную подпоследовательность, кончающуюся в i − 1, т. е. знаем такой индекс k, что сумма S (k, i − 1) максимальна среди заключительных подпоследовательностей, Значение суммы S (k, i − 1) равно s. Может случиться, что эта заключительная подпоследовательность является наилучшей возможной во всей пройденной части, и в этом случае имеем r = k, q = i − 1, s = m. В любом другом случае s ≤ m. Если i = n − 1, то весь вектор пройден и получен искомый результат r, q, m.

В противном случае нужно включить элемент a[i]. Если s отрицательно, то a[i] и образует (как единственный участник) наилучший заключительный отрезок; берем k = i, s = a[i]. В противном случае s ≥ 0 и сумма s + a[i] больше s и больше а[i], и это и есть сумма для наилучшего заключительного отрезка, который по-прежнему начинается с номера k. В этих двух случаях отрезок s становится наилучшим отрезком, если он оказывается больше m.

Для начала можно положиться на пробег вектора, начиная с его единственного первого элемента. В этот момент наилучший сегмент и наилучший заключительный сегмент — это одно и то же.

d := 1; f := 1; m := a [1]Я здесь совершаю плагиат по отношению к поговорке жителей плоскогорья Высоких Вивар, которая звучит так: кто сам пилит свои дрова, согревается дважды.
; s := m ; i := 2

ПОКА i ≤ n ВЫПОЛНЯТЬ

  ЕСЛИ s < 0 ТО k := i ; s := a [ i ]

    ИНАЧЕ s := s + a [ i ]

  КОНЕЦ_ЕСЛИ

  ЕСЛИ s > m ТО d := k ; f := i ; m := s

  КОНЕЦ_ЕСЛИ

   i := i + 1

ВЕРНУТЬСЯ

Эта программа осуществляет пробег вектора a один-единственный раз, что и было предписано в условии. Это очень просто, но это совершенно не очевидно.