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

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

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

x g2(x)

1 2

2 5

3 10

4 17

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

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

f (a, b) = a2 + b2.

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

p2 + q2 = a2 + b2.

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

p'2 + q'2 = (2s + 1)2p2 + s2q2 = s2 (4р2 + q2) + 4sp + р2.

Вычислим s:

r := q2/p2, s = r/(r + 4) = q2(q2 + 4p2),

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

s (4р2 + q2) = q2.

Возвращаясь отсюда к предыдущему соотношению, получаем

p'2 + q'2 = sq2 + 4sp2 + р2 = s(4р2 + q2) + p2 = p2 + q2.

Таким образом, все кончено… Это соотношение гарантирует, что p2 + q2 является инвариантом цикла. При каждом входе в цикл выполняется соотношение

p2 + q2 = a2 + b2.

При выходе из цикла

p2 + q2 = a2 + b2, причем q < ерs.

Отсюда следует, что

p2 = (a2 + b2) * (1 - q2/(a2 + b2)).

Cpaey получаем, что

p = a2 + b2

с относительной ошибкой eps2/(2 * (a2 + b2)).

Чтобы получить точность до 10– 5, совершенно ненужно брать eps = 10– 5; более чем достаточно eps = 0.004. Эта программа сходится очень быстро.

Игра 13.

Задача о наиболее длинном взятии не имеет однозначного решения. Вот как ее сделал я — с учетом моих привычек в программировании и упрощений, предоставляемых моим микрокомпьютером.

Я представил всю игру одной-единственной цепочкой символов с кодами возврата каретки, расположенными надлежащим образом — так, чтобы визуализация игры сводилась к визуализации этой цепочки бее какого-либо дополнительного исследования. Куры обозначаются в этой цепочке присвоенными им буквами, лисы — буквами X, пустые игровые поля обозначаются точками. Остальные символы (пробелы или возврат каретки) не отвечают никаким используемым игровым полям. Я добавил в начале и в конце по строчке пробелов, чтобы не было необходимости изучать возможность некоторых перемещений на границе игрового поля.