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

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Вы рассчитываете факториал до 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!)  

Таким образом, вы можете забыть о вашем массиве и просто рассчитать эту формулу, которая будет работать без переполнения для больших значений 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);
    }

Который производит этот вывод (похоже, что мы все еще получаем переполнение для n=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