Меню
Главная

Статистика

 

 


Понятие рекуррентного соотношения

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

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

Пример #4.

Вычислить сумму S=1+1/x+1/x2+...+1/xN при x, не равном 0.

Как и в предыдущем примере можно записать следующее соотношение:
S(i) = S(i - 1) + a(i), i³1, где
a(i) = 1/xi,
S(0) = 1.

Конечно, можно и эти соотношения использовать для написания программы. При этом у нас возникла новая задача - найти способ вычисления a(i). Для этого можно воспользоваться тем же приемом - попытаться вычислить a(i) через значение a(i - 1). Соотношение между значениями a(i) и a(i - 1) имеет следующий вид:
a(i) = a(i - 1)/x, i³1
a(0) = 1

Поэтому поставленную задачу можно решить следующим образом. 

S[0]: = 1;
a[0]: = 1;
for i:=1 to N do        {1. 2}
begin
 a[i]: = a[i - 1]/x;
 S[i]: = S[i - 1] + a[i]
end;
                    
Procedure Init (var q: Queue;
                        var Free,First:integer);
begin
  First: =1;
  Free: =1;
end;

Отметим, что и в этом случае индексы при SM и a можно опустить в связи с тем, что для вычисления текущего элемента каждой из таблиц достаточно знать только значение предыдущего элемента.

Соотношения, связывающие одни и те же функции, но с различными аргументами, называются рекуррентными соотношениями или рекуррентными уравнениями.

Назад