Преобразовать каталанский рекурсивный алгоритм в итеративный

Question

Привет всем могучим хакерам, математикам и программистам!

Я усердно работаю над созданием рекурсивного алгоритма для уравнения каталонских чисел ниже

C (n) = ∑ C (i − 1) C (n − i) (и упрощение этого уравнения с использованием чисел перемешивания или других форм не допускается ..)

Вот рекурсивный алгоритм до сих пор:

int Cval[1024];//1024 just for example

int C( int n )
    {
    if( Cval[n] ) != ­1 ) return Cval[n];
        int ans = 0;
        if( n == 0 ) ans = 1;
        for( int i = 1; i <= n; i++ )
            ans += C( i ­- 1 ) * C( n ­- i );
                return Cval[n] = ans;
    }

int main()
{
    for( int i = 0; i < 1024; i++ ) Cval[i] = ­1;
    // call C(n) for any n up to 1023
}

Теперь я пытаюсь преобразовать это в итеративный алгоритм. И мне нужна ваша драгоценная помощь;) Есть идеи?

Answer 1

Вы пытаетесь реализовать более общий шаблон, известный как Динамическое программирование .

Используемый вами механизм кэширования иногда называется динамическим программированием сверху вниз, так как вы начинаете вычисления с наибольшегоN первый.(Кстати, в вашем главном случае вам нужно всего лишь вызвать C() для наибольшего N, так как правило для каталонских чисел заставляет его рекурсивно вызывать все остальные значения в любом случае).

Чтобы превратить этот алгоритм в низ-вверх (итеративный подход) вам нужно найти порядок для аргументов таким образом, чтобы C(x) зависело только от элементов, меньших x.Вычисляя значения C в этом порядке, вы всегда можете просто использовать значения массива напрямую, вместо того, чтобы полагаться на функцию запоминания:

//initialize your base cases by hand, in 
Cval[0] = 1

//Now handle the inductive cases:
for n from 1 up to N:
    Cval[n] = 0
    for i from 1 to n:
        Cval[n] += Cval[i -1] * Cval[n -i];
    // i-1 and n-i are both less than n, so we know that
    // Cval has already been calculated for them.

Answer 2

Создайте массив чисел C и соберите его. Это на самом деле меньше обработки, чем рекурсивная версия (которая будет вычислять большинство чисел несколько раз), и занимает меньше места (поскольку массив находится в непрерывной памяти, а не распространяется по стеку вызовов).

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