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

Таким образом, все три распознаваемые программой случая являются единственными возможными исходами программы, и каждый из них может произойти.

Таким образом, перед нами — очень забавный алгоритм, который дает значение квадратного корня, и который определяет случай, когда 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 ).

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

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

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

x g 2(x)

1 2

2 5

3 10

4 17

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

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

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

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

p 2+ q 2 = a 2+ b 2.

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

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

Вычислим s :

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

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

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

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

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

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

p 2+ q 2 = a 2+ b 2.

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

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

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

p 2= ( a 2+ b 2) * (1 − q 2/( a 2+ b 2)).

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

p = √ a 2+ b 2

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

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

Игра 13.

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

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

Я не храню положений лис с помощью двух переменных. Я отыскиваю их положение в цепочке, представляющей игру, с помощью функции «положение» языка LSE . Это — существенная деталь. Поиск наиболее длинного взятия я осуществляю итеративно. Я образую две цепочки:

— одна из них содержит список кур, уже взятых при исследовании данного пути (это — последовательность букв взятых кур),

— вторая цепочка содержит дуплеты: положение в игре и рассматриваемое направление (мы осуществляем взятие, исходя из положения x и двигаясь в направлении, обозначенном через i ).

Находясь в положении x и в направлении i я смотрю, есть ли кура на поле x + d [ i ]. Если ее нет, то в этом направлении никакое взятие невозможно. Если же такая кура есть, то я смотрю, не содержится ли буква этой куры в цепочке уже взятых кур. Если содержится, то в этом направлении ничего не сделаешь. Если же эта кура еще не взята, то я проверяю, действительно ли поле x + 2 * d [ i ] содержит именно точку — в противном случае никакого взятия нет. Действуя таким образом, я не сталкиваюсь ни с какими трудностями на краях (там есть предохранительная строка, и она не содержит ни одной куры).

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