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

2. Если эта первая программа уже готова, переходите к гораздо большим числам. Нужно выполнить следующие операции:

произведение двух чисел по модулю n,

н. о. д. двух чисел, числа n и числа, меньшего n.

Настоящая трудность — это произведение по модулю n. Так как к ней часто обращаются, то она должна быть оптимальной…

Может оказаться опасным пускаться в этот метод Полларда, не зная, является ли исследуемое число составным. Используйте для этого тест Ферма.

В этом единственную трудность представляет возведение x в степень n ? 1 по модулю n.

Следовательно, пусть нужно вычислить y = x^p.

Примем следующую индуктивную гипотезу: искомый результат имеет вид y = u^kw.

Если k есть нуль, то u^k = 1 и потому у = w, и все закончено.

Если k не нуль и если k четно, то u^k = u^2(k/2) = (u²)^k/2.

Заменяя u на u * u и k на k/2 возвращаемся к общей ситуации.

Если k нечетно, то u^k = u * u^2((k?1)/2)

w * u^k = (w * u) * (u²)^{(k ?1)/2}

Заменим w на w * u, u на u * u и k на целую часть от k/2.

Все это должно проделываться по модулю n. Операции над k не содержат трудностей. Если числа достаточно малы, то вы действуете обычными умножениями или делениями.

Если же числа не являются достаточно малыми, то все сводится к предыдущему случаю. Но у вас здесь есть элемент ответа. Я уже говорил вам, как можно вычислить y = x^p с помощью бинарного разложения p, выполняя умножения только по модулю n. Переделайте то же рассуждение для y = p * x, заменяя возведение в степень умножением, а умножение — сложением. Предположите, что результат имеет вид

y = k * u + w.

Если k четно, то k * u (k/2) * (u + u), и т. д.

Сложения нужно делать по модулю n, что не требует, впрочем, операции деления…

Я на своем компьютере получил отличные результаты для теста Ферма. А метод Полларда-Брента еще остается очень медленным. Работайте надежно. Можно ли пользоваться программой, в правильности которой вы не уверены?

Головоломка 17.

Подсказка: эта программа сообщает, делится ли n на b.

Головоломка 18.

Снова подсказка: эта программа выводит НЕТ, если n не является точным квадратом; в противном случае она выводит квадратный корень из n. Но это из области бесполезных подсказок. Как вы сможете показать, что эта программа действительно делает то, что я анонсировал? Испытав ее? Вы можете испытать все целые?

По индукции? Почему бы и нет? Напишите мне, если получится…

Головоломка 19.

Не пренебрегайте крохами информации, которые можно извлечь из текста программы. Вполне правдоподобна гипотеза, что eps — параметр, характеризующий точность, маленький и потому вещественный. Следовательно, p и q, и — вследствие этого — a и b имеют хорошие шансы оказаться вещественными. Примите это как гипотезу, касающуюся типа данных и результата.

Вы не можете исследовать плоскость a, b, чтобы увидеть, что же именно вычисляет эта программа. Но можно сделать несколько простых замечаний. Пусть f(a, b) — значение, вычисляемое программой.

Вы без особых усилий сумеете показать, что

f(a, b) = f (b, a),

f(ac, bc) = cf(a, b)

и вследствие этого

f(a, b) = bf(a/b, 1).

Ho g(x) = f (x, 1) — функция только одного аргумента. Можно ограничиться областью x ? 1. Я написал программу, вычисляющую g (простой и очевидный вариант предыдущей программы), а затем вычислил g для

x = 1, 2, 3, …, 10,

x = 1.1, 1.2, 1.3, …, 1.9.

Природа функции g становится очевидной, если исходить из этой таблицы. Уразумев, что именно нужно доказать, мы справимся с этим без труда.

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

Игра 6.

Единственная задача: считать белые шашки. На самом деле, черные можно получить, сравнивая шашку на шашкой в тайной комбинации и в комбинации, предложенной игроком.

Для подсчета белых шашек у вас есть много возможностей.

1. Во время подсчета черных шашек удалите из тайной комбинации и из комбинации, предложенной игроком, находящиеся в соответствии элементы (имеющие одинаковые значения и одинаковые места). Затем для каждого из элементов, оставшихся в предложенной комбинации, посмотрите, участвует ли он в тайной комбинации, и если да, то учтите его белой шашкой и удалите его из тайной комбинации.

Этот метод требует, чтобы вы создали копию тайной комбинации, Это стоит не слишком дорого…

2. Для каждого из возможных значений шашек (6, если есть 6 цветов) подсчитайте число шашек этого цвета в тайной комбинации и в предложенной комбинации. Меньшее из этих двух чисел равно сумме белых и черных шашек, отвечающих этому цвету (почему?).