|
|
 |
Условие
Петя купил в магазине "Машины Тьюринга и другие вычислительные устройства" микрокалькулятор, который может выполнять следующие операции:
по любым числам x и y он вычисляет x + y, x − y и (при x ≠ 0). Петя утверждает, что он может возвести любое положительное число в квадрат с помощью своего микрокалькулятора, сделав не более 6 операций. А вы можете это сделать? Если да, то попробуйте перемножить любые два положительных числа, сделав не более 20 операций (промежуточные результаты можно записывать, неоднократно используя их в вычислениях).
Решение
Приведём схему возведения любого числа x(x ≠ 0) в квадрат за 6 операций. Промежуточные результаты будем обозначать
x1, x2,..., x6; разумеется, их можно запоминать и неоднократно использовать в последующих вычислениях. Итак, надо последовательно вычислить:
x1 = 1/x, x2 = x + 1, x3 = 1/x2 = 1/(x + 1), x4 = x1 − x3 = 1/x − 1/(x + 1) = 1/(x2 + x), x5 = 1/x4 = x2 + x, x6 = x5 − x = x2.
Пусть надо перемножить числа x и y. Вычисления проводим в следующем порядке: сначала найдём x + y и x − y (2 операции), затем возведём эти числа в квадрат, как в пункте а) (ещё 12 операций), затем вычисляем
z = (x + y)2 − (x − y)2 и 1/z = 1/(4xy) (2 операции), потом — последовательным сложением —
2/(4xy) = 1/(4xy) + 1/(4xy), 3/(4xy) = 2/(4xy) + 1/(4xy) и 1/(xy) = 3/(4xy) + 1/(4xy) (3 операции) и, наконец, 1 / (1/(xy)) = xy. Итого нам
потребовалось 2 + 12 + 2 + 3 + 1 = 20 операций. (Решение задачи М791 из журнала "Квант".)
