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

8mmmxcuj 于 2023-10-16 发布在其他

关注(0)|答案(8)|浏览(123)

我正在写一个程序，它可以打印出pascals，traingle的行，它可以打印到第14行，它的值是13。我已经把问题缩小到选择函数，我做了“N选择K”，这似乎产生不正确的值后，“12选择X”，我不知道为什么。
下面是我为计算factory的函数编写的代码，（它似乎可以工作）和有问题的函数。还包括一个复制和粘贴的三角形后产生的第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 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，以为这是数据问题，但事实并非如此。

编辑：这是打印三角形的代码：*

int main(int argc, char **argv)
{
    int i, numRows, j;
    /*printf("%ld \n", factorial(13));
    printf("%ld \n", choose(13, 1));*/
    if (argc==2)
    {
        char *ptr;
        numRows = strtol(argv[1], &ptr,10);

        for(i=numRows; i>0; i--)
        {
            for(j=numRows - i; j>0; j--)
            {
                printf("  ");
            }
            printRow(i);
        }
        return 0;
    }
    return 1;
    
}

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));
    }
}

来源：https://stackoverflow.com/questions/77232779/strange-calculation-error-when-calculating-n-choose-k-in-c

8条答案

按热度按时间

dxxyhpgq1#

阶乘13！将溢出32位整数，而21！**将溢出64位整数。有一种方法可以解决这个问题，那就是使用一个运行项。
下面是一种输出一行Pascal三角形的方法，不需要factory。

#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

赞(0）回复(0）举报 2023-10-16

jgzswidk2#

对于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 triangles。
（测试到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);
  }
}

输出

赞(0）回复(0）举报 2023-10-16

xnifntxz3#

这实际上不是一个编程问题，而是一个数学问题。你不需要计算所有的因素。

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）回复(0）举报 2023-10-16

iswrvxsc4#

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

13！= 6 227 020 800。这将在long为32位的平台上溢出。
21！= 51 090 942 171 709 440 000。这将在long为64位的平台上溢出。

所以，你的factorial函数对大数字不起作用。所以你不能天真地使用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);
    }
}

赞(0）回复(0）举报 2023-10-16

2sbarzqh5#

使用匹配说明符

当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;。这是 undefined behavior（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

赞(0）回复(0）举报 2023-10-16

j2cgzkjk6#

不需要计算成本。Pascal三角形有一个特性，即每一行都以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");
    }
}

这将不会溢出，直到实际结果值溢出unsigned long long。

赞(0）回复(0）举报 2023-10-16

kxeu7u2r7#

下面是一个使用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)处开始超出范围。

赞(0）回复(0）举报 2023-10-16

gojuced78#

下面是一个使用double类型的解决方案。没有溢出，甚至高达25行（和更高），并给出了一个很好的扩展。参见runnable@https://godbolt.org/z/Y6Evas1YK
这个想法归功于@dan04，他在OP的评论中提到了同样的想法。
编辑：这段代码几乎没有改变OP的任何代码，除了数据类型，为了简洁，main（）被减少了。
编辑2：重要的是要知道choose（）不会溢出32位有符号整数，直到numbertits达到35+，如这里所示：https://godbolt.org/z/rnvnaEW6d
编辑3：看起来准确度在number 2 =22或23时达到最高。factorial（22），to be exact.注意factorial（）是用参数row-1调用的，因此numval =23应该没问题。请参阅评论/交流与@chux -恢复莫妮卡的更多细节。

#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;
}

赞(0）回复(0）举报 2023-10-16

我来回答

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

8条答案

相关问题

热门标签

最新问答