Программирование игр и головоломок
Шрифт:
Запишите это символическое умножение и обозначьте его величины «в уме». После умножения на 3 величина «в уме» может быть только 0, 1 или 2. Замечая, что все 9 цифр, отличных от 0, использованы, вы можете узнать сумму величин «в уме» (10). Так как 6 не может быть связано с 2 «в уме», поскольку 3 x 6 + 2 = 20 дает 0 в качестве цифры единиц, а это исключено, то вы сможете таким образом полностью определить величины «в уме», связанные с этими двумя цифрами. Это разрешает задачу о решениях, оканчивающихся на 3.
Так как величины «в уме» являются ключом к задаче, составьте маленькую таблицу, показывающую для каждой цифры, как она может быть получена в качестве цифры единиц произведения некоторой
Если число кончается на 9, то результат кончается на 7, и 2 оказывается «в уме». Можно почти закончить вручную. Во всяком случае вручную легко найти какое-то решение. Программа для компьютера остается необходимой для того, чтобы найти все остальные решения.
Головоломка 12.
Легко! Чтобы доказать эту теорему, достаточно доказать, что ее утверждение справедливо для любого n, кратного трем. Давайте-ка их все переберем. Сначала для каждого n вычислим первое число n, сумму кубов цифр числа n. Если n' меньше n, то дальше идти незачем. Покажите, что n' кратно трем. Если оно меньше n, то оно уже испытано, и для него результат известен.
Можете ли вы найти такое k, что при n > k имеем n' < n?
Если можете, то достаточно проверить искомое свойство для всех n, кратных трем и меньших k. Это делается очень быстро.
Головоломка 13.
Эти варианты исследуются таким же способом. Проделайте сначала вручную пробы, чтобы увидеть, как ведут себя последовательности сумм кубов цифр для чисел п, не кратных трем, различая случаи: n на единицу больше кратного трем, и на 2 единицы больше кратного трем.
В случае суммы квадратов вы знаете, какой результат нужно доказывать. Это легко…
Головоломка 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·106, что немного. Возникают еще некоторые сомнения, как только принимаются во внимание деления…
Чтобы узнать, становится ли последовательность периодической, вы можете ограничиться рассмотрением разностей ai– aj, где i и j меняются в соответствии с вполне определенными законами, Вам следует рассматривать н. о. д. этих разностей и n. Это невыполнимо для каждой разности и потребует много времени.
Идея в том, чтобы образовать произведение на некоторое число этих разностей по модулю n, а затем брать н. о. д. этих разностей и n. Если одна из этих разностей имеет с n н. о. д., отличный от 1, то для произведения будет выполняться то же самое. Выбор числа членов для участия в произведении предоставляется вашему усмотрению. Если членов слишком мало, то вы вычисляете много н о. д. и замедляете метод. Если членов много, то вы делаете ненужные операции! вы долго ждете перед тем, как обнаружить делитель…
2. Если эта первая программа уже готова, переходите к гораздо большим числам. Нужно выполнить следующие операции:
произведение двух чисел по модулю n,
н. о. д. двух чисел, числа n и числа, меньшего n.
Настоящая трудность — это произведение по модулю n. Так как к ней часто обращаются, то она должна быть оптимальной…
Может оказаться опасным пускаться в этот метод Полларда, не зная, является ли исследуемое число составным. Используйте для этого тест Ферма.