ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98013
Темы:    [ Процессы и операции ]
[ Теория алгоритмов (прочее) ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Фомин С.В.

Даны 1000 линейных функций:  fk(x) = pkx + qk  (k = 1, 2, ..., 1000).  Нужно найти значение их композиции  f(x) = f1(f2(f3(...f1000(x)...)))  в точке x0. Докажите, что это можно сделать не более чем за 30 стадий, если на каждой стадии можно параллельно выполнять любое число арифметических операций над парами чисел, полученных на предыдущих стадиях, а на первой стадии используются числа  p1, p2, ..., p1000q1, q2, ..., q1000,  x0.


Решение

    f(x) = p1p2 ... p1000x0 + p1p2 ... p999q1000 + p1p2 ...p998q999 + ... + p1q2 + q1.
  Самое "длинное" из слагаемых – произведение 1001 числа  p1p2 ...p1000x0  – вычисляется за 10 стадий, поскольку  1001 < 210:  на первой стадии вычисляем 500 произведений  p1p2, p3p4, ..., p999p1000,  на второй – 250 произведений  (p1p2)(p3p4), ..., (p997p998)(p999p1000)
и т. д. Параллельно вычислим все остальные слагаемые.
  Аналогично за 10 следующих стадий можно вычислить сумму  f(x)  1001 слагаемого.

Замечания

5 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 1988/1989
Номер 10
вариант
Вариант весенний тур, основной вариант, 9-10 класс
Задача
Номер 3

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .