Страница:
<< 3378 3379 3380 3381
3382 3383 3384 >> [Всего задач: 21755]
Та же задача, если требуется, чтобы число операций было
пропорционально
log
n. (Переменные должны быть
целочисленными.)
(В. Баур, Ф.Штрассен)
Дана программа вычисления значения некоторого многочлена
P(
x1,...,
xn), содержащая только команды
присваивания. Их правые части — выражения, содержащие
сложение, умножение, константы, переменные
x1,...,
xn
и ранее встречавшиеся (в левой части) переменные. Доказать,
что существует программа того же типа, вычисляющая все
n производных
P/
x1,...,
P/
xn,
причём общее число арифметических операций не более чем
в
C раз превосходит число арифметических операций
в исходной программе. Константа
C не зависит от
n.
Предложенный выше алгоритм перемножения многочленов требует
порядка
n2 действий для перемножения двух многочленов
степени
n. Придумать более эффективный (для больших
n)
алгоритм, которому достаточно порядка
nlog 4/log 3 действий.
|
|
|
Сложность: 4 Классы: 10,11
|
В двух различных плоскостях лежат два треугольника:
ABC и
A1B1C1. Прямая
AB пересекается с прямой
A1B1, прямая
BC — с
прямой
B1C1, прямая
CA — с прямой
C1A1. Доказать, что прямые
AA1,
BB1 и
CC1 или все три пересекаются в одной точке, или
параллельны друг другу.
Даны прямая и две точки
A и
B по одну сторону от неё. Найти на прямой такую
точку
M, чтобы сумма
MA +
MB равнялась заданному отрезку.
Страница:
<< 3378 3379 3380 3381
3382 3383 3384 >> [Всего задач: 21755]