英文:
Having trouble with the output of this combination in Java
问题
我遇到了输出问题。当我运行这段代码时,我的程序只会输出0:
public class Lottery {
public static long numPossibleTickets(int k, int n, int m) {
int i;
int j;
long numerator = n;
long denominator = k;
long total = 0;
for (i = n - 1; i > (k + 1); i--) {
numerator = numerator * i;
}
i = 0;
for (j = k; j > 0; j--) {
denominator = denominator * (denominator - i);
i++;
}
total = m * (numerator / denominator);
return total;
}
public static void main(String[] args) {
Scanner scnr = new Scanner(System.in);
int k = 5;
int n = 69;
int m = 26;
System.out.println(numPossibleTickets(k, n, m));
}
}
然而,输出应该是292,201,338。对此有任何帮助将不胜感激。非常感谢!
英文:
I'm trying to calculate a combination using this formula:
I'm running into issues with the output. My program simply outputs 0 when I run this code:
public class Lottery {
public static long numPossibleTickets(int k, int n, int m) {
int i;
int j;
long numerator = n;
long denominator = k;
long total = 0;
for (i = n - 1; i > (k + 1); i--) {
numerator = numerator * i;
}
i = 0;
for (j = k; j > 0; j--) {
denominator = denominator * (denominator - i);
i++;
}
total = m * (numerator / denominator);
return total;
}
public static void main(String[] args) {
Scanner scnr = new Scanner(System.in);
int k = 5;
int n = 69;
int m = 26;
System.out.println(numPossibleTickets(k, n, m));
}
}
However, the output should be 292,201,338. Any help with this would be much appreciated. Thanks so much!
答案1
得分: 1
我更愿意创建一个方法来获取一个数字的阶乘。
此外,使用 BigInteger
作为长整数不足以存储大数字的阶乘,因此以下是最终代码,它可以正常工作。
public static void main(String[] args) {
int k = 5;
int n = 69;
int m = 26;
System.out.println(numPossibleTickets(k, n, m)); // 结果为 292201338
}
public static BigInteger numPossibleTickets(int k, int n, int m) {
int i;
int j;
BigInteger numerator = getFactorial(n);
BigInteger denominator = getFactorial(k).multiply(getFactorial(n - k));
BigInteger total;
total = new BigInteger(m + "").multiply(numerator.divide(denominator));
return total;
}
// 获取给定数字的阶乘
public static BigInteger getFactorial(int number) {
BigInteger factorial = new BigInteger(number + "");
for (int i = number - 1; i > 1; i--) {
factorial = factorial.multiply(new BigInteger(i + ""));
}
return factorial;
}
请注意,代码中的 ""
已被正确翻译为字符串引号 ""
。
英文:
I'd prefer to create a method to get the factorial of a number.
besides also using a BigInteger
as long isn't enough to store big numbers factorial
so here's final code and it's working
public static void main(String[] args) {
int k = 5;
int n = 69;
int m = 26;
System.out.println(numPossibleTickets(k, n, m)); // result is 292201338
}
public static BigInteger numPossibleTickets(int k, int n, int m) {
int i;
int j;
BigInteger numerator = getFactorial(n);
BigInteger denominator = getFactorial(k).multiply(getFactorial(n-k));
BigInteger total ;
total = new BigInteger(m+"").multiply(numerator.divide(denominator));
return total;
}
// to get the factorial of given number
public static BigInteger getFactorial(int number){
BigInteger factorial = new BigInteger(number+"");
for (int i = number - 1; i > 1; i--) {
factorial = factorial.multiply(new BigInteger(i+""));
}
return factorial;
}
答案2
得分: 1
你的代码存在至少3个不同的问题。
首先,你试图使用阶乘来计算组合数。阶乘的问题是它增长非常快:中间结果无法适应long
数据类型的范围,结果无用。你可以使用BigInteger
进行计算,但效率不会特别高。做出以下更改:
public static long numPossibleTickets(int k, int n, int m) {
int i;
int j;
BigInteger numerator = BigInteger.valueOf(n);
BigInteger denominator = BigInteger.valueOf(k);
long total = 0;
for (i = n - 1; i >= (k + 1); i--) {
numerator = numerator.multiply(BigInteger.valueOf(i));
}
i = 0;
for (j = k; j > 0; j--) {
denominator = denominator.multiply(denominator.subtract(BigInteger.valueOf(i)));
i++;
}
total = m * numerator.divide(denominator).longValue();
return total;
}
其次,计算分子的循环存在问题:它计算的是69!/6!而不是69!/5!。幸运的是这个问题很容易修复:
for (i = n - 1; i >= (k + 1); i--) {
numerator = numerator.multiply(BigInteger.valueOf(i));
}
第三,计算分母的循环似乎完全错误。我不知道你试图做什么,但根据你计算分子的方式,分母应该是计算(n-k)!,可以像这样修改:
BigInteger denominator = BigInteger.ONE;
for (int j = n - k; j > 1; j--) {
denominator = denominator.multiply(BigInteger.valueOf(j));
}
通过这三个更改,我得到了期望的输出 292201338
。
英文:
There are at least 3 different problems with your code.
You are trying to compute the number of combinations using factorials. The problem with factorial is that it grows incredibly fast: the intermediate results don't fit in the range for the long
data type, and the result is useless. You could use the BigInteger
for the computations, but it won't be particularly efficient. With that change:
public static long numPossibleTickets(int k, int n, int m) {
int i;
int j;
BigInteger numerator = BigInteger.valueOf(n);
BigInteger denominator = BigInteger.valueOf(k);
long total = 0;
for (i = n - 1; i > (k + 1); i--) {
numerator = numerator.multiply(BigInteger.valueOf(i));
}
i = 0;
for (j = k; j > 0; j--) {
denominator = denominator.multiply(denominator.subtract(BigInteger.valueOf(i)));
i++;
}
total = m * numerator.divide(denominator).longValue();
return total;
}
Second, the loop that computes the numerator is off by one: instead of computing 69!/5! it's computing 69!/6!. Luckily that's easy to fix:
for (i = n - 1; i >= (k + 1); i--) {
numerator = numerator.multiply(BigInteger.valueOf(i));
}
Third, the loop that computes the denominator seems to be way off. I don't know what you're trying to do, but given what you are computating for the numerator, the denominator should be computing (n-k)!, and that could look like this:
BigInteger denominator = BigInteger.ONE;
for (int j = n-k; j > 1; j--) {
denominator = denominator.multiply(BigInteger.valueOf(j));
}
With these three changes, I get the expected output 292201338
.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论