Đếm số không theo sau của các số kết quả từ giai thừa

Question

Tôi đang cố gắng đếm số không theo số được tạo thành từ giai thừa (có nghĩa là các con số nhận được khá lớn). Mã sau có một số, tính giai thừa của số và đếm số không theo sau. Tuy nhiên, khi số lượng lớn khoảng 25 !, numZeros không hoạt động.

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

Tôi không lo lắng về hiệu quả của mã này và tôi biết rằng có nhiều cách để làm cho hiệu quả của mã này TỐT HƠN. Những gì tôi đang cố gắng tìm ra là lý do tại sao đếm số 0 của các con số lớn hơn 25! không hoạt động.

Bất kỳ ý tưởng nào?

Answer 1

Nhiệm vụ của bạn là không để tính giai thừa nhưng số zero. Giải pháp tốt sử dụng công thức từ http://en.wikipedia.org/wiki/Trailing_zeros (bạn có thể thử chứng minh)

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 

Hy vọng bạn có thể dịch điều này sang Java. Điều này chỉ đơn giản là tính [n/5] + [n/25] + [n/125] + [n/625] + ... và dừng khi số chia lớn hơn n.

KHÔNG sử dụng BigIntegers. Đây là một bozosort. Các giải pháp như vậy đòi hỏi thời gian cho số lượng lớn.

Answer 2

Bạn chỉ thực sự cần biết có bao nhiêu 2s và 5s có ​​trong sản phẩm. Nếu bạn đếm số 0 theo sau, thì bạn thực sự đếm "Số lần mười chia số này?". nếu bạn đại diện cho n! như q * (2^a) * (5^b) trong đó q không chia hết cho 2 hoặc 5. Sau đó, chỉ lấy tối thiểu a và b trong biểu thức thứ hai sẽ cho bạn biết số lần 10 chia số. Trên thực tế làm phép nhân là quá mức cần thiết.

Chỉnh sửa: Đếm số twos cũng quá mức cần thiết, vì vậy bạn chỉ thực sự cần các fives.

Và đối với một số trăn, tôi nghĩ rằng điều này sẽ làm việc:

def countFives(n): 
    fives = 0 
    m = 5 
    while m <= n: 
     fives = fives + (n/m) 
     m = m*5 
    return fives 

Answer 3

Bạn có thể sử dụng một DecimalFormat để định dạng số lớn. Nếu bạn định dạng số của mình theo cách này, bạn sẽ nhận được số trong scientific notation thì mọi số sẽ giống như 1.4567E7 điều này sẽ giúp công việc của bạn dễ dàng hơn nhiều. Bởi vì số sau E - số ký tự đằng sau. là số lượng số không theo đuôi tôi nghĩ.

Tôi không biết đây có phải là mẫu chính xác cần thiết hay không. Bạn có thể xem làm thế nào để hình thành mô hình here

DecimalFormat formater = new DecimalFormat("0.###E0"); 

Answer 4

Loại đôi đã hạn chế độ chính xác, vì vậy nếu các số bạn đang làm việc với nhận được quá lớn đôi sẽ chỉ là gần đúng. Để làm việc này, bạn có thể sử dụng một cái gì đó như BigInteger để làm cho nó hoạt động cho các số nguyên lớn tùy ý.

Answer 5

Tăng gấp đôi tối đa của Java ở mức trên 9 * 10^18 ở mức 25! là 1,5 * 10^25. Nếu bạn muốn có thể có giai thừa cao bạn có thể muốn sử dụng BigInteger (tương tự như BigDecimal nhưng không làm số thập phân).

Answer 6

Tôi đã viết điều này thật nhanh, tôi nghĩ nó giải quyết vấn đề của bạn một cách chính xác. Tôi đã sử dụng lớp BigInteger để tránh việc truyền từ hai đến số nguyên, trong đó có thể đang gây ra sự cố cho bạn. Tôi đã thử nghiệm nó trên một số lớn hơn 25, chẳng hạn như 101, mà chính xác trở lại 24 số không.

Ý tưởng đằng sau phương pháp là nếu bạn lấy 25! sau đó phép tính đầu tiên là 25 * 24 = 600, vì vậy bạn có thể gõ hai số 0 ngay lập tức và sau đó thực hiện 6 * 23 = 138. Vì vậy, nó tính toán số 0 thừa nhận khi nó đi.

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

Vì bạn nói rằng bạn không quan tâm đến thời gian chạy ở tất cả (không phải là đầu tiên của tôi là đặc biệt hiệu quả, chỉ cần một chút nhiều hơn như vậy) cái này chỉ làm giai thừa và sau đó đếm số không, do đó, nó cenceptually đơn giản hơn :

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

Answer 7

2 xu của tôi: tránh làm việc gấp đôi vì chúng dễ bị lỗi. Một datatype tốt hơn trong trường hợp này là BigInteger, và ở đây có một phương pháp nhỏ sẽ giúp bạn:

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

Answer 8

Đây là cách tôi đã làm cho nó, nhưng với lớn hơn> 25 thừa công suất dài là không đủ và cần được sử dụng lớp BigInteger, với phù thủy Tôi không quen chưa :)

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(); 

} 

} 

Answer 9

tốt nhất với logarit thời gian phức tạp như sau:

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

không biết xấu hổ sao chép từ http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/

Answer 10

tôi đã cùng một vấn đề để giải quyết trong Javascript, và tôi s olved it like:

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 

Giải pháp này cung cấp cho bạn số lượng dấu sau.

var number = 1000010000; 
 
var str = (number + '').split(''); //convert to string 
 
var i = str.length - 1; // start from the right side of the \t array 
 
var count = 0; //var where to leave result 
 
for (;i>0 && str[i] === '0';i--){ 
 
\t count++; 
 
} 
 
console.log(count)