• 翻译来源

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