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

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