Обобщенные численные алгоритмы 203

Значение выражения

0 + 11 + - + п-Ал

называется скалярным произведением последовательностей {а, а,а} и {Ь, Ь, Простейшая версия алгоритма inner product добавляет

вычисленное таким образом скалярное произведение к значению четвертого аргумента, что демонстрирует следующая программа:

inprodl.cpp: Обычное скалярное произведение.

♦include <iostream> ♦include <numeric> using namespace std;

int main()

{ int a[3] = {2, 20, 4},

b[3] = {5, 2, 10}, inprod = 100; inprod = inner product(a, a+3, b, inprod); cout inprod endl; 100 + 2 * 5 + 20 * 2 + 4 * 10 = 190 return 0;

Как указывает комментарий в конце программы, для вычисления значения используются два арифметических оператора - + и *. В другом варианте алгоритма inner product мы пятым и шестым аргументом задаем наши собственные операции вместо + и * соответственно. В следующей программе эта версия алгоритма используется для вычисления произведения степеней.

inprod2.cpp: Произведение степеней, вычисляемое с помощью алгоритма inner product.

♦include <iostream> ♦include <numeric> ♦include <functional> using namespace std;

double power(int x, int n) { double у = 1;

for (int k=0; k<n; k++) у *= x;

return y; x в степени n

int mainO

{ int a[3] = {2, 3, 5}, b[3] = {4, 1, 2}, product=l; product = inner product(a, a+3, b, product,

multiplies<double>(), power); cout product endl;

111* power(2, 4) * power(3, 1) * power(5, 2) = 1 * 16 * 3 * 25 = 1200 return 0;

7.4.3. Частичная сумма

Outputlterator partial s\im

(Inputlterator first, Inputlterator last,

Outputlterator result); Outputlterator partial sum

(Inputlterator first, Inputlterator last,

Outputlterator result, BinaryOperation binary op);

Алгоритм partial sum практически рассчитывает суммы элементов с накоплением. Например, из последовательности {2, 3, 4, 8} мы получим {2, 5, 9, 17}, копируя первое значение, 2, и вычисляя три других элемента следующим образом:

2 + 3 = 5 5 + 4 = 9 9 + 8= 17

Приведенная ниже программа использует алгоритм partial sum для вычисления значений в рассмотренном примере:

partsum.срр: Частичная сумма, ttinclude <iostream> ttinclude <numeric> ttinclude <algorithm> using namespace std;

int mainO

{ int a[4] = {2, 3, 4, 8), b[4], *iEnd; iEnd = partial sum(a, a+4, b);

copy(b, iEnd, ostream iterator<int>(cout, )); cout << endl; Вывод 2 5 9 17 return 0;

Алгоритм partialjsum возвращает итератор, который ссылается на элемент, следующий за концом результирующей последовательности. Другими словами, iEnd равно значению b + Ав этой программе. Результирующие суммы могут быть помещены в исходном контейнере, поэтому нам не потребуются два различных массива а и Ь, если мы хотим получить результат в массиве а; для этого достаточно написать

iEnd = partial sum(a, a+4, а);

Обобщенные численные алгоритмы 205

Существует другая версия partial sum, которая принимает дополнительный параметр, позволяющий заменить оператор + на другую операцию. Например, мы можем написать

iEnd = partial sum(a, а+4, b, multiplies<int>()) ;

вместо вызова partial sum в приведенной выше программе, чтобы получить в результате 2 6 24 192, поскольку

2x3= 6 6x4= 24 24x8 = 192

7.4.4. Разность между смежными элементами

Outputlterator adjacent difference

(Inputlterator first, Inputlterator last, Outputlterator result); Outputlterator adjacent difference

(Inputlterator first, Inputlterator last, Outputlterator result, BinaryFunction binary op);

Алгоритм adjacent difference (смежная разность) вычисляет разности

d, = а.- а

для г > о и = <2ц. Например, для массива а = {2,3, 4, 8} мы получим разности d = {2, 1, 1, 4}, потому что 3-2=1,4-3=1и8-4 = 4. Алгоритм возвращает значение итератора за концом результата , что демонстрируется в следующей программе:

adjdif.срр: Разность между смежными элементами.

♦include <iostream> ♦include <numeric> ♦ include <algorithin> using namespace std;

int mainO

{ int a[4] = {2, 3, 4, 8}, d[4], *iEnd; iEnd = adjacent difference(a, a+4,.d); copy(d, iEnd, ostream iterator<int>(cout, )); cout endl; Вывод 2 114 return 0;

Чтобы результат был сохранен в исходной последовательности, мы можем написать

iEnd = adjacent difference(а, а+4, а);