В программирование алгоритмов. Оценка алгоритмов с точки зрения времени и объёма. Схема Горнера для вычисления значений многочленов

Представляется в виде:

Вычисление значения многочлена производится в порядке, определяемом скобками. Что имеем? Чтобы вычислить многочлен по схеме Горнера, надо выполнить n умножений и n-k сложений (здесь k- число коэффициентов многочлена, равных 0). Если а0=1,

то умножений будет n-1.

Можно показать, что для вычисления многочленов, общего вида нельзя построить схему более экономичную по числу операций, чем схема Горнера.

Схема горнера для вычисления значений многочлена

Прежде чем переходить к проектированию алгоритма решения определенной задачи мы должны, предварительно, убедится в корректности постановки задачи. Это означает, во-первых, существование решения задачи, во-вторых, если нет особых оговорок, единственность решения. Для этого необходимо наличие всех условий обеспечивающих существование и единственность решения. Для иллюстрации рассмотрим следующую задачу: На сумму 133 000 сумов необходимо купить 10 тетрадей по цене 5 000, 11 000 и 18 000 сумов. Определите количество каждого вида тетрадей.

Схема горнера для вычисления значений многочлена

Обычно многочлен представлен в виде:

или

Где ak это действительные числа, представляющие коэффициенты многочлена и xk это переменные многочлена.

Вышеупомянутый многочлен называют многочленом n-ой степени, то есть deg(f(x)) = n, где n представляет наивысшую степень переменной.