C++中使用霍纳法则高效计算多项式

Horner方法提供了一种高效的多项式求值方法，最大限度地减少了所需的乘法次数。与朴素方法相比，这显著提高了性能，尤其对于高次多项式更是如此。本文探讨了Horner法则的几种C++实现，用于求解以下形式的多项式：

P(x) = a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀

目录

• 迭代法（反向循环）
• 迭代法（正向循环）
• 递归法
• 结论

迭代法（反向循环）

此实现使用反向迭代循环直接反映Horner法则的嵌套乘法结构。

#include <iostream>
#include <vector>

double hornerBackward(const std::vector<double>& coefficients, double x) {
  double result = coefficients.back(); 
  for (int i = coefficients.size() - 2; i >= 0; --i) {
    result = result * x + coefficients[i];
  }
  return result;
}

int main() {
  std::vector<double> coefficients = {2, -6, 2, -1}; 
  double x = 3;
  double result = hornerBackward(coefficients, x);
  std::cout << "The value of the polynomial at x = " << x << " is: " << result << std::endl;
  return 0;
}

迭代法（正向循环）

虽然反向迭代更直观，但正向循环同样高效。此版本从常数项开始迭代，逐步构建结果。

#include <iostream>
#include <vector>

double hornerForward(const std::vector<double>& coefficients, double x) {
  double result = coefficients[0];
  for (size_t i = 1; i < coefficients.size(); ++i) {
    result = result * x + coefficients[i];
  }
  return result;
}

int main() {
  std::vector<double> coefficients = {2, -6, 2, -1}; 
  double x = 3;
  double result = hornerForward(coefficients, x);
  std::cout << "The value of the polynomial at x = " << x << " is: " << result << std::endl;
  return 0;
}

递归法

Horner法则可以优雅地用递归实现，直接反映嵌套乘法结构。但是，对于非常高次的多项式，函数调用的开销可能会影响性能。

#include <iostream>
#include <vector>

double hornerRecursive(const std::vector<double>& coefficients, double x, int n) {
  if (n == 0) {
    return coefficients[0];
  } else {
    return x * hornerRecursive(coefficients, x, n - 1) + coefficients[n];
  }
}

int main() {
  std::vector<double> coefficients = {2, -6, 2, -1}; 
  double x = 3;
  double result = hornerRecursive(coefficients, x, coefficients.size() - 1);
  std::cout << "The value of the polynomial at x = " << x << " is: " << result << std::endl;
  return 0;
}

结论

本文介绍了Horner法则的三个C++实现：迭代法（反向和正向循环）和递归法。虽然递归法更优雅，但由于开销较小，迭代法通常提供更好的性能，尤其对于较大的多项式而言。最佳选择取决于应用程序的特定需求和偏好；然而，理解Horner法则对于高效的多项式求值至关重要。