Жак Арсак - Программирование игр и головоломок
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(2qn' + 1)/Зp) − 1.
Как и следовало ожидать, это имеет в точности тот смысл, что если деление на Зp можно выполнить нацело, то в связи с этим возникает соотношение между (p, q) и n'.
Если n" увеличить на 1, а затем умножить на 3p−1/2p−1, то получится (2qn' + 1)/3.
Тогда нужно уменьшить результат на 1: получим (2qn' − 2)/3. Но это число делится на 2, так что с помощью перехода (p − 1, 1) число n" дает
(2q−1n' − 1)/3.
По общим правилам получаем
3 ((2q−1n' − 1)/3) + 1 = 2q−1n',
а затем 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(2qn + 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.
Обозначим через ai цифры исходного числа, bi — цифры результата, ki — цифры «в уме»:
3ai + ki = bi + 10ki+1.
Сумма всех ai равна 45, как и сумма всех bi. Обозначим через K сумму всех ki:
