учебники, программирование, основы, введение в,

 

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

Как правило, компьютеры прежде всего используются для обработки значительных объемов информации. В большинстве алгоритмов информация читается последовательно, от начала к концу. Поэтому в программах очень часто встречаются фрагменты кода, вычисляющие некоторую функцию на последовательности элементов.
Предположим для простоты, что последовательность элементов находится в массиве. В реальных программах она также может читаться из файла или из более сложных структур данных - например, из списка. В любом случае можно встать в начало последовательности, прочесть ее очередной элемент, а также определить, есть ли еще непрочитанные элементы.
Рассмотрим пример: дана последовательность вещественных чисел, требуется вычислить сумму ее элементов. Запишем алгоритм на неформальном языке в самом общем виде.
вещ алгоритм сумма последовательности
| дано: последовательность вещественных чисел
| надо: вернуть сумму ее элементов
начало алгоритма
| вещ s, x;
| s := 0.0;
| встать в начало последовательности
| цикл пока есть непрочитанные элементы
| | прочесть очередной элемент последовательности в (вых:x)
| | s := s + x;
| конец цикла
| ответ := s;
конец алгоритма
Здесь перед словом "алгоритм" записывается тип возвращаемого значения, т.е. "вещ" для вещественного числа. Это означает, что алгоритм можно использовать как функцию. Например, для функции "sin" можно записать выражение
y = sin(x)
При вычислении выражения сначала вызывается алгоритм (функция), вычисляющий sin, затем значение, которое возвращается этим алгоритмом, присваивается переменной y. В нашем случае можно использовать выражение
y := сумма последовательности;
для вызова алгоритма и записи возвращаемого значения в переменную y.
В случае, когда последовательность чисел находится в массиве, алгоритм выглядит следующим образом:
вещ алгоритм сумма последовательности(вх: цел n, вещ a[n])
| дано: n    -- число элементов последовательности,
|       a[n] -- массив элементов последовательности
| надо: вернуть сумму элементов последовательности
начало алгоритма
| вещ s; цел i;
| s := 0.0;        // Инициализация значения ф-ции
| i := 0
| цикл пока i < n
| | s := s + a[i]; // Вычисление нового значения по старому
| |                //     значению и очередному элементу
| | i := i + 1;    // Переходим к следующему элементу
| конец цикла
| ответ := s;
конец алгоритма
Здесь целочисленная переменная i используется в качестве индекса элемента массива. Она последовательно принимает значения от 0 до n-1. Очередной элемент последовательности записывается как a[i].
Отметим следующие составные части алгоритма, вычисляющего функцию на последовательности элементов:

  1. инициализация значения функции для пустой последовательности - в данном случае

s : = 0.0;

  1. вычисление нового значения функции по прочтению очередного элемента последовательности. Новое значение вычисляется по старому значению и очередному прочитанному элементу. В данном случае это суммирование

