ในบทความนี้ เราจะเข้าใจปัญหาการหาจำนวนศูนย์ต่อท้ายของจำนวน N ในการแทนค่าแฟกทอเรียล (N!) ในฐาน 16 เช่น
Input : N = 7 Output : 1 Explanation : fact(7) = 5040 ในฐาน 10 และ 13B0 ในฐาน 16 มี 1 ศูนย์ต่อท้าย Input : N = 11 Output : 2 Explanation : fact(11) = 39916800 ในฐาน 10 และ 2611500 ในฐาน 16 มี 2 ศูนย์ต่อท้าย
ทบทวนการแปลงเลขฐานสิบไปฐานอื่น เช่น แปลง (5040)10 เป็น (?)16
คือการหารด้วย 16 และเก็บเศษจนกว่าจะหารไม่ลง ผลลัพธ์คือเศษเรียงจากหลังมาหน้า
ได้ 1 ศูนย์ต่อท้าย ซึ่งเกิดเมื่อ 16 หารจำนวนลงตัว
การแยกตัวประกอบเฉพาะของ 5040 = 16¹ × 451 × 7¹ หมายความว่า 16 หาร 5040 ลงตัว 1 ครั้ง เท่ากับจำนวนศูนย์ต่อท้าย
วิธีการแก้ปัญหา
เรารู้ว่า 16 = 2⁴ ดังนั้นกำลังสูงสุดของ 2 ใน N หาร 4 จะได้กำลังสูงสุดของ 16 ซึ่งเป็นสูตรของเลจองดร (Legendre's Formula)
โค้ด C++ สำหรับวิธีการข้างต้น
นี่คือโค้ด C++ ที่ใช้แก้ปัญหานี้
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main () {
int n = 11;
long long int count = 0;
long long int value, power = 2;
long long int result;
do{
value = n / power;
count += value;
power *= 2;
} while (value != 0);
// count เก็บกำลังสูงสุดของ 2
result = count / 4;
cout << "Number of trailing zeroes in base 16 representation of N : " << result;
}
ผลลัพธ์
Number of trailing zeroes in base 16 representation of N: 2
คำอธิบายโค้ด
- เริ่มต้น power = 2 เพราะต้องหากำลังสูงสุดของ 2
- ใช้สูตรเลจองดรในลูป while: หาร n ด้วย power (เริ่มต้น 2) บวกเข้า count แล้วคูณ power ด้วย 2
- หลังลูปจบ count จะมีกำลังสูงสุดของ 2 แล้วหาร 4 ได้คำตอบ
- พิมพ์ผลลัพธ์
สรุป
ในบทความนี้ เราแก้ปัญหาการหาจำนวนศูนย์ต่อท้ายในฐาน 16 ของ N! โดยใช้สูตรของเลจองดร เรายังเขียนโค้ด C++ เพื่อแก้ปัญหานี้ สามารถนำไปใช้กับภาษาอื่น เช่น Java, C, Python ได้ หวังว่าจะเป็นประโยชน์
