C++如何判断一个正整数是否为三角形数(Triangular Number)-C++-PHP中文网

三角形数是能表示为k(k+1)/2的正整数n，等价于判别式1+8n为完全平方数且其平方根为奇数；判断时需用round(sqrt(1+8n))再验证平方，避免浮点误差。

c++如何判断一个正整数是否为三角形数(triangular number)

什么是三角形数，以及它和平方根的关系

一个正整数 n 是三角形数，当且仅当存在某个正整数 k，使得 n = k*(k+1)/2。这个公式来自前 k 个自然数之和。直接遍历 k 效率低，但可以变形：把等式两边乘 2 得 2n = k² + k，再配方得 k² + k + 1/4 = 2n + 1/4，即 (k + 0.5)² = 2n + 0.25。于是 k = sqrt(2n + 0.25) - 0.5。只要这个结果是正整数，n 就是三角形数。

用 `sqrt` 判断时必须处理浮点精度问题

C++ 的 std::sqrt 返回 double，直接取整可能因精度误差误判。比如对 n = 55（确实是第 10 个三角形数），sqrt(2*55 + 0.25) 理论上是 10.5，但实际计算可能得到 10.499999999999998，减去 0.5 后变成 9.999...，向下取整就错了。

正确做法：计算 long long root = round(sqrt(2LL * n + 0.25))，再验证 root * root == 2LL * n + 0.25 是否成立（但浮点比较仍不稳）
更稳妥方式：算出候选 k = static_cast<long long>(std::round(std::sqrt(2.0 * n + 0.25) - 0.5))</long>，然后代回公式检查 k * (k + 1) / 2 == n
注意：n 要转成 long long 防溢出，尤其当 n 接近 INT_MAX 时，2*n 可能溢出 int

一行可读的判断函数写法

下面这个函数在实践中足够健壮，适用于 n 量级：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

bool isTriangular(long long n) {
    if (n (std::sqrt(2.0 * n));
    // 在 k-1, k, k+1 范围内试，避免浮点误差导致漏判
    for (long long cand : {k-1, k, k+1}) {
        if (cand > 0 && cand * (cand + 1) / 2 == n) return true;
    }
    return false;
}

这里不依赖 sqrt 的精确性，只把它当作粗略估计，再用整数运算验证——这是最不容易踩坑的做法。

为什么不用二分查找？

理论上可以在 [1, sqrt(2n)] 区间二分搜索满足 k*(k+1)/2 == n 的 k，逻辑清晰且无精度问题。但它比上面三候选法多几次除法和乘法，常数更大；而三候选法最多三次整数运算，在绝大多数情况下一次就命中。除非你在写高可靠性数学库，否则没必要为这点“理论严谨”增加复杂度。

真正容易被忽略的是：所有涉及 2*n 的中间计算都必须用足够宽的整数类型，int 在 n > 1e9 时就会溢出，哪怕最终结果没超 int 范围。