对于N的每个值，打印N个因子中有多少个数字

Question

我有以下问题，如标题所述：对于N的每个值，打印出N！中有多少个数字。例如，如果n = 32000，我应该得到130271. 我曾想过一个递归解决方案。它适用于较小的数字，但对于上面的例子，它打印31997.我相信我的想法是错误的，但我无法找到更大数字的规则。某处，n！我想，开始跳过步骤。我的意思是，它不会随着数字增加，而是会增加两到三个。 我有以下代码：

#include <stdio.h> 
#include <stdlib.h> 

//For each value of N, print out how many digits are in N!. 

int how_many(int n){ 
    if(n <= 3) 
     return 1; 
    if(n == 4) 
     return 2; 
    if(n == 5 || n == 6) 
     return 3; 
    if(n >= 7) 
     return 1 + how_many(n-1); 

    } 


int main() 
{ 
    int n; 
    printf("The number n is : "); 
    scanf("%d", &n); 

    int counter = 0; 

    counter = how_many(n); 

    printf("n! has %d digits", counter); 

    return 0; 
} 

Answer 1

你正在做什么是真正log10(N!)。一旦你意识到这一点，你可以使用斯特林的逼近或其他探索技巧之一：https://math.stackexchange.com/questions/138194/approximating-log-of-factorial

Answer 2

@JohnZwinck的答案解决了我的问题。下面是生成的代码：

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

#define M_PI 3.14159265358979323846 

//For each value of N, print out how many digits are in N!. 

int digits_in_factorial(int n){ 
    return floor((n+0.5)*log(n) - n+ 0.5*log(2*M_PI))/log(10) + 1; 
} 

int main() 
{ 
    int n; 
    printf("Numarul n este : "); 
    scanf("%d", &n); 

    int counter = 0; 

    counter = digits_in_factorial(n); 

    printf("n! are %d cifre", counter); 

    return 0; 
} 

Answer 3

OP的递归方法估计过低：

return 1 + how_many(n-1); 

应该更像

return log10(n) + how_many(n-1); 

使用OP的原始整数做法及以下how_many(32000) --> n! has 123560 digits - 更好的估计。

int how_many(int n) { 
    if (n <= 3) 
    return 1; 
    if (n == 4) 
    return 2; 
    if (n == 5 || n == 6) 
    return 3; 

    int count = 0 + how_many(n - 1); 
    while (n > 3) { 
    n /= 10; 
    count++; 
    } 
    return count; 
} 

IAC，OP has found斯特林的方法。