s : = s+a[i].
Эти две части присутствуют в любом алгоритме, вычисляющем функцию на последовательности.
Рассмотрим еще один важный пример: вычисление максимального элемента последовательности. В отличие от суммы элементов, здесь не вполне ясно, каким значением надо инициализировать максимум, то есть чему равен максимум пустой последовательности. Для того, чтобы максимум одноэлементной последовательности вычислялся правильно, надо, чтобы максимум пустой последовательности был меньше любого числа. Поэтому максимум пустой последовательности не может быть обычным числом. В математике и в программировании очень полезен следующий прием: к обычным элементам добавляется специальный воображаемый элемент с заданными свойствами. Так были изобретены ноль, отрицательные числа, иррациональные и комплексные числа и т.п. В данном случае, таким воображаемым элементом является "минус бесконечность".
вещ алгоритм максимум последовательности(вх: цел n, вещ a[n])
| дано: n    -- число элементов последовательности,
|       a[n] -- массив элементов последовательности
| надо: вернуть максимум элементов последовательности
начало алгоритма
| вещ m; цел i;
| m := минус бесконечность; // Инициализация значения ф-ции
| i := 0;
| цикл пока i < n
| | если a[i] > m   // Вычисление нового значения по
| | | то m := a[i]; // старому значению и очередному эл-ту
| | конец если
| | i := i + 1;
| конец цикла
| ответ := m;
конец алгоритма
Здесь переменная m на любом шаге содержит максимальное значение для просмотренного начального отрезка последовательности, т.е. кандидата на максимум. Если очередной элемент больше, чем m, то он запоминается в переменной m и становится новым кандидатом на максимум.
Значение "минус бесконечность" в случае операции взятия максимума двух чисел обладает следующим замечательным свойством: для всякого числа x выполняется равенство
max(минус бесконечность,x) = x
Можно сравнить с операцией сложения:
0+x = x
Таким образом, значение "минус бесконечность" играет роль нуля для операции взятия максимума двух чисел. Ноль - это нейтральный элемент для операции сложения: будучи прибавленным слева к произвольному числу x, он не изменяет числа x. Точно так же значение "минус бесконечность" является нейтральным для операции взятия максимума.
Для операции "минимум" нейтральным элементом является "плюс бесконечность". Таким образом, алгоритм нахождения минимума последовательности выглядит следующим образом:
вещ алгоритм минимум последовательности(вх: цел n, вещ a[n])
| дано: n    -- число элементов последовательности,
|       a[n] -- массив элементов последовательности
| надо: вычислить минимум элементов последовательности
начало алгоритма
| вещ m; цел i;
| m := плюс бесконечность; // Инициализация значения ф-ции
| i := 0;
| цикл пока i < n
| | если a[i] < m   // Вычисление нового знач. по старому
| | | то m := a[i]; // значению и очередному элементу
| | конец если
| | i := i + 1;
| конец цикла
| ответ := m;
конец алгоритма
Значения "минус" и "плюс бесконечность"
Как реализовать воображаемые элементы "минус бесконечность" и "плюс бесконечность" при программировании на конкретных алгоритмических языках, а не на псевдокоде? Вспомним, что компьютер может представлять не все возможные числа, а только их ограниченное подмножество. Поэтому для компьютера существует минимальное и максимальное целое и вещественное числа. В языке Си эти константы записаны в стандартных заголовочных файлах "limits.h" для целочисленных типов и "float.h" для вещественных типов. Для типа int эти константы называются INT_MIN и INT_MAX.
INT_MIN = (-2147483647 - 1)
INT_MAX = 2147483647
Для вещественных типов максимальное и минимальное числа равны по абсолютной величине и отличаются лишь знаками, поэтому специального названия для максимальной по абсолютной величине отрицательной константы не существует. Максимальное число типа float называется FLT_MAX, типа double - DBL_MAX.
FLT_MAX = 3.402823466e+38
DBL_MAX = 1.7976931348623158e+308
Стоит отметить, что через FLT_MIN и DBL_MIN обозначены минимальные положительные числа, а вовсе не максимальные по абсолютной величине отрицательные!
FLT_MIN = 1.175494351e-38
DBL_MIN = 2.2250738585072014e-308
Константа DBL_MAX является нормальным числом, она не равна
специальному бесконечно большому значению, см. с. 1.4.2.
Использовать бесконечно большое значение опасно,
т.к. операции с ним могут приводить к ошибкам.
Итак, в качестве значений "минус бесконечность" и "плюс бесконечность" можно использовать константы INT_MIN и INT_MAX для типа int. Для типа double в качестве значений "минус бесконечность" и "плюс бесконечность" можно использовать выражения (-DBL_MAX) и DBL_MAX. Не забудьте только при программировании на Си подключить стандартные заголовочные файлы:
#include <limits.h>
для целых типов и

#include <float.h>
для вещественных. Впрочем, вовсе не обязательно помнить названия этих констант и имена стандартных заголовочных файлов. В качестве значения "минус бесконечность" всегда можно использовать произвольное значение, заведомо меньшее, чем любое конкретное число, которое может встретиться в программе. Например, если известно, что программа работает только с неотрицательными числами, то в качестве значения "минус бесконечность" можно использовать произвольное отрицательное число, например, минус единицу. Аналогично, в качестве значения "плюс бесконечность" можно применять любое достаточно большое число. Оно должно быть заведомо больше, чем все конкретные числа, которые могут встретиться в алгоритме. Пусть, например, известно, что в программе могут встретиться вещественные числа не больше миллиона. Тогда в качестве значения "плюс бесконечность" можно использовать константу

1.0e+30
т.е. десять в тридцатой степени. (Можно даже использовать 1.0e+7, т.е. десять миллионов, но не стоит мелочиться.)
Схема Горнера
Рассмотрим еще один важный пример функции на последовательности. Пусть дана последовательность коэффициентов многочлена p(x) по убыванию степеней:
p(x) = a0xn +a 1xn-1 + ... + an
Нужно вычислить значение многочлена в точке x = t. Алгоритм, основанный на просмотре последовательности коэффициентов в направлении от старшего к младшему, называется схемой Горнера. Проиллюстрируем его идею на примере многочлена третьей степени:
p(x) = ax3+bx2+cx+d
Его можно представить в виде
p(x) = ((ax+b)x+c)x+d
Для вычисления значения многочлена достаточно трех умножений и трех сложений. В общем случае, многочлен представляется в следующем виде:
p(x) = (...((a0x+a1)x+a2)x+...+an-1)x+an.
Обозначим через pk(x) многочлен k-ой степени, вычисленный по коэффициентам a0, a1, ..., ak:
pk(x) = a0xk + a1xk-1 + ... + ak.
Тогда
pk+1(x) = pk(x)x + ak+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;
конец алгоритма

