資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學階乘末尾有 n 個零的數
一個數的階乘是所有正整數直到該數的乘積。例如，5 的階乘表示為 5!，等於所有正整數直到 5 的乘積。
5! = 5 x 4 x 3 x 2 x 1 = 120
一個數的階乘的十進位制表示中末尾零的個數稱為階乘中的“尾隨零”。例如，5 的階乘是 120，它有一個尾隨零，而 10 的階乘是 3,628,800，它有兩個尾隨零。
問題陳述
給定一個整數 n，我們必須確定階乘具有 n 個尾隨零的正整數的個數。
示例
輸入
n = 1
輸出
5 6 7 8 9
解釋
5! = 120
6!= 720
7! = 5040
8! = 40320
9! = 362880
可以觀察到，所有輸出數字的階乘都有 n 個尾隨零，即一個尾隨零。
輸入
n = 2
輸出
10 11 12 13 14
解釋
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
可以觀察到，所有輸出數字的階乘都有 n 個尾隨零，即兩個尾隨零。
輸入
n = 5
輸出
No Output
解釋
25! = 15511210043330985984000000 有 6 個尾隨零。
階乘中恰好有 5 個尾隨零的數字在其素數分解中將有 5 個因子 5，但不會有額外的因子 5。然而，素數分解中具有 5 個因子 5 的最小數字是 25!，其階乘中有 6 個零。
樸素解法
我們簡單地迭代一系列整數（1 到 106）。對於每個數字，我們檢查其階乘中零的個數是否等於給定的數字 n。如果是，我們將其新增到 ans 向量中。如果階乘中的尾隨零個數超過給定的數字 n，我們中斷迴圈。
這種方法不適用於較大的數字，因為會發生溢位。
演算法
階乘函式 factorial(n)
Initialize fact = 1 for i = 2 to n: fact = fact * i return fact
尾隨零計數函式 count_trailing_zeros(num)
Initialize count = 0
while num % 10 = 0:
count = count + 1
num = num / 10
return count
查詢具有 n 個尾隨零的數字函式 find_numbers_with_n_trailing_zeros(n)
Initialize ans = empty vector
for i = 1 to 1e6:
a = count_trailing_zeros(factorial(i))
if a = n:
ans.push_back(i)
else if a > n:
break
if size of ans = 0:
print "No Output"
else:
for x in ans:
print x
時間和空間複雜度分析
時間複雜度：O(n*log n)
這段程式碼的時間複雜度為 O(n*log n)，因為 factorial() 函式的時間複雜度為 O(n)，並且在 for 迴圈中為 n 個值呼叫它，導致總時間複雜度為 O(n^2)。但是，如果尾隨零的個數超過輸入值 n，則迴圈會提前中斷，這會大大減少迭代次數。
空間複雜度：O(n)
空間複雜度為 O(n)，因為程式使用向量來儲存結果。
最佳化方法
該技術尋找階乘中具有指定數量尾隨零的所有數字。我們使用二分查詢策略來找到具有指定數量尾隨零的第一個數字，然後迭代所有後續具有相同數量尾隨零的數字，直到找到一個沒有 'n' 個尾隨零的數字。
此方法包括以下步驟
定義一個函式 count_trailing_zeros()，它接受一個整數 num 並返回 num 階乘中尾隨零的個數。
定義一個函式 find_numbers_with_n_trailing_zeros()，它接受一個整數 n 作為輸入並返回一個整數向量，這些整數的階乘具有 n 個尾隨零。
使用二分查詢找到第一個具有 n 個尾隨零的數字。
將開始後所有具有 n 個尾隨零的數字推入 ans。
返回 ans。
演算法
計算給定階乘數 (num) 尾隨零的函式
count = 0
while num > 0:
num = num / 5
count += num
return count
查詢具有 n 個尾隨零 (n) 的數字的函式
start = 0
end = maximum integer value
while start < end:
mid = (start + end) / 2
count = count_trailing_zeros(mid)
if count < n:
start = mid + 1
else:
end = mid
ans = empty vector
while count_trailing_zeros(start) == n:
ans.push_back(start)
start++
return ans
列印向量 (ans) 的函式
for i = 0 to ans.size(): print ans[i] + " "
主函式
n = 3 result = find_numbers_with_n_trailing_zeros(n) print(result)
示例：C++ 程式
在下面的程式中，為了返回階乘具有 'n' 個尾隨零的數字，我們使用二分查詢和素數因子的概念。其思想是考慮階乘 n 的素數因子。尾隨零總是由素數因子 2 和 5 產生的。可以很容易地觀察到，素數因子中 2 的個數總是大於或等於 5 的個數。因此，如果我們計算素數因子中 5 的個數，我們可以找出尾隨零的個數。然後，我們使用二分查詢來確定階乘中具有 'n' 個尾隨零的數字。
// C++ program to find numbers which have ‘n’ trailing zeros in their factorial
#include <bits/stdc++.h>
using namespace std;
// function to count trailing zeros of the given factorial number
int count_trailing_zeros(int num){
int count = 0;
while (num > 0){
num /= 5;
count += num;
}
return count;
}
// function to find the number which have n trailing zeros
vector<int> find_numbers_with_n_trailing_zeros(int n){
int start = 0;
int end = INT_MAX;
// binary search for first number with n trailing zeros
while (start < end){
int mid = (start + end) / 2;
int count = count_trailing_zeros(mid);
if (count < n)
start = mid + 1;
else
end = mid;
}
// push all numbers after low with n trailing zeros.
vector<int> ans;
while (count_trailing_zeros(start) == n){
ans.push_back(start);
start++;
}
return ans;
}
void print(vector<int> &ans){
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
}
// driver function
int main(){
int n = 3;
vector<int> result = find_numbers_with_n_trailing_zeros(n);
print(result);
return 0;
}
輸出
15 16 17 18 19
時間和空間複雜度分析
時間複雜度：O(n)
程式碼的時間複雜度為 O(log n)，因為它使用二分查詢來找到第一個具有 n 個尾隨零的數字，這在每次迭代中都會將搜尋空間減半。
空間複雜度：O(m)
空間複雜度為 O(m)，其中 m 是具有 n 個尾隨零的數字的數量，因為程式將所有這些數字儲存在向量中。
結論
本文討論了兩種查詢階乘末尾有 n 個零的數字的方法。為了更深入地理解，對這些方法的概念、示例、使用的演算法、C++ 程式解決方案以及時間和空間複雜度分析進行了徹底的解釋。
270 次檢視
