Жак Арсак - Программирование игр и головоломок

При t = 2 имеем

p = 4 s , 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 = а − 2 b , r = a − b ,

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

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

b = ар + b 2

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

ар = n − b 2

дает p = ( n − b 2)/ a < n / а .

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

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

4 q < n < 4 q +1.

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

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

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

2 2 q +1< n < 2 2 q +2,

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

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

r = 2 a − b и b < а , откуда а < 2 a − 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 ).

Эти две функции симметричны по a и b , и поэтому точно так же симметрична f . При анализе программы мы ограничены действиями, происходящими внутри цикла. Величины r и s являются вспомогательными переменными, которые не оставляют никакой проблемы. Трудность вызывают преобразования, проделываемые над p и q . Чтобы ясно увидеть эту трудность, осуществим введение новых переменных без разрушения старых. Перепишем наш цикл:

ПОКА q ≥ eps ВЫПОЛНЯТЬ

r := ( q / p ) 2; s := r /( r + 4)

p ' := (2 * s + 1) * p ; q ' := s * q

p := p '; q := q '

ВЕРНУТЬСЯ

Рассмотрим действия этой программы, производимые над данными a , b с одной стороны и над ac , bc с другой.

Когда мы входим в цикл, то и p , и q умножаются на с при переходе от первого вычисления ко второму.

Это не меняет величины r и, следовательно, не меняет величины s . Таким образом, p и q в этих вычислениях умножаются на одни и те же сомножители, так что значения p ', q ' во втором вычислении получаются из значений p , q в первом вычислении умножением их обоих на c . Следовательно, мы еще раз входим в цикл при том же соотношении между входными данными; следовательно, это соотношение будет иметь место при каждом входе в цикл, и, следовательно, также и на выходе из цикла. Отсюда получаем, что f ( ac , bc ) = cf ( a , b ).