c++中如何计算组合数C(n,m)_c++求排列组合方法汇总_网络技术

c++中如何计算组合数C(n,m)_c++求排列组合方法汇总

发布时间 - 2026-01-04 00:00:00 点击率：次

应避免用std::tgamma或阶乘公式直接计算大数组合数，而采用迭代乘除法控制中间值；unsigned long long可安全计算至C(67,33)，超限需用boost::multiprecision::cpp_int等高精度方案。

直接用 `std::tgamma` 计算大数 C(n, m) 容易精度丢失

当 n 超过 20 左右，用阶乘公式 C(n,m) = n! / (m! * (n-m)!) 直接算 double 或 long double 会迅速溢出或失真。比如 std::tgamma(n+1) 在 n=171 就返回 inf（超出 double 表示范围）。更糟的是，中间结果远大于最终结果，导致有效数字被截断。

实际应避免全阶乘：改用迭代乘除，边乘边除，控制中间值在合理范围内。

从 max(m, n-m) 开始向上累乘分子，向下累除分母，减少迭代次数
用 unsigned long long 可安全算到 C(67, 33) ≈ 1.4e19（接近 ULLONG_MAX）
超过这个范围必须上高精度（如 boost::multiprecision::cpp_int 或手写数组）

用 `unsigned long long` 迭代实现安全整数版 `C(n,m)`

这是最常用、零依赖、兼顾速度与可读性的方案。核心是把组合数拆成连乘积：C(n,m) = ∏_{i=1}^m (n - m + i) / i，并保证每一步除法整除（数学上成立）。

unsigned long long comb(unsigned n, unsigned m) {
    if (m > n) return 0;
    if (m > n - m) m = n - m; // 利用对称性减少循环
    unsigned long long res = 1;
    for (unsigned i = 0; i < m; ++i) {
        res = res * (n - i) / (i + 1); // 先乘后除，整除成立
    }
    return res;
}

注意：res * (n - i) 这一步仍可能溢出——所以务必在 n 较大时加溢出检查，或改用 __builtin_mul_overflow（GCC/Clang）。

需要支持 `n > 67`？用 `boost::multiprecision::cpp_int`

标准库不提供大整数，但 boost::multiprecision 是事实上的补充。它支持任意精度整数，且语法几乎和原生类型一致，适合科学计算或算法验证场景。

需链接 -lboost_system（部分平台），头文件为：

#include 
using namespace boost::multiprecision;
cpp_int comb_big(unsigned n, unsigned m) {
    if (m > n) return 0;
    if (m > n - m) m = n - m;
    cpp_int res = 1;
    for (unsigned i = 0; i < m; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

性能比 ULLONG_MAX 版慢 10–100 倍，但换来的是完全无溢出风险。调试时可直接 std::cout 打印完整十进制结果。

`std::next_permutation` 和 `std::next_combination` 不是标准库函数

很多人搜“C++ 排列组合库函数”，误以为有类似 std::next_combination 的东西。实际上只有 std::next_permutation（用于生*排列），而组合没有对应标准函数。

若需枚举所有大小为 m 的子集（即所有组合），常见做法是：

用 std::vector mask(n, false)，设前 m 位为 true，再用 std::next_permutation(mask.begin(), mask.end()) 枚举所有掩码
每次循环中，遍历 mask 收集下标，构造一个组合
注意：该方法时间复杂度 O(C(n,m) × n)，仅适用于 n ≤ 30 且 m 不极端的情况

真正高频使用组合数的场景（比如 DP、数论题），几乎都只需求值而非枚举；枚举本身应按需定制，避免依赖不存在的“标准组合函数”。

# c++ # 排列 # overflow # 标准库 # 阶乘 # double # 算法 # 的是 # 迭代 # 这是 # 合数 # 很多人 # 遍历 # 只需 # 适用于 # 不存在 # 再用

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：个人所得税怎么查询自己交了多少税_查询收入纳税明细教程

下一篇：小猿口算app怎样设置答题时间_小猿口算app答题时间设置步

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：个人所得税怎么查询自己交了多少税_查询收入纳税明细教程

下一篇：小猿口算app怎样设置答题时间_小猿口算app答题时间设置步