Страница: 1 [Всего задач: 4]
В массивах a: array[0..k] of integer и b:
array[0..l] of integer хранятся коэффициенты двух
многочленов степеней k и l. Поместить в массив
c: array[0..m] of integer коэффициенты их
произведения. (Числа
k,l,m — натуральные,
m = k + l; элемент массива с индексом i
содержит коэффициент при степени i.)
(В. Баур, Ф.Штрассен)
Дана программа вычисления значения некоторого многочлена
P(x1,..., xn), содержащая только команды
присваивания. Их правые части — выражения, содержащие
сложение, умножение, константы, переменные
x1,..., xn
и ранее встречавшиеся (в левой части) переменные. Доказать,
что существует программа того же типа, вычисляющая все
n производных
P/x1,...,P/xn,
причём общее число арифметических операций не более чем
в C раз превосходит число арифметических операций
в исходной программе. Константа C не зависит от n.
Предложенный выше алгоритм перемножения многочленов требует
порядка n2 действий для перемножения двух многочленов
степени n. Придумать более эффективный (для больших n)
алгоритм, которому достаточно порядка
nlog 4/log 3 действий.
(Для знакомых с основами анализа; сообщил
А. Г.Кушниренко) Дополнить алгоритм вычисления значения
многочлена в заданной точке по схеме Горнера вычислением
значения его производной в той же точке.
Страница: 1 [Всего задач: 4]
Фильтр
