Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

(а) Многочлен f (x) = x2^k можно вычислить за k умножений (а не за 2k по Горнеру):

p1 = x·x = x2, p2 = p1·p1 = x4, ..., pk = pk–1·pk–1, f (x) = pk.

(б) Многочлен f (x) = x15 можно вычислить за пять (×, :)-операций, так как f (x) = x15 = x16 : x = x2^4 : x.

(в) Многочлен f (x) = xn + xn–1 + ... + x + 1 вычисляется по формуле геометрической прогрессии: f (x) = (xn+1 – 1) : (x – 1).

(г) Многочлен

f (x) = xn +

(

n 1

)

xn–1 + ... +

(

n n–1

)

x + 1;

есть бином Ньютона: f (x) = (x + 1)n.

Число примеров можно, конечно, увеличить.

Упражнения

1. Докажите, что многочлены (а) и (б) не могут быть вычислены быстрее.

2. В «Задачнике «Кванта» № 12 за 1973 год была помещена задача (М240): доказать, что многочлен f (x) = xn может быть вычислен не более чем за 3/2 log2 n + 1 (×, :)-операций (n — натуральное число).

Пользуясь результатом этой задачи, оцените число операций для вычисления многочленов (в) и (г).

Решение

Рекомендуем скачать другие рефераты по теме: бесплатные курсовые работы, банк курсовых.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата