|
|
 |
Условие
(В. Баур, Ф.Штрассен)
Дана программа вычисления значения некоторого многочлена
P(x1,..., xn), содержащая только команды
присваивания. Их правые части — выражения, содержащие
сложение, умножение, константы, переменные
x1,..., xn
и ранее встречавшиеся (в левой части) переменные. Доказать,
что существует программа того же типа, вычисляющая все
n производных
P/
x1,...,
P/
xn,
причём общее число арифметических операций не более чем
в C раз превосходит число арифметических операций
в исходной программе. Константа C не зависит от n.
Подсказка
Можно считать, что каждая команда — сложение двух чисел,
умножение двух чисел или умножение на константу.
Использовать индукцию по числу команд, применяя индуктивное
предположение к программе, получающейся отбрасыванием
первой команды.
