迹忆客 专注技术分享

Horner 规则是一种计算多项式值的有效算法。

考虑 x = 4 处的多项式 p(x) = 6x^3 - 2x^2 + 7x + 5。要使用 C++ 中的Horner法则计算它，第一个系数 6 乘以 x 处的值，即 4 ，并且两者的乘积为 24，被添加到下一个系数 -2。

结果乘以 4 并加到下一个系数。

对等式中的系数个数重复该过程。 剩下的最终产品是多项式的值。

本文通过将上述规则转换为计算机代码，说明如何使用 C++ 中的Horner规则求多项式的值。

让我们考虑一个多项式：

如果 x = 4，则多项式的值为 385。

通过向后迭代循环，在 C++ 中使用 Horner 规则求多项式的值

让我们看一下在 C++ 中使用 Horner 规则通过反向循环查找多项式值的程序。

1. 第一行代码导入库包iostream； 在第二行中，命名空间被定义为 std。
2. 使用三个参数创建方法 int Horner() - 将传递系数列表的指针数组 a、存储多项式次数的整数变量 n 和另一个存储多项式在 x 处的值的整数变量 x。

   int Horner(int* a, int n, int x)
   

3. 这解释了如何将多项式的乘积相加。 创建一个整型变量 result，用数组 a[n] 的最后一个元素初始化。

   int result = a[n];
   

   注意：不要误认为是数组的大小； 它用数组 a 中第 n 个位置的元素初始化变量 result。
4. 创建一个 for 循环，从数组 a 的最后一个元素到第 0 个索引反转循环。 每次循环迭代都会更新结果变量的值。

   for (int i = n - 1; i >= 0; --i)
   

   在第一次迭代中，a[n] 的值乘以 x，然后添加到数组中的前一个元素 - a[n-1]。 对于数组 - {2,3,4}，循环将取最后一个元素 a[n]，即 4，将其与 x 相乘，然后添加到数组的 n-1 个元素，即 3。 因此，在主函数中初始化时需要反转系数。 结果的值在方法结束时返回。
5. 在 main 函数内部，创建了一个数组以将其传递给方法 Horner 的第一个参数。 请注意，数组内系数的值是相反的，因为循环向后迭代。
6. 创建一个整数变量 sol 来存储从名为 Horner 的方法返回的结果。 在第一个参数中，传递了正在创建的数组。 第二个参数传递方程中多项式的次数，3，传递x处的第三个参数值。

   int sol = Horner(arr, 3, 4);
   

完整代码:

#include <iostream>
using namespace std;
int Horner(int* a, int n, int x)
{
    int result = a[n];
    for (int i = n - 1; i >= 0; --i)
        result = result * x + a[i];
    return result;
}

int main() {
    int arr[4] = {5,7,-2,6};
    int sol = Horner(arr, 3, 4);
    cout << sol;
}

输出（C++ 中的反向循环 Horner 规则）：

385

通过向前迭代循环在 C++ 中使用 Horner 规则求多项式的值

如果我们需要向前运行循环，与上一个示例不同，我们可以取消引用数组的指针以获取其第一个元素并向前运行循环而不是反向运行循环。 这是在 C++ 中使用循环来实现 Horner 规则的另一种方法。

让我们了解代码的作用：

1. 第一行代码导入库包 iostream 。
2. 与前面的示例类似，使用三个参数创建了一个 Horner 方法。

   int Horner(int a[], int n, int x)
   

3. 通过取消引用指针，使用数组的第一个元素创建并初始化变量结果。 指针*a和写 arr[0] 是一样的。

   int result = *a;
   

   在前面的例子中，方法 Horner 需要一个大小组件附加到它的数组：int result = a[n]; 指向最后一个元素。 在这里，它只是取消引用。
4. 创建一个从 1 迭代到 n 的 for 循环。 在每次迭代中，结果变量的值都会用多项式的值更新。 结果的值在方法结束时返回。

   for (int i = 1; i < n; i++)
    result = result * x + a[i];
   return result;
   

