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

Арсак Жак

а' = 2*а, p' = p/2 - а/2 - b, b' = a + b.

Для этих значений получаем:

a'*p' = a*p– a²– 2a*b = а*р– (а + b)² + b² = а*р– b'² + b².

Это,

наконец, дает

а'*p' + b'² = а*р + b².

Инвариантной величиной цикла оказывается, таким образом, сумма ар + b², причем p остается четным. Это обеспечивается тем, что в случаях, когда p/2 нечетно, мы вычитаем нечетные b из нечетного p/2. Что касается b, то он нечетен потому, что он начинается со значения 1 и к нему прибавляются только четные значения а.

В начале а = 4, p (целая часть дроби (n– 1)/4) четно, b = 1, так что ар + b² = n.

Наконец, a, начиная с 4, умножается на 2 при каждом прохождении цикла; b начинается с 1, которое меньше соответствующего начального а = 4.

Тогда при переходе от a, b, p к a', b', p' либо

b' = b, а' = 2*а, так что если b < а, то и b' < а';

либо

b' = а + b, а' = 2*а, что также сохраняет справедливость отношения а' < b'.

Следовательно, вот ситуация, которую цикл оставляет инвариантной:

n = а*p + b²;

а — степень двойки,

p четно,

b нечетно, b < а.

Кроме того, мы знаем, что при выходе из цикла p < а.

Если p равно нулю, то n = b². Тогда мы видим, что n — квадрат числа b, которое выводится, и все закончено.

Но n может оказаться полным квадратом и тогда, когда p не нуль. Попробуем рассмотреть все возможные случаи. Положим n = r² (r

нечетно). Соотношение

r² = ар + b дает

r²– b² = ар.

Положим r + b = 2u, r– b = 2v (r и b нечетны). Отсюда получаем 4uv = ар.

Поскольку r = u + v, где r нечетно, получаем, что u и v не могут быть числами одинаковой четности, так что одно из них четно, а другое нечетно. Так как а является степенью двойки, то нечетный сомножитель относится к p. Выявим его, полагая р = s2^t, где s нечетно, a t >= 1 (p четно).

Напомним, что а = 2^k. В этих обозначениях 4uv = ар = s2^k+t, uv = s2^{k+t– 2}.

Возможные решения для пары u, v имеют вид пар

s'2^{k+t– 2}, s''

где s's" = s.

Покажем сначала, что s" — меньший из этих двух элементов пары. Вследствие t >= 1 имеем k– t <= k + t– 2.

Вследствие p < а последовательно выводим

s2^t < 2^k,

s's"2^t < 2^k.

s's" < 2^{k– t} <= 2^{k+t– 2} <= s'²2^{k+t– 2}

(потому что s' нечетен и не меньше 1).

Следовательно, нужно взять u = s'2^{k+t– 2}, v = s".