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