Странная ошибка с генератором каталонских чисел

Question

Я пытаюсь написать итеративный генератор числа каталогов, а не рекурсивный. Он работает, но только до номера «10», а затем начинает печатать номера, которые не имеют смысла. Вот что я до сих пор.

public static long dpr1(int n) 
    { 
    long [] Array = new long[(2*n)+1]; 

    Array[0]=1; 

    Array[1]=1; 

    int count=0; 

    long c=0; 

    for(int i = 2; i<=(2*n); i++){ 

     Array[i]=(i)*(Array[i-1]); 
     count=i; 
    } 

    return(((Array[count])/(((Array[n]))*(Array[n])))/(n+1)); 

}

Я тестировал его с помощью этого в качестве основного:

public class CatalanTest 
{ 
public static void main(String[] args) 
{ 
    long startTime, endTime, result; 
    for (int n = 2; n < 18; n = n + 2) 
{ 
System.out.println(Catalan.dpr1(n)); 
}}} 

Который возвращает

2 
14 
132 
1430 
16796 
-2 
97 
0 

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

Answer 1

На основании этого кода A[i] равен Factorial(i). Когда n=11, вы вычисляете Factorial до 22, а Factorial(22) больше максимального значения long, поэтому ваши вычисления переполняются, а результат неверен.

Вы можете избежать переполнения вы понимаете, что:

(Array[count]/(Array[n]*Array[n]))/(n+1) = 
((2*n)!/(n!*n!))/(n+1) = 
((n+1)*(n+2)*...*(2n)/(n!))/(n+1)= 
(n+2)*(n+3)*...*(2n)/(n!) 

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

весь код может быть уменьшен до:

for (long n=2;n<18;n+=2) { 
     long res = 1; 
     for (long l=n+2;l<=2*n;l++) 
      res *= l; 
     for (long l=2;l<=n;l++) 
      res=res/l; 
     System.out.println(res); 
    } 

Который производит этот выход (похоже, что мы до сих пор получить переполнение при п = 16):

2 
14 
132 
1430 
16796 
208012 
2674440 
91351 

Чтобы избежать этого, мы могут сочетать умножения и деления, чтобы сохранить средний результат небольшим:

for (long n=2;n<18;n+=2) { 
     double res = 1; 
     for (long l=n+2;l<=2*n;l++) { 
      res *= l; 
      res /= (l-n); 
     } 
     System.out.println((long)res); 
    } 

Это производит:

2 
14 
132 
1430 
16796 
208012 
2674440 
35357670