คำอธิบายปัญหา
ที่นี่เราจะดูวิธีคำนวณจำนวนศูนย์ต่อท้าย (trailing zeros) ของผลลัพธ์แฟกทอเรียลของจำนวนใดๆ เช่นถ้า n = 5 แล้ว 5! = 120 มีศูนย์ต่อท้ายเพียง 1 ตัว สำหรับ 20! จะเป็น 4 ศูนย์ เพราะ 20! = 2432902008176640000
วิธีที่ง่ายที่สุดคือคำนวณแฟกทอเรียลแล้วนับศูนย์ แต่วิธีนี้ล้มเหลวสำหรับค่า n ที่ใหญ่ ดังนั้นเราจะใช้วิธีอื่น ศูนย์ต่อท้ายจะเกิดขึ้นถ้าตัวประกอบเฉพาะเป็น 2 และ 5 ถ้านับจำนวน 2 และ 5 เราจะได้ผลลัพธ์ สำหรับนั้น เราจะปฏิบัติตามกติกานี้:
Trailing 0s = จำนวน 5 ในตัวประกอบเฉพาะของ factorial(n)
ดังนั้น Trailing 0s = $$\lvert\frac{n}{5}\rvert+\lvert\frac{n}{25}\rvert+\lvert\frac{n}{125}\rvert+...$$
เพื่อแก้ปัญหานี้ เราต้องทำตามขั้นตอนเหล่านี้:
- ตั้งค่า count = 0
- for i = 5, (n/i) > 1, อัปเดต i = i * 5, ทำ
- count = count + (n / i)
- คืนค่า count
ตัวอย่างโค้ด (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); }นำเข้า
Number of trailing zeroes: 20
ผลลัพธ์
Number of trailing zeros: 4
