在Java中实现选择表示法的好方法是什么？

…最好是用Java。 这是我有的：

//x choose y public static double choose(int x, int y) { if (y  x) return 0; if (y == 0 || y == x) return 1; double answer = 1; for (int i = x-y+1; i  1; j--) { answer = answer / j; } return answer; } 

我想知道是否有更好的方法吗？

Answer 1

 选择（n，k）= n！  /（nk）！  ķ！ 

你可以在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,nk), // 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; } 

编辑如果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; 

Answer 2

您正在处理的数字将变得非常大并且将快速超过double值的精度，从而给您出乎意料的错误结果。 因此，您可能需要考虑一个任意精度的解决方案，例如使用java.math.BigInteger ，它不会遇到此问题。

Answer 3

说实话，你对我的看法非常清楚。 不可否认，我将返回语句放在括号中，因为这是我遵循的惯例，但除此之外，它看起来和它一样好。

我想我可能会颠倒第二个循环的顺序，这样两个循环都是递增的。

正如格雷格所说，如果你需要获得大数的准确答案，你应该考虑其他数据类型。 假设结果应该总是一个整数，你可能想要选择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; } 

Answer 4

我在C＃中对此进行了编码，但我尝试尽可能使其适用于Java。

源自其中一些来源，加上我的几件小事。

• http://blog.plover.com/math/choose.html
• http://blog.plover.com/math/choose-2.html

码：

 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; } 

Answer 5

对于

N！/（（R 1）（NR）！）

用这个（伪代码）

 if (R>N) return 0; long r = max(R, Nr)+1; if (R==N) return 1; for (long m = r+1, long d = 2; m <= N; m++, d++ ) { r *= m; r /= d; } return r; 

Answer 6

此版本不需要BigInteger或浮点运算，并且对于小于62的所有n都没有溢出错误.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; } 

以下测试certificate这是真的：

 @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; }