我正在写一个程序,它可以打印出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));
}
}
8条答案
按热度按时间dxxyhpgq1#
阶乘13!将溢出32位整数,而21!**将溢出64位整数。有一种方法可以解决这个问题,那就是使用一个运行项。
下面是一种输出一行Pascal三角形的方法,不需要factory。
方案会议
和
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)输出
xnifntxz3#
这实际上不是一个编程问题,而是一个数学问题。你不需要计算所有的因素。
https://godbolt.org/z/7j37b18GM
您可以进一步优化它
iswrvxsc4#
你遇到的问题是阶乘是一个增长非常快的函数。
long
为32位的平台上溢出。long
为64位的平台上溢出。所以,你的
factorial
函数对大数字不起作用。所以你不能天真地使用n!/(k!(n-k)!)公式,但必须以其他方式计算choose
。这里有一个简单的(如果不一定是最优的)递归算法:
2sbarzqh5#
使用匹配说明符
当
long
是64位(int
是32位)时,使用"%d"
打印long
是 * 未定义行为 *(UB)。(提示:启用所有编译器警告。如果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
输出
j2cgzkjk6#
不需要计算成本。Pascal三角形有一个特性,即每一行都以
1
开始和结束。中间的每个元素都是前一行中最近的两个元素的和,因为:因此,我们可以根据前一行计算每一行:
这将不会溢出,直到实际结果值溢出
unsigned long long
。kxeu7u2r7#
下面是一个使用
uintmax_t
来存储结果的版本,并广泛使用最大公约数计算来尽可能地保持运行计算的范围。如果由于算术溢出而无法表示结果,则返回0。(当返回值为0时,如果参数无效,则errno
将被设置为EINVAL
,如果结果无法表示,则ERANGE
。如果
uintmax_t
是64位宽,它将在choose(68, 31)
处开始超出范围。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 -恢复莫妮卡的更多细节。