math - c中非常高的数字的二项式系数

所以我必须解决的任务是计算 100>=n>k>=1 的二项式系数,然后说出 n 和 k 有多少个解超过 123456789 的下障碍。我没有我的计算二项式系数的公式中存在问题,但对于大数字 n & k -> 100,c 的数据类型会变小,无法计算。

你有什么建议我可以通过溢出数据类型绕过这个问题。我考虑过立即除以下障碍物,因此数字不会变得太大,我必须检查结果是否为 >=1 但我无法使其工作。

回答1

假设您的任务是确定 1 ≤ k < n ≤ 8 有多少二项式系数 C(n, k) 超过了 m = 18 的限制。您可以使用递归 C(n, k) = C (n − 1, k) + C(n − 1, k − 1) 可以在https://en.wikipedia.org/wiki/Pascal%27s_triangle中可视化。

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

从顶部开始,然后向下工作。直到 n = 5,所有内容都低于 18 的限制。在下一行,20 超过了限制。从现在开始,越来越多的系数超过 18。

三角形是对称的,并且在每行的前半部分严格递增。您只需要在每行中找到第一个超出限制的元素即可知道要计算的项目数。

您不必 store 整个三角形。保留最后一行和当前行就足够了。或者,您可以使用 [in this article][ot] 详细介绍的算法在每一行上从左到右工作。由于您只想计算超出限制的系数而不关心它们的 values,因此常规整数类型就足够了。

回答2

首先,您需要一种可以处理结果的类型。您需要处理的最大数字是 C(100,50) = 100,891,344,545,564,193,334,812,497,256。这个数字需要 97 位的精度,因此您的普通数据类型无法解决问题。如果您的环境提供,https://en.wikipedia.org/wiki/Quadruple-precision_floating-point_format 可以解决问题。否则,您将需要某种形式的高/任意精度库。

然后,为了将数字保持在这个大小范围内,您需要取消分子和分母中的常用项。您需要使用 ( a / c ) * ( b / d ) * ... 而不是 ( a * b * ... ) / ( c * d * ... ) 来计算结果。

相似文章