[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]

Вычисление рекуррентных последовательностей

Рекуррентная последовательность.

Из курса математики известно понятие рекуррентной последовательности. Это понятие вводится так: пусть известно k чисел а1 ..., аk Эти числа являются первыми числами числовой последовательности. Следующие элементы данной последовательности вычисляются так:
ak+1 =F(a1, ..., ak ); ak+2 =F(a2, ..., ak+1 ); ak+3 =F(a3, ..., ak+2 )...
Здесь F - функция от k аргументов.
Формула вида ai =F(ai-1, ..., ai-k)
называется рекуррентной формулой.
Величина k называется глубиной рекурсии.
Другими словами, можно сказать, что рекуррентная последовательность — это бесконечный ряд чисел, каждое из которых, за исключением k начальных, выражается через предыдущие.
Примерами рекуррентных последовательностей являются арифметическая (1) и геометрическая (2) прогрессии:
a1= 1, a2=3, a3=5, a4=7, a5=9,... (I)
a1= 1, a2=2, a3=4, a4=8, a5= 16,... (2)
Рекуррентная формула для указанной арифметической прогрессии:
ai = ai + 2.
Рекуррентная формула для данной геометрической прогрессии:
ai = ai-1 * 2.
Глубина рекурсии в обоих случаях равна единице (такую зависимость еще называют одношаговой рекурсией). В целом рекуррентная последовательность описывается совокупностью начальных значений и рекуррентной формулы. Все это можно объединить в одну ветвящуюся формулу. Для арифметической прогрессии:

Для геометрической прогрессии:

Следующая числовая последовательность известна в математике под названием чисел Фибоначчи:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Начиная с третьего элемента каждое число равно сумме значений двух предыдущих, т.е. это рекуррентная последовательность с глубиной равной 2 (двухшаговая рекурсия). Опишем ее в ветвящейся форме:

Введение представления о рекуррентных последовательностей позволяет по-новому взглянуть на некоторые уже известные нам задачи. Например, факториал целого числа n! можно рассматривать как значение n-го элемента следующего ряда чисел:
a0= 1, a1= 1!, a2=2!, a3=3!, a4=4!, ...
Рекуррентное описание такой последовательности выглядит следующим образом:

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

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

  1. вычислить заданный (n -й) элемент последовательности; математически обработать определенную часть последовательности (например, вычислить сумму или произведение первых n членов);

  2. подсчитать количество элементов на заданном отрезке последовательности, удовлетворяющих определенным свойствам;

  3. определить номер первого элемента, удовлетворяющего определенному условию;

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

Пример 1. Вычислить n-й элемент арифметической прогрессии (1)
Var N, I: 0..Max int;
A: Real;
Begin
Write ('N=') ;
ReadLn(N);
A:=1;
For I:=2 To N Do
A:=A+2;
WriteLn('A(',N:1,')=',A:6:0)
End.
Рекуррентная формула ai= ai-1 + 2 перешла в оператор А := А + 2.
Пример 2. Просуммировать первые п элементов геометрической прогрессии (2) (не пользуясь формулой для суммы первых п членов прогрессии).
Var N,I: 0...Max int;
A, S: Real;
Begin
Write('N='); ReadLn(N);
A:=1;
S;=A;
For I:=2 To N Do
Begin
A:=2*A;
S:=S+A
End;
WriteLn('Сумма равна',S:6:0)
End
При вычислении рекуррентной последовательности с глубиной 2 уже нельзя обойтись одной переменной. Это видно из следующего примера.
Пример 3 . Вывести на печать первые п (п > = 3) чисел Фибоначчи. Подсчитать, сколько среди них четных чисел.
Var,N,I,K,F,F1,F2: 0...Max int;
Begin
F1:=1; F2:=1;
K:=0;
WriteLn('F(1)=',F1,'F(2)=',F2);
For I:=3 To N Do
Begin F:=F1+F2;
WriteLn('F(',I:1,')=',F);
If Not Odd(F) Then K:=K+1;
F1:=F2; F2:=F
End;
WriteLn('Количество четных чисел в последовательности равно',К)
End.
Понадобились три переменные для последовательного вычисления двухшаговой рекурсии, поскольку для нахождения очередного элемента необходимо помнить значения двух предыдущих.
Пример 4. Для заданного вещественного x и малой величины (например с=0,000001) вычислить сумму ряда 
1 + x +(x2/ 2! ) + (x3/ 3! ) + ... ,
включив в нее только слагаемые, превышающие c. Известно, что сумма такого бесконечного ряда имеет конечное значение, равное еx, где e = 2,71828... — основание натурального логарифма. Поскольку элементы этого ряда представляют собой убывающую последовательность чисел, стремящуюся к нулю, то суммирование нужно производить до первого слагаемого, по абсолютной величине не превышающего с. |
Если слагаемые в этом выражении обозначить следующим образом: ,
  a0=1,  a1= x,  a2=x2/ 2! ,  a3=x3/ 3!, ... .
то обобщенная формула для i-то элемента будет следующей:
ai=xi / i!.
Нетрудно увидеть, что между элементами данной последовательности имеется рекуррентная зависимость. Ее можно найти интуитивно, но можно и вывести формально. Правда нужно догадаться, что рекурсия одношаговая и следующий элемент получается путем умножения предыдущего на некоторый множитель, т.е.
ai = ai-1 * k
Используя обобщенную формулу, имеем:
(xi / i!)= K ((xi-1)/(i-1)!)
Отсюда:
K=(xi / i!)/((xi-1)/(i-1)!)=xi / i!
Действительно:
a0=1,  a1=a0 x / 2,  a3= a2 x/ 3!, и т.д. .
Следовательно, данная рекуррентная последовательность мо жег быть описана следующим образом:

