Nの各値について、N階乗で何桁の数字が表示されるのですか

Question

タイトルには次のような問題があります。Nの値ごとに、N！たとえば、n = 32000の場合、私は130271を取得する必要があります。 私は再帰的なソリューションについて考えました。それはより小さい数字のために働いていますが、上記の例では31997が出力されます。私は思考が間違っていると確信していますが、実際には大きな数字の規則を見つけることはできません。どこか、n！ステップをスキップし始めると思います。つまり、数字では増加しませんが、2つまたは3つで増加します。 私は、次のコードを持って：あなたは何をやっている

#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!)です。あなたがそれを理解すると、Stirling's Approximationやここで取り上げた他のテクニックの1つを使うことができます：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); 

はより

OPの元の整数のアプローチを使用して

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

のようにして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スターリングの方法。