Назад
Задача 179422 • Сложность: 3 • 9-11 класс
Задача

Петя приобрёл в магазине "Машины Тьюринга и другие вычислительные устройства" микрокалькулятор, который может по любым действительным числам 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?

Разделы:
Многочлены Теория алгоритмов Индукция Алгебраические методы
Источники:
Московская математическая олимпиада 1982 год 10 класс Олимпиады и турниры
Количество версий:
2
Решение

  а) Обозначим  φ(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  строится индуктивно с помощью "схемы Горнера":

P(х − 1),  ...,  fn−1,  P(fn−1 − 1),  φ(fn−1 − 1, х − 1) = хfn−1 = fn − 1,  0,  φ(fn−1, 0)) = fn.
  б) Пусть  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(х) не существует.

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Войти Зарегистрироваться
Комментариев нет