什么是加泰罗尼亚数字: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
我无法真正理解这里发生了什么/如何将其转换为我的问题:加泰罗尼亚数字生成器的奇怪bug
// 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);
}
双精度会导致错误。默默地.
为什么?嗯,电脑。他们是强大的，但他们不是魔法。
想象一条数字线——在0和1之间有无限的数量
double声称能够表示整个无穷大。甚至更多;2.0是double类型
事实证明计算机实际上不能做到这一点。因为物理，数学，常识。所以，取而代之的是这些特定的少数数字。让我们称他们为幸运的一组。
一个double值实际上可以只表示祝福集合中的数字。很自然，这里的数字是有限的。double的设计，正如人们所预料的，是相当花哨的数学，使它们很容易被cpu使用来做你想让它们做的计算，然后尽可能有用。作为这个过程的一部分，在0-1区域有更多的幸运数字，而在10000到10001之间，当你离0越远，幸运数字就越少。
无论如何，当计算结果不赋值时，则将其舍入到最接近的赋值数，静默地.
这会引入错误;没有警告的错误(您无法获得第二个值与错误大小相同的数字)。毕竟，"三角洲"也不受祝福，所以这是不可能的)。当你对双精度进行越来越多的数学运算时，这些错误就会加剧。它解释了为什么会发生这种情况。
你有几个选择。
只使用整数
整数(例如long和int)只"默默地"做一件事，这是从它们的最大值(Long.MAX_VALUE和Integer.MAX_VALUE- 2^31-1和2^63-1)"循环"到它们的最小值，例如，Integer.MAX_VALUE + 1实际上是一个大的负数，事实上，它是Integer.MIN_VALUE:它一直循环。
除此之外，他们是"完美的"。没有安静的环绕。简单的例子:不要在double中存储欧元。在long中存储美分。
使用BigDecimal
这是一个保证完美的java类。然而，这是有代价的:
- 它像糖蜜一样慢，比
double数学慢很多个数量级。 - 如果你除法，它会崩溃，除非除法碰巧"很好"，或者你明确要求……失去精度。1除以3是多少，写成十进制，没有任何损失?你会发现这个问题无法回答。这是0.3333333333……这样一直持续下去，所以不能无损地表示非常简单的1/3十进制记数法。我不确定BigDecimal是否使用十进制或更可能的二进制，但关键是，无论您选择哪种进制，各种除数都不会"适合"。(在十进制中，1/4是好的:那是0.25，具有完美的精度，所以一个可以完成)。
考虑到不需要除任何东西，您可以使用它，或者更好的是，BigInteger(因为您似乎不需要十进制数学-BigInteger将变得任意大，只要您的系统内存允许)。
我能够将链接的代码翻译成我的问题，但是，我仍然无法弄清楚BigInteger对象的语法/用例。
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;
}
^ This ^确实很有效，但是在我的循环中有double让我有点紧张。我很想看看如何使用BigInteger对象以及/而不是因为我知道这只会工作到X位数，直到它溢出。
在哪里了解更多关于BigInteger对象的信息:
- https://www.geeksforgeeks.org/biginteger-class-in-java/
- https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html
另外，感谢@rzwitserloot解释了浮点是如何处理大数的。如果您是Java新手，甚至是编程新手，我强烈建议您阅读他的回答。