* @詳細說明* 給定一個整數作為輸入。目標是找出該數的階乘結果中末尾零的數量。
一個數 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 表示程序正常退出。
)
