Олимпиадная задача: быстрая композиция линейных функций для 8-10 классов
Задача
Даны 1000 линейных функций: fk(x) = pkx + qk (k = 1, 2, ..., 1000). Нужно найти значение их композиции f(x) = f1(f2(f3(...f1000(x)...))) в точке x0. Докажите, что это можно сделать не более чем за 30 стадий, если на каждой стадии можно параллельно выполнять любое число арифметических операций над парами чисел, полученных на предыдущих стадиях, а на первой стадии используются числа p1, p2, ..., p1000, q1, 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 слагаемого.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь