1. Случайные числа
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.