在C中计算“N选择K”时出现奇怪的计算错误

Question

我正在编写一个程序，打印出帕斯卡三角形的行，它最多可以工作到第 14 行，该行的值为 13。我已将问题范围缩小到我所做的“N 选择 K”的选择函数”，在“12 Choose X”之后似乎会产生不正确的值，我不知道为什么。

这是我计算阶乘的函数（似乎有效）和有问题的函数的代码。还包括第 14 行之后生成的三角形的复制和粘贴。

另外，作为参考，这样做printf("%ld \n", choose(13, 1));会产生 4 的结果。它应该是 13。

long factorial(int value)
{
    int i;
    long running = 1;
    for (i = 1; i <= value; i++)
    {
        running *= i;
    }
    return running;
}

long choose(int n, int k)
{
    if (n < k)
        return 0; 

    return factorial(n) / (factorial(k) * factorial(n - k));
}

1 1 -4 -1 2 4 7 9 9 7 4 2 -1 -4 1 1

1 0 1 5 14 29 44 50 44 29 14 5 1 0 1

1 4 24 88 221 399 532 532 399 221 88 24 4 1 <--------- 问题开始的地方。

1 12 66 220 495 792 924 792 495 220 66 12 1

1 11 55 165 330 462 462 330 165 55 11 1

1 10 45 120 210 252 210 120 45 10 1

1 9 36 84 126 126 84 36 9 1

1 8 28 56 70 56 28 8 1

1 7 21 35 35 21 7 1

1 6 15 20 15 6 1

1 5 10 10 5 1

1 4 6 4 1

1 3 3 1

1 2 1

1 1

1

我尝试将类型从 Int 更改为 Long ，认为这是数据问题，但事实并非如此。

Answer 1

阶乘13！32位整数会溢出，21！将会溢出 64 位整数。有一种方法可以解决这个问题，即使用运行术语。

这是输出一行帕斯卡三角形的方法，无需阶乘。

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

void PascalRow(int row)
{
    long long term = 1;
    int multiplier = row;
    int divisor = 1;
    printf("1");
    for(int i=0; i<row; i++) {
        term = term * multiplier / divisor;
        printf(" %lld", term);
        multiplier--;
        divisor++;
    }
    printf("\n");
}

int main(int argc, char *argv[]) {
    if(argc < 2)
        return 1;
    PascalRow(atoi(argv[1]));   // note: improve this
    return 0;
}

节目会议

test 6
1 6 15 20 15 6 1 

和

test 15
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1