1. Случайные числа
Головоломка 1.
Первая стратегия. Нужно сравнить u2i и ui. Они равны, если 2i = i + kp для целого k, следовательно, если i делится на p. Кроме того, i должно превосходить r. Следовательно, нужно искать наименьшее кратное p, большее или равное r.
Положим vi = u2i. Тогда
vi+1 = u2i+2 = f(f(u2i)) = f(f(vi)).
Если вы начинаете 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.