在 Java 中实现选择符号的好方法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1678690/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is a good way to implement choose notation in Java?
提问by echoblaze
... preferably in Java. Here is what I have:
...最好是Java。这是我所拥有的：
//x choose y
public static double choose(int x, int y) {
if (y < 0 || y > x) return 0;
if (y == 0 || y == x) return 1;
double answer = 1;
for (int i = x-y+1; i <= x; i++) {
answer = answer * i;
}
for (int j = y; j > 1; j--) {
answer = answer / j;
}
return answer;
}
I'm wondering if there's a better way of doing this?
我想知道是否有更好的方法来做到这一点？
回答by mob
choose(n,k) = n! / (n-k)! k!
You could do something like this in O(k):
你可以在 O(k) 中做这样的事情：
public static double choose(int x, int y) {
if (y < 0 || y > x) return 0;
if (y > x/2) {
// choose(n,k) == choose(n,n-k),
// so this could save a little effort
y = x - y;
}
double denominator = 1.0, numerator = 1.0;
for (int i = 1; i <= y; i++) {
denominator *= i;
numerator *= (x + 1 - i);
}
return numerator / denominator;
}
EDITIf xand yare large, you will overflow more slowly (i.e., be safe for larger values of x & y) if you divide your answer as you go along:
编辑如果x和y很大，如果您在继续进行时划分答案，您将更慢地溢出（即，对于较大的 x & y 值是安全的）：
double answer = 1.0;
for (int i = 1; i <= y; i++) {
answer *= (x + 1 - i);
answer /= i; // humor 280z80
}
return answer;
回答by Jon Skeet
What you've got looks pretty clear to me, to be honest. Admittedly I'd put the return statements in braces as that's the convention I follow, but apart from that it looks about as good as it gets.
老实说，你所拥有的对我来说很清楚。诚然，我会将 return 语句放在大括号中，因为这是我遵循的约定，但除此之外，它看起来和它一样好。
I think I'd probably reverse the order of the second loop, so that both loops are ascending.
我想我可能会颠倒第二个循环的顺序，这样两个循环都是升序的。
As Greg says, if you need to get accurate answers for large numbers, you should consider alternative data types. Given that the result should always be an integer, you might want to pick BigInteger(despite all the divisions, the result will always be an integer):
正如 Greg 所说，如果您需要获得大量数字的准确答案，您应该考虑替代数据类型。鉴于结果应始终为整数，您可能需要选择BigInteger（尽管进行了所有划分，但结果始终为整数）：
public static BigInteger choose(int x, int y) {
if (y < 0 || y > x)
return BigInteger.ZERO;
if (y == 0 || y == x)
return BigInteger.ONE;
BigInteger answer = BigInteger.ONE;
for (int i = x - y + 1; i <= x; i++) {
answer = answer.multiply(BigInteger.valueOf(i));
}
for (int j = 1; j <= y; j++) {
answer = answer.divide(BigInteger.valueOf(j));
}
return answer;
}
回答by Greg Hewgill
The numbers you are dealing with will become quite large and will quickly exceed the precision of doublevalues, giving you unexpectedly wrong results. For this reason you may want to consider an arbitrary-precision solution such as using java.math.BigInteger, which will not suffer from this problem.
您正在处理的数字将变得非常大，并会迅速超过double值的精度，从而给您带来意想不到的错误结果。出于这个原因，您可能需要考虑任意精度的解决方案，例如 using java.math.BigInteger，它不会遇到此问题。
回答by Sam Harwell
I coded this in C#, but I tried to make it as applicable as possible to Java.
我用 C# 编写了这个代码，但我试图让它尽可能适用于 Java。
Derived from some of these sources, plus a couple small things from me.
源自其中一些来源，以及来自我的一些小东西。
Code:
代码：
public static long BinomialCoefficient(long n, long k)
{
if (n / 2 < k)
return BinomialCoefficient(n, n - k);
if (k > n)
return 0;
if (k == 0)
return 1;
long result = n;
for (long d = 2; d <= k; d++)
{
long gcd = (long)BigInteger.GreatestCommonDivisor(d, n);
result *= (n / gcd);
result /= (d / gcd);
n++;
}
return result;
}
回答by Ralph M. Rickenbach
for
为了
N!/((R!)(N-R)!)
N!/((R!)(NR)!)
use this (Pseudocode)
使用这个（伪代码）
if (R>N) return 0;
long r = max(R, N-r)+1;
if (R==N) return 1;
for (long m = r+1, long d = 2; m <= N; m++, d++ ) {
r *= m;
r /= d;
}
return r;
回答by devconsole
This version does not require BigIntegeror floating-point arithmetic and works without overflow errors for all nless than 62. 62 over 28 is the first pair to result in an overflow.
此版本不需要BigInteger浮点运算，并且在所有n小于 62 的情况下都不会出现溢出错误。62 超过 28 是导致溢出的第一对。
public static long nChooseK(int n, int k) {
k = Math.min(k, n - k);
if (n < 0 || k < 0)
throw new IllegalArgumentException();
if (k == 0)
return 1;
long value = n--;
for (int i = 2; i <= k; i++) {
value = Math.multiplyExact(value, n--);
value /= i;
}
return value;
}
The following test proves that this is true:
下面的测试证明这是真的：
@Test
void nChooseKLongVsBigInt() {
for (int n = 0; n < 62; n++) {
for (int k = 0; k <= n; k++) {
assertEquals(nChooseKBigInt(n, k), BigInteger.valueOf(nChooseK(n, k)));
}
}
}
private BigInteger nChooseKBigInt(int n, int k) {
return factorial(n).divide(factorial(k).multiply(factorial(n - k)));
}
private BigInteger factorial(int number) {
BigInteger result = BigInteger.ONE;
for (int factor = 2; factor <= number; factor++) {
result = result.multiply(BigInteger.valueOf(factor));
}
return result;
}
