本文介绍一种无需导入任何模块、避免阶乘溢出与递归栈溢出的优化方法，通过乘法公式直接计算二项式系数，并结合幂次缩放求得精确概率值，可稳定处理 n=100000 级别的输入。
本文介绍一种无需导入任何模块、避免阶乘溢出与递归栈溢出的优化方法，通过乘法公式直接计算二项式系数，并结合幂次缩放求得精确概率值，可稳定处理 n=100000 级别的输入。
传统实现中，直接计算 n! / (m! × (n−m)!) 会导致三个严重问题：
- 阶乘结果迅速超出 Python 整数合理范围（虽 Python 支持大整数，但后续除法转为浮点时精度丢失）；
- (1/2)**n 在 n 很大时下溢为 0.0，导致整个概率结果错误；
- 使用递归+记忆化实现阶乘会触发深度递归，引发 stack overflow（尤其在 Windows 默认栈限制下）。
根本解法是避开显式阶乘，改用二项式系数的乘法递推公式：
$$ \binom{n}{m} = \prod_{i=1}^{\min(m,\,n-m)} \frac{n - i + 1}{i} $$
该公式具备两大优势：
✅ 每一步都是整数除法（//），全程保持精确整数运算；
✅ 迭代次数仅为 min(m, n−m)，显著降低计算量（例如 n=100000, m=50000 时仅需 50000 次迭代，而非计算 100000!）；
✅ 中间结果增长远慢于阶乘，不易溢出（Python 整数自动扩容，但数值规模可控）。
以下是完整、健壮、无依赖的实现：
def binomial_coefficient(n, m):
"""计算组合数 C(n, m)，使用乘法公式避免阶乘"""
if m < 0 or m > n:
return 0 # 或返回 "Indefinido"，按需调整
if m == 0 or m == n:
return 1
# 利用对称性：C(n,m) == C(n, n−m)，取较小者减少循环次数
m = min(m, n - m)
result = 1
for i in range(1, m + 1):
result = result * (n - i + 1) // i # 关键：先乘后整除，保持整数性
return result
def binomial_pdf(n, m):
"""计算公平硬币下恰好 m 次正面（或反面）的概率：C(n,m) / 2^n"""
if m < 0 or m > n:
return 0.0
# 直接计算 2**n 可能极大 → 改用逐步缩放避免浮点下溢
# 更优策略：边算组合数边累积除以 2（见进阶提示）
# 此处为简洁性，仍用整数除法转浮点，但确保分子不过载
coeff = binomial_coefficient(n, m)
# 使用 pow(2, n) 比 2**n 更高效（底层优化），且 n 大时仍可行
denominator = 1 << n # 位运算等价于 2**n，更快更清晰
return coeff / denominator✅ 使用示例：
print(binomial_pdf(10_000, 5_000)) # 输出约 0.007978646139382154 print(binomial_pdf(100_000, 50_000)) # 可稳定运行（耗时约数百毫秒，取决于硬件）
⚠️ 注意事项：
- 1 1_000_000）时会生成超大整数，内存占用上升；若需更高性能或更大规模，应改用对数空间计算（log(C(n,m)) − n×log(2)）再指数还原，但本方案已满足题设“不引入模块”且支持 n=10⁵ 级别；
- 所有除法必须使用 //（整除），不可用 /，否则会提前转为浮点并损失精度；
- 不要尝试缓存 binomial_coefficient 结果——其输入空间太大（O(n²)），缓存无实际意义；
- 若需支持非公平硬币（概率 p ≠ 0.5），可扩展为 binomial_pdf(n, m, p) = C(n,m) × p^m × (1−p)^(n−m)，此时建议改用对数计算规避下溢。
总结：抛弃阶乘思维，拥抱组合数的递推本质，是处理大规模二项分布的核心优化思想。本方案零依赖、高精度、强鲁棒，是纯 Python 环境下的最优实践。
