В рассмотренных выше примерах при добавлении к последовательности еще одного элемента новое значение функции на последовательности можно было вычислить, зная только старое значение функции и добавленный элемент. Обозначим через Sn последовательность
Sn = {a0, a1, ..., an-1}
длины n. С помощью знака & обозначим операцию приписывания нового элемента справа к последовательности (ее называют также конкатенацией):
Sn+1 = Sn&an = {a0, a1, ..., an-1, an}
Пусть 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 = {a0, a1, ..., an}
последовательность коэффициентов многочлена
p(x) = a0xn+a1xn-1+...+an
и через f(S) значение производной многочлена p′(x) в точке x=2:
f(S) = p′(2)
Покажем, что функция f не индуктивна. Достаточно указать две последовательности S1 и S2, такие, что значения функции f на них совпадают, но при добавлении к последовательностям S1 и S2 одного и того же элемента a новые значения функции уже не равны:
f(S1) = f(S2),
f(S1&a)≠ f(S2&a)
Возьмем последовательности
S1 = {1},
S2 = {1, -4,1}
Им соответствуют многочлены
p1(x) = 1
p2(x) = x2-4x+1
Производные многочленов равны
p′(x) = 0,
p′2(x)= 2x-4
Значения обеих производных в точке x=2 равны нулю, т.е.
f(S1) = p′1(2) = 0,
f(S2) = p′2(2) = 2*2-4 = 0
Припишем теперь к обеим последовательностям элемент a = 1:
S1&1 = {1,1},
S2&1 = {1, -4,1,1}.
Новым последовательностям соответствуют многочлены
g1(x) = x+1,
g2(x) = x3-4x2+x+1
Их производные равны
g1(x) = 1,
g2(x) = 3x2-8x+1
Значения производных в точке x=2 равны соответственно
f(S1&1) = g′1(2) = 1
f(S2&1) = g′2(2) = 12-16+1 = -3
Мы видим, что значения f(S1) и f(S2) совпадают, но значения f(S1&1) и f(S2&1) не совпадают. Следовательно, функция f не индуктивна.
