尝试打印帕斯卡三角形时，第 13 次迭代打印错误答案

Question

我正在用 C 编写一个脚本来打印帕斯卡三角形，所以我写了一个阶乘函数，然后将变量 c = 设为二项式展开方程，直到第 n = 13 行它产生输出：

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 
1 10 45 120 210 252 210 120 45 10 1 
1 11 55 165 330 462 462 330 165 55 11 1 
1 12 66 220 495 792 924 792 495 220 66 12 1 
0 4 24 88 221 399 532 532 399 221 88 24 4 0

最后一行是 n = 13。我最初认为它被打破了，因为阶乘对于 32 位整数来说太大了，但错误仍然存在于 64 位整数中......

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


int64_t factorial(int k);

int main(int argc, char **argv)
{
    int c, n, r, i;

    if (argc < 2) {
        printf("[function]:  %s [number of lines to print]", argv[0]);
        return -1;
    }

    n = atoi(argv[1]);

    for (i = 0; i <= n; i++) {
        for (r = 0; r <= i; r++) {
            c = (int) factorial(i) / (factorial(r) * factorial((i - r)));
            printf("%d ", c);
        }
        printf("\n");
    }
    return 1;


}

int64_t factorial(int k)
{
    int64_t j;

    if (k == 0 || k == 1)
        return 1;

    int n = k;

    for (j = k; n > 1;)
        j = j * --n;
    return j;
}

非常感谢您对此提供帮助...

Answer 1

        c = (int) factorial(i) / (factorial(r) * factorial((i - r)));

这与您认为的不同。尝试

        c = (int) (factorial(i) / (factorial(r) * factorial((i - r))));

Answer 2

即使在 64 位中，您的计算也会失败，因为您用石膏打中了自己的脚（很痛）：

c = (int) factorial(i) / (factorial(r) * factorial((i - r)));

被解析为

c = ((int)factorial(i)) / (factorial(r) * factorial((i - r)));

只需删除强制转换或将其放在结果上：

c = (int)(factorial(i) / (factorial(r) * factorial(i - r)));

注意你的factorial函数太复杂了，这里有一个更简单的版本：

int64_t factorial(int n) {
    int64_t x;
    for (x = 1; n > 1; n--) {
        x *= n;
    }
    return x;
}

另请注意，您不需要计算全阶乘，此版本为 29，并且可以通过一些工作进一步改进：

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

long long binomial(int n, int p) {
    int q;
    long long x;

    if (p < n - p)
        p = n - p;
    q = n - p;
    for (x = 1; n > p; n--)
        x *= n;
    for (; q > 1; q--)
        x /= q;
    return x;
}

int main(int argc, char **argv)
{
    int n, r, i;

    if (argc < 2) {
        printf("[function]:  %s [number of lines to print]", argv[0]);
        return -1;
    }

    n = atoi(argv[1]);

    for (i = 0; i <= n; i++) {
        for (r = 0; r <= i; r++) {
            printf("%lld ", binomial(i, r));
        }
        printf("\n");
    }
    return 0;
}

最后，如果允许使用数组，则可以进一步简化帕斯卡三角形的计算，因为每个系数都是其上方系数与左侧系数之和：

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

int main(int argc, char **argv) {
    int n, r, i;

    if (argc < 2) {
        printf("[function]:  %s [number of lines to print]", argv[0]);
        return -1;
    }

    n = atoi(argv[1]);
    long long coeff[n + 1];

    coeff[0] = 1;
    for (r = 1; r <= n; r++) {
        coeff[r] = 0;
    }
    for (i = 0; i <= n; i++) {
        for (r = i; r > 0; r--) {
            coeff[r] += coeff[r - 1];
        }
        for (r = 0; r <= i; r++) {
            printf("%lld ", coeff[r]);
        }
        printf("\n");
    }
    return 0;
}

尝试打印帕斯卡三角形时，第 13 次迭代打印错误答案

When trying to print pascals triangle 13th iteration prints wrong answer

c

pascals-triangle