- 翻譯來源
Count digits in a factorial | Set 1
Count digits in a factorial | Set 2
第一部分
給定一個整數(shù) n 兴蒸，找出其階乘結果包括多少個數(shù)字图谷。階乘 factorial 定義為：
factorial(n) = 1 * 2 * 3 * 4 ............. * n
factorial(0) = 1
舉例
Input : n = 1
Output : 1
1! = 1平委，所以數(shù)字個數(shù)為1
Input : 5
Output : 3
5! = 120己单，個數(shù)為3
Input : 10
Output : 7
10! = 362880，個數(shù)為7
一個幼稚（naive）的解決方法是先算出 n! 邑蒋，再計算結果中包含多少個數(shù)字贿讹。但由于 n! 的值可以非常大养篓，將其存儲在一個變量中是非常繁重的任務（除非你用的是 python!）。
一種更好的解決方法是利用對數(shù)的有用性質來計算要求的答案忠聚。
我們知道设哗，
log(a * b) = log(a) + log(b)
因此
log( n! ) = log(1 * 2 * 3 * ....... * n)
= log(1) + log(2) + ....... + log(n)
現(xiàn)在，可以觀察到一個數(shù)取 10 的對數(shù)两蟀，向下取整的結果再加 1 网梢，
就能得到其階乘結果中包含的數(shù)字個數(shù)；
即赂毯，所需輸出為 : floor(log(n!)) + 1
下面是等價的 C++ 程序战虏。
// 一個用來計算階乘結果中數(shù)字個數(shù)的c++程序
#include <bits/stdc++.h>
using namespace std;
// 函數(shù)接受一個整數(shù) n ，返回 n! 中的數(shù)字個數(shù)
int findDigits(int n)
{
// 只有當 n >= 0 時階乘才有意義
if (n < 0)
return 0;
// 基準情形
if (n <= 1)
return 1;
// 此外党涕，迭代 n 次求出所需值
double digits = 0;
for (int i=2; i<=n; i++)
digits += log10(i);
return floor(digits) + 1;
}
// 驅動代碼
int main()
{
cout << findDigits(1) << endl;
cout << findDigits(5) << endl;
cout << findDigits(10) << endl;
cout << findDigits(120) << endl;
return 0;
}
Output :
1
3
7
199
下一部分烦感，我們將看到如何進一步優(yōu)化方案，降低相同程序的時間復雜度膛堤。
第二部分
給定一個整數(shù) n （可以是非常大的值）手趣，找出其階乘結果中包含多少個數(shù)字。階乘 factorial 定義為：
factorial(n) = 1 * 2 * 3 * 4 ....... * n
factorial(0) = 1
舉例
Input : n = 1
Output : 1
1! = 1, 因此數(shù)字的個數(shù)是1
Input : 5
Output : 3
5! = 120, 即3個數(shù)字
Input : 10
Output : 7
10! = 3628800, 即7個數(shù)字
Input : 50000000
Output : 363233781
Input : 1000000000
Output : 8565705523
在前一部分我們討論了當 n 較小時的解決方法肥荔。然而绿渣，前面的解決方法將不能處理 n > 10^6 時的情況朝群。
所以，我們能改進我們的解決方法嗎中符？
是的潜圃！我們可以。
我們可以使用 Kamenetsky 的方程來找出答案舟茶！
可以通過
f(x) = log10( ((n/e)^n) * sqrt(2 * pi * n))
來接近答案谭期。
我們可以簡單使用對數(shù)的性質：
f(x) = n * log10(( n/ e)) + log10(2 * pi * n) / 2
好！
現(xiàn)在我們的解決方法可以處理 32 位整數(shù)所能容納的巨大數(shù)字吧凉，甚至更大的數(shù)字隧出！
下面是對以上思考過程的實現(xiàn)。
// 優(yōu)化后的計算 n! 中數(shù)字個數(shù)的程序
#include <bits/stdc++.h>
using namespace std;
// 返回 n! 中的所有數(shù)字的個數(shù)
// 由于結果可能很大阀捅，使用 long long 作為返回值
long long findDigits(int n)
{
// 負數(shù)的階乘不存在
if (n < 0)
return 0;
// 基準情形
if (n <= 1)
return 1;
// 使用 Kamenetsky 方程計算數(shù)字的個數(shù)
double x = ((n * log10(n / M_E) +
log10(2 * M_PI * n) /
2.0));
return floor(x) + 1;
}
// 驅動代碼
int main()
{
cout << findDigits(1) << endl;
cout << findDigits(50000000) << endl;
cout << findDigits(1000000000) << endl;
cout << findDigits(120) << endl;
return 0;
}
*譯注：建議用exp(1)代替M_E胀瞪，用acos(-1)代替M_PI。
Output：
1
363233781
8565705523
199
