Что не так с моей логикой каталонских чисел? - PullRequest
Новая
       36

Что не так с моей логикой каталонских чисел?

1 голос
/ 19 апреля 2011

Я хотел написать код для Каталонские номера .Каталанские номера определены следующим образом:

C(n) = 2n C n/(n+1). Но вместо вычисления (2n C n) я хотел вычислить каталонские числа снизу вверх, используя следующие факты: 

Catalan(n) =    
2n! /n! * n! * (n+1)  

Catalan(n+1) =  
2*(n+1)  
--------------------------- =    
(n+1)! * (n+1)! * ((n+1)+1)  

(2n+2) * (2n+1) * 2n!    
------------------------------- =  
(n+1) * n! * (n+1) * n! * (n+2)    

(2n+2) * (2n+1) * 2n!    
----------------------------------- =    
(n+1) * (n+2) * n! * n! * (n+1)    

(2n+2) * (2n+1)    
--------------- * Catalan(n)      
(n+1) * (n+2)

Теперь, используя приведенный выше факт, это мой следующий код: 

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       return (((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan(n-1)
}

Теперь мой вопрос: почему вышеупомянутая функция возвращает 12, когда мой ввод равен 4. Он должен вернуть 14, потому что c (4) = 14.

Может кто-нибудь помочь мне, пожалуйста?

Ответы [ 5 ]

9 голосов
/ 19 апреля 2011

Даже если исходное выражение для C(n) может быть неправильным, фактическое повторение

enter image description here

равно правильно .

Выдалее можно упростить это до

enter image description here

Но это дает вам C(n+1) в терминах C(n).То, что вы хотите, это C(n) с точки зрения C(n-1).Подключите n-1, чтобы получить

enter image description here

Также обратите внимание, что для того, чтобы целочисленное деление не усекало ваш результат, вам нужно сначала умножить, а затем делить. 

int catalan(int n) {
  if (n == 1)
    return 1; 
  else
    return 2 * (2*n - 1) * catalan(n-1) / (n+1);
}

РЕДАКТИРОВАТЬ: , если значения enter image description here необходимо использовать часто, а не просто рассчитывать один раз, вероятно, будет хорошей идеей использовать memoization , чтобы избежать вычисленияих более одного раза.

Кроме того, обратите внимание, что из-за большой скорости роста каталонские числа быстро переполняют любой из предопределенных целочисленных типов данных C.

4 голосов
/ 19 апреля 2011

Согласно http://en.wikipedia.org/wiki/Catalan_number формула повторения:

C(n+1)=2(2n+1)/(n+1) * C(n) или C(n)=2(2(n-1)+1)/n * C(n-1)

Я думаю, что вы забыли это преобразование из C(n+1) в C(n).

3 голосов
/ 19 апреля 2011

В вашей формуле есть ошибка.Ваша формула для расчета c (n + 1), но вы вводите n.Это можно исправить, уменьшив значение n на единицу, прежде чем использовать его в вычислениях: 

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       n=n-1
       return (((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan(n)
}

Редактировать: Как указывает abeln, приведенный выше код не будет выполнен из-за целогоделение сбрасывает остаток.Вместо этого используйте код ниже: 

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       n=n-1
       return ((catalan(n) * (2*n+2) * (2*n+1))/((n+1)*(n+2)))
}
3 голосов
/ 19 апреля 2011

При переходе от математического выражения к коду вы неявно заменяете n на n-1 в частях Catalan (), но не в самом выражении. Таким образом, вы вычисляете множитель для значения N и умножаете его на C (N-1). Попробуйте заменить N-1 на N в вашем уравнении, что приводит к: 

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       return (((2*n) * (2*n-1))/((n)*(n+1))) * catalan(n-1)
}
0 голосов
/ 19 апреля 2011

В вашей формуле у вас есть 

         (2n)!
C(n) = ----------------
        (n+1)! * n! * n!

, тогда как на самом деле каталонские числа определены как 

         (2n)!
C(n) = ----------------
        (n+1)! * n!

, т.е. у вас слишком много одного факториала в знаменателе

...