java 计算由阶乘产生的数字的尾随零
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1174505/
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
Counting trailing zeros of numbers resulted from factorial
提问by codingbear
I'm trying to count trailing zeros of numbers that are resulted from factorials (meaning that the numbers get quite large). Following code takes a number, compute the factorial of the number, and count the trailing zeros. However, when the number is about as large as 25!, numZeros don't work.
我正在尝试计算由阶乘产生的数字的尾随零（意味着数字变得非常大）。以下代码取一个数字，计算该数字的阶乘，并计算尾随零。但是，当数字大约为 25! 时，numZeros 不起作用。
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
double fact;
int answer;
try {
int number = Integer.parseInt(br.readLine());
fact = factorial(number);
answer = numZeros(fact);
}
catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
public static double factorial (int num) {
double total = 1;
for (int i = 1; i <= num; i++) {
total *= i;
}
return total;
}
public static int numZeros (double num) {
int count = 0;
int last = 0;
while (last == 0) {
last = (int) (num % 10);
num = num / 10;
count++;
}
return count-1;
}
I am not worrying about the efficiency of this code, and I know that there are multiple ways to make the efficiency of this code BETTER. What I'm trying to figure out is why the counting trailing zeros of numbers that are greater than 25! is not working.
我并不担心这段代码的效率，我知道有多种方法可以使这段代码的效率更好。我想弄清楚的是为什么要计算大于 25 的数字的尾随零！不管用。
Any ideas?
有任何想法吗？
回答by sdcvvc
Your task is not to compute the factorial but the number of zeroes. A good solution uses the formula from http://en.wikipedia.org/wiki/Trailing_zeros(which you can try to prove)
您的任务不是计算阶乘，而是计算零的数量。一个好的解决方案使用来自http://en.wikipedia.org/wiki/Trailing_zeros的公式（您可以尝试证明）
def zeroes(n):
i = 1
result = 0
while n >= i:
i *= 5
result += n/i # (taking floor, just like Python or Java does)
return result
Hope you can translate this to Java. This simply computes [n / 5] + [n / 25] + [n / 125] + [n / 625] + ... and stops when the divisor gets larger than n.
希望你能把它翻译成Java。这只是计算 [n / 5] + [n / 25] + [n / 125] + [n / 625] + ... 并在除数大于 n 时停止。
DON'T use BigIntegers. This is a bozosort. Such solutions require seconds of time for large numbers.
不要使用 BigIntegers。这是一个bozosort。此类解决方案需要数秒的时间来处理大量数据。
回答by job
You only really need to know how many 2s and 5s there are in the product. If you're counting trailing zeroes, then you're actually counting "How many times does ten divide this number?". if you represent n! as q*(2^a)*(5^b) where q is not divisible by 2 or 5. Then just taking the minimum of a and b in the second expression will give you how many times 10 divides the number. Actually doing the multiplication is overkill.
您只需要真正知道产品中有多少个 2 和 5。如果您计算尾随零，那么您实际上是在计算“10 除以这个数字多少次？”。如果你代表n！如 q*(2^a)*(5^b) 其中 q 不能被 2 或 5 整除。然后在第二个表达式中取 a 和 b 的最小值就会得到 10 除以这个数字的次数。实际上做乘法是矫枉过正的。
Edit: Counting the twos is also overkill, so you only really need the fives.
编辑：计算二分法也太过分了，所以你只需要五分法。
And for some python, I think this should work:
对于一些python，我认为这应该有效：
def countFives(n):
fives = 0
m = 5
while m <= n:
fives = fives + (n/m)
m = m*5
return fives
回答by Amok
The double type has limited precision, so if the numbers you are working with get too big the double will be only an approximation. To work around this you can use something like BigInteger to make it work for arbitrarily large integers.
double 类型的精度有限，因此如果您使用的数字太大，double 将只是一个近似值。要解决此问题，您可以使用 BigInteger 之类的方法使其适用于任意大的整数。
回答by Janusz
You can use a DecimalFormat to format big numbers. If you format your number this way you get the number in scientific notationthen every number will be like 1.4567E7 this will make your work much easier. Because the number after the E - the number of characters behind the . are the number of trailing zeros I think.
您可以使用 DecimalFormat 来格式化大数字。如果您以这种方式格式化您的数字，您将获得以科学记数法表示的数字，那么每个数字都将类似于 1.4567E7，这将使您的工作更加轻松。因为E后面的数字是.后面的字符数。是我认为的尾随零的数量。
I don't know if this is the exact pattern needed. You can see how to form the patterns here
我不知道这是否是所需的确切模式。您可以在此处查看如何形成图案
DecimalFormat formater = new DecimalFormat("0.###E0");
回答by Yordan
This is how I made it, but with bigger > 25 factorial the long capacity is not enough and should be used the class Biginteger, with witch I am not familiar yet:)
我就是这样做的，但是如果大于 25 阶乘，长容量是不够的，应该使用 Biginteger 类，我还不熟悉女巫:)
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
System.out.print("Please enter a number : ");
long number = in.nextLong();
long numFactorial = 1;
for(long i = 1; i <= number; i++) {
numFactorial *= i;
}
long result = 0;
int divider = 5;
for( divider =5; (numFactorial % divider) == 0; divider*=5) {
result += 1;
}
System.out.println("Factorial of n is: " + numFactorial);
System.out.println("The number contains " + result + " zeroes at its end.");
in.close();
}
}
回答by Anushree Acharjee
The best with logarithmic time complexity is the following:
最好的对数时间复杂度如下：
public int trailingZeroes(int n) {
if (n < 0)
return -1;
int count = 0;
for (long i = 5; n / i >= 1; i *= 5) {
count += n / i;
}
return count;
}
shamelessly copied from http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/
无耻地抄自http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/
回答by miguel.angel
I had the same issue to solve in Javascript, and I solved it like:
我在 Javascript 中有同样的问题要解决，我解决了它：
var number = 1000010000;
var str = (number + '').split(''); //convert to string
var i = str.length - 1; // start from the right side of the array
var count = 0; //var where to leave result
for (;i>0 && str[i] === '0';i--){
count++;
}
console.log(count) // console shows 4
This solution gives you the number of trailing zeros.
此解决方案为您提供尾随零的数量。
var number = 1000010000;
var str = (number + '').split(''); //convert to string
var i = str.length - 1; // start from the right side of the array
var count = 0; //var where to leave result
for (;i>0 && str[i] === '0';i--){
count++;
}
console.log(count)回答by dfa
My 2 cents: avoid to work with double since they are error-prone. A better datatype in this case is BigInteger, and here there is a small method that will help you:
我的 2 美分：避免使用 double，因为它们容易出错。在这种情况下，更好的数据类型是 BigInteger，这里有一个小方法可以帮助您：
public class CountTrailingZeroes {
public int countTrailingZeroes(double number) {
return countTrailingZeroes(String.format("%.0f", number));
}
public int countTrailingZeroes(String number) {
int c = 0;
int i = number.length() - 1;
while (number.charAt(i) == '0') {
i--;
c++;
}
return c;
}
@Test
public void 8() {
assertEquals(0, countTrailingZeroes("128"));
}
@Test
public void 0() {
assertEquals(1, countTrailingZeroes("120"));
}
@Test
public void 00() {
assertEquals(2, countTrailingZeroes("1200"));
}
@Test
public void 000() {
assertEquals(3, countTrailingZeroes("12000"));
}
@Test
public void 0000() {
assertEquals(4, countTrailingZeroes("120000"));
}
@Test
public void 2350000() {
assertEquals(4, countTrailingZeroes("102350000"));
}
@Test
public void 23500000() {
assertEquals(5, countTrailingZeroes(1023500000.0));
}
}
回答by Zakmobl
Java's doubles max out at a bit over 9 * 10 ^ 18 where as 25! is 1.5 * 10 ^ 25. If you want to be able to have factorials that high you might want to use BigInteger (similar to BigDecimal but doesn't do decimals).
Java 的双倍最大超过 9 * 10 ^ 18，其中 25！是 1.5 * 10 ^ 25。如果您希望能够拥有那么高的阶乘，您可能需要使用 BigInteger（类似于 BigDecimal 但不做小数）。
回答by Eric Lifka
I wrote this up real quick, I think it solves your problem accurately. I used the BigInteger class to avoid that cast from double to integer, which couldbe causing you problems. I tested it on several large numbers over 25, such as 101, which accurately returned 24 zeros.
我写得很快，我认为它准确地解决了你的问题。我使用 BigInteger 类来避免从双精度转换为整数的转换，这可能会给您带来问题。我在几个超过 25 的大数上对其进行了测试，例如 101，它准确地返回了 24 个零。
The idea behind the method is that if you take 25! then the first calculation is 25 * 24 = 600, so you can knock two zeros off immediately and then do 6 * 23 = 138. So it calculates the factorial removing zeros as it goes.
该方法背后的想法是，如果你拿 25！那么第一次计算是 25 * 24 = 600，所以你可以立即敲掉两个零，然后做 6 * 23 = 138。所以它会计算去除零的阶乘。
public static int count(int number) {
final BigInteger zero = new BigInteger("0");
final BigInteger ten = new BigInteger("10");
int zeroCount = 0;
BigInteger mult = new BigInteger("1");
while (number > 0) {
mult = mult.multiply(new BigInteger(Integer.toString(number)));
while (mult.mod(ten).compareTo(zero) == 0){
mult = mult.divide(ten);
zeroCount += 1;
}
number -= 1;
}
return zeroCount;
}
Since you said you don't care about run time at all (not that my first was particularly efficient, just slightly more so) this one just does the factorial and then counts the zeros, so it's cenceptually simpler:
因为你说你根本不关心运行时间（不是说我的第一个特别有效，只是稍微多一点）这个只是做阶乘然后计算零，所以它在概念上更简单：
public static BigInteger factorial(int number) {
BigInteger ans = new BigInteger("1");
while (number > 0) {
ans = ans.multiply(new BigInteger(Integer.toString(number)));
number -= 1;
}
return ans;
}
public static int countZeros(int number) {
final BigInteger zero = new BigInteger("0");
final BigInteger ten = new BigInteger("10");
BigInteger fact = factorial(number);
int zeroCount = 0;
while (fact.mod(ten).compareTo(zero) == 0){
fact = fact.divide(ten);
zeroCount += 1;
}
}
