กำหนดจำนวนเต็มเป็นอินพุต เป้าหมายคือการหาจำนวนศูนย์ต่อท้ายในแฟกทอเรียลที่คำนวณสำหรับตัวเลขนั้น แฟกทอเรียลของจำนวน N คือผลคูณของจำนวนทั้งหมดในช่วง [1, N]
เรารู้ว่าเราจะได้ศูนย์ต่อท้ายก็ต่อเมื่อตัวเลขนั้นทวีคูณของ 10 หรือมีคู่ตัวประกอบ (2,5) ในแฟกทอเรียลทั้งหมดของจำนวนใดๆ ที่มากกว่า 5 เรามีจำนวน 2s ที่มากกว่า 5s ในการแยกตัวประกอบเฉพาะของจำนวนนั้น การหารจำนวนด้วยยกกำลัง 5 จะทำให้เรานับ 5s ในตัวประกอบของมัน ดังนั้นจำนวน 5 วินาทีจะบอกเราถึงจำนวนศูนย์ต่อท้าย
ตัวอย่าง
อินพุต
number=6
ผลลัพธ์
Count of trailing zeros in factorial of a number are: 1
คำอธิบาย
The factorial is 30. Prime factors of 30 : 2 * 3 * 5 So only one pair of (2,5) exists so trailing zeros is 1.
อินพุต
number=12
ผลลัพธ์
Count of trailing zeros in factorial of a number are: 2
คำอธิบาย
The factorial is 479001600. Prime factors of 479001600 : 210 x 35 x 52 x 71 x 111 So we can get 2 pairs of (2,5) so trailing zeros are 2
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
ในแนวทางนี้ เราจะหารตัวเลขด้วยยกกำลัง 5 หากผลลัพธ์ออกมามากกว่า 1 ตัวเลขของศูนย์ต่อท้ายจะเป็นจำนวน 5s เพิ่มสิ่งนี้เพื่อนับ
-
ใช้ตัวเลขจำนวนเต็มเป็นอินพุต
-
ฟังก์ชัน trailing_zeros(int number) รับค่าตัวเลขและคืนค่าจำนวนศูนย์ต่อท้ายในแฟกทอเรียลของตัวเลข
-
นับเริ่มต้นเป็น 0
-
ใช้ for loop หารเลขยกกำลัง 5
-
ถ้า number/i มากกว่า 1 ให้เพิ่มค่านี้เพื่อนับ
-
นับกลับเป็นผลเมื่อสิ้นสุดการวนซ้ำ
ตัวอย่าง
#include <iostream>
using namespace std;
int trailing_zeros(int number){
int count = 0;
for (int i = 5; number / i >= 1; i *= 5){
int temp = number / i;
count = count + temp;
}
return count;
}
int main(){
int number = 50;
cout<<"Count of trailing zeros in factorial of a number are: "<<trailing_zeros(number);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of trailing zeros in factorial of a number are: 12
