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

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

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

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

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

Если вы начинаете u с u 1= a , то вы начинаете v с v 1= 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(З p − 2 p )/(2 p + 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 ≠ С ).