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

Рассмотрим еще один важный пример функции на последовательности. Пусть дана последовательность коэффициентов многочлена p(x) по убыванию степеней:

p(x) = a₀xⁿ +a₁x^n-1 + ... + a_n

Нужно вычислить значение многочлена в точке x=t. Алгоритм, основанный на просмотре последовательности коэффициентов в направлении от старшего к младшему, называется схемой Горнера. Проиллюстрируем его идею на примере многочлена третьей степени:

p(x) = ax³+bx²+cx+d

Его можно представить в виде

p(x) = ((ax+b)x+c)x+d

Для вычисления значения многочлена достаточно трех умножений и трех сложений. В общем случае, многочлен представляется в следующем виде:

p(x) = (...((a₀x+a₁)x+a₂)x+...+a_n-1)x+a_n

Обозначим через p_k(x) многочлен k-ой степени, вычисленный по коэффициентам a₀, a₁, ..., a_k:

pk(x) = a₀x^k + a₁x^k-1 + ... + a_k

Тогда

p_k+1(x) = p_k(x)x + a_k+1

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

Выпишем алгоритм:

вещ алгоритм схема Горнера(вх: цел n, вещ a[n+1], вещ t)

| дано: n -- степень многочлена

| a[n+1] -- массив коэффициентов многочлена по

| убыванию степеней

| надо: вычислить значение многочлена в точке t

начало алгоритма

| вещ p; цел i;

| p := 0.0; // Инициализация значения многочлена

| i := 0;

| цикл пока i <= n

| | p := p * t + a[i]; // Вычисление нового значения по

| | // старому значению и добавленному коэффициенту

| | i := i + 1;

| конец цикла

| ответ := p;

конец алгоритма

5.2. Индуктивные функции

В рассмотренных выше примерах при добавлении к последовательности еще одного элемента новое значение функции на последовательности можно было вычислить, зная только старое значение функции и добавленный элемент. Обозначим через S_n последовательность

S_n = {a₀, a₁, ..., a_n-1}

длины n. С помощью знака & обозначим операцию приписывания нового элемента справа к последовательности (ее называют также конкатенацией):

S_n+1 = S_n&a_n = {a₀, a₁, ..., a_n-1, a_n}

Пусть f(S) - некоторая функция на множестве последовательностей, например, сумма элементов последовательности. Функция называется индуктивной, если при добавлении нового элемента к последовательности новое значение функции можно вычислить, зная только старое значение функции и добавленный элемент. На математическом языке функция

f:W Y

где W - множество всех последовательностей, составленных из элементов некоторого множества X, индуктивна, если существует функция G от двух аргументов

G:Y*X Y

такая, что для любой последовательности S из W и любого элемента a из X значение функции f на последовательности S, к которой добавлен элемент a, вычисляется с помощью функции G:

f(S&a) = G(f(S), a)

Функция G по паре (y,a), где y - старое значение функции f на последовательности S и a - элемент, добавленный к последовательности, вычисляет новое значение y, равное значению функции f на новой последовательности.

В примере с суммой элементов последовательности функция G равна сумме элементов y и a:

G(y, a) = y+a

В примере с максимальным элементом последовательности функция G равна максимуму:

G(y, a) = max(y,a)

В примере со схемой Горнера вычисления значения многочлена в точке t, где коэффициенты многочлена заданы в последовательности по убыванию степеней, функция G равна

G(y, a) = yt+a

Во всех трех случаях рассматриваемая функция на последовательности индуктивна.

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

алгоритм значение индуктивной функции( вх: последовательность S)

| дано: последовательность S

| надо: вычислить функцию y = f(S)

начало алгоритма

| y := значение функции f на пустой последовательности;

| встать в начало последовательности S;

| цикл пока в последовательности S есть

| | непрочитанные элементы

| | прочесть очередной элемент

| | последовательности S в (вых:x);

| | y := G(y, x);

| конец цикла

| ответ := y;

конец алгоритма

Таким образом, для каждой конкретной индуктивной функции надо лишь правильно задать ее значение на пустой последовательности (инициализация) и определить, как новое значение функции вычисляется через старое при добавлении к последовательности очередного элемента, т.е. задать функцию G(y,x). Схема вычисления для всех индуктивных функций одна и та же.

Однако не все функции на последовательностях являются индуктивными. Рассмотрим следующий пример. Пусть коэффициенты многочлена заданы в последовательности по убыванию степеней. Надо вычислить значение производной многочлена в точке x = 2. Обозначим через

S = {a₀, a₁, ..., a_n}

последовательность коэффициентов многочлена

p(x) = a₀xⁿ+a₁x^n-1+...+a_n

и через f(S) значение производной многочлена p′(x) в точке x=2:

f(S) = p′(2)

Покажем, что функция f не индуктивна. Достаточно указать две последовательности S1 и S2, такие, что значения функции f на них совпадают, но при добавлении к последовательностям S1 и S2 одного и того же элемента a новые значения функции уже не равны:

f(S₁) = f(S₂),

f(S₁&a)≠ f(S₂&a)

Возьмем последовательности

S₁ = {1},

S₂ = {1, -4,1}

Им соответствуют многочлены

p₁(x) = 1

p₂(x) = x²-4x+1

Производные многочленов равны

p′(x) = 0,

p′₂(x)= 2x-4

Значения обеих производных в точке x=2 равны нулю, т.е.

f(S₁) = p′₁(2) = 0,

f(S₂) = p′₂(2) = 2*2-4 = 0

Припишем теперь к обеим последовательностям элемент a = 1:

S₁&1 = {1,1},

S₂&1 = {1, -4,1,1}.

Новым последовательностям соответствуют многочлены

g₁(x) = x+1,

g₂(x) = x³-4x²+x+1

Их производные равны

g₁(x) = 1,

g₂(x) = 3x²-8x+1

Значения производных в точке x=2 равны соответственно

f(S₁&1) = g′₁(2) = 1

f(S₂&1) = g′₂(2) = 12-16+1 = -3

Мы видим, что значения f(S₁) и f(S₂) совпадают, но значения f(S₁&1) и f(S₂&1) не совпадают. Следовательно, функция f не индуктивна.