Программирование игр и головоломок - [67]
Головоломка 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 = (2s + 1)>2p>2 + s>2q>2 = s>2 (4р>2 + q>2) + 4sp + р>2.
Вычислим s:
r := q>2/p>2, s = r/(r + 4) = q>2(q>2 + 4p>2),
откуда, наконец,
s (4р>2 + q>2) = q>2.
Возвращаясь отсюда к предыдущему соотношению, получаем
p'>2 + q'>2 = sq>2 + 4sp>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. Эта программа сходится очень быстро.
3. Игры без стратегии
Игра 13.
Задача о наиболее длинном взятии не имеет однозначного решения. Вот как ее сделал я — с учетом моих привычек в программировании и упрощений, предоставляемых моим микрокомпьютером.
Я представил всю игру одной-единственной цепочкой символов с кодами возврата каретки, расположенными надлежащим образом — так, чтобы визуализация игры сводилась к визуализации этой цепочки бее какого-либо дополнительного исследования. Куры обозначаются в этой цепочке присвоенными им буквами, лисы — буквами X, пустые игровые поля обозначаются точками. Остальные символы (пробелы или возврат каретки) не отвечают никаким используемым игровым полям. Я добавил в начале и в конце по строчке пробелов, чтобы не было необходимости изучать возможность некоторых перемещений на границе игрового поля.
Я не храню положений лис с помощью двух переменных. Я отыскиваю их положение в цепочке, представляющей игру, с помощью функции «положение» языка LSE. Это — существенная деталь. Поиск наиболее длинного взятия я осуществляю итеративно. Я образую две цепочки:
— одна из них содержит список кур, уже взятых при исследовании данного пути (это — последовательность букв взятых кур),
— вторая цепочка содержит дуплеты: положение в игре и рассматриваемое направление (мы осуществляем взятие, исходя из положения x и двигаясь в направлении, обозначенном через i).
Находясь в положении x и в направлении i я смотрю, есть ли кура на поле x + d[i]. Если ее нет, то в этом направлении никакое взятие невозможно. Если же такая кура есть, то я смотрю, не содержится ли буква этой куры в цепочке уже взятых кур. Если содержится, то в этом направлении ничего не сделаешь. Если же эта кура еще не взята, то я проверяю, действительно ли поле x + 2 * d[i] содержит именно точку — в противном случае никакого взятия нет. Действуя таким образом, я не сталкиваюсь ни с какими трудностями на краях (там есть предохранительная строка, и она не содержит ни одной куры).

Java Enterprise Edition (Java EE) остается одной из ведущих технологий и платформ на основе Java. Данная книга представляет собой логичное пошаговое руководство, в котором подробно описаны многие спецификации и эталонные реализации Java EE 7. Работа с ними продемонстрирована на практических примерах. В этом фундаментальном издании также используется новейшая версия инструмента GlassFish, предназначенного для развертывания и администрирования примеров кода. Книга написана ведущим специалистом по обработке запросов на спецификацию Java EE, членом наблюдательного совета организации Java Community Process (JCP)

Что такое ГЕЙМДИЗАЙН? Это не код, графика или звук. Это не создание персонажей или раскрашивание игрового поля. Геймдизайн – это симулятор мечты, набор правил, благодаря которым игра оживает. Как создать игру, которую полюбят, от которой не смогут оторваться? Знаменитый геймдизайнер Тайнан Сильвестр на примере кейсов из самых популярных игр рассказывает как объединить эмоции и впечатления, игровую механику и мотивацию игроков. Познакомитесь с принципами дизайна, которыми пользуются ведущие студии мира! Создайте игровую механику, вызывающую эмоции и обеспечивающую разнообразие.

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

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

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

Python - объектно-ориентированный язык сверхвысокого уровня. Python, в отличии от Java, не требует исключительно объектной ориентированности, но классы в Python так просто изучить и так удобно использовать, что даже новые и неискушенные пользователи быстро переходят на ОО-подход.