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

Наконец, 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".

Покажем теперь, что нужно обязательно взять s' =1, s" = s. По выбору u и v

b = 2^k+t-2s' - s" а = 2^k.

Отсюда получаем:

s" 2^k+t-2s' - 2^k,

и, так как t >= 1:

s" 2^k-1s' - 2^k,

s = s's" 2^k-1s'² - 2^ks = 2^k-1s' (s' - 2).

Вследствие р = s2^t а = 2^k выводим s 2^k-t = 2^k-1.

Объединим два полученных неравенства:

2^k-1s' (s' - 2) x 2^k-1, поэтому s' (s' - 2) 1.

Единственное нечетное число s', удовлетворяющее этому соотношению, это s' = 1. Следовательно, у нас остается единственная возможность:

u = 2^k+t-2, v = s,

b = u - v = 2^k+t-2 - s а = 2^k,

s 2^k+t-2 - 2^k.

Так как s 2^k-t, то t должно быть таким, чтобы

2^k-t 2^k+t-2 - 2^k.

Поскольку t должно быть строго положительно, то его единственными возможными значениями являются t = 1 и t = 2.

При t = 1 имеем

p = 2s, b = 2^k-t - s = a/2 - p/2.

Следовательно, если 2b = а - p, то n — квадрат числа (а + p)/2 = а - b.

При t = 2 имеем

p = 4s, b = 2^k - s = a - p/4.

Следовательно, если p = 4(a - b), то n — квадрат числа a + p/4 = 2а - b.

Этим исчерпываются случаи, когда n может быть полным квадратом.

Можно спросить себя, могут ли эти различные случаи действительно осуществляться. Заметим, что при вступлении в цикл у нас b = 1, a = 4. После этого b может быть изменено добавлением а, т. е. кратным числа 4. Следовательно, b остается сравнимым с 1 по модулю 4. В трех возможных случаях:

p = 0, r = b,

p = а - 2b, r = a - b,

p = 4 (a - b), r = 2a - b,

первый случай — единственный, в котором квадратный корень из n сравним с 1 по модулю 4; два других дают квадратный корень, сравнимый с 3 по модулю 4. При выходе из цикла равенство

b = ар + b²

с учетом соотношений p a, b a дает n 2a² и, следовательно, при выходе из цикла a² n/2. Равенство

ар = n - b²

дает p = (n - b²)/a n/а.

Если окажется, что n/а a, то непременно p а и цикл закончен. Чтобы цикл остановился, необходимо, чтобы a² n/2, и цикл заведомо останавливается, если a³ n.

Следовательно, все зависит от положения n по отношению к степеням двойки. Существует такое целое n, что

4^q n 4^q+1.

Возможны два случая. Во-первых, может выполняться неравенство

4^q = 2^2q n 2^2q+1,

и тогда для k = q число a² = 2^2q n/2 может быть значением остановки, но в этом нет уверенности. С другой стороны, если

2^2q+1 n 2^2q+2,

то единственное значение a, удовлетворяющее условию a² n/2, есть a = 2^q+1, и для этого значения имеем a² n, что гарантирует остановку. Поскольку r = a - b, то а = r + b r и, следовательно, a² n.

Во втором случае

r = 2a - b и b а, откуда а 2a - b = r.

Таким образом, все три распознаваемые программой случая являются единственными возможными исходами программы, и каждый из них может произойти.

Таким образом, перед нами — очень забавный алгоритм, который дает значение квадратного корня, и который определяет случай, когда n не является корнем, но в этом случае не дает никакой дополнительной информации.

Программа заведомо останавливается при а = 2^q+1, так что число шагов цикла не больше q - 1 (начиная с 4), причем q — логарифм квадратного корня из n по основанию 2. Таким образом, получилась программа порядка In n, что дает ту же сложность, что и обычный алгоритм, действующий кусками по две цифры. Но для этого последнего алгоритма нужен еще первый цикл, чтобы найти порядок величины n.

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

Соотношение f(a, b) = f(b, a) следует из самой инициализации p и q:

p := max (a, b); q := min (a, b).