5. 在 main 函数中，使用系数的值创建了一个数组。 这里使用的多项式是： $$p(x) = 5x^4 + 3x^3 - 2x^2 + 4x - 6; x=-2$$

   该数组是通过取多项式的系数创建的 - int arr[] = {5,3,-2,4,-6};。

6. 变量 n 保存多项式的次数。 n 的值计算如下： n = 数组的大小 -1。

   int n = (*(&arr + 1) - arr)        -    1;
   //  n =      size of the array            -   1;
   

   通过传递数组、n 的值和 x 处的值来调用 Horner 方法。 返回的结果存储在一个新的整数变量中并打印出来。

   int sol = Horner(arr, n, -2);
   std::cout << "Value of polynomial = " << sol;
   

完整代码:

#include <iostream>
int Horner(int a[], int n, int x)
{
    int result = *a;
    for (int i = 1; i < n; i++)
        result = result * x + a[i];
    return result;
}

int main() {
    int arr[] = {5,3,-2,4,-6};
    int n = (*(&arr + 1) - arr)-1;
    int sol = Horner(arr, n, -2);
    std::cout << "Value of polynomial = " << sol;
}

输出（C++ 中的前向循环 Horner 规则）：

Value of polynomial = -20

在 C++ 中使用 Horner 规则使用递归求多项式的值

到目前为止，我们已经学习了如何在 C++ 中使用 Horner 规则求多项式的值。 它是通过迭代循环并使用累加器变量更新计数来完成的。

在这个例子中，多项式的值是通过递归计算的。 让我们看一下代码。

1. 第一行代码导入包 iostream 并将命名空间定义为 std。

   #include <iostream>
   using namespace std;
   

2. 创建了一个 Horner 方法，它具有三个参数 - 一个指针整数 *pi，另一个整数变量 degree，它是多项式的次数（在前面的示例中用作 n），以及用于在 x 处传递值的 x。

   int Horner(int* pi, int degree, int x)
   

3. 递归函数的特点是像循环一样不断调用自己，直到满足一个条件，这样就降低了时间复杂度。 对于条件，仅当度数的值减少到 0 时，if 语句才返回第 0 个索引处的 pi 值。

   if (degree == 0)
   {
   return pi[0];
   }
   

4. 为了应用递归，再次调用 Horner 方法而不是返回值。

   return Horner(pi, degree - 1, x) * x + pi[degree];
   

   上述语法使 Horner 方法针对多项式的次数重复调用自身。 在等式中，多项式的次数是它的最高指数。 如果考虑上一个示例中使用的等式：
   $$p(x) = 5x^4 + 3x^3 - 2x^2 + 4x - 6; x=-2$$

   多项式的次数为 4。

   这意味着递归将自身迭代 n+1 = 5 次（数组的大小）。 在每次迭代中，该方法将调用自身，直到度数的值减少到 0。

   一旦它达到 0，递归将采用 *p[0] 元素并将其传递给其先前的方法调用。

   return Horner(pi, degree - 1, x) * x + pi[degree];
   

5. 在 main 函数内部，创建了一个整数数组以将方程的系数传递给 Horner 方法。 然后将参数的值传递给方法。

   int sol = Horner(arr, 4, -2);
   

   该数组为 arr，度数为 - 4，x 处的值为 -2。
6. 最后，将返回的结果存储在整数变量 sol 中并打印出来。

完整代码:

#include <iostream>
using namespace std;

int Horner(int* pi, int degree, int x)
{
    if (degree == 0)
    {
        return pi[0];
    }
    return Horner(pi, degree - 1, x) * x + pi[degree];
}
int main() {
    int arr[] = { 5,3,-2,4,-6 };
    int sol = Horner(arr, 4, -2);
    cout << "Value of Polynomial using recursion = " << sol;
}

输出如下:

Value of Polynomial using recursion = 34

总结

本文介绍如何在 C++ 中使用 Horner 规则求多项式的值。 这三种方法具有不同的时间复杂度，这对于读者来说是一个很好的学习工具。

建议尝试自己编写代码，然后回来获取提示。 读者将很容易理解在 C++ 中使用 Horner 规则求多项式值的概念。