http://localhost:3232/img/empty.gifАрифметический цикл

В рассмотренных выше программах в цикле перебираются элементы массива с индексом i, где i пробегает значения от 0 до n-1 (в последней программе - от 0 до n, поскольку многочлен n-й степени имеет n+1 коэффициент). Для удобства записи таких циклов большинство языков программирования предоставляет конструкцию арифметического цикла. В нем используется так называемая переменная цикла, т.е. целочисленная переменная, которая последовательно принимает значения в указанных пределах. Для каждого значения переменной цикла выполняется тело цикла, в котором эта переменная может использоваться.
цикл для i от a до b
| . . .
| тело цикла
| . . .
конец цикла
Здесь переменная цикла i последовательно принимает значения от a до b с шагом 1, где a и b - некоторые целочисленные выражения. Таким образом, всего тело цикла выполняется b-a+1 раз. Если b меньше, чем a, то цикл не выполняется ни разу. Возможна также конструкция арифметического цикла с шагом s, отличным от единицы:
цикл для i от a до b шаг s
| . . .
| тело цикла
| . . .
конец цикла
Переменная цикла последовательно принимает значения a, a+s, a+2s, ... до тех пор, пока ее значение содержится в отрезке [a,b]. Для каждого значения переменной цикла выполняется тело цикла. Шаг может быть и отрицательным, в этом случае b должно быть не больше, чем a, иначе цикл не выполняется ни разу.
В принципе, без конструкции арифметического цикла можно обойтись, поскольку ее можно смоделировать с помощью цикла "пока". А именно, конструкция
цикл для i от a до b
| . . .
| тело цикла
| . . .
конец цикла
эквивалентна конструкции

i := a
цикл пока i <= b
| . . .
| тело цикла
| . . .
| i := i + 1
конец цикла
Однако традиционно арифметический цикл включается в большинство языков высокого уровня. С использованием арифметического цикла схема Горнера переписывается следующим образом:
вещ алгоритм схема Горнера(вх: цел n, вещ a[n+1], вещ t)
| дано: n      -- степень многочлена
|       a[n+1] -- массив коэффициентов многочлена по
|                 убыванию степеней
| надо: вычислить значение многочлена в точке t
начало алгоритма
| вещ p; цел i;
| p := 0.0;     // Инициализация значения многочлена
| цикл для i от 0 до n
| | p := p * t + a[i]; // Вычисление нового значения
| |                    // при добавлении коэффициента
| конец цикла
| ответ := p;
конец алгоритма
Аналогично можно переписать и другие приведенные выше алгоритмы вычисления функций на последовательностях. Приведем также пример использования арифметического цикла с отрицательным шагом. Пусть коэффициенты многочлена заданы по возрастанию, а не по убыванию степеней. В схеме Горнера следует просматривать коэффициенты многочлена от старшего к младшему. Для этого удобно использовать арифметический цикл с отрицательным шагом:
вещ алгоритм схема Горнера2(вх: цел n, вещ b[n+1], вещ t)
| дано: n      -- степень многочлена
|       b[n+1] -- массив коэффициентов многочлена по
|                 убыванию степеней
| надо: вычислить значение многочлена в точке t
начало алгоритма
| вещ p; цел i;
| p := 0.0;     // Инициализация значения многочлена
| цикл для i от n до 0 шаг -1
| | p := p * t + b[i]; // Вычисление нового значения
| |                    // при добавлении коэффициента
| конец цикла
| ответ := p
конец алгоритма

http://localhost:3232/img/empty.gifИндуктивные функции на последовательностях и индуктивные расширения

