什么是一个很好的方式来实现选择符号在Java?
-
16-09-2019 - |
题
...优选。这里是我有什么:
//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;
}
我想知道,如果有一个更好的方式这样做?
解决方案
choose(n,k) = n! / (n-k)! 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;
}
修改如果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;
其他提示
您正在处理的数字会变得非常大,并且将很快超过double
值的精度,给你意外错误的结果。出于这个原因,你可能要考虑一个任意精度的解决方案,如使用java.math.BigInteger
,不会存在这个问题。
什么你得看起来很清楚,我,说实话。诚然,我把大括号中return语句因为这是我按照约定,但,除了它看起来大约尽善尽美。
我想我可能会反转第二环路的顺序,使得两个环被提升。
由于格雷格说,如果你需要得到准确的答案为大的数字,你应该考虑其他的数据类型。鉴于该结果应该永远是一个整数,你可能要选择的 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;
}
我编写这C#但是我试图把它作为适用于尽可能Java。
源自这些来源,再加上几个小东西从我的。
代码:
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;
}
的
N!/((R 1)(N-R)!)
使用此(伪代码)
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;
此版本不需要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;
}
下面的试验证明,这是真实的:
@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;
}
不隶属于 StackOverflow