Схема Горнера

Схема Горнера – это алгоритм деления (деление схемой Горнера) многочленов, записываемый для

частного случая, если частное равно двучлену .

Построим этот алгоритм:

Предположим, что - делимое

- частное (его степень, вероятно, будет на удиницу меньше),

r - остаток (т.к. деление осуществляется на многочлен 1-ой степени, то степень остатка будет на

единицу меньше, т.е. нулевая, таким образом, остаток это константа).

По определению деления с остатком P(x) = Q(x) (x–a) + r. После подстановки выражений многочленов

получаем:

Раскрываем скобки и приравниваем коэффициенты при одинаковых степенях, после чего выражаем

коэффициенты частного через коэффициенты делимого и делителя:

Удобно вычисления сводить в такую таблицу:

В ней выделены те клетки, содержимое которых участвует в вычислениях на очередном шаге.

Схема Горнера примеры:

Пусть надо поделить многочлен на двучлен x–2.

Составляем таблицу с двумя строками. В 1 строку выписываем коэффициенты нашего многочлена. Во

второй строке будем получать коэффициенты неполного частного по следующей схеме: в первую очередь

переписываем старший коэффициент данного многочлена, далее, дабы получить очередной коэффициент,

умножаем последний найденный на а=2 и складываем с соответствующим коэффициентом

многочлена F(x). Самый последний коэффициент будет остатком, а все предыдущие – коэффициентами

неполного частного.

34. Найбільший спільний дільник (НСД). Алгоритм Евкліда.