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

Question

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

3

我正在编写一个程序，用于打印帕斯卡三角形的行数，它可以正常工作到第14行，该行对应的是13个值。我已经缩小了问题范围，发现是我编写的“N选K”函数出现了问题，在“12选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 <--------- Where the issue starts. 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

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，以为这是一个数据问题，但事实并非如此。

- mizzmo

3

我懒得进行实际计算，但我敢打赌你可能遇到了整数溢出的问题。提示：你或许可以通过消除不同阶乘的重叠部分来解决这个问题（在某种程度上），并且优化你的代码。 - undefined

8

long的大小是多少？阶乘在计算到**12!**后会超过32位。 - undefined

3

你应该能够简化一个分子和分母都有阶乘的表达式。 - undefined

3

首先注意到 (1*2*3*4*5) / (1*2*3) = 4*5。 - undefined

1

@Kz2023 ...直到你达到21！这将打破记录。 - undefined

显示剩余7条评论

8个回答

4

这里有一个使用double类型的解决方案。即使是在25行（甚至更高）的情况下也不会溢出，并且打印效果也很好。请参考可运行的代码：https://godbolt.org/z/Y6Evas1YK 这个想法的功劳归于@dan04，在评论中提到了同样的解决方案。

编辑：这段代码几乎没有改动OP的代码，只是改变了数据类型，并且为了简洁起见，减少了main()函数的内容。

编辑2：重要的是要知道，只有当numRows达到35+时，choose()函数才会溢出32位有符号整数，这在这里得到了证明：https://godbolt.org/z/rnvnaEW6d 编辑3：看起来精度在numRows=22或23时达到了顶峰。确切地说，是factorial(22)...需要注意的是，factorial()函数的参数是row-1，因此numRows=23应该没问题。请参考与@chux - Reinstate Monica的评论/交流以获取更多详细信息。

#include <stdio.h>

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

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

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

void printRow(int row)
{   
    int i;
    for(i=0; i<=row-1; i++)
    {
        if(i!=row-1)
            printf("%d   ",choose(row-1, i));
        else
            printf("%d \n",choose(row-1, i));
    }
}


int main()
{
    int i, numRows, j;
    numRows = 23; /* 23 is max? Pls see numRows-related comments */
    for(i=numRows; i>0; i--)
    {
        for(j=numRows - i; j>0; j--)
        {
            printf("  ");
        }
        printRow(i);
    }
    return 0;
}

- greg spears

1

"即使是到第25行也不会溢出，但是在计算factorial(22)之后，double类型的结果通常开始失去精度。那么计算factorial(23)会得到什么结果呢？" - undefined

1

嗨 @chux - Reinstate Monica -- 我得到了 25852016738884978212864.0（代码在这里）... 这只有大约1.5M的偏差，所以我们没问题，对吧？哈哈。嗯嗯。谢谢你的教程。这个结果真的很具有欺骗性！但最终，双精度有其限制，这限制了这段代码的最大值为22行...再次感谢。 - undefined

1

注意：如果印象可以接受，对于使用double的大型factorial()，我们可以使用gamma函数而不是一个慢速循环。 - undefined

4

使用factorial(n_greater_than_12)时，running *= i会导致32位数学运算溢出。
代码应该使用相匹配的打印格式。
printf("%d ",choose(row-1, i)); -->
printf("%ld ",choose(row-1, i));

玩一下，怎么样扩大数学范围？

我们可以使用 uintmax_t 替代 long 类型，并重新构建三角形生成，但这只能得到大约67行，就像其他答案所示。

通过简单实现 @nielsen 并使用我们自己的扩展整数数学，我们可以形成任意大的 Pascal 三角形。
（测试到 ROWS 2000，以下是到200行的结果）

#include <assert.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define ROWS 200

typedef struct {
    size_t n;
    uint32_t *digit;
} intn;

intn intn_add(intn a, intn b) {
  intn sum = { .n = a.n > b.n ? a.n : b.n, .digit = malloc(sizeof sum.digit[0] * (sum.n + 1))};
  assert(sum.digit);
  size_t i;
  for (i = 0; i < a.n; i++) {
    sum.digit[i] = a.digit[i];
  }
  for (; i <= sum.n; i++) {
    sum.digit[i] = 0;
  }
  for (i = 0; i < b.n; i++) {
    sum.digit[i] += b.digit[i];
    if (sum.digit[i] < b.digit[i]) {
      sum.digit[i+1]++;
    }
  }
  if (sum.digit[sum.n] > 0) {
    sum.n++;
  }
  return sum;
}

intn intn_set(unsigned i) {
  intn x = { .n = 1, .digit = malloc(sizeof x.digit[0]) };
  assert(x.digit);
  x.digit[0] = i;
  return x;
}

void intn_print(intn x) {
  if (x.n == 0) {
    printf("0x0");
  } else {
    if (x.n <= 2) {
      uintmax_t y = x.n > 1 ? x.digit[1]*0x100000000u : 0;
      y += x.digit[0];
      printf("%ju", y);
      return;
    }
    printf("0x%lX", (unsigned long) x.digit[x.n - 1]);
    for (size_t i = x.n - 1; i-- > 0; ) {
      printf("%08lX", (unsigned long) x.digit[i]);
    }
  }
}

int main() {
  intn value[ROWS + 1] = {0};
  value[0] = intn_set(1);
  for (unsigned r = 1; r <= ROWS; r++) {
    value[r] = intn_set(1);
    for (unsigned c = r - 1; c >= 1; c--) {
      intn sum = intn_add(value[c - 1], value[c]);
      free(value[c].digit);
      value[c] = sum;
    }
    for (unsigned c = 0; c <= r; c++) {
      intn_print(value[c]);
      printf(" ");
    }
    printf("\n");
  }
  for (unsigned r = 1; r <= ROWS; r++) {
    free(value[r].digit);
  }
}

输出

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 
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1 
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1 
1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1 
...
1 200 19900 1313400 64684950 2535650040 82408626300 2283896214600 55098996177225 1175445251780800 22451004309013280 387790074428411200 6107693672247476400 0x4C9C7496DBD37F640 0x3FF4E5E7153AD934A0 0x3190FEF97D40CEBBFC0 0x23D1C8424B83D565D91C 0x183B168733156AB5D6A20 0xF658BA5E8759BCE35B6F0 0x937BDB5DA53E254B7BCAE0 0x536BA8142B10C04B7ED1F38 0x2CB087C1A95B427196399DE0 0x16B9C50906D9510F946492770 0xAFE07A726186B61F878FE7F20 0x51117870B8F417F2887C54E98C 0x23AB86E9EAFAC2DB5AC610E1A40 0xF016337537706E4E4570368C460 0x60B39BD652C62C6DBF8615F87FC0 0x2557A4BFE7F6D00385F57E32D1550 0xDD7A9357B810212F6122C92D66CC0 0x4EE6DE173FF8F238E1013144F96BE0 0x1B0AFFBB94E4CEE402CBC377A3F0540 0x8ED21696AA5864A42EC4204FD9CD3BA 0x2D716447363365D72627218DC54CF010 0xDF347B9A02B128EC0E38AC56764531B8 0x422A125A73FF7C966E45D40007A14FA70 0x12F40D41E93A8505C2415610022F8AD12C 0x54026446BDA970353382768C255D1B3070 0x1685B19EC129A2B6AF128E18F0C0F606AB8 0x5D8DCE1D49C0A3E325FE4E4036D2C2E0A10 0x1788DF735E2742D3F1285FAF5A976B6C821A 0x5BD7B2EDEC4E497987A3CCD1C56E2017D640 0x15BB09316FE961627817E62D0FDB3305A3D60 0x4FD8EC32AD12186FC52E2416B1550ED33C3C0 0x11CE8EDB4D24662D4A27BE97F8463DDA045790 0x3DBB004D93F5A67ADEF02E53186AF88D6462C0 0xD0013E3D0E62B0F710989C17FECC9E8E8457E0 0x2A98C3E503A0774DD46B820230C67FCA1F2FF40 0x87C6F069FB8F7C481516AE66FB78B7544368D9C 0x1A52FA5DB0C59D51E4BDDDE4F20F9141F82BD6A0 0x4F7FB6AA4E2BD5FC703D65CD03FBD0473A46F3B0 0xE9D1FB221317846DFED2B2F1933EFB2BD8947260 0x29DFC234905798A3B2DDBBBD1BE88285153F82058 0x74EE6B979CBAA568846185019662A19A44FEA0360 0x13E5024E3D5516CF1DA25EA128B28F0CE9F5FD0930 0x34CF9FB86AF47DB616CF9973F303E22247D2CE3DA0 0x88BE2B46A7390EA531EBD1E7A7857BCF9E8AFA966C 0x15974A3393AAB1786632B55A78C43BF85C66C9402C0 0x353BA0E04459D009F324BF21443C1845710F137F520 0x801EB2EC084D4FD285F04E2D5A7699DF89997002B40 0x12D14F14446B5AEC8545B1E1DC7C9E99A1CF560D3270 0x2B301E6944E59A1ED58AF8C76B58C421A5BA4797FE40 0x60D31AE3BF9FA7FACE3BB1E01E1575A64621A0822DA0 0xD417903C0545579319150BBA2984570AB200842957C0 0x1C60270C07B486F76E1B10D1A80DF4A52E5091AE87FD7 0x3B5ED79B23D05D5868582330C2155294AFAC8384CDC38 0x79708A77837004C0785730B52FE5CBD30A3DF5BE30844 0xF2E114EF06E00980F0AE616A5FCB97A6147BEB7C61088 0x1DB0B0E9745EAE5695E46024C4A6C5204D53DAAB34550A 0x38CC73D4DE9EDE365666FAB5A4B9791C6768C3B6D36B08 0x6A4B6B0E5ECA3974513D0FB304BA2F7353CF07DD75B604 0xC29FB9338D1BBC20B19776E2D29232D329AD8C99186DB8 0x15CB38127077C5BBA9384B5010E9B45BA5556F13CF66F3F 0x2636BD7F0453C3EA5D512C624EC05BCE4879BF424C1A380 0x41954C22A31A2342A7123AE0118866350DAE5989FF26140 0x6E2E0506FD88124704331B3AFEBC30D40281114E3C02880 0xB5377ACB7F4EF5A3F610B027C4A80CF0E92BDC7691DBBE0 0x123D45B5BA871DB5E7BA32FA0753685E10D1B69AE51F4280 0x1CC3154FCD864C63C608154F32EFD5CF694AB3A57D001040 0x2C6AD66150D5E0E7DA53C62C88FDB85D7879D7DBEB2A3980 0x432E643FFD76B0F847051BBCF5995A0D5FD1E3496D4976F8 0x638719425B0EA75CDAFE16216BD9B4D17182CBFB00B8B040 0x906FC3E04BF2ECA2D9E75E8E29009F61E64A4D7BDEB49BE0 0xCD57F48BFCF07EB0015B70D671CF8925663E745392FA99C0 0x11E03A6E78E05D5076F9ACAE18C3C7F0660B26B2B4393E870 0x186534A2CF201EF85A157C38E28CB07B45FD25C0ADAB7C7C0 0x209F25A420E088AB5AB191461D156EF830F0475206001A8E0 0x2ABEE1DFE475AA41A2FA546D8736916886BF42F8B86A11240 0x36E3A7DC96D14642D42FFDDE194329434FEFC773BE4261A58 0x4512FB82E60FFC5F9AD7B84864D3144933B20F21797EAEA80 0x553102FF4EF19520944E5237270454C0AEB0F08726E90A9C0 0x66FA8AA7F4867BFFFF3A1A3D0A978564B1682B3007A65B980 0x7A01E17EA47DF1858FC79F163BDA79DE417E332AFDEED6420 0x8DAF9A828D797B92D884B8BEFB2F4333A6E522A589FC95B80 0xA147E39F805BFC52BA8C2EE4497F54AA7471C2AC179F844C0 0xB3F4979453F011748F796221C07DE7E69CDFF17742C78B880 0xC4D385CA3BCE93177CECC354EA89B5A43B94F01A710A409CC 0xD307BC4F973736C75E5A385B0B4C63BD47CC8D4E7E79D66E0 0xDDCC0C72FF9575A7BE984AE786A67DB9E05C3679AEB985F10 0xE484A7FA5CA980FA674792FE0E9C056A2CFA289C667191C20 0xE6CDA9A862B570591145BADCC1F49F11A32FDC37906D95C68 0xE484A7FA5CA980FA674792FE0E9C056A2CFA289C667191C20 0xDDCC0C72FF9575A7BE984AE786A67DB9E05C3679AEB985F10 0xD307BC4F973736C75E5A385B0B4C63BD47CC8D4E7E79D66E0 0xC4D385CA3BCE93177CECC354EA89B5A43B94F01A710A409CC 0xB3F4979453F011748F796221C07DE7E69CDFF17742C78B880 0xA147E39F805BFC52BA8C2EE4497F54AA7471C2AC179F844C0 0x8DAF9A828D797B92D884B8BEFB2F4333A6E522A589FC95B80 0x7A01E17EA47DF1858FC79F163BDA79DE417E332AFDEED6420 0x66FA8AA7F4867BFFFF3A1A3D0A978564B1682B3007A65B980 0x553102FF4EF19520944E5237270454C0AEB0F08726E90A9C0 0x4512FB82E60FFC5F9AD7B84864D3144933B20F21797EAEA80 0x36E3A7DC96D14642D42FFDDE194329434FEFC773BE4261A58 0x2ABEE1DFE475AA41A2FA546D8736916886BF42F8B86A11240 0x209F25A420E088AB5AB191461D156EF830F0475206001A8E0 0x186534A2CF201EF85A157C38E28CB07B45FD25C0ADAB7C7C0 0x11E03A6E78E05D5076F9ACAE18C3C7F0660B26B2B4393E870 0xCD57F48BFCF07EB0015B70D671CF8925663E745392FA99C0 0x906FC3E04BF2ECA2D9E75E8E29009F61E64A4D7BDEB49BE0 0x638719425B0EA75CDAFE16216BD9B4D17182CBFB00B8B040 0x432E643FFD76B0F847051BBCF5995A0D5FD1E3496D4976F8 0x2C6AD66150D5E0E7DA53C62C88FDB85D7879D7DBEB2A3980 0x1CC3154FCD864C63C608154F32EFD5CF694AB3A57D001040 0x123D45B5BA871DB5E7BA32FA0753685E10D1B69AE51F4280 0xB5377ACB7F4EF5A3F610B027C4A80CF0E92BDC7691DBBE0 0x6E2E0506FD88124704331B3AFEBC30D40281114E3C02880 0x41954C22A31A2342A7123AE0118866350DAE5989FF26140 0x2636BD7F0453C3EA5D512C624EC05BCE4879BF424C1A380 0x15CB38127077C5BBA9384B5010E9B45BA5556F13CF66F3F 0xC29FB9338D1BBC20B19776E2D29232D329AD8C99186DB8 0x6A4B6B0E5ECA3974513D0FB304BA2F7353CF07DD75B604 0x38CC73D4DE9EDE365666FAB5A4B9791C6768C3B6D36B08 0x1DB0B0E9745EAE5695E46024C4A6C5204D53DAAB34550A 0xF2E114EF06E00980F0AE616A5FCB97A6147BEB7C61088 0x79708A77837004C0785730B52FE5CBD30A3DF5BE30844 0x3B5ED79B23D05D5868582330C2155294AFAC8384CDC38 0x1C60270C07B486F76E1B10D1A80DF4A52E5091AE87FD7 0xD417903C0545579319150BBA2984570AB200842957C0 0x60D31AE3BF9FA7FACE3BB1E01E1575A64621A0822DA0 0x2B301E6944E59A1ED58AF8C76B58C421A5BA4797FE40 0x12D14F14446B5AEC8545B1E1DC7C9E99A1CF560D3270 0x801EB2EC084D4FD285F04E2D5A7699DF89997002B40 0x353BA0E04459D009F324BF21443C1845710F137F520 0x15974A3393AAB1786632B55A78C43BF85C66C9402C0 0x88BE2B46A7390EA531EBD1E7A7857BCF9E8AFA966C 0x34CF9FB86AF47DB616CF9973F303E22247D2CE3DA0 0x13E5024E3D5516CF1DA25EA128B28F0CE9F5FD0930 0x74EE6B979CBAA568846185019662A19A44FEA0360 0x29DFC234905798A3B2DDBBBD1BE88285153F82058 0xE9D1FB221317846DFED2B2F1933EFB2BD8947260 0x4F7FB6AA4E2BD5FC703D65CD03FBD0473A46F3B0 0x1A52FA5DB0C59D51E4BDDDE4F20F9141F82BD6A0 0x87C6F069FB8F7C481516AE66FB78B7544368D9C 0x2A98C3E503A0774DD46B820230C67FCA1F2FF40 0xD0013E3D0E62B0F710989C17FECC9E8E8457E0 0x3DBB004D93F5A67ADEF02E53186AF88D6462C0 0x11CE8EDB4D24662D4A27BE97F8463DDA045790 0x4FD8EC32AD12186FC52E2416B1550ED33C3C0 0x15BB09316FE961627817E62D0FDB3305A3D60 0x5BD7B2EDEC4E497987A3CCD1C56E2017D640 0x1788DF735E2742D3F1285FAF5A976B6C821A 0x5D8DCE1D49C0A3E325FE4E4036D2C2E0A10 0x1685B19EC129A2B6AF128E18F0C0F606AB8 0x54026446BDA970353382768C255D1B3070 0x12F40D41E93A8505C2415610022F8AD12C 0x422A125A73FF7C966E45D40007A14FA70 0xDF347B9A02B128EC0E38AC56764531B8 0x2D716447363365D72627218DC54CF010 0x8ED21696AA5864A42EC4204FD9CD3BA 0x1B0AFFBB94E4CEE402CBC377A3F0540 0x4EE6DE173FF8F238E1013144F96BE0 0xDD7A9357B810212F6122C92D66CC0 0x2557A4BFE7F6D00385F57E32D1550 0x60B39BD652C62C6DBF8615F87FC0 0xF016337537706E4E4570368C460 0x23AB86E9EAFAC2DB5AC610E1A40 0x51117870B8F417F2887C54E98C 0xAFE07A726186B61F878FE7F20 0x16B9C50906D9510F946492770 0x2CB087C1A95B427196399DE0 0x536BA8142B10C04B7ED1F38 0x937BDB5DA53E254B7BCAE0 0xF658BA5E8759BCE35B6F0 0x183B168733156AB5D6A20 0x23D1C8424B83D565D91C 0x3190FEF97D40CEBBFC0 0x3FF4E5E7153AD934A0 0x4C9C7496DBD37F640 6107693672247476400 387790074428411200 22451004309013280 1175445251780800 55098996177225 2283896214600 82408626300 2535650040 64684950 1313400 19900 200 1

- chux - Reinstate Monica

2

这不是一个真正的编程问题，而是数学问题。你不需要计算整个阶乘。

fact(6) / fact(3) = 4 * 5 * 6

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

unsigned long long  choose(int n, int k)
{
    unsigned long long result = 1;
    if (n < k)
        return 0; 

    for(int x = k + 1; x < n; x++) result *= x;
    return result / factorial(n - k);
}

void printRow(int row)
{   
    int i;
    for(i=0; i<=row-1; i++)
    {
        if(i!=row-1)
            printf("%llu   ",choose(row-1, i));
        else
            printf("%llu \n",choose(row-1, i));
    }
}

https://godbolt.org/z/7j37b18GM

你可以进一步优化它

- 0___________

2

你遇到的问题是阶乘是一个增长极快的函数。

13! = 6 227 020 800。在32位平台上，这将溢出。

21! = 51 090 942 171 709 440 000。在64位平台上，这将溢出。

因此，你的阶乘函数对于大数值是无法工作的。所以你不能简单地使用n! / (k! (n-k)!)公式，而必须以其他方式计算choose。

这里有一个简单（虽然不一定是最优）的递归算法：

long choose(int n, int k)
{
    if (n < 0 || k < 0 || k > n)
    {
        return 0;
    }
    else if (k == 0 || k == n)
    {
        return 1;
    }
    else
    {
        return choose(n - 1, k - 1) + choose(n - 1, k);
    }
}

- dan04

2

使用匹配的说明符

当long为64位（而int为32位）时，使用"%d"来打印一个long是未定义行为（UB）。（提示：启用所有编译器警告。）

//printf("%d   ",choose(row-1, i));
printf("%ld   ",choose(row-1, i));

如果OP使用64位的long类型，这一点就能解决OP的很多困扰。

使用更宽的类型

当long类型为32位时，factorial(value_more_than_12)会导致running *= i; 溢出。这是未定义行为（UB）。

可能的替代方案，也许可以结合使用：

使用比long更宽的类型。 uintmax_t是最宽的标准整数类型。它至少为64位。结果仍然可能溢出，但可以处理更大的n, k
要注意factorial(n) / (factorial(k) * factorial(n - k)可以重写，以避免中间的大数。或者直接从前一列计算行系数。结果仍然可能溢出，但可以处理更大的n, k
可以使用支持任意精度整数运算的库。
可以使用double, long double，但通常最好使用整数类型来解决整数问题。

大大简化的替代方案如下，使用点1和点2。至少好到rows = 62。

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

void printRow_alt(unsigned row) {
  const char *separator = "";
  uintmax_t product = 1;
  for (unsigned i = 1; i <= row; i++) {
    printf("%s%ju", separator, product);
    separator = "   ";
    product = product * (row - i) / i;
  }
  printf("\n");
}

int main(/*int argc, char **argv*/) {
  int i, numRows;
  numRows = 63;

  // Output redone for simplified illustrative output.
  for (i = 1; i <= numRows; i++) {
    printRow_alt((unsigned) i);
  }
  return 0;
}

输出

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
1   13   78   286   715   1287   1716   1716   1287   715   286   78   13   1
1   14   91   364   1001   2002   3003   3432   3003   2002   1001   364   91   14   1
1   15   105   455   1365   3003   5005   6435   6435   5005   3003   1365   455   105   15   1
...
1   60   1770   34220   487635   5461512   50063860   386206920   2558620845   14783142660   75394027566   342700125300   1399358844975   5166863427600   17345898649800   53194089192720   149608375854525   387221678682300   925029565741050   2044802197953900   4191844505805495   7984465725343800   14154280149473100   23385332420868600   36052387482172425   51915437974328292   69886166503903470   88004802264174740   103719945525634515   114449595062769120   118264581564861424   114449595062769120   103719945525634515   88004802264174740   69886166503903470   51915437974328292   36052387482172425   23385332420868600   14154280149473100   7984465725343800   4191844505805495   2044802197953900   925029565741050   387221678682300   149608375854525   53194089192720   17345898649800   5166863427600   1399358844975   342700125300   75394027566   14783142660   2558620845   386206920   50063860   5461512   487635   34220   1770   60   1
1   61   1830   35990   521855   5949147   55525372   436270780   2944827765   17341763505   90177170226   418094152866   1742058970275   6566222272575   22512762077400   70539987842520   202802465047245   536830054536825   1312251244423350   2969831763694950   6236646703759395   12176310231149295   22138745874816900   37539612570341700   59437719903041025   87967825456500717   121801604478231762   157890968768078210   191724747789809255   218169540588403635   232714176627630544   232714176627630544   218169540588403635   191724747789809255   157890968768078210   121801604478231762   87967825456500717   59437719903041025   37539612570341700   22138745874816900   12176310231149295   6236646703759395   2969831763694950   1312251244423350   536830054536825   202802465047245   70539987842520   22512762077400   6566222272575   1742058970275   418094152866   90177170226   17341763505   2944827765   436270780   55525372   5949147   521855   35990   1830   61   1
1   62   1891   37820   557845   6471002   61474519   491796152   3381098545   20286591270   107518933731   508271323092   2160153123141   8308281242850   29078984349975   93052749919920   273342452889765   739632519584070   1849081298960175   4282083008118300   9206478467454345   18412956934908690   34315056105966195   59678358445158600   96977332473382725   147405545359541742   209769429934732479   279692573246309972   349615716557887465   409894288378212890   450883717216034179   465428353255261088   450883717216034179   409894288378212890   349615716557887465   279692573246309972   209769429934732479   147405545359541742   96977332473382725   59678358445158600   34315056105966195   18412956934908690   9206478467454345   4282083008118300   1849081298960175   739632519584070   273342452889765   93052749919920   29078984349975   8308281242850   2160153123141   508271323092   107518933731   20286591270   3381098545   491796152   61474519   6471002   557845   37820   1891   62   1

- chux - Reinstate Monica

2

这里有一个版本，它使用uintmax_t来存储结果，并广泛使用最大公约数计算来尽可能保持运行计算在范围内。如果由于算术溢出而无法表示结果，则返回0。（当返回值为0时，如果参数无效，则errno将被设置为EINVAL，如果结果无法表示，则设置为ERANGE。）

#include <stdint.h>
#include <errno.h>

uintmax_t gcd(uintmax_t a, uintmax_t b)
{
    while (a)
    {
        uintmax_t x;

        x = a;
        a = b % a;
        b = x;
    }
    return b;
}

uintmax_t choose(unsigned int n, unsigned int k)
{
    if (n < k)
    {
        /* Invalid. */
        errno = EINVAL;
        return 0;
    }

    if (k > n - k)
    {
        /* Symmetry. */
        k = n - k;
    }

    uintmax_t numer = 1;
    uintmax_t denom = 1;
    for (; k > 0; k--, n--)
    {
        unsigned int g = gcd(numer, k);
        unsigned int h = gcd(denom, n);
        unsigned int n_h = n / h;
        unsigned int k_g = k / g;
        numer /= g;
        denom /= h;
        if (UINTMAX_MAX / n_h < numer || UINTMAX_MAX / k_g < denom)
        {
            /* Overflow! */
            errno = ERANGE;
            return 0;
        }
        numer *= n_h;
        denom *= k_g;
        uintmax_t gg = gcd(numer, denom);
        numer /= gg;
        denom /= gg;
    }
    return numer / denom;
}

#include <stdio.h>

uintmax_t choose(unsigned int n, unsigned int k)

int main(void)
{
    for (unsigned int n = 0; n <= 100; n++)
    {
        for (unsigned int k = 0; k <= n; k++)
        {
            printf("%ju%c", choose(n, k), k < n ? ' ' : '\n');
        }
    }
}

如果`uintmax_t`的宽度为64位，它将在`choose(68, 31)`处开始超出范围。

- Ian Abbott

1

@chux-ReinstateMonica 谢谢！我本应该知道的。这就显示了我多久没有使用uintmax_t了！ - undefined

2

不需要计算阶乘。帕斯卡三角形具有每一行都以1开头和结尾的特性。中间的每个元素是前一行中最近两个元素的和，因为：

choose(n,k) = choose(n-1, k-1) + choose(n-1, k)

因此，我们可以根据前一行来计算每一行：

#include <stdio.h>

#define ROWS 20

int main()
{
    unsigned long long value[ROWS+1] = {1};
    for(unsigned r = 1; r <= ROWS; r++)
    {
        value[r] = 1;
        for(unsigned c = r-1; c >= 1; c--)
        {
            value[c] = value[c-1] + value[c];
        }
        for(unsigned c = 0; c <= r; c++)
        {
            printf("%llu ", value[c]);
        }
        printf("\n");
    }
}

这将不会溢出，直到实际结果值溢出一个无符号长长整型。

- nielsen

1

不错！简单的数学运算，内存复杂度为O(n)，加1分。我在c:37，r:68处首次溢出，value[c-1]的值为0xA577A4634B89CFB0，value[c]的值为0x8AA282CFBBD45410。使用128位数学运算，可以处理r == 132的情况。 - undefined

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Weather Vane · Accepted Answer

阶乘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