|
|
 |
Условие
Петя приобрёл в магазине "Машины Тьюринга и другие вычислительные
устройства" микрокалькулятор, который может по любым действительным числам
x и y вычислить xy + x + y + 1 и не имеет других операций. Петя хочет написать "программу" для вычисления многочлена
1 + x + x² + ... + x1982. Под
"программой" он понимает такую последовательность многочленов f1(x), ..., fn(x), что
f1(x) = x и для любого i = 2, ..., n fi(x) – константа или
fi(x) = fj(x)·fk(x) + fk(x) + fj(x) + 1, где j < i, k < i, причём fn(x) = 1 + x + ... + x1982.
а) Помогите Пете написать "программу".
б) Можно ли написать "программу", если калькулятор имеет только одну операцию xy + x + y?
Решение
а) Обозначим φ(x, y) = xy + x + y + 1 = (x + 1)(y + 1).
Многочлен x – 1 вычисляется по программе P(x – 1): x, – 3/2, –3, φ(– 3/2, x) = – ½ (x + 1), φ(– 3, – ½ (x + 1)) = –2(½ – x/2) = x – 1.
Отсюда следует, что если есть программа для вычисления многочлена g(x), то есть и программа для вычисления многочлена g(х) – 1.
Программа Р(fn) вычисления многочлена fn(x) = 1 + x + ... + хn строится индуктивно с помощью "схемы Горнера":
б) Пусть g1, g2, ..., gn – произвольная программа. Индукцией докажем, что если gn – не константа, то
gn(− 1) = − 1.
База. g1(х) = х.
Шаг индукции. gn = gigj + gi + gj (i, j < n), и, например, gi − не константа. Тогда gi(− 1) = − 1 и
gn(− 1) = − gj(− 1) − 1 + gj(− 1) = − 1.
Если f(х) = 1 + x + x² + ... + x1982, то f(− 1) = 1. Поэтому программы для вычисления f(х) не существует.
Замечания
Все многочлены, вычислимые на калькуляторе с операцией φ(х, y) = xy + x + y, имеют вид A(х + 1)n − 1, и каждый такой многочлен вычислим.
