My-library.info
Все категории

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

На электронном книжном портале my-library.info можно читать бесплатно книги онлайн без регистрации, в том числе Жак Арсак - Программирование игр и головоломок. Жанр: Программирование издательство -, год 2004. В онлайн доступе вы получите полную версию книги с кратким содержанием для ознакомления, сможете читать аннотацию к книге (предисловие), увидеть рецензии тех, кто произведение уже прочитал и их экспертное мнение о прочитанном.
Кроме того, в библиотеке онлайн my-library.info вы найдете много новинок, которые заслуживают вашего внимания.

Название:
Программирование игр и головоломок
Автор
Издательство:
-
ISBN:
-
Год:
-
Дата добавления:
17 сентябрь 2019
Количество просмотров:
159
Читать онлайн
Жак Арсак - Программирование игр и головоломок

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

Жак Арсак - Программирование игр и головоломок - описание и краткое содержание, автор Жак Арсак, читайте бесплатно онлайн на сайте электронной библиотеки My-Library.Info
Рассматриваются способы программирования различных занимательных игр и головоломок с числами, геометрическими фигурами и др. Изложение большинства игр и головоломок ведется в несколько этапов. Сначала разъясняется сама постановка задачи и требования, предъявляемые к алгоритму ее решения.В следующем разделе книги обсуждается сам алгоритм и возможные пути его реализации.В конце книга по многим играм и головоломкам даются наброски их программной реализации. Используемый при этом язык типа Паскаля допускает перевод на другие широко распространенные языки программирования.Для начинающих программистов, студентов вузов и техникумов.

Программирование игр и головоломок читать онлайн бесплатно

Программирование игр и головоломок - читать книгу онлайн бесплатно, автор Жак Арсак

r2 − b2 = ар.

Положим r + b = 2u, rb = 2v (r и b нечетны). Отсюда получаем 4uv = ар.

Поскольку r = u + v, где r нечетно, получаем, что u и v не могут быть числами одинаковой четности, так что одно из них четно, а другое нечетно. Так как а является степенью двойки, то нечетный сомножитель относится к p. Выявим его, полагая р = s2t, где s нечетно, a t ≥ 1 (p четно).

Напомним, что а = 2k. В этих обозначениях 4uv = ар = s2k+t, uv = s2k+t−2.

Возможные решения для пары u, v имеют вид пар

s'2k+t-2, s''

где s's" = s.

Покажем сначала, что s" — меньший из этих двух элементов пары. Вследствие t ≥ 1 имеем ktk + t − 2.

Вследствие p < а последовательно выводим

s2t < 2k,

s's"2t < 2k.

s's" < 2k-t ≤ 2k+t-2 ≤ s'22k+t-2

(потому что s' нечетен и не меньше 1).

Следовательно, нужно взять u = s'2k+t-2, v = s".

Покажем теперь, что нужно обязательно взять s' =1, s" = s. По выбору u и v

b = 2k+t−2s' − s" < а = 2k.

Отсюда получаем:

s" > 2k+t−2s' − 2k,

и, так как t ≥ 1:

s" > 2k−1s' − 2k,

s = s's" > 2k−1s'2 − 2ks = 2k−1s' (s' − 2).

Вследствие р = s2t < а = 2k выводим s < 2kt ≤ 2k−1.

Объединим два полученных неравенства:

2k−1s' (s' − 2) < x < 2k−1, поэтому s' (s' − 2) < 1.

Единственное нечетное число s', удовлетворяющее этому соотношению, это s' = 1. Следовательно, у нас остается единственная возможность:

u = 2k+t-2, v = s,

b = uv = 2k+t-2 − s < а = 2k,

s > 2k+t-2 − 2k.

Так как s < 2kt, то t должно быть таким, чтобы

2kt > 2k+t-2 − 2k.

Поскольку t должно быть строго положительно, то его единственными возможными значениями являются t = 1 и t = 2.

При t = 1 имеем

p = 2s, b = 2kts = a/2 − p/2.

Следовательно, если 2b = аp, то n — квадрат числа (а + p)/2 = аb.

При t = 2 имеем

p = 4s, b = 2ks = ap/4.

Следовательно, если p = 4(ab), то n — квадрат числа a + p/4 = 2аb.

Этим исчерпываются случаи, когда n может быть полным квадратом.

Можно спросить себя, могут ли эти различные случаи действительно осуществляться. Заметим, что при вступлении в цикл у нас b = 1, a = 4. После этого b может быть изменено добавлением а, т. е. кратным числа 4. Следовательно, b остается сравнимым с 1 по модулю 4. В трех возможных случаях:

p = 0, r = b,

p = а − 2b, r = ab,

p = 4 (ab), r = 2ab,

первый случай — единственный, в котором квадратный корень из n сравним с 1 по модулю 4; два других дают квадратный корень, сравнимый с 3 по модулю 4. При выходе из цикла равенство

b = ар + b2

с учетом соотношений p < a, b < a дает n < 2a2 и, следовательно, при выходе из цикла a2 > n/2. Равенство

ар = nb2

дает p = (nb2)/a < n/а.

Если окажется, что n/а < a, то непременно p < а и цикл закончен. Чтобы цикл остановился, необходимо, чтобы a2 > n/2, и цикл заведомо останавливается, если a3 > n.

Следовательно, все зависит от положения n по отношению к степеням двойки. Существует такое целое n, что

4q < n < 4q+1.

Возможны два случая. Во-первых, может выполняться неравенство

4q = 22q < n < 22q+1,

и тогда для k = q число a2 = 22q > n/2 может быть значением остановки, но в этом нет уверенности. С другой стороны, если

22q+1 < n < 22q+2,

то единственное значение a, удовлетворяющее условию a2 > n/2, есть a = 2q+1, и для этого значения имеем a2 > n, что гарантирует остановку. Поскольку r = ab, то а = r + b > r и, следовательно, a2 > n.

Во втором случае

r = 2ab и b < а, откуда а < 2ab = r.

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

Таким образом, перед нами — очень забавный алгоритм, который дает значение квадратного корня, и который определяет случай, когда n не является корнем, но в этом случае не дает никакой дополнительной информации.

Программа заведомо останавливается при а = 2q+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. Чтобы ясно увидеть эту трудность, осуществим введение новых переменных без разрушения старых. Перепишем наш цикл:

ПОКА qeps ВЫПОЛНЯТЬ

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

p' := (2 * s + 1) * p; q' := s * q

p := p'; q := q'

ВЕРНУТЬСЯ

Рассмотрим действия этой программы, производимые над данными a, b с одной стороны и над ac, bc с другой.


Жак Арсак читать все книги автора по порядку

Жак Арсак - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки My-Library.Info.


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

Отзывы читателей о книге Программирование игр и головоломок, автор: Жак Арсак. Читайте комментарии и мнения людей о произведении.

Прокомментировать
Подтвердите что вы не робот:*
Подтвердите что вы не робот:*
Все материалы на сайте размещаются его пользователями.
Администратор сайта не несёт ответственности за действия пользователей сайта..
Вы можете направить вашу жалобу на почту librarybook.ru@gmail.com или заполнить форму обратной связи.