В рассмотренных выше примерах при добавлении к последовательности еще одного элемента новое значение функции на последовательности можно было вычислить, зная только старое значение функции и добавленный элемент. Обозначим через Sn последовательность
Sn = {a0, a1, ..., an-1} 
длины n. С помощью знака & обозначим операцию приписывания нового элемента справа к последовательности (ее называют также конкатенацией):
Sn+1 = Sn&an = {a0, a1, ..., an-1, an}   
Пусть f(S) - некоторая функция на множестве последовательностей, например, сумма элементов последовательности. Функция называется индуктивной, если при добавлении нового элемента к последовательности новое значение функции можно вычислить, зная только старое значение функции и добавленный элемент. На математическом языке функция
f:W http://localhost:3232/img/symbols/srarr.gif Y  
где W - множество всех последовательностей, составленных из элементов некоторого множества X, индуктивна, если существует функция G от двух аргументов
G:Y*X http://localhost:3232/img/symbols/srarr.gif 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) http://localhost:3232/img/symbols/ne.gif 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 не индуктивна.
Как поступать в случае, когда функция f не индуктивна? Общий рецепт следующий: надо придумать индуктивную функцию F, такую, что, зная значение F, легко можно вычислить исходную функцию f. Функция F называется индуктивным расширением функции f.
Приведем формальные определения. Пусть исходная функция на множестве W всех последовательностей
f:W http://localhost:3232/img/symbols/srarr.gif Y 
не индуктивна. Индуктивная функция
F:W http://localhost:3232/img/symbols/srarr.gif Z  
называется индуктивным расширением функции f, если существует отображение
P:Z http://localhost:3232/img/symbols/srarr.gif Y  
такое, что для всякой последовательности S, принадлежащей W, выполняется равенство
f(S) = P(F(S))
(т.е. функция f равна композиции отображений F и P, f = PºF.) Отображение P обычно называют проекцией множества Z на Y.
Как построить индуктивное расширение функции f? Это творческий момент, готового рецепта на все случаи не существует. Неформальный рецепт следующий: надо понять, какой информации не хватает для того, чтобы уметь вычислять новое значение функции на последовательности при добавлении к последовательности нового элемента. Эту информацию надо хранить дополнительно к значению функции. Отсюда и появился термин расширение: вычисляется более сложная, расширенная, функция, чтобы по ней затем восстановить исходную. Как правило, значением индуктивного расширения F является пара (y, h), где y - значение исходной функции f, а h - некоторая дополнительная информация, позволяющая перевычислять значение y при добавлении нового элемента к последовательности. Таким образом, множество Z значений индуктивного расширения
F:W http://localhost:3232/img/symbols/srarr.gif Z  
чаще всего является множеством пар (y, h), т.е. декартовым произведением:
Z = Y*H
Отображение P на практике должно легко вычисляться. Так оно и есть в случае декартово произведения - это просто проекция на первый аргумент.
P(y, h) = y
Рассмотрим пример с вычислением производной многочлена в точке; коэффициенты многочлена заданы в последовательности по убыванию степеней. При добавлении к последовательности
Sk = {a0, a1, ...,ak}
нового коэффициента ak+1 получаем последовательность
Sk+1 = S&ak+1 = {a0, a1, ...,ak, ak+1}
Пусть этим двум последовательностям соответствуют многочлены pk(x) и pk+1(x). Тогда
pk+1(x) = pk(x)*x + ak+1. 
Дифференцируя это равенство, получим:
p'k+1(x) = p'k(x)*x + pk(x).
Мы видим, что для вычисления нового значения производной нужно знать старое значение производной, а также старое значение многочлена. Следовательно, дополнительно к значению производной многочлена надо хранить еще значение самого многочлена. Таким образом, индуктивным расширением функции, равной производной многочлена в точке t, является пара (значение производной, значение многочлена):
F:S http://localhost:3232/img/symbols/srarr.gif (p'(t), p(t)) 
Новое значение производной вычисляется по приведенной выше формуле через старое значение производной и старое значение многочлена. После этого вычисляется новое значение многочлена по схеме Горнера.
Выпишем алгоритм вычисления производной многочлена.
вещ алг. значение производной(вх: цел n, вещ a[n+1], вещ t)
| дано: n      -- степень многочлена
|       a[n+1] -- массив коэффициентов многочлена по
|                 возрастанию степеней
| надо: найти значение производной многочлена в точке t
начало алгоритма
| вещ p, dp; цел i;
| p := 0.0;     // Инициализация значения многочлена
| dp := 0.0;    // Инициализация значения производной
| цикл для i от 0 до n
| | dp := dp * x + p;  // Новое значение производной
| | p := p * t + a[i]; // Новое значение многочлена
| конец цикла
| ответ := dp;
конец алгоритма
Другой пример неиндуктивной функции - это среднее арифметическое значение элементов последовательности. Индуктивным расширением является пара (сумма элементов последовательности, длина последовательности):
F(S) = (сумма(S), длина(S)).
Легко видеть, что функция F индуктивна. При известном значении функции F не составляет труда вычислить исходную функцию:
среднее арифметическое(S) = сумма(S)/длина(S).
В данном случае отображение P не является в чистом виде проекцией, т.к. в процессе вычислений удобнее хранить сумму элементов прочитанного отрезка последовательности, а не среднее арифметическое. Вычисления проще и, кроме того, сумма определена на пустой последовательности в отличие от среднего арифметического.
Итак, в каждом конкретном случае при вычислении неиндуктивной функции f надо придумать ее индуктивное расширение F и в программе вычислять сначала индуктивное расширение F, а затем по значению F вычислять требуемое значение исходной функции f.
http://localhost:3232/img/empty.gif

 

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика