Программирование игр и головоломок - [41]

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

Изучаемое число имеет вид 1000a + 100b + 10c + d при a ≥ b ≥ c ≥ d. И, так как не все цифры одинаковы, то непременно a > d.

Вы можете доказать, что результат первого вычитания кратен девяти, так что, переходя к первой разности, вы кое-что знаете о сумме a + b + c + d.

Каково бы ни было исходное число, первая из полученных разностей имеет вид 999u + 90v с v < u, 0 ≤ v, 0 < u ≤ 9. Так что-не так уж много чисел нужно испытывать…

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

Эта головоломка намного труднее. Используйте все данные задачи, хотя и кажется, что их не слишком много.

Господин P не может найти искомые числа. Следовательно, число р не является произведением двух простых чисел — в противном случае их разложение на множители было бы однозначным.

Господин S это знает. Но их сумма s может быть многими способами представлена в виде суммы двух чисел. Ни одна из этих пар не является парой простых чисел. Это условие гораздо более ограничительно: нужно вычеркнуть из списка возможных значений s все такие значения, которые являются суммами двух простых чисел — таковы 12 (так как 12 = 7 + 5), 13 (11 + 2). Компьютер позволит вам составить оставшийся список.

Господин P не может найти решение, так как его произведение может быть многими разными способами разложено в произведение двух чисел. Учитывая, что именно знает S, он исключает все пары, сумма которых вычеркнута. У него остается в точности одна пара. Каковы произведения, обладающие этим свойством?

Наконец, господин S получает решение. Следовательно, среди всех пар с суммой s есть только одна пара, дающая произведение с упомянутым выше свойством.

Компьютер нужен, чтобы порождать списки и вычеркивать в них. В конце должна оставаться одна и только одна пара.

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

Я предлагаю вам решить эту задачу в два приема.

1. Составьте сначала программу по методу Полларда-Брента о «маленькими» числами, иначе говоря, такими, что машина представляет их бее округления или усечения, Это зависит от машины. Я на своей машине могу получить около 8·10⁶, что немного. Возникают еще некоторые сомнения, как только принимаются во внимание деления…

Чтобы узнать, становится ли последовательность периодической, вы можете ограничиться рассмотрением разностей a_i − a_j, где i и j меняются в соответствии с вполне определенными законами, Вам следует рассматривать н. о. д. этих разностей и n. Это невыполнимо для каждой разности и потребует много времени.

Идея в том, чтобы образовать произведение на некоторое число этих разностей по модулю n, а затем брать н. о. д. этих разностей и n. Если одна из этих разностей имеет с n н. о. д., отличный от 1, то для произведения будет выполняться то же самое. Выбор числа членов для участия в произведении предоставляется вашему усмотрению. Если членов слишком мало, то вы вычисляете много н о. д. и замедляете метод. Если членов много, то вы делаете ненужные операции! вы долго ждете перед тем, как обнаружить делитель…

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. Но это из области бесполезных подсказок. Как вы сможете показать, что эта программа действительно делает то, что я анонсировал? Испытав ее? Вы можете испытать все целые?