Ở đây chúng ta sẽ xem cách tính số chữ số 0 ở cuối cho kết quả giai thừa của một số bất kỳ. Vì vậy, nếu n =5, thì 5! =120. Chỉ có một dấu 0. Cho 20! nó sẽ là 4 số không là 20! =2432902008176640000.
Cách tiếp cận đơn giản nhất là chỉ tính giai thừa và đếm các số 0. Nhưng cách tiếp cận này không thành công đối với giá trị lớn của n. Vì vậy, chúng tôi sẽ làm theo một cách tiếp cận khác. Các số không ở cuối sẽ ở đó nếu thừa số nguyên tố là 2 và 5. Nếu chúng ta đếm 2s và 5s, chúng ta có thể nhận được kết quả. Vì vậy, chúng tôi sẽ tuân theo quy tắc này.
Số 0 ở sau =Đếm 5 5 trong các thừa số nguyên tố của giai thừa (n)
vì vậy Dấu vết 0s =$$ \ lvert \ frac {n} {5} \ rvert + \ lvert \ frac {n} {25} \ rvert + \ lvert \ frac {n} {125} \ rvert + ... $$
Để giải quyết vấn đề này, chúng ta phải làm theo các bước sau -
- bộ đếm =0
- cho i =5, (n / i)> 1, cập nhật i =i * 5, thực hiện
- count =count + (n / i)
- số lượng trả lại
Ví dụ (C ++)
#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;
int countTrailingZeros(int n) {
int count = 0;
for (int i = 5; n / i >= 1; i *= 5)
count += n / i;
return count;
}
main() {
int n = 20;
cout << "Number of trailing zeros: " << countTrailingZeros(n);
} Đầu vào
Number of trailing zeroes: 20
Đầu ra
Number of trailing zeros: 4