java - 加泰罗尼亚数字生成器的奇怪错误

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!)  

所以你可以忘记你的数组，只计算这个公式，对于较大的 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