На этом шаге мы рассмотрим алгоритмы нахождения частичных сумм и произведений.

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

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

    Для выполнения этой операции можно использовать следующие алгоритмы:

  OutputIterator
  partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, 
               OutputIterator destBeg)

  OutputIterator
  partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, 
               OutputIterator destBeg, BinaryFunc op)

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

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

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

  a1 a2 a3 ...

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

  a1, a1 + a2, a1 + а2 + a3, ... 
  a1, a1 op а2, a1 op a2 op a3, ...

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

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

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

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

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

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

    Пример использования алгоритма partial_sum():

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iterator>
#include "algostuff.hpp"

#include <conio.h> //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main()
{
  vector<int> coll;

  INSERT_ELEMENTS(coll,1,6);
  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  // Вывод всех частичных сумм
  cout << ToRus("Вывод всех частичных сумм:\n");
  partial_sum (coll.begin(), coll.end(),          // Источник
               ostream_iterator<int>(cout," "));  // Приемник
  cout << endl;
  // Вывод всех частичных произведений
  cout << ToRus("Вывод всех частичных произведений:\n");
  partial_sum (coll.begin(), coll.end(),          // Источник
               ostream_iterator<int>(cout," "),   // Приемник
               multiplies<int>());                // Операция
  cout << endl;


  getch();
  return 0;
}

//---------------------------------------------------------------------------

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

Рис.1. Результат работы приложения

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

Предыдущий шаг Содержание Следующий шаг