0

该程序是在一个数字的阶乘中找到位数

#include <stdio.h>
#include <math.h>
int main()
{
int n = 0 , i , count = 0 , dig ;
double sum = 0, fact;
scanf("%d" , &n );
for(i=1;i<=n;i++)
{
 sum = sum + log(i);
}
fact = (exp(sum));
while(fact!=0)
{
 dig = ((int)fact%10);
 count++;
 fact = floor(fact/10);
}
printf("%d\n",count);
return 0; 
}

由于我在编码方面还没有广泛的经验,因此请随意评论对此代码的改进。

4

3 回答 3

1

您的代码花费这么长时间的原因是,一旦n达到大约 180,值fact就会变得太大而无法保存在双精度浮点变量中。当您执行此行时:

    fact = (exp(sum));

你基本上设置fact为无穷大。结果,以下while()循环永远不会终止。

在您的代码中计算对数也没什么意义。它只会减慢速度。只需计算double变量中的阶乘并在它变得太大时重置它。像这样,例如:

int factorial_digit_count(int n) {
    int i, nd=1;
    double f = 1.0;
    for (i=2; i<=n; i++) {
        f *= i;
        if (f > 1.0E+100) {
            f /= 1.0E+100;
            nd += 100;
        }
    }
    while (f > 1.0E+10) {
        f /= 1.0E+10;
        nd += 10;
    }
    while (f >= 10.0) {
        f /= 10.0;
        nd++;
    }
    return nd;
}
于 2020-09-25T20:21:10.730 回答
0

b一个数字的底对数和该数字的底b表示之间有一个简单的关系:

len(repr(x, b)) = 1 + floor(log(x, b))

特别是,在以 10 为底的情况下,x 的位数是1 + floor(log10(x))。(要了解为什么会这样,请查看 10 次方公式的结果。)

现在, 的对数a×b是 和 的对数之ab。所以 的对数n!就是从 1 到 的整数的对数之和n。如果我们以 10 为底进行计算,那么我们可以轻松提取n!.

换句话说,如果你log10对每个值求和而不是log,那么你可以摆脱:

fact = (exp(sum));

while(fact!=0)
{
 dig = ((int)fact%10);
 count++;
 fact = floor(fact/10);
}

并且只是输出1 + floor(sum)

从理论上讲,这可能会受到舍入误差的影响。但是,您需要做大量的对数才能使错误项传播到足以在计算中产生错误。(并不是说它不会发生。但如果它发生了,n确实是一个非常大的数字。)

于 2020-09-25T20:56:03.017 回答
0

假设您不想使用任何数学计算但想“蛮力”通过您的方式 - 这就是我将如何缩短您的运行时间(并且主要是清理您的代码)。

#include <stdio.h>
#include <math.h>
int main()
{
    int n, fact = 1;
    scanf("%d" , &n );
    for (int i = 1; i < n; i++)
        fact *= i;
    
    int sum = 0;
    while (fact != 0)
    {
        fact /= 10;
        sum++
    }

    printf("%d\n",count);
    return 0; 
}

希望这能回答你的问题,祝你好运!

于 2020-09-25T20:15:39.710 回答