ในบทความนี้ เราจะเข้าใจปัญหาในการค้นหาเลขศูนย์ต่อท้ายของตัวเลขที่ระบุ N ในการแทนค่าแฟกทอเรียลในฐาน 16 เป็นต้น
Input : N = 7 Output : 1 Explanation : fact(7) = 5040 in base10 and 13B0 in base16 having 1 trailing zero. Input : N = 11 Output : 2 Explanation : fact(11) = 39916800 in base10 and 2611500 in base16 having 2 trailing zeroes.
เรามาสรุปขั้นตอนการแปลงเลขฐานสิบจากฐานหนึ่งเป็นฐานอื่นกันก่อน มาดูตัวอย่างการแปลง (5040)10 เป็น (?)16
คือ หารเลขด้วย 16 แล้วเหลือเศษไว้จนหารเลขไม่ได้อีก ผลลัพธ์จะเป็นส่วนที่เหลือในลำดับที่กลับกัน
เป็นผลให้เรามีศูนย์ต่อท้ายหนึ่งตัว และศูนย์ต่อท้ายนี้เราได้เมื่อ 16 หารตัวเลขด้วยเศษ 0
การแยกตัวประกอบเฉพาะของ 5040 =161 * 451* 71 ซึ่งหมายถึง 16 หาร 5040 1 ครั้งด้วยเศษ 0 เท่ากับศูนย์ตามหลัง ด้วยวิธีนี้ เราสามารถคำนวณจำนวนศูนย์ต่อท้ายได้
แนวทางในการหาทางออก
เราได้กล่าวถึงวิธีการหาจำนวนศูนย์ต่อท้าย เรายังรู้ 16 =24 ซึ่งหมายความว่ากำลังสูงสุด 2 ใน N หารด้วยสี่จะเท่ากับกำลังสูงสุดของ 16 ซึ่งเรียกอีกอย่างว่าสูตรของ Legendre
โค้ด 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 has the highest power of 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
คำอธิบายของโค้ดด้านบน
- เรากำลังเริ่มต้นกำลังด้วยสองกำลังเนื่องจากเราต้องคำนวณกำลังสูงสุด 2
- การนำสูตรของ Legendre ไปใช้ในชั่วขณะหนึ่ง โดยที่เราหาร n ด้วยกำลัง ซึ่งเท่ากับ 2 ในตอนแรก และนับเพิ่มขึ้นด้วยค่าและกำลังด้วย 2
- หลังจากแบ่งกำลังสูงสุดของ 2 กับ 4 ซึ่งเก็บไว้ในตัวแปรการนับ
- ในที่สุดเราก็พิมพ์ผลออกมาได้
บทสรุป
ในบทความนี้ เราแก้ปัญหาการหาจำนวนเลขศูนย์ต่อท้ายในการแทนค่าแฟกทอเรียล N ฐาน 16 ซึ่งเราแก้โดยใช้สูตรของ Legendre เรายังเขียนโค้ด C++ เพื่อแก้ปัญหาเดียวกัน คุณสามารถเขียนโค้ดนี้ในภาษาอื่นๆ เช่น Java, C, python เป็นต้น เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
