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

Вследствие р = 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).

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

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

r := (q/p)²; 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).

Выполнение программы для вычисления g(x) = f(x, 1) с x = 1 и eps = 10^-5 дает мне результат, равный 1.4142.

Дальше считать бесполезно, это √2.

Я немедленно изменяю программу, чтобы она выполняла вывод не только величины g, но также и g². Я получаю:

x g²(x)

1 2

2 5

3 10

4 17

Нет возможности сомневаться: g(х) = √х² + 1.

Перенося эту формулу в соотношение между f и g, мы видим, проделав все вычисления, что

f (a, b) = √a² + b².

«Осталось только» доказать это. Мы не можем доверять заверениям программистов, утверждающих, что их программа делает то-то и то-то. При входе в цикл p и q имеют значения а и b в каком-то порядке, поэтому

p² + q^{2 =} a² + b².

Что происходит с величиной p² + q² после изменений, которым p и q подвергаются в цикле? Вычислим p'² + q'²: