В серии: Библиотека alt м. В. Сысоева, И. В. Сысоев

3.3 Некоторые основные алгоритмические приёмы

3.3.1 Приёмы накопления суммы и произведения. Их комбинация

В разделе про цикл while рассматривались примеры с накоплением суммы и произведения. Эти же приёмы можно и нужно применять при работе с циклом for. Так же их можно комбинировать. Рассмотрим следующий пример: необходимо вычислить значение выражения 1! + 2! + ··· + n!
Решение в лоб состоит в том, чтобы в теле цикла, осуществляющего суммирование, производить вычисление факториала:
n = ( (’Сколько факториалов будем суммировать? ’)) s = 0 i (1, n+1):
# Вычисление факториала от i:
p = 1 k (1, i+1): p = p * k;
# Добавление вычисленного факториала к сумме:
s = s + p
(s)
Циклы позволяют повторять выполнение любого набора операторов. В частности, можно повторять много раз выполнение другого цикла. Такие циклы называются вложенными. В приведённом выше примере один цикл for вложен в другой цикл for.
Типичная ошибка, когда в качестве счётчиков вложенных циклов (i и k в приведённом примере) используется одна и та же переменная. То есть, нельзя в каждом из циклов использовать одну переменную i. Ваша программа запустится, но делать будет вовсе не то, что вы от неё ждёте. В приведённом примере, если допустить ошибку, заменив переменную k на i, внешний цикл выполнится всего 1 раз вместо 4-х. Возможна также ситуация, когда такая ошибка приведет к зацикливанию: внешний цикл будет выполняться бесконечно долго — программа зависнет.
Заметим, что при вычислении факториала на каждом шаге получается факториал все большего целого числа. Эти «промежуточные» результаты однократного вычисления факториала и можно суммировать:
n = ( (’Сколько факториалов суммировать? ’)) s = 0 p = 1 i (1, n+1):
p = p * i s = s + p
(s)
Стоит отметить, что в основе рассмотренных ранее алгоритмических приёмов накопления суммы и произведения лежит фундаментальная идея о том, что результат вычислений на каждом шаге цикла должен зависеть от результата вычислений на предыдущем шаге. Обобщенным математическим выражением этой идеи являются рекуррентные соотношения.
В наших примерах в качестве рекуррентных соотношений выступали, например, формулы p = p * i и s = s + p. Причём, последнее выражение (s = s + p) является сложною рекурсией, когда значение s зависит не только от своего прошлого значения, но и от значения p на прошлом шаге.
Для лучшего понимания решим задачу: пусть дано рекуррентное соотношение x_n+1 = 1−λx²_n. В нелинейной динамике это соотношение называют логистическим отображением. Оно, например, может использоваться для приближённого описания изменения численности популяций некоторых животных во времени. Пусть начальное значение x₀ = 1. Параметр λ = 0.75. Необходимо найти x₅.
x = 1 i (1, 6): x = 1 - 0.75*x**2
(x)
Вывод программы:
0.35989018693629404
Однократное вычисление следующих значений по предыдущим посредством рекуррентных соотношений называется итерацией. А процесс вычислений с помощью рекуррентных соотношений — итерированием.
Задание 7 Придумайте рекуррентное соотношение, задающее следующие числовые последовательности:

1. 
   1,2,3,4,...
   
2. 
   0,5,10,15,...
   
3. 
   1,1,1,1,...
   
4. 
   1,−1,1,−1,...
   
5. 
   1,−2,3,−4,5,−6...
   
6. 
   2,4,8,16,...
   
7. 
   2,4,16,256,...
   
8. 
   0,1,2,3,0,1,2,3,0,...
   
9. 
   1!,3!,5!,7!,...
   

Важно!!! Если в написанной вами формуле вам встречается значок суммы
, то вы сразу должны представлять себе цикл for с накоплением суммы внутри:
x = 0 i (0, N): x = x + i
Аналогично, если в задании вам встречается значок произведения , то вы сразу должны представлять себе цикл for с накоплением произведения внутри:
x = 1 i (0, N): x = x * i