ได้รับจำนวนเต็ม num เป็นอินพุต เป้าหมายคือหาจำนวนศูนย์นำหน้าในผลคูณ 11 × 22 × 33 × ... × numnum
ตัวอย่าง
Input
num=5
Output
Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5
Explanation
The number of 2s and 5s in the product will be: 1^1 * 2^2* 3^3* 4^4* 5^5=1^1 * 2^2* 3^3* (2^2)^4* 5^5. So total 10 2s and 5 5s, minimum is 5 so trailing zeroes will be 5.
Input
num=10
Output
Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 15
Explanation
The number of 2s and 5s in the product will be: 1^1 *2^2*3^3*4^4*5^5*6^6 *7^7*8^8*9^9*10^10 = 1^1 *2^2*3^3*4^4*5^5*6^6 *7^7*8^8*9^9*(2*5)^10. So total 20 2s and 15 5s, minimum is 15 so trailing zeroes will be 15.
วิธีการที่ใช้ในโปรแกรม
วิธีนี้นับจำนวน 2 และ 5 ในการแยกตัวประกอบเฉพาะของแต่ละตัวเลขในผลคูณ เนื่องจากแต่ละตัวเลขยกกำลังด้วยตัวมันเอง จำนวนน้อยที่สุดระหว่างจำนวน 2 และ 5 จะให้จำนวนศูนย์นำหน้า เพราะแต่ละคู่ 2×5 เพิ่มศูนย์หนึ่งตัวในผลคูณ
- รับจำนวนเต็ม
numเป็นอินพุต - ฟังก์ชัน
count_trailing(int num)คืนค่าจำนวนศูนย์นำหน้า - กำหนดจำนวนนับเริ่มต้นเป็น 0
- ตัวแปร
temp_2 = 0,temp_5 = 0สำหรับนับ 2 และ 5 - วนลูป i=1 ถึง num
- เก็บ
temp = i - while temp หาร 2 ลงตัว ลด temp เหลือครึ่ง และบวก i เข้า
temp_2 - while temp หาร 5 ลงตัว หาร temp ด้วย 5 และบวก i เข้า
temp_5 - กำหนด
count = min(temp_2, temp_5) - คืนค่า count เป็นผลลัพธ์
ตัวอย่างโค้ด
#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;
}
Output
หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:
Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5
