- 翻译来源
Count digits in a factorial | Set 1
Count digits in a factorial | Set 2
第一部分
给定一个整数 n ，找出其阶乘结果包括多少个数字。阶乘 factorial 定义为：
factorial(n) = 1 * 2 * 3 * 4 ............. * n
factorial(0) = 1
举例
Input : n = 1
Output : 1
1! = 1，所以数字个数为1
Input : 5
Output : 3
5! = 120，个数为3
Input : 10
Output : 7
10! = 362880，个数为7
一个幼稚（naive）的解决方法是先算出 n! ，再计算结果中包含多少个数字。但由于 n! 的值可以非常大，将其存储在一个变量中是非常繁重的任务（除非你用的是 python!）。
一种更好的解决方法是利用对数的有用性质来计算要求的答案。
我们知道，
log(a * b) = log(a) + log(b)
因此
log( n! ) = log(1 * 2 * 3 * ....... * n)
= log(1) + log(2) + ....... + log(n)
现在，可以观察到一个数取 10 的对数，向下取整的结果再加 1 ，
就能得到其阶乘结果中包含的数字个数；
即，所需输出为 : floor(log(n!)) + 1
下面是等价的 C++ 程序。
// 一个用来计算阶乘结果中数字个数的c++程序
#include <bits/stdc++.h>
using namespace std;
// 函数接受一个整数 n ，返回 n! 中的数字个数
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
下一部分，我们将看到如何进一步优化方案，降低相同程序的时间复杂度。
第二部分
给定一个整数 n （可以是非常大的值），找出其阶乘结果中包含多少个数字。阶乘 factorial 定义为：
factorial(n) = 1 * 2 * 3 * 4 ....... * n
factorial(0) = 1
举例
Input : n = 1
Output : 1
1! = 1, 因此数字的个数是1
Input : 5
Output : 3
5! = 120, 即3个数字
Input : 10
Output : 7
10! = 3628800, 即7个数字
Input : 50000000
Output : 363233781
Input : 1000000000
Output : 8565705523
在前一部分我们讨论了当 n 较小时的解决方法。然而，前面的解决方法将不能处理 n > 10^6 时的情况。
所以，我们能改进我们的解决方法吗？
是的！我们可以。
我们可以使用 Kamenetsky 的方程来找出答案！
可以通过
f(x) = log10( ((n/e)^n) * sqrt(2 * pi * n))
来接近答案。
我们可以简单使用对数的性质：
f(x) = n * log10(( n/ e)) + log10(2 * pi * n) / 2
好！
现在我们的解决方法可以处理 32 位整数所能容纳的巨大数字，甚至更大的数字！
下面是对以上思考过程的实现。
// 优化后的计算 n! 中数字个数的程序
#include <bits/stdc++.h>
using namespace std;
// 返回 n! 中的所有数字的个数
// 由于结果可能很大，使用 long long 作为返回值
long long findDigits(int n)
{
// 负数的阶乘不存在
if (n < 0)
return 0;
// 基准情形
if (n <= 1)
return 1;
// 使用 Kamenetsky 方程计算数字的个数
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
