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

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));
}}}

哪个returns

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 的溢出）：

为了避免这种情况，我们可以结合乘法和除法，以保持中间结果较小：

    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);
    }

这会产生：

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

Strange bug with Catalan number generator

java

numbers

generator

long-integer

catalan