Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Рекуррентные соотношения

На главную Математический раздел Криптография и т.д. Новости

Рекуррентные соотношения - соотношения вида "следующий через предыдущих", то есть отношение, когда значение f(n) описывается через f(m), где n > m. f - функция целого аргумента, обычно натурального или целого неотрицательного.

Должны быть известны некоторые начальные условия, за счёт которых вычисление значения f будет без зацикливания.

В общем случае рекуррентное соотношение записывается в виде g(n) = f(n, g(n-1), g(n-2), ..., g(n-k)), где k - порядок рекуррентного соотношения.

Для рекуррентного соотношения порядка k должны быть хотя бы k начальных условий вида g(x)=y, где x, y известны, например, известны значения g(0), g(1), ..., g(k-1).

Пример: i-ый член арифметической прогрессии может определяться как a(i) = a(i - 1) + d. В качестве начального условия выступает первый член прогрессии, а порядок k = 1.

Другой пример:

Эта немного страшная формула определяет так называемые числа Фибоначчи, то есть последовательность натуральных чисел, где каждое число есть сумма двух предыдущих. Порядок данного рекуррентного соотношения равен 2, соответственно требуется два начальных условия.

Для прогеров аналогом рекуррентных соотношений являются рекурсивные функции. Если f - рекурсивная функция, то при вычислении её значения выполняются вызовы самой же f. В реализацию рекурсивной функции обязательно входят так называемые граничные условия. Если они не прописаны, неизбежно возникает переполнение стека, поскольку память ЭВМ всегда конечная.

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

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

Как получить рекуррентные соотношения для рядов

Иногда задание n-го члена ряда как функции от n неудобно. Например, эта ситуация имеет место, когда требуется найти сумму первых k членов ряда, при этом формула для n-го члена содержит такие штуки, как степени, факториалы.

В случаях вроде только что названного поступают так: первый член ряда берут как начальное условие. Составляют формулу вида g(n) = a(n+1)/a(n). Далее равенство a(n+1) = a(n) * g(n) берут как рекуррентное соотношение.

Допустим, n-ый член ряда определяется по такой вот страшной формуле:

Скажем, нужно найти сумму этак 50-100 членов ряда. Попробуем "в лоб" написать прогу, которая это делает (идиоты могут считать и вручную, кто же против-то?). Выходит, что в цикле складываем a(i), i = 1, 2, ..., вычисляя a(i) по значению i и не используя при этом значения предыдущих членов ряда:

double fact(int n) { ... /* реализуем вычисление факториала */ }

double a(int i) { return pow(2, n) / fact(n); }

double StupidFuncSum(int n) {

double sum = 0;

for(int i = 1; i <= n; i++) sum += a(i);

return sum; }


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

А теперь без лобовых атак) Действуем вот как:

Граничное условие: a(1) = 2. Через a(1) вычисляем a(2), через a(2) определяем a(3) и т.д. В итоге ни степеней, ни факториалов мы не вычисляем - вот как нам помогает рекуррентное соотношение:

double MegoFunc() {

double sum = 0, cur = 2;

for(int i = 1; i <= n; i++)
{
    sum += cur;
    cur = (2.0 * cur / (i + 1.0));
}

return sum; }

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X