Часть III. И если вы все еще не нашли решения

Часть III. И если вы все еще не нашли решения

Многие игры или головоломки уже не требуют никаких дополнительных пояснений. Но некоторые из них еще могут вам сопротивляться. Поэтому следует сказать вам все…

1. Случайные числа

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

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

Положим v_i = u_2i. Тогда

v_i+1 = u_2i+2 = f(f(u_2i)) = f(f(v_i)).

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