Вычисление скалярного произведения двух интервалов

1nner procluct (Inputlteratorl begl. Inputlteratorl endl. Inputlterator? beg2. T initValue)

inner product (Inputlteratorl begl. Inputlteratorl endl. InputIterator2 beg2. T initValue. BinaryFunc opl. BinaryFunc op2)

О Первая форма вычисляет и возвращает скалярное произведение initValue и элементов интервалов \beg,end) и [beg2,...). Для каждого элемента выполняется команда:

initValue = initValue + eleml * elem2

О Вторая форма вычисляет и возвращает накопленный результат вызова ор для initValue и элементов интервала [beg,end), объединенных с элементами [beg2,...). Для каждого элемента выполняется команда:

initValue = opl{initValue.op2{eleml .elem2))

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

al а2 аЗ а4... Ы Ь2 ЬЗ ...

Для этих значений соответственно вычисляются и записываются такие величины:

initValue + (al * Ы) + (а2 * Ь2) + (аЗ * ЬЗ) + ...

initValue opl (al ор2 Ы) opl (а2 ор2 Ь2) opl (аЗ ор2 ЬЗ) opl .,.

О Для пустого первого интервала {beg1 end1) обе формы возвращают initValue.

О Перед вызовом необходимо убедиться в том, что интервал \beg2,...) содержит достаточное количество элементов.

О Предикаты ор1 w ор2 не должны модифицировать передаваемые аргументы.

О Сложность линейная {numberOfElements вызовов операторов + и * или numberOfElements вызовов ор1{) и ор2{) соответственно).

В следующем примере алгоритм inner product() используется для вычисления суммы произведений и произведения сумм элементов двух интервалов.

algo/innerl.cpp #include algostuff.hpp using namespace std:

int mainO

I1st<int> coll;

INSERT ELEMENTS(coll.l.6):

PRlNT ELEMENTS(coll):

/* Вычисление суммы произведений элементов

* (О + 1*1 + 2*2 + 3*3 + 4*4 + 5*5 + 6*6) */

cout inner product:

lnner product (coll.beginO, coll.endO. Первый интервал coll.beginO. Второй интервал

0) Начальное значение

endl:

/* Вычисление суммы 1*6 ... 6*1

* (О + 1*6 + 2*5 + 3*4 + 4*3 + 5*2 + 6*1) */

cout inner reverse product:

inner product (coll.beginO, coll.endO, Первый интервал coll.rbeginO, Второй интервал

0) Начальное значение

endl;

/* Вычисление произведения сумм элементов

* (1 * 1+1 * 2+2 * 3+3 * 4+4 * 5+5 * 6+6) */

cout product of sums:

inner product (coll.beginO. coll.endO. Первый интервал coll.beginO. Второй интервал

1, Начальное значение

multiplies<1nt>(), Внутренняя операция

plus<int>0) Внешняя операция

endl:

Результат выполнения программы выглядит так:

1 2 3 4 5 6 inner product: 91 Inner reverse product: 56 product od sums: 46080

Преобразования относительных и абсолютных значений

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

Преобразование относительных значений в абсолютные

Outputlterator

part1al sum (Inputlterator sourceBeg. Inputlterator sourceEnd. Outputlterator destBeg)

Outputlterator

part1al su[n (Inputlterator sourceBeg, Inputlterator sourceEnd, Outputlterator destBeg. BinaryFunc op)

О Первая форма вычисляет частичную сумму для каждого элемента в интервале [sourceBeg,sourceEnd) и записывает результат в приемный интервал [destBeg,...).

О Вторая форма вызывает ор для каждого элемента в интервале [sourceBeg, sourceEnd), объединяет полученное значение со всеми предыдущими значениями и записывает результат в приемный интервал [destBeg,...).

О Таким образом, пусть мы имеем следующие значения; al а2 аЗ ...

Для этих значений соответственно вычисляются и записываются такие величины:

al. al + а2. al + а2 + аЗ. ... al. al op а2. al op a2 op аЗ, ...

О Обе формы возвращают позицию за последним записанным элементом в приемном интервале (то есть позицию первого элемента, который ие был заменен).

О Первая форма эквивалентна преобразованию серии относительных значений в серию абсолютных значений. В этом отношении алгоритм partiaLsum() является логическим дополнением алгоритма adjacent difference().

О Исходный и приемный интервалы могут быть идентичными,

О Перед вызовом необходимо убедиться в том, что приемный интервал имеет достаточный размер, или использовать итераторы вставки.

О Предикат ор не должен модифицировать передаваемые аргументы.

О Сложность линейная {numberOfElements вызовов оператора + или ор{) соответственно).

Пример использования алгоритма partial sum();

algo/partsuml.cpp Iinclude algostuff.hpp using namespace std;

int mainO {

vector<int> coll;

INSERT ELEMENTS(C0ll.l.6); PRINT ELEMENTS(coll):

Вывод всех частичных сумм

partial sum (coll .beginO . coll.endO. Источник

ostream iterator<int>(cout. )); Приемник

cout endl: