* @详细说明* 给定一个整数作为输入。目标是找出该数的阶乘结果中末尾零的数量。
一个数 N 的阶乘是范围 [1, N] 内所有数的乘积。* * 我们知道，只有当一个数是 10 的倍数或者有因数对 (2, 5) 时，才会产生末尾零。
在任何大于 5 的数的阶乘中，该数的质因数分解里 2 的数量比 5 的数量多很多。
用一个数除以 5 的幂可以得到其因数中 5 的个数。所以，5 的个数就代表了末尾零的数量。
#include <cassert> /// 用于断言
#include <iostream> /// 用于输入输出操作/*** @命名空间 bit_manipulation* @brief 位操作算法*/
namespace bit_manipulation {/*** @命名空间 count_of_trailing_ciphers_in_factorial_n* @brief 用于实现 [计算 n! 中末尾零的数量](https://www.tutorialspoint.com/count-trailing-zeros-in-factorial-of-a-number-in-cplusplus) 的函数*/namespace count_of_trailing_ciphers_in_factorial_n {/*** @brief 计算阶乘末尾零的数量的函数* @param n 要计算其阶乘末尾零数量的数* @return count，n! 中末尾零的数量*/uint64_t numberOfCiphersInFactorialN(uint64_t n) {// count 用于存储 n! 中 5 的个数uint64_t count = 0;// 不断用 n 除以 5 的幂并更新 countfor (uint64_t i = 5; n / i >= 1; i *= 5) {count += static_cast<uint64_t>(n) / i;}return count;}} // 命名空间 count_of_trailing_ciphers_in_factorial_n
} // 命名空间 bit_manipulation/*** @brief 自测实现* @returns 无*/
static void test() {// 第一个测试std::cout << "第一个测试 ";assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::numberOfCiphersInFactorialN(395) == 97);std::cout << "通过" << std::endl;// 第二个测试std::cout << "第二个测试 ";assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::numberOfCiphersInFactorialN(977) == 242);std::cout << "通过" << std::endl;// 第三个测试std::cout << "第三个测试 ";assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::numberOfCiphersInFactorialN(871) == 215);std::cout << "通过" << std::endl;// 第四个测试std::cout << "第四个测试 ";assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::numberOfCiphersInFactorialN(239) == 57);std::cout << "通过" << std::endl;// 第五个测试std::cout << "第五个测试 ";assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::numberOfCiphersInFactorialN(0) == 0);std::cout << "通过" << std::endl;
}/*** @brief 主函数* @returns 程序退出时返回 0*/
int main() {test(); // 运行自测实现return 0;
}
代码解释
-
numberOfCiphersInFactorialN 函数：
- 该函数接收一个无符号 64 位整数
n作为参数。 - 使用一个
for循环，不断用n除以 5 的幂（从 5 开始，每次循环乘以 5），并将商累加到count中。 - 最后返回
count，即n!中末尾零的数量。
-
test 函数：
- 该函数用于进行自测，包含 5 个测试用例。
- 每个测试用例使用
assert宏来验证numberOfCiphersInFactorialN函数的输出是否符合预期。 - 如果测试通过，会输出相应的信息。
-
main 函数：
- 调用
test函数进行自测。 - 最后返回 0 表示程序正常退出。
