Java "Catalan number" 生成器几乎正常工作

Question

什么是加泰罗尼亚数字： https://en.wikipedia.org/wiki/Catalan_number

我正在做一些 Java 练习，一些测试数字没有通过，尽管我确定它们应该通过。

我成功获得了 13 个结果中的 11 个，但在编程方面，我知道如果我没有获得最后两个结果，我一定是以某种奇怪的方式获得了另外 11 个结果。数字 0 - 9 和 20 效果很好，但 14 和 25 略有偏差：

catalanNumber(14) -> 2674439 (expected 2674440)
catalanNumber(25) -> 4861946401451 (expected 4861946401452)

这是我写的代码：

public static long catalanNumber(int place) 
{   // declare variables
    double numerator = (2 * place), 
        denFirst = (place + 1), denSecond = place;
    // C(0) = 1
    if(place == 0)
        return 1;
    // find (2n)!
    for(long i = (long)numerator - 1; i > 0; i--)
        numerator *= i;
    // find (n + 1)!
    for(long i = (long)denFirst - 1; i > 0; i--)
        denFirst *= i;
    // find (n)!
    for(long i = (long)denSecond - 1; i > 0; i--)
        denSecond *= i;
    // C(n) = (2n)! / (n + 1)!(n)!
    return (long)(numerator / (denFirst * denSecond));
}

这个问题的关键限制是我不能使用递归...如果只是;p

I wasn't able to really understand what was happening here/how to convert it into my problem:

// code from that link ^
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);
}

Answer 1

双打会引入错误。默默地。

为什么？嗯，电脑。它们很强大，但并不神奇。

想一想数字线 - 在 0 和 1 之间有无限个数。

而 double 声称能够代表整个无穷大。更均匀； 2.0 是双倍的。

事实证明，计算机实际上无法做到这一点。因为物理、数学、常识。因此，取而代之的是这些非常具体的选择的少数数字。让我们称他们为祝福集吧。

一个 double 值可以 实际上 只能代表祝福集中的数字。自然地，那里只有有限数量的数字。 double 的设计，正如人们可能预料的那样，是相当花哨的数学，使它们成为 CPU 轻松使用的正确组合，以执行您希望它们进行的计算，然后尽可能地有用。作为该过程的一部分，0-1 区域中的祝福数字比 10000 到 10001 之间的数字要多得多 - 随着您离 0 越来越远，祝福数字越来越少。

无论如何，当计算结果是不祝福时，则取而代之的是四舍五入到最接近的祝福数，默默.

这引入了错误；你没有得到警告的错误（你不能得到第二个数字，其值是错误的确切大小。毕竟， 'delta' 也没有得到祝福，所以这是不可能的）。当你用双打进行越来越多的数学运算时，这些错误就会复杂化。它解释了为什么会发生这种情况。

你有几个选择。

仅使用积分数学

整数（例如long和int）只做一件事'silently'，即从它们的最大值'loop'（Long.MAX_VALUE和Integer.MAX_VALUE - 2^31-1 和 2^63-1)，到它们的最小值，即 Integer.MAX_VALUE + 1 实际上是一个很大的 negative 数字，事实上，它是 Integer.MIN_VALUE：它一直循环。

除此之外，他们是'perfect'。那里没有安静的四舍五入。简单的例子：不要将欧元存储在 double 中。将美分存储在 long.

中

使用 BigDecimal

这是保证完美的javaclass。然而，这是有代价的：

它像糖蜜一样慢，比 double 数学慢很多数量级。
除法会崩溃，除非除法恰好解决了 'nicely'，或者您明确要求...精度损失。 1 除以 3，写成十进制且没有任何损失是多少？你会发现这个问题无法回答。它是 0.3333333333... 并且会一直持续下去，因此您不能无损地表示十进制表示法中非常简单的 1/3。我不确定 BigDecimal 是否使用十进制或更可能的二进制，但关键是，无论您选择什么基数，各种除数都不会 'fit'。（在十进制中，1/4 很好：即 0.25，非常精确，因此可以完成）。

鉴于不需要除以任何东西，您可以只使用它，甚至更好，BigInteger（因为您似乎一开始就不需要十进制数学 - BigInteger 将变得任意大，只要你的系统内存允许你就可以。

Answer 2

我能够将 link 的代码转化为我的问题，但是，我仍然无法弄清楚 BigInteger 对象的 syntax/use 情况。

public static long catalanNumber(int number) 
{   // negative catalan DNE
    if(!(number < 0))
    {   // assign starting catalan number
        double value = 1;
        // C(0) & C(1) = 1
        if(number > 1)
        {
            for(long place = number + 2; 
                 place <= 2 * number; place++) 
            {
                value *= place;
                value /= (place - number);
            }
        }
        // remove decimals
        return (long)value;
    }
    // invalid catalan number (n < 0)
    return -1;
}

^ 这个 ^ 确实很好用，但是在我的循环中有 double 让我有点紧张。我很想看看如何使用 BigInteger 对象作为 well/instead 来做到这一点，因为我知道 这只会对 X 位数起作用，直到它溢出.

在哪里可以了解有关 BigInteger 对象的更多信息：

另外，感谢@rzwitserloot 解释浮点数如何处理大数。如果您是 Java 的新手，我强烈建议您阅读他的回答——甚至是一般的编程。

Java "Catalan number" 生成器几乎正常工作

Java "Catalan number" generator is almost working right

java

catalan

仅使用积分数学

使用 BigDecimal