假设我有一种方法可以从n个项目计算r个项目的组合：
public static long combi(int n, int r) {
if ( r == n) return 1;
long numr = 1;
for(int i=n; i > (n-r); i--) {
numr *=i;
}
return numr/fact(r);
}
public static long fact(int n) {
long rs = 1;
if(n <2) return 1;
for (int i=2; i<=n; i++) {
rs *=i;
}
return rs;
}
如您所见，它涉及阶乘，很容易导致结果溢出。例如，如果我有foctorial方法的fact（200），我将得到零。问题是为什么我得到零？
其次，在上述情况下我该如何处理溢出？如果结果太大，该方法应返回尽可能大的数字以适合，而不是返回错误的答案。
一种方法（但这可能是错误的）是，如果结果超过某个较大的数字，例如1,400,000,000，则返回结果模的余数
1,400,000,001。您能否解释一下这意味着什么，以及如何在Java中做到这一点？
请注意，我不保证上述方法对于计算阶乘和组合是正确的。如果您发现错误并纠正错误，则可获得额外的奖励。
请注意，我只能使用int或long，如果不可避免，也可以使用double。不允许使用其他数据类型。
我不确定谁将此问题标记为作业。这不是功课。我希望这是家庭作业，我回到了大学的年轻学生。但是我已经有十多年的程序员年龄了。我只想练习用Java开发高度优化的解决方案。在我们大学时代，互联网甚至不存在。今天的学生很幸运，他们甚至可以像SO这样的网站上张贴作业。
参考方案
为了回答您的第一个问题（为什么会归零），由模块化算术计算出的fact（）值等于全部64位归零！将您的事实代码更改为此：
public static long fact(int n) {
long rs = 1;
if( n <2) return 1;
for (int i=2; i<=n; i++) {
rs *=i;
System.out.println(rs);
}
return rs;
}
看看输出！他们非常有趣。
现在进入第二个问题。
似乎您想为适合的long和n值给出精确的整数（er，r）答案，如果不正确，则抛出异常。这是一个公平的练习。
为了正确地做到这一点，您根本不应该使用阶乘。诀窍是认识到C(n,r)可以通过添加项来递增计算。这可以通过带备忘录的递归来完成，也可以通过Stefan Kendall提到的乘法公式来完成。
当您将结果累积到将用于答案的long变量中时，请在每次添加后检查该值是否为负。当发生时，引发异常。如果它保持肯定，则可以安全地返回累积结果作为答案。
要了解为什么这样做有效，请考虑Pascal三角形
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
生成如下：
C(0,0) = 1 (base case)
C(1,0) = 1 (base case)
C(1,1) = 1 (base case)
C(2,0) = 1 (base case)
C(2,1) = C(1,0) + C(1,1) = 2
C(2,2) = 1 (base case)
C(3,0) = 1 (base case)
C(3,1) = C(2,0) + C(2,1) = 3
C(3,2) = C(2,1) + C(2,2) = 3
...
使用备注计算C(n,r)的值时，将递归调用的结果存储在适当的结构中，例如数组或哈希图，以将它们存储在其中。每个值是两个较小数字的总和。数字从小开始，总是正数。每当您计算新值（我们称其为子项）时，您都会添加较小的正数。从您的计算机组织类回想起，每当您添加两个模数正数时，当且仅当总和为负数时，才会发生溢出。在整个过程中只需要一个溢出就可以使您知道要查找的C(n,r)太大。
可以将这一论点转换为一个很好的归纳证明，但这可能是针对另一个任务，也许是另一个StackExchange网站。
附录
这是可以运行的完整应用程序。 （我还没有弄清楚如何使Java在键盘和ideone上运行）。
/**
* A demo showing how to do combinations using recursion and memoization, while detecting
* results that cannot fit in 64 bits.
*/
public class CombinationExample {
/**
* Returns the number of combinatios of r things out of n total.
*/
public static long combi(int n, int r) {
long[][] cache = new long[n + 1][n + 1];
if (n < 0 || r > n) {
throw new IllegalArgumentException("Nonsense args");
}
return c(n, r, cache);
}
/**
* Recursive helper for combi.
*/
private static long c(int n, int r, long[][] cache) {
if (r == 0 || r == n) {
return cache[n][r] = 1;
} else if (cache[n][r] != 0) {
return cache[n][r];
} else {
cache[n][r] = c(n-1, r-1, cache) + c(n-1, r, cache);
if (cache[n][r] < 0) {
throw new RuntimeException("Woops too big");
}
return cache[n][r];
}
}
/**
* Prints out a few example invocations.
*/
public static void main(String[] args) {
String[] data = ("0,0,3,1,4,4,5,2,10,0,10,10,10,4,9,7,70,8,295,100," +
"34,88,-2,7,9,-1,90,0,90,1,90,2,90,3,90,8,90,24").split(",");
for (int i = 0; i < data.length; i += 2) {
int n = Integer.valueOf(data[i]);
int r = Integer.valueOf(data[i + 1]);
System.out.printf("C(%d,%d) = ", n, r);
try {
System.out.println(combi(n, r));
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
}
希望它是有用的。这只是一个快速的技巧，因此您可能需要对其进行清理...。还要注意，一个好的解决方案将使用适当的单元测试，尽管此代码确实给出了不错的输出。
JAVA:字节码和二进制有什么区别？ - javajava字节代码（已编译的语言，也称为目标代码）与机器代码（当前计算机的本机代码）之间有什么区别？我读过一些书，他们将字节码称为二进制指令，但我不知道为什么。 参考方案 字节码是独立于平台的，在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的，如果在Windows x86中编译，则它将仅在Win…
java:继承 - java有哪些替代继承的方法？ java大神给出的解决方案 有效的Java：偏重于继承而不是继承。 （这实际上也来自“四人帮”）。他提出的理由是，如果扩展类未明确设计为继承，则继承会引起很多不正常的副作用。例如，对super.someMethod()的任何调用都可以引导您通过未知代码的意外路径。取而代之的是，持有对本来应该扩展的类的引用，然后委托给它。这是与Eric…
Java:BigInteger，如何通过OutputStream编写它 - java我想将BigInteger写入文件。做这个的最好方式是什么。当然，我想从输入流中读取（使用程序，而不是人工）。我必须使用ObjectOutputStream还是有更好的方法？目的是使用尽可能少的字节。谢谢马丁 参考方案 Java序列化（ObjectOutputStream / ObjectInputStream）是将对象序列化为八位字节序列的一种通用方法。但…
Java-如何将此字符串转换为日期？ - java我从服务器收到此消息，我不明白T和Z的含义，2012-08-24T09:59:59Z将此字符串转换为Date对象的正确SimpleDateFormat模式是什么？ java大神给出的解决方案 这是ISO 8601标准。您可以使用SimpleDateFormat simpleFormat = new SimpleDateFormat("yyyy-MM…
Java:从类中查找项目名称 - java仅通过类的实例，如何使用Java反射或类似方法查找项目名称？如果不是，项目名称（我真正想要的是）可以找到程序包名称吗？ 参考方案 项目只是IDE使用的简单组织工具，因此项目名称不是类或JVM中包含的信息。要获取软件包，请使用Class#getPackage()。然后，可以调用Package#getName()将包作为您在代码的包声明中看到的String来获取…