如何优化程序来计算catalan数

Question

我必须编写一个计算加泰罗尼亚数的程序，因此我必须计算一些阶乘。问题是，程序需要能够处理多达5000的输入，并且有一定的时间限制，必须填满。我使用BigInteger类来处理这些大数字，但现在它需要太长时间。我不知道如何进一步优化程序。

这是我计算阶乘的代码：

public static BigInteger factorial(BigInteger toFactorial) 
{
if(toFactorial.intValue() <= 1) 
{
return new BigInteger("1");
}

return toFactorial.multiply(factorial(toFactorial.subtract(new BigInteger("1"))));
}

下面是我如何使用这些来计算加泰罗尼亚数：

for(int i = 0; i < anzCases; i++)
{
BigInteger x = new BigInteger(io.getWord());
BigInteger facX = factorial(x);
BigInteger facXPlus1 = facX.multiply(x.add(new BigInteger("1")));           
System.out.println( factorial( x.multiply( new BigInteger("2") ) ).divide( facXPlus1.multiply( facX ) ) );
}

在这种情况下，x是输入。谢谢你的帮助。

Answer 1

有常量，请使用BigInteger.ONE和您自己的常量。

在BigInteger的某个极限以内使用阶乘。

运用数学智慧。最富有成果，但需要应用数学。