На этом шаге мы некоторые общеизвестные факты о суммах.
Поскольку суммы появляются не только в определениях функций и в формулах, которые приходится кодировать, но и в оценках эффективности итерационных и рекурсивных алгоритмов, важно владеть математическим аппаратом суммирования. Сумма, или суммирование, - это просто сложение множества математических объектов (целых или вещественных чисел, векторов, матриц, функций и т. д.). Сумму значений некоторой функции f(i) для последовательности целочисленных значений i от начального значения m до конечного значения n можно записать коротко с использованием символа суммирования:
n ∑ f(i) = f(m) + f(m + 1) + ... + f(n) (3.4) i=m
Таким образом, результат сложения - это просто сумма членов, которые получаются при подстановке в функцию f(i) всех значений i от m до n. Например:
4 ∑ k * i2 = k * 02 + k * 12 + k * 22 + k * 03 + k * 42 i=0
Важно понимать, что результат суммирования не зависит от индексной переменной i. Например, сумма в (3.4) зависит от функции f и заданных граничных значений m и n, но не от конкретных значений i. Кстати, заметьте, что i нет в правой части (3.4). Поэтому целочисленный индекс i - это просто вспомогательная переменная, позволяющая одним выражением задать все слагаемые суммы. Таким образом, индексная переменная может иметь любое имя - скажем, j или k:
n n n ∑ f(i) = ∑ f(j) = ∑ f(k) i=m j=m k=m
Более того, с помощью замены индексной переменной одну и ту же сумму можно выразить различными способами:
n n-1 n ∑ f(i) = ∑ f(i + 1) = ∑ f(n - i + m) i=m i=m-1 i=m
Во второй сумме смещены пределы (и аргумент f) суммы, а в третьей элементы суммы складываются в обратном порядке (при i = m к сумме добавляется f(n), а при i = n к сумме добавляется f(m)). Наконец, если нижний предел суммы m больше верхнего n, сумма по умолчанию считается равной 0.
На следующем шаге мы рассмотрим основные свойства сумм.
