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

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.

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

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

x g²(x)

1 2

2 5

3 10

4 17

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

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

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

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

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

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

p'² + q'² = (2s + 1)²p² + s²q² = s² (4р² + q²) + 4sp + р².

Вычислим s:

r := q²/p², s = r/(r + 4) = q² (q² + 4p²),

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

s (4р² + q²) = q².

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

p'² + q'² = sq² + 4sp² + р² = s (4р² + q²) + p² = p² + q².

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

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

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

p² + q^{2 =} a² + b², причем q < ерs.

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

p² = (a² + b²) * (1 ? q²/ (a² + b²)).

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

p = va² + b²

с относительной ошибкой eps²/(2 * (a² + b²)).

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

3. Игры без стратегии

Игра 13.

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

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

Я не храню положений лис с помощью двух переменных. Я отыскиваю их положение в цепочке,