Cho một số nguyên làm đầu vào. Mục đích là để tìm số lượng các số 0 ở cuối trong giai thừa được tính cho số đó. Giai thừa của số N là tích của tất cả các số trong phạm vi [1, N].
Chúng ta biết rằng chúng ta chỉ nhận được số 0 ở cuối nếu số đó là bội số của 10 hoặc có một cặp thừa số (2,5). Trong tất cả các thừa số của bất kỳ số nào lớn hơn 5, chúng ta có một số lớn hơn 2s hơn 5 trong phép thừa số nguyên tố của số đó. Chia một số cho lũy thừa của 5 sẽ cho chúng ta số lượng là 5 trong các thừa số của nó. Vì vậy, số 5 sẽ cho chúng ta biết số lượng các số 0 ở cuối.
Ví dụ
Đầu vào
number=6
Đầu ra
Count of trailing zeros in factorial of a number are: 1
Giải thích
The factorial is 30. Prime factors of 30 : 2 * 3 * 5 So only one pair of (2,5) exists so trailing zeros is 1.
Đầu vào
number=12
Đầu ra
Count of trailing zeros in factorial of a number are: 2
Giải thích
The factorial is 479001600. Prime factors of 479001600 : 210 x 35 x 52 x 71 x 111 So we can get 2 pairs of (2,5) so trailing zeros are 2
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng ta sẽ chia số cho lũy thừa của 5. Nếu nó dẫn đến nhiều hơn 1 thì số không ở cuối sẽ là số của 5. Thêm cái này để đếm.
-
Lấy một số nguyên làm đầu vào.
-
Hàm trailing_zeros (int number) nhận số và trả về số lượng các số 0 ở cuối theo giai thừa của số.
-
Lấy số lượng ban đầu là 0.
-
Sử dụng vòng lặp for, chia số cho lũy thừa của 5.
-
Nếu số / i lớn hơn 1, hãy thêm giá trị này để đếm.
-
Kết quả trả về là kết quả ở cuối vòng lặp.
Ví dụ
#include <iostream>
using namespace std;
int trailing_zeros(int number){
int count = 0;
for (int i = 5; number / i >= 1; i *= 5){
int temp = number / i;
count = count + temp;
}
return count;
}
int main(){
int number = 50;
cout<<"Count of trailing zeros in factorial of a number are: "<<trailing_zeros(number);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of trailing zeros in factorial of a number are: 12