Задача 79406

Темы:    [ Теория алгоритмов (прочее) ] [ Арифметические действия. Числовые тождества ] [ Процессы и операции ]

Сложность: 3+ Классы: 7,8,9

Условие

Автор: Гашков С.Б.

Петя купил в магазине "Машины Тьюринга и другие вычислительные устройства" микрокалькулятор, который может выполнять следующие операции: по любым числам x и y он вычисляет x + y, x − y и (при x ≠ 0). Петя утверждает, что он может возвести любое положительное число в квадрат с помощью своего микрокалькулятора, сделав не более 6 операций. А вы можете это сделать? Если да, то попробуйте перемножить любые два положительных числа, сделав не более 20 операций (промежуточные результаты можно записывать, неоднократно используя их в вычислениях).

Решение

Приведём схему возведения любого числа x(x ≠ 0) в квадрат за 6 операций. Промежуточные результаты будем обозначать x₁, x₂,..., x₆; разумеется, их можно запоминать и неоднократно использовать в последующих вычислениях. Итак, надо последовательно вычислить: x₁ = 1/x, x₂ = x + 1, x₃ = 1/x₂ = 1/(x + 1), x₄ = x₁ − x₃ = 1/x − 1/(x + 1) = 1/(x² + x), x₅ = 1/x₄ = x² + x, x₆ = x₅ − x = x².
Пусть надо перемножить числа x и y. Вычисления проводим в следующем порядке: сначала найдём x + y и x − y (2 операции), затем возведём эти числа в квадрат, как в пункте а) (ещё 12 операций), затем вычисляем z = (x + y)² − (x − y)² и 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 из журнала "Квант".)

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1983
выпуск
Номер	3
Задача
Номер	М791
олимпиада
Название	Московская математическая олимпиада
год
Номер	45
Год	1982
вариант
Класс	7
задача
Номер	1