Cho một số nguyên làm đầu vào. Mục tiêu là tìm số lượng các số 0 ở cuối trong tích 11 X 22 X 33 X… X num num .
Ví dụ
Đầu vào
num=5
Đầu ra
Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5
Giải thích
The number of 2s and 5s in the product will be: 11 * 22* 33* 44* 55=11 * 22* 33* (22)4* 55. So total 10 2s and 5 5s, minimum is 5 so trailing zeroes will be 5.
Đầu vào
num=10
Đầu ra
Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5
Giải thích
The number of 2s and 5s in the product will be: 11 *22*33*44*55*66 *77*88*99*1010 = 11 *22*33*44*55*66 *77*88*99*(2*5)10. So total 20 2s and 15 5s, minimum is 15 so trailing zeroes will be 15.
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ẽ đếm số 2 và 5 theo thừa số nguyên tố của mỗi số trong tích. Khi mỗi số được nâng lên thành lũy thừa của chính nó, số đếm tối thiểu là 2s hoặc 5 trong quá trình phân tích nhân tử sẽ cho số lượng các số 0 ở cuối. Khi mỗi 2 * 5 thêm một số 0 trong sản phẩm.
-
Lấy một số nguyên làm đầu vào.
-
Hàm count_trailing (int num) nhận num và trả về số lượng các số không chuyển tiếp trong (1 ^ 1) * (2 ^ 2) * (3 ^ 3) * (4 ^ 4) * .....
-
Lấy số lượng ban đầu là 0.
-
Lấy các biến temp_2 =0, temp_5 =0 cho số đếm là 2 giây và 5 giây.
-
Di chuyển bằng cách sử dụng các vòng lặp for từ i =1 đến i <=num.
-
Hãy tạm thời như tôi.
-
Trong khi nhiệt độ chia hết cho 2, sau đó giảm nó xuống một nửa và thêm i để đếm temp_2 là số 2.
-
Trong khi tạm thời chia hết cho 5 thì chia cho 5 và thêm i để đếm temp_5 là số 5s.
-
Lấy số đếm tối thiểu là hai số bằng cách sử dụng count =min (temp_2, temp_5).
-
Kết quả là số lượt trả lại.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int count_trailing(int num){
int count = 0;
int temp_2 = 0;
int temp_5 = 0;
for (int i = 1; i <= num; i++){
int temp = i;
while(temp % 2 == 0 && temp > 0){
temp = temp / 2;
temp_2 = temp_2 + i;
}
while (temp % 5 == 0 && temp > 0){
temp = temp / 5;
temp_5 = temp_5+ i;
}
}
count = min(temp_2, temp_5);
return count;
}
int main(){
int num = 5;
cout<<"Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: "<<count_trailing(num);
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 number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5