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

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