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

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

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

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

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

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

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

Чтобы узнать, становится ли последовательность периодической, вы можете ограничиться рассмотрением разностей 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 2) k /2.

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

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

w * u k = ( w * u ) * ( u 2) ( 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 становится очевидной, если исходить из этой таблицы. Уразумев, что именно нужно доказать, мы справимся с этим без труда.

Игра 6.

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

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

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

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

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