5.1. Рекуррентные вычисления

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

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

Пусть в некоторой последовательности известны первые nзначений:

Тогда элемент при определяется так:

Или, иными словами:

Простейшим примером рекуррентного соотношения является вычисление факториала числа:

Программная реализация вычисления факториала:

unsigned Factorial (unsigned n)

{

unsigned i = 0; // Текущее значение i

unsigned F = 1; // Текущее значение i!

while (i < n)

{

++ i; // i = i + 1

F *= i; // F = F * i - текущее значение i!

}

return F; //Возвращаем значениеn!

}

Недостатком этой реализации является то, что с помощью этой функции можно вычислить n!только дляnот0до12. Значение13!уже выходит за верхнюю границу диапазона значений типаunsignedи функция начинает возвращать неверные значения факториала. Для предотвращения получения неверных значений факториалов модифицируем функцию следующим образом:

unsigned Factorial (unsigned n)

{

unsigned i = 0; // Текущее значение i

unsigned F = 1; //Текущее значение i!

while (i < n)

{

++ i; // i = i + 1

if (0xffffffffu / i < F ) // 0xffffffffu – максимальное значение типа unsigned

{

F = 0;

break;

}

F *= i; // F = F * i - текущее значение i!

}

return F; //Возвращаем значениеn!

}

Добавленная проверка обнаруживает ситуацию, когда умножение предыдущего значения факториала на следующее значение iприведет к выходу полученного значения произведения за верхнюю границу диапазона значений типаunsigned. В этом случае значению факториала присваивается значение0 (факториал любого числа всегда больше 0), и с помощью инструкцииbreakвыполнение цикла прерывается. В этом случае функция вернет значение0.

При такой реализации функцию Factorial в программе можно использовать, например, так:

unsigned F, n;

…..

if (F = Factorial (n))

….. // Используем вычисленное значение факториала F

else

cout << “Ошибка. Факториал числа ” << n << “ не может быть вычислен! \n”;

Важно. При рекуррентном накоплении сумм, произведений (степеней, факториалов) целых типов следует очень внимательно контролировать возможность выхода за границы диапазона значений используемого целого типа данных. При возникновении таких ситуаций поведение программы будет непредсказуемым.

Еще один пример. Требуется подсчитать сумму первых nэлементов следующего степенного ряда:

Если подойти к решению этой задачи “в лоб”, то получится следующая весьма неэффективная программа:

int n = 20; // Количество суммируемых элементов ряда

double x = 2.5; // Значение аргументаx

double S = 0; // Начальное значение суммы ряда

int i = 0; //Начальное значение индекса элемента ряда

while (i < n)

{

S = S + pow(x, i) / Factorial (i);

++ i;

}

cout << “Сумма первых ” << i << “ элементов ряда равна ” << S << endl;

Неэффективность этого варианта реализации объясняется двумя причинами. Во-первых, поскольку функция вычисления факториала представляет собой цикл, общее количество операций будет быстро расти с увеличением n. Во-вторых, нам вообще не удастся подсчитать сумму более чем13элементов этого ряда, так как приi = 13, функция вычисления факториала возвратит значение0, и наша программа аварийно завершится с ошибкой “Деление на0”. Избежать аварийного завершения программы можно, как это было описано выше – путем проверки значения факториала на 0 и прерывания цикла, однако более 13 элементов ряда все равно просуммировать не удастся.

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

Несложно заметить, что откуда следует, чтопри.

Тогда можно предложить следующий вариант реализации:

int n = 20; // Количество суммируемых элементов ряда

double x = 2.5; // Значение аргументаx

double a = 1;//Значение первого элемента ряда

double S = 1; // Начальное значение суммы ряда приi= 0

int i = 1; //Начальное значение индекса элемента ряда

while (i < n)

{

a = a * x / i ;

S = S + a;

++ i;

}

cout << “Сумма первых ” << i << “ элементов ряда равна ” << S << endl;

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

Более сложный вариант рекуррентного соотношения. Требуется написать функцию для получения значения многочлена Чебышева первого рода степени n>= 0 , задающегося следующим рекуррентным соотношением:

Реализация:

double Cheb_1 (double x, int n)

{

double Tn, Tn_1 = x, Tn_2 = 1;

switch (n)

{

case 0: return Tn_2;

case 1: return Tn_1;

default:

int i = 2;

while (i < = n)

{

Tn = 2 * x * Tn_1 - Tn_2;

Tn_2 = Tn_1;

Tn_1 = Tn;

++ i;

}

return Tn;

}

}

При выполнении рекуррентных вычислений с вещественными значениями беспокоиться о переполнении значений вещественного диапазона приходится очень редко (особенно при использовании типа double). Но и здесь встречаются некоторые “подводные камни”.

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

double a = 1.1, b = 0;

while ( ! (b == a) )

{

b = b + 0.1;

}

Такой цикл никогда не закончится, так как из-за погрешностей вычислений и представления вещественных значений точного равенства aиbпри выбранных значениях никогда не будет (так, по крайней мере, происходит для этого примера вMSVisualC++ 2010). Лучше сделать так:

double a = 1.11, b = 0;

while ( b <= a )

{

b = b + 0.1;

}

Здесь цикл закончится гарантированно, и последнее значение bбудет очень близко к1.1.

Предостережение № 2. Остерегайтесь складывать (вычитать) очень большие и относительно малые вещественные значения. Например:

double a = 1e20, b = a, d = 1000;

int i = 1;

for ( int i = 1; i <= 1000000; ++ i)

{

b = b + d;

}

cout << b – a << endl;

Ожидается, что значение bпосле окончания цикла будет большеaна1 000 000 000, однако разность междуbиaоказывается равной 0. Это происходит, потому что величинаd = 1 000по отношению к значениюa = 1e20оказывается пренебрежимо малой из-за дискретности представления вещественных значений.

Если увеличить значение dи сделать его равным10 000, то разностьb – a окажется равной приблизительно1.64e10, а не1e10как это следует из арифметики – достаточно грубая ошибка.

Для того, чтобы избавиться от этой неприятности, можно поступить так:

double a = 1e20, b = a, d = 1000, s = 0;

int i = 1;

for ( int i = 1; i <= 1000000; ++ i)

{

s = s + d;

}

b = b + s;

cout << b – a << endl;

Вот теперь мы увидим то, что ожидалось (или очень близкое к тому) и в первом и во втором случаях. Здесь мы сначала накопили отдельно сумму sотносительно малых величинd, а затем уже относительно большое значениеsдобавили кb.