计算数字的尾随零是由因子计算的
我试图计算由阶乘产生的数字的尾随零（意味着数字变得非常大）。 下面的代码取一个数字，计算数字的阶乘，并计算尾随零。 但是，当数量大约为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; } 我并不担心这段代码的效率，我知道有很多方法可以提高这段代码的效率。 我想弄清楚的是为什么计数尾随的数字大于25！ 不管用。
有任何想法吗？
您的任务不是计算阶乘而是计算零的数量。 一个好的解决方案使用http://en.wikipedia.org/wiki/Trailing_zeros中的公式（您可以尝试certificate）
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
希望你能把它翻译成Java。 这只是计算[n / 5] + [n / 25] + [n / 125] + [n / 625] + …并在除数大于n时停止。
不要使用BigIntegers。 这是一个bozosort。 这种解决方案需要几秒钟才能获得大量数据。
您只需知道产品中有多少2和5。 如果你正在计算尾随零，那么你实际上是在计算“十次除以这个数字的次数是多少？”。 如果你代表n！ 作为q *（2 ^ a）*（5 ^ b）其中q不能被2或5整除。然后在第二个表达式中取a和b的最小值将给出10次除数的次数。 实际上做乘法是过度的。
编辑：计算两个也是矫枉过正，所以你只需要五个人。
对于一些python，我认为这应该工作：
def countFives(n): fives = 0 m = 5 while m <= n: fives = fives + (n/m) m = m*5 return fives
double类型的精度有限，因此如果您使用的数字太大，则double将只是近似值。 要解决这个问题，你可以使用像BigInteger这样的东西来使它适用于任意大的整数。
您可以使用DecimalFormat格式化大数字。 如果您通过这种方式格式化数字，那么您可以使用科学计数法获得数字，那么每个数字都会像1.4567E7一样，这将使您的工作变得更加容易。 因为E之后的数字 – 后面的字符数。 是我认为的尾随零的数量。
我不知道这是否是所需的确切模式。 您可以在此处查看如何形成模式
DecimalFormat formater = new DecimalFormat("0.###E0");
我的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 $128() { assertEquals(0, countTrailingZeroes("128")); } @Test public void $120() { assertEquals(1, countTrailingZeroes("120")); } @Test public void $1200() { assertEquals(2, countTrailingZeroes("1200")); } @Test public void $12000() { assertEquals(3, countTrailingZeroes("12000")); } @Test public void $120000() { assertEquals(4, countTrailingZeroes("120000")); } @Test public void $102350000() { assertEquals(4, countTrailingZeroes("102350000")); } @Test public void $1023500000() { assertEquals(5, countTrailingZeroes(1023500000.0)); } }
这就是我制作它的方式，但是如果大于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(); } }
具有对数时间复杂度的最佳方法如下：
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; }
无耻地从http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/复制
我在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
此解决方案为您提供尾随零的数量。
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)
Java的双倍最大值超过9 * 10 ^ 18，其中25！ 是1.5 * 10 ^ 25.如果你想能够使用高阶因子，你可能想要使用BigInteger（类似于BigDecimal但不做小数）。
我写得很快，我认为它可以准确地解决你的问题。 我使用BigInteger类来避免从double转换为整数，这可能会导致问题。 我在超过25的几个大数字上测试了它，例如101，它准确地返回了24个零。
该方法背后的想法是，如果你采取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; }
既然你说你根本不关心运行时间（不是我的第一次特别高效，只是稍微多一些），这个只做了阶乘，然后计算零，所以它在理论上更简单：
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; } }