И наконец, приведем программу, решающую поставленную задачу.
Var A, X, S, Eps: Real;
I: Integer;
Begin
Write('X='); ReadLn(X);
Write('Epsilon ='); ReadLn(Eps);
A:=1; S:=0; I:=0;
While Abs(A)>Eps Do
Begin
S:=S+A;
I:=I+1;
A:=A*X/I
End;
WriteLn('Сумма ряда равна', S:10:4)
End.
Как и прежде, значения одношаговой рекуррентной последовательности вычисляются в одной переменной.
Каждое повторное выполнение цикла в этой программе приближает значение s к искомому (уточняет значащие цифры в его записи). Такой вычислительный процесс в математике называется итерационным процессом. Соответственно, циклы, реализующие итерационный вычислительный процесс, называются итерационными циклами. Для их организации используются операторы While или Repeat.
Пример 5. Для заданного натурального N и вещественного х (х >0) вычислить значение выражения:

В этом случае рекуррентность не столь очевидна. Попробуем найти ее методом индукции. Будем считать, что искомое выражение есть N-й элемент последовательности следующего вида:

Отсюда видна связь:

Теперь поставленная задача решается очень просто:
Var A,X: Real; I,N: Integer;
Begin
Write ('X='); ReadLn(X) ;
Write('N='); ReadLn(N);
A:= Sqrt(X),
for I:=2 ТO N Do
A:=Sqrt(X+A);
WriteLn('OTBЕT:',A)
End.
К решению всех перечисленных выше задач можно подойти иначе. Вспомним о рекурсивно определенных подпрограммах. Посмотрите на описание арифметической прогрессии в форме рекуррентной последовательности. Из него непосредственно вытекает способ определения функции для вычисления заданной элемента прогрессии.
Сделаем это для общего случая, определив арифметическую прогрессию с первым членом a0
и разностью d:

Соответствующая подпрограмма-функция выглядит так:
Funcition Progres(A0,D: Real;I: Integer): Real;
Begin
If I=1
Then Progres:=A0
Else Progres:=Progres(A0,D,I-1)+D
End;
Следующая программа выводит на экран первые 20 чисел Фибоначчи, значения которых вычисляет рекурсивная функция Fibon.
Var К: Byte;
Function Fibon(N: Integer); Integer;
Begin
if (N=1) Or (N=2) Then Fibon:=1
Else Fibon :=Fibon(N-l)+Fibon(N-2)
End;
Begin
For K=1 To 20 Do
WriteLn(Fibon(K))
End.
Необходимо отметить, что использование рекурсивных функций ведет к замедлению счета. Кроме того, можно столкнуться проблемой нехватки длины стека, в котором запоминается маршрут рекурсивных обращений.
Рекуррентные последовательности часто используются для решения разного рода эволюционных задач, т.е. задач, в которых прослеживается какой-то процесс, развивающийся во времени. Рассмотрим такую задачу.
Пример 6. В ходе лечебного голодания масса пациента за 30 дней снизилась с 96 до 70 кг. Было установлено, что ежедневные потери массы пропорциональны массе тела. Вычислить, чему была равна масса пациента. Через k дней после начала голодания для k= 1, 2, 29.
Обозначим массу пациента в i-и день через pi (i'=0,1,2,. ..,30). Из условия задачи известно, что p0 = 96кг.
Пусть К— коэффициент пропорциональности убывания массы за один день.
Тогда P1 = P0-K P0 =(1-K) P0 P2=(1-К} P1 P3=(1-К} P2; ...; Pi=(1-К} Pi-1
Получаем последовательность, описываемую следующей рекуррентной формулой:

Однако нам неизвестен коэффициент К. Его можно найти, используя условие P30=70. Для этого будем делать обратные подстановки:
P30=(1-К) P29 = (1-К)2 P28 =(1-К)3 P27 =...= (1-К)30 P0 =(1-К)30 * 96
Из равенства (1-K)^30*96 = 70 находим:  1-K =(70/96)(1/30)
Далее программирование становится тривиальным."
Var I: Byte;
P,Q: Real;
Begin
P:=96;
Q:=Exp(l/30*ln (70/96));
for I:=1 To 29 Do
Begin
Р:=Q*P;
WriteLn(I,'-й день-',Р:5:3,'кг')
End
End.
Упражнения
1. Рекуррентная последовательность определена следующим образом:

Для данного натурального n получить значение ai. 2. Дана последовательность;

Вычислить произведение элементов с 1-го по 20й.
3. Используя рекуррентный подход, вычислить сумму многочлена 10-й степени по формуле Горнера, где х — данное вещественное число 4. Для данного вещественного х и натурального N вычисли цепную дробь: х/(1 + x/(2 + х/(3 + x/(.../(N+x))...).
5. Вычислить и вывести все члены числового ряда 1, 1/2! , 1/3! , ... , 1/N! превышающие значение 10-5
6. Функцию у=SQRT(х) можно вычислить как предельное значение последовательности, определяемой рекуррентной формулой: yk = (1/2)(yk-1 + ( x / yk-1) ; k = 1, 2, ... . Начальное значение y0 задается произвольно (желательно ближе SQRT(х). За приближенное значение корня с точностью е берется первое yk, для которого выполняется условие:
| yk - yk-1|< е. Составить программу.  

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]