c

Question

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

您对如何绕过数据类型溢出问题有什么建议吗？ 我考虑过立即除以下障碍物，这样数字一开始就不会变得太大，我必须检查结果是否> = 1，但我无法让它工作。

Answer 1

假设您的任务是确定 1 ≤ k < n ≤ 8 exceed a limit of m = 18. You can do this by using the recurrence C(n, k) = C(n − 1, k) + C(n − 1, k − 1) that can visualized in 帕斯卡三角形有多少个二项式系数 C(n, k)。

                              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。

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

您不必存储整个三角形。键入最后一行和当前行就足够了。或者，您可以使用本文中详细介绍的算法在每行上从左到右进行处理。由于您只想计算超出限制的系数而不关心它们的值，因此常规整数类型应该足够了。

Answer 2

首先，您需要一个可以处理结果的类型。您需要处理的最大数字是 C(100,50) = 100,891,344,545,564,193,334,812,497,256。该数字需要 97 位精度，因此普通数据类型无法实现这一目的。如果您的环境提供，四精度 IEEE float 就可以解决问题。否则，您将需要某种形式的高精度/任意精度库。

然后，为了将数字保持在这个大小之内，您需要取消分子和分母中的常用项。您需要使用

( a / c ) * ( b / d ) * ...

而不是

( a * b * ... ) / ( c * d * ... )

来计算结果。