1.2. Алгоритмы вычисления сумм и произведений в цикле

В практике программирования довольно часто приходится вычислять выражения вида

где – некоторая функция.

Эффективным средством реализации указанных вычислений является использование циклических вычислительных процессов, но при этом сле­дует соблюдать два правила:

Правило накопления суммы: переменной, с помощью которой будет накапливаться сумма в цикле, необходимо при­своить начальное значение 0 (ноль) до входа в цикл.

Правило накопления произведений: переменной, с помощью которой будет накапливаться произведение в цикле, необходимо присвоить начальное значение 1 (единица) до входа в цикл.

Рассмотрим, чем обусловлены эти два правила.

При вычислении сумм вида (8.5) используется принцип накапливания сумм, реализуемый при помощи рекуррентной формулы вида

где – значение суммы, содержащей k-1 слагаемое; – зна­чение суммы, содержащей k слагаемых; – значение k-го слагаемого.

Использование формулы (8.7) заключается в следующем. Примем на­чальное значение суммы равным нулю: S₀ (при k = 1). Зададим ин­дексу k начальное значение к = 1. Тогда получим сумму с первым сла­гаемым: S₁ = S₀ + Y₁ = 0 + Y₁ = Y₁ . Увеличим значение индекса k на единицу: k = k + 1 = 2 и вновь просуммируем со вторым слагаемым по выражению (8.7): S₂ = S₁ + Y₂ = (S₀ + Y₁ ) + Y₂ = (0 + Y₁ ) + Y₂ = Y₁ + Y₂. Вновь увеличим значение индекса k на единицу и просуммируем с третьим членом: S₃ = S₂ + Y₃ = (S₁ + Y₂ ) + Y₃ = (S₀ + Y₁ + Y₂ ) + Y₃ = (0 + Y₁ + Y₂ ) + Y₃ = Y₁ + Y₂ + Y₃ .

Повторяя эти операции до k = n, мы получим искомую сумму

S = S_n = (0 + Y₁ + Y₂ + … + Y_n-1) + Y_n .

Поскольку при вычислениях надобности в запоминании значений всех слагаемых и промежуточных сумм нет, в качестве S_k и Y_k нужно ис­пользовать простые без индексов переменные и накапливание вести в цикле по формуле

S = S +Y, (8.8)

где знак = означает присваивание значения.

Если начальное значение S предварительно приравнять нулю, то после первого выполнения цикла значение S будет равно первому зна­чению функции, находящейся под знаком суммы.

Таким образом, получаем схему, реализующую принцип накапливания суммы. Алгоритм такого принципа включает следующие операции (рис. 8.2,а):

1) присвоение сумме S начального значения: S = 0 (блок 2);

2) присвоение индексу k начального значения: k = 1 (блок 3);

3) вычисление очередного (k-го) слагаемого накапливаемой суммы: (блок 4);

4) накапливание суммы по выражению: S = S + Y_k (блок 5);

5) увеличение значения индекса k на единицу: k = k + 1 (блок 6);

6) проверку текущего значения индекса k с его конечным значением n (блок 7). Если k ≤ n, то возвратимся к п. 3 (блок 4). Если нет (k > n), переходим на следующую операцию (п. 7);

7) выводим на печать полученное значение суммы S (блок 8);

8) останавливаем вычисления (блок 9).

По аналогии с накапливанием суммы принцип вычисления произведений вида (8.6), реализуется при помощи рекуррентной формулы вида

где – произведение, содержащее k-1 сомножитель; – произ­ведение, содержащее k сомножителей; – значение k-го со­множителя.

Использование формулы (8.9) заключается в следующем. Примем на­чальное значение произведения равным единице: р₀ = 1 (при k =1 ). За­дадим индексу k начальное значение k = 1.

Тогда получим произведение с первым сомножителем: P₁ = P₀ * Y₁ = 1 * Y₁ = Y₁ .

Увеличим значение индекса k на единицу: k = k + 1 = 2 и вновь произ­ведем умножение со вторым слагаемым по выражению (8.9): P₂ = P₁ * Y₂ = (P₀ * Y₁ ) * Y₂ = (1 * Y₁ ) * Y₂ = Y₁ *Y₂. Вновь увеличим значение индекса k на единицу и произведем умножение с третьим членом: P₃ = P₂ * Y₃ = (P₁ * Y₂ ) * Y₃ = (P₀ *Y₁ * Y₂ ) * Y₃ = (1 * Y₁ * Y₂ ) * Y₃ = Y₁ * Y₂ * Y₃ .

а)	б)

Рис. 8.2. Блок-схемы алгоритмов вычисления в цикле: