Отправляет email-рассылки с помощью сервиса Sendsay

Всё о работе в Интернет

Подписаться Бесплатная «Серебряная» новостная рассылка Подписчиков 7.350 RSS
←   Сентябрь 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней 1 выпусков (1 раз в 2 месяца)


Сайт рассылки: http://bestinvestblog.com
Открыта: 10-02-2009

Автор
bestinvestblog

Статистика

7.350 подписчиков
0 за неделю
←   Все выпуски   →

Занятие 45. Вычисление члена числовой последовательности рекуррентного типа, заданного своим порядковым номером.


Мы, уважаемые подписчики, снова переходим к изучению методов программирования основных типов циклических алгоритмов.

Впредь мы с вами будем активно использовать процедурный тип, в эффективности которого убедились на прошлом занятии.  

ЧЛЕН ПОСЛЕДОВАТЕЛЬНОСТИ РЕКУРРЕНТНОГО ТИПА

1. Свойства последовательности рекуррентного типа.

Изучая основные случаи применения циклических алгоритмов (см. материалы занятия 41), мы упоминали числовые последовательности рекуррентного типа. Это такие последовательности, в которых значение каждого очередного члена связано функциональной зависимостью не только с его порядковым номером, но и со значением предыдущего члена этой же последовательности (возможно, даже нескольких предыдущих).

При этом совершенно очевидно, что первый её член обязательно должен задаваться каким-то иным образом, иначе последовательность просто невозможно будет начать.

Если первый член определять как константу, то рекуррентная последовательность может быть представлена следующей комбинированной формулой общего члена:

A i = f ( A i – 1 , i ) при i = 2, 3, ... , где Ai = const при i = 1.

Например, в случае комбинированной формулы

A i = A i – 1  Ln ( 1.5 + Cos ( i )) при i = 2, 3, ... , где A i  = 2.5 при i = 1.

члены числовой последовательности должны вычисляться следующим образом: A1 = 2.5; A2 = A1  Ln (1.5 + Cos (2)); A3 = A2  Ln (1.5 + Cos (3)) и т.д.

2. Обсуждение алгоритма вычисления очередного члена последовательности.

Вышеприведённый пример показывает, что процесс вычисления члена рекуррентной последовательности с заданным порядковым номером N просто обязан быть циклическим. При этом с использованием комбинированной формулы должны быть вычислены по порядку все N членов последовательности, от первого при i = 1 до последнего при i = N. Для их обозначения в соответствующем алгоритме вполне достаточно одной переменной A. Действительно, после того как очередной член последовательности использован в вычислениях, он уже затем более не понадобится. Поэтому “его” переменная может быть использована для обозначения следующего члена. Таким образом, здесь мы имеем ещё одно проявление отбрасывания индексов.

Очередной член последовательности может вычисляться посредством обращения к функции f(A,i), которая для нашего примера имеет следующий вид:   

     Function f ( A: Real; i: Integer ): Real;
     Begin
        If i = 1 Then f := 2.5 Else f := A * Ln(1.5 + Cos(i))
     End;

Эта функция имеет интересную особенность. Обращение к ней при i = 1 может осуществляться с неопределённым значением параметра A. Впрочем, никаких неприятностей это не доставляет, так как в этом случае для вычисления функции значение переменной A не требуется.

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

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

Таким образом, очередной член последовательности мы будем вычисляться посредством обращения к функции f(A,i) следующего вида:   

     Function f ( A: Real; i: Integer ): Real;
     Begin
        f := A * Ln(1.5 + Cos(i))
     End;

3. Циклическая подпрограмма вычисления заданного члена последовательности.

Решим следующую задачу.

Задача C.1.3. “Член последовательности рекуррентного типа”. Бесконечная числовая последовательность рекуррентного типа задана формулой общего члена A i = f ( A i – 1 , i ), A1=const, i = 2, 3, ... . Построить подпрограмму вычисления члена этой последовательности с порядковым номером N (N ³ 1).

Function Part_Sequence ( A: Real; N: Integer; f: TFunction ): Real;
   Var i: Integer;
Begin
   For i:=2 To N Do A := f(A,i);
   Part_Sequence := A
End;

В подпрограмме C.1.3 (функция Part_Sequence) продемонстрирован наиболее эффективный подход к программированию вычисления заданного члена рекуррентной последовательности.

С целью вычисления очередного члена последовательности в подпрограмме C.1.3 используется обращение к некоторой функции f(A,i), указанной в качестве формального параметра подпрограммы. Эта функция имеет нестандартный процедурный тип TFunction, который предварительно должен быть определён в разделе типов программы следующим образом:   Type TFunction = Function(A: Real; i: Integer): Real.

 Для функций, имена которых предполагается использовать в качестве фактических параметров обращения к подпрограмме C.1.3, или для программы в целом должна устанавливаться дальняя модель памяти.

Известное значение первого члена последовательности A должно задаваться в качестве фактического параметра подпрограммы C.1.3. Поэтому цикл вычисления членов последовательности начинается сразу со второго, то есть с i=1. Чтобы найти член с порядковым номером N для рекуррентной последовательности, приведённой выше в качестве примера, к подпрограмме C.1.3 следует обратиться так: A:=Part_Sequence(2.5,N,f).

Отметим, что при вычислении с помощью подпрограммы C.1.3 первого члена последовательности ( N = 1 ) её цикл не выполняется ни разу и значение первого члена, указанное в качестве фактического параметра обращения, сразу “проскакивает” на выход.

Отметим также, что значения N < 1 являются недопустимыми, поскольку членов последовательности с такими порядковыми номерами не существует 

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru. При этом настоятельно рекомендую пользоваться браузером Internet Explorer.

С уважением, Александр.
В избранное