3

我尝试190!在C.

我将我的变量定义为 long double，但我看到它只计算（正确）到 172！：

在那之后，我得到了#INF00000......`

有什么办法吗？

4

4 回答 4

5

实际上只需要几行代码就可以实现足够的 bigint 实现来计算阶乘。这是打印前 200 个阶乘的代码。

#include <stdio.h>

int mult(int n, size_t size, unsigned char *data) {
    int carry = 0;
    for (int i = 0; i < size; i++) {
        int result = data[i] * n + carry;
        data[i] = result % 100;
        carry = (result - data[i]) / 100;
    }
    return carry != 0;
}

void print(size_t size, unsigned char *data) {
    int first = 1;
    for (int i = 0; i < size; i++) {
        int d = data[size - i - 1];
        if (first && d == 0) continue;
        printf("%0*d", first && d < 10 ? 1 : 2, d);
        first = 0;
    }
}

int main(int argc, char*argv[]) {
    for (int fact = 1; fact <= 200; fact++) {
        unsigned char data[1000] = {1};
        for (int i = 1; i <= fact; i++) {
            if (mult(i, sizeof(data), data)) {
                return 1;
            }
        }
        printf("%d! = ", fact);
        print(sizeof(data), data);
        printf("\n");
    }
    return 0;
}
于 2013-11-02T18:07:59.990 回答
3

190 的阶乘是：

9680322675255249156123346514615331205418161260462873360750859919944104623425228207640470674933540169424682360525991982916161596983449594045525553704253602287443197783274656957056546338783001340434094795097553229620273057440272298773179365935914105128629426348958748638226084106818484328004851174161755668480000000000000000000000000000000000000000000000

或者，1170 位。所以这不适合任何内置类型。你真的需要一个 bigint 库来表示这么大的东西。

于 2013-11-02T17:33:00.977 回答
1

一种方法是使用任意精度算术。您可以自己实现它或使用这些库之一。

注意连值172！你得到的很可能只是大致正确的。

于 2013-11-02T17:24:17.297 回答
0

此示例 (Win32/Visual Studio Express) 程序显示错误变为带有无符号 64 位的 !23：

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


unsigned __int64 fact( unsigned __int64 in) {
    if( in == 1 ) {
        return 1;
    }
    unsigned __int64 f = fact(in-1);
    printf( "!%3I64u = %20I64u = 0x%016I64X\n", in-1, f, f );
    return in*f;
}

int main( int argc, char * argv[] ) {
    unsigned __int64 in = atoi(argv[1]);
    unsigned __int64 f  = fact(in);
    printf( "!%3I64u = %20I64u = 0x%016I64X\n", in, f, f );
    return 0;
}

跑：

C:\> Factorial 23
!  1 =                    1 = 0x0000000000000001
!  2 =                    2 = 0x0000000000000002
!  3 =                    6 = 0x0000000000000006
!  4 =                   24 = 0x0000000000000018
!  5 =                  120 = 0x0000000000000078
!  6 =                  720 = 0x00000000000002D0
!  7 =                 5040 = 0x00000000000013B0
!  8 =                40320 = 0x0000000000009D80
!  9 =               362880 = 0x0000000000058980
! 10 =              3628800 = 0x0000000000375F00
! 11 =             39916800 = 0x0000000002611500
! 12 =            479001600 = 0x000000001C8CFC00
! 13 =           6227020800 = 0x000000017328CC00
! 14 =          87178291200 = 0x000000144C3B2800
! 15 =        1307674368000 = 0x0000013077775800
! 16 =       20922789888000 = 0x0000130777758000
! 17 =      355687428096000 = 0x0001437EEECD8000
! 18 =     6402373705728000 = 0x0016BEECCA730000
! 19 =   121645100408832000 = 0x01B02B9306890000
! 20 =  2432902008176640000 = 0x21C3677C82B40000
! 21 = 14197454024290336768 = 0xC5077D36B8C40000
! 22 = 17196083355034583040 = 0xEEA4C2B3E0D80000
! 23 =  8128291617894825984 = 0x70CD7E2933680000

!21 及之后是错误的。

于 2013-11-02T17:58:50.797 回答