Программирование игр и головоломок

Теперь вы получили два равных элемента. Чтобы получить период, нужно пройти интервал между полученными числами — например, начиная с 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.

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

Головоломка 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 = (2^p(2^qn' + 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', что и доказывает наше утверждение.

Если вы примените это правило перехода к 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 = (2^p(2^qn + 1)/3^p) - 1,

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

(З^p– 2^p)/(2^p+q– З^p)