计算大n ~ 100的n阶乘，但结果不正确[已关闭]

Question

我正在尝试使用一个数组来解决这个问题，我在其中放置了 n 的数字！

这是我尝试过的

int main()
{
    int a[1000];
    int n = 1;
    a[0] = 1;
    int limit = 100;
    for (int i = 2; i <= limit; i++) {
        int carry = 0;
        for (int j = 0; j < n; j++) {
            int prod = a[j] * i + carry;
            a[j] = prod % 10;
            carry = prod / 10;
            if (carry) {
                a[j + 1] = carry;
                n = n + 1;
            }
        }
    }
    for (int i = (n - 1); i >= 0; i--)
        printf("%d", a[i]);

    return 0;
}

2人用效果很好！和 3！但对于较大的

limit

值，它只会打印许多随机数。

例如，输出为 4!是

504

。
预期输出是

24

。

Answer 1

问题在于您处理

carry

的方式：您应该在完成对现有数字的循环之后存储多余的数字。可能需要存储超过 1 个额外数字，因此您需要一个循环。 另请注意，对于

int

数组的类型，您不需要

a

，

char

或

unsigned char

就足够了。这是一个修改版本，可以处理最多 3248 个数字（少于 10001 位）。

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

int main(int argc, char *argv[]) {
    int limit = (argc > 1) ? atoi(argv[1]) : 100;
    unsigned char a[10000];
    int len = sizeof a / sizeof a[0];
    int n = 1;
    a[0] = 1;
    for (int i = 2; i <= limit; i++) {
        int carry = 0;
        // compute the digits using high school arithmetics
        for (int j = 0; j < n; j++) {
            carry += a[j] * i;
            a[j] = carry % 10;
            carry = carry / 10;
        }
        // store the extra digits
        while (carry > 0) {
            if (n >= len) {
                printf("too many digits\n");
                return 1;
            }
            a[n] = carry % 10;
            carry = carry / 10;
            n = n + 1;
        }
    }
    for (int i = n; i-- > 0;) {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

输出：

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

对于较大的阶乘，可以使用斯特林公式来近似计算小数位数：

小数位数如下

位数(n!)

≈ log10(2π)/2 - n.log10(e) + (n+0.5).log10(n) 这是一个修改版本，一次计算 9 位数字：

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

// approximating the number of digits:
// log10 n! = log10(2*pi)/2 - n*log10(e) + (n+0.5)*log10(n)

int main(int argc, char *argv[]) {
    int limit = (argc > 1) ? atoi(argv[1]) : 100;
    size_t len = (size_t)((limit * 0.434 + (limit + 0.5) * log((double)limit) + 17) / 9);
    uint32_t *a = malloc(len * sizeof(*a));
    if (a == NULL) {
        fprintf(stderr, "cannot allocate %zu bytes\n", len * sizeof(*a));
        return 1;
    }
    size_t n = 1;
    a[0] = 1;
    uint64_t factor = 1;
    for (int i = 2;; i++) {
        if (i > limit || factor * i > UINT32_MAX) {
            uint64_t carry = 0;
            // compute the digits using high school arithmetics
            for (size_t j = 0; j < n; j++) {
                carry += (uint64_t)a[j] * (uint32_t)factor;
                a[j] = carry % 1000000000;
                carry = carry / 1000000000;
            }
            // store the extra digits
            while (carry > 0) {
                if (n >= len) {
                    fprintf(stderr, "too many digits %zu at %d\n", n * 9, i);
                    return 1;
                }
                a[n] = carry % 1000000000;
                carry = carry / 1000000000;
                n = n + 1;
            }
            factor = 1;
            if (i > limit)
                break;
        }
        factor *= i;
    }
    if (n > 1) {
        uint64_t num = a[n - 1] * 1000000000ULL + a[n - 2];
        int exp = (n - 1) * 9;
        // should perform proper rounding
        while (num >= 10000000000) {
            num /= 10;
            exp += 1;
        }
        printf("%d.%09"PRIu64"e%d\n", (int)(num / 1000000000), num % 1000000000, exp);
    } else {
        printf("%"PRIu32"\n", a[n - 1]);
    }
#if 0
    printf("%"PRIu32, a[n - 1]);
    if (n > 1) {
        for (size_t i = n - 1; i-- > 0;) {
            printf("%09"PRIu32, a[i]);
        }
    }
    putchar('\n');
#endif
    free(a);
    return 0;
}

它可以计算大阶乘的所有数字（可以在

Factorial

维基百科页面上进行验证），但可以使用更先进的乘法技术和二进制计算来提高其时间复杂度，而将基数10转换仅用于打印。 这个版本还是很简单，计算了 1000000 的 5565709 位数字！在我的 M2 MacBook Air 上只需 16 分钟。