时间戳

首页 > 解决方案 > 霍纳算法在 C++ 中的实现

c++ - 霍纳算法在 C++ 中的实现

问题描述

实现确定多项式值的霍纳算法。输入数据应作为程序参数给出：多项式系数和值。

下面是一个示例调用：/horner 1.0 2.2 -3.3 7.0

-145.3

计算 W (7.0) 的值，其中 W (x) = 1.0 + 2.2x ^ 1-3.3x ^ 2

转这个：

double Horner(int n, double A[], double x0)
{
  double w;

  w = A[n];
  for (int i = n - 1; i >= 0; i--)
    w = w * x0 + A[i];
  return w;
}

进入带有指针和字符的代码，所以它看起来像任务示例。w=A[n];如果代码朝着正确的方向发展，请坚持 下去。到目前为止我得到了什么：

int main(int argc, char *argv[])
{
  int n = argc - 3;
  double x0 = atof(argv[argc - 1]);
  double *A = new double[n + 1];

  for (int i = 0; i <= n; i++)
  {
    A[i] = atof(argv[i + 1]);
  }
  double w;
  w=A[n]; 
  for(int k =n; k>=0; k=k-1) {
    w=w*x0+A[k];
  }
  cout << w;
  delete[] A;
  return 0;
}

标签： c++

解决方案

假设在第一个片段中使用参数调用函数n = 2，A[] = {1.0, 2.2, -3.3}并且x0 = 7.0，如果我们跟踪它的执行，我们会发现：

w = A[n] = A[2] = -3.3
i = n - 1 = 1  // <----- Note this.
w = w * x0 + A[1] = -3.3 * 7.0 + 2.2 = -20.9
w = w * x0 + A[0] = -20.9 * 7.0 + 1.0 = 145.3

但是，在第二个片段中，idices 差了一个。

int n = argc - 3;

让我们假设命令行是/horner 1.0 2.2 -3.3 7.0，如 OP 所述，其中最后一个数字表示x0，其他数字是多项式的系数。该公式为其度数提供了正确的值（2，在一个完美的世界中，用户总是以所需的确切顺序键入正确数量的值）。

系数 和w已正确初始化，但是接下来的循环从错误的索引开始（它应该跳过最后一个，已经用于初始化w）。

for( int k = n; k >= 0; k = k - 1) {
//       ^^^^^
    w = w * x0 + A[k];
}

推荐阅读