C++如何判断一个正整数是否为三角形数(判定公式与迭代效率对比)-C++-PHP中文网

三角形数是能表示为k(k+1)/2（k为正整数）的正整数；判定时需验证1+8n是否为奇数的完全平方数，且应通过校验sqrt前后整数避免浮点误差。

c++如何判断一个正整数是否为三角形数(判定公式与迭代效率对比)

什么是三角形数？直接用数学公式判定最可靠

一个正整数 n 是三角形数，当且仅当存在某个正整数 k，使得 n = k * (k + 1) / 2。等价地，解这个二次方程： k² + k - 2n = 0，判别式 Δ = 1 + 8 * n 必须是完全平方数，且其平方根 sqrt(Δ) 是奇数（因为 k = (-1 + sqrt(Δ)) / 2 需为正整数）。

所以判定逻辑很明确：
- 计算 delta = 1 + 8 * n
- 检查 delta 是否为完全平方数（即 sqrt(delta) 取整后平方仍等于 delta）
- 再验证 sqrt(delta) 是否为奇数（或直接算 (sqrt(delta) - 1) % 2 == 0）

注意：sqrt 返回浮点数，必须四舍五入或向下取整后验证——直接用 (int)sqrt(delta) 容易因浮点精度丢位，比如对大数 n = 1e12，sqrt(8e12 + 1) 可能略小于真实整数根。

C++里怎么安全判断完全平方数？别信 `sqrt` 直接转 int

常见错误写法：int root = (int)sqrt(delta); if (root * root == delta) ... —— 在 delta 接近 LLONG_MAX 或某些边界值时，sqrt 的浮点误差会导致 root 少 1。

更稳妥的做法是：先取整，再前后各试一个：

long long root = sqrt(delta);
for (long long r : {root - 1, root, root + 1}) {
    if (r >= 0 && r * r == delta) {
        return (r & 1); // r 是奇数才对应合法的 k
    }
}

或者用二分查找求整数平方根（对超大 n 更鲁棒，但日常够用）；std::sqrt 配合校验已足够，关键不是快，是不漏判、不错判。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

迭代法为什么不该用？时间复杂度和数值溢出风险

有人写循环：for (long long k = 1; k * (k + 1) / 2 ……这在 <code>n 很大时极慢。例如 n = 1e16，k 约需迭代 1.4e8 次，实测 >100ms；而公式法是 O(1)。

更要命的是溢出：k * (k + 1) 可能早于 / 2 就溢出。比如 long long 最大约 9e18，k ≈ 3e9 时 k*(k+1) 就超限，但此时 n 还远没到上限（对应三角形数约 4.5e18）。所以必须改写成 k 类不乘形式，或直接放弃迭代。

结论：除非你明确知道 n 总是

实际代码怎么写？兼顾可读、正确和类型安全

推荐函数签名用 long long，避免 int 溢出：

bool isTriangular(long long n) {
    if (n = 0 && r * r == delta) {
            return (r & 1) != 0; // r 是奇数 → k = (r-1)/2 是整数
        }
    }
    return false;
}

注意点：
- 不要用 float 或 double 存 delta，它可能超过 2^53 导致精度丢失
- sqrt 对 long long 需显式转 double，但只要 delta （即 <code>n ），就安全；更大时建议用 <code>sqrtl 或整数开方
- 别忘了 n == 1 是三角形数（k=1），测试用例至少包含这个