数据结构
网络
关系数据库管理系统 (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 次查看
