c++中如何计算多项式的值_c++实现秦九韶算法

裘德小鎮的故事 2026-01-07 00:00:00 次阅读

应使用秦九韶算法而非pow()计算多项式，因其避免重复幂运算、提升精度与稳定性；C++实现需按降幂系数顺序从a[0]开始递推result = result * x + a[i]，注意空数组、升幂误用及整数溢出时类型提升。

为什么不用 `pow()` 直接算多项式

用 pow(x, i) 逐项计算 a[i] * x^i 看似直观，但实际开销大：每次调用 pow() 都涉及浮点运算、查表或迭代，且重复计算高次幂（比如 x^3 里已算过 x^2，却没复用）。更严重的是，当系数数组很长或 x 绝对值较大时，pow() 可能因精度丢失或溢出导致结果异常。秦九韶算法本质是递推化简，把 n 次多项式转成 n 次乘加，避免幂运算，也更稳定。

秦九韶算法的 C++ 实现要点

核心公式：对多项式 P(x) = a₀xⁿ + a₁xⁿ⁻¹ + ... + aₙ₋₁x + aₙ，等价于嵌套形式 P(x) = ((a₀)x + a₁)x + a₂) ... )x + aₙ。注意系数顺序——标准输入常按降幂排列（a[0] 是最高次项系数），但算法从 a[0] 开始累乘累加。

输入系数数组 a 长度为 n+1，对应 n 次多项式
初始化结果为 a[0]，然后循环 n 次：每次执行 result = result * x + a[i]
循环下标从 1 到 n（含），不能越界
若系数按升幂存储（即 a[0] 是常数项），需先反转数组，否则结果错误

double horner(const std::vector& a, double x) {
    if (a.empty()) return 0.0;
    double result = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
        result = result * x + a[i];
    }
    return result;
}

处理整数系数和溢出风险

如果系数全是整数，但中间结果可能超出 int 范围（例如高次、大 x），直接用 int 累加会溢出。此时必须提升到更大类型：

用 long long 替代 int，适用于多数 OJ 场景（|x| , n ）
若 x 或系数极大（如 10⁹ 量级），即使 long long 也可能在乘法时溢出，需改用 __int128（GCC）或模意义下计算
无符号类型不推荐——负系数很常见，强制转无符号会导致逻辑错误

示例：整数版（防溢出）

long long horner_int(const std::vector& a, long long x) {
    if (a.empty()) return 0;
    long long result = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
        result = result * x + a[i];
    }
    return result;
}

边界与调试常见错误

实际写的时候最容易栽在三处：

系数数组为空或只含一个元素——函数要单独判断，否则循环不执行，但初始值 a[0] 可能越界
误把升幂顺序当降幂用：比如传入 {1, 2, 3} 意图表示 1 + 2x + 3x²，但按标准秦九韶实现会算成 1x² + 2x + 3，结果完全不对
std::vector::size() 返回 size_t（无符号），若循环中写成 i >= 0 倒序遍历，i-- 到 0 后继续减会绕成极大正数，导致崩溃