使用阶乘函数实现nCr函数时的计算错误问题

这段代码在n>12时计算结果出现数学错误，核心原因是int类型的整数溢出，具体细节如下：

• int类型的取值限制：通常情况下，C++中的int是32位带符号整数，取值范围为-2147483648到2147483647。
• 阶乘的增长特性：阶乘数值增长极快，12的阶乘12! = 479001600，该值小于int的最大值，能被正确存储；但13的阶乘13! = 6227020800，远超过int的最大值，此时会发生整数溢出。
• 溢出的影响：C++中带符号整数溢出属于未定义行为，不会触发编译或运行时报错，但存储的数值会变成循环取模后的错误值。后续基于这个错误的阶乘值计算组合数，最终结果自然不符合数学预期。
• 编译器无提示的原因：默认情况下，编译器不会主动检测整数溢出这类运行时未定义行为，只有开启特定编译选项（比如GCC的-Woverflow）时，才会针对可能的溢出给出警告。

可选优化方案 #

如果需要计算更大n值的组合数，可以通过以下方式解决：

• 改用更大范围的整数类型，比如long long（64位带符号整数，最大值约9e18，可容纳到20!左右），将代码中所有int替换为long long即可提升计算上限。
• 优化组合数计算逻辑，避免直接计算大数阶乘。例如使用递推公式：C(n,r) = C(n,r-1) * (n - r + 1) / r，分步计算的同时可以减少中间结果的大小，进一步降低溢出风险。

内容的提问来源于stack exchange，提问作者Aryan Kumar