Программирование игр и головоломок
Шрифт:
Если k не нуль и если k четно, то uk = u2(k/2) = (u2)k/2.
Заменяя u на u * u и k на k/2 возвращаемся к общей ситуации.
Если k
w * uk = (w * u) * (u2)(k– 1)/2
Заменим w на w * u, u на u * u и k на целую часть от k/2.
Все это должно проделываться по модулю n. Операции над k не содержат трудностей. Если числа достаточно малы, то вы действуете обычными умножениями или делениями.
Если же числа не являются достаточно малыми, то все сводится к предыдущему случаю. Но у вас здесь есть элемент ответа. Я уже говорил вам, как можно вычислить y = xp с помощью бинарного разложения 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 цветов) подсчитайте число шашек этого цвета в тайной комбинации и в предложенной комбинации. Меньшее из этих двух чисел равно сумме белых и черных шашек, отвечающих этому цвету (почему?).
Так как вы нуждаетесь в подсчете по цветам шашек тайной комбинации и так как эти величины не меняются в течение партии, то вам может оказаться полезным сделать этот подсчет до запрашивания первой комбинации игрока, а затем сохранять его в виде таблицы…