在 C++ 中使用 Horner 规则求多项式的值
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 规则通过反向循环查找多项式值的程序。
- 第一行代码导入库包iostream; 在第二行中,命名空间被定义为 std。
-
使用三个参数创建方法 int Horner() - 将传递系数列表的指针数组 a、存储多项式次数的整数变量 n 和另一个存储多项式在 x 处的值的整数变量 x。
int Horner(int* a, int n, int x)
-
这解释了如何将多项式的乘积相加。 创建一个整型变量 result,用数组
a[n]
的最后一个元素初始化。int result = a[n];
-
创建一个 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。 因此,在主函数中初始化时需要反转系数。 结果的值在方法结束时返回。 - 在 main 函数内部,创建了一个数组以将其传递给方法 Horner 的第一个参数。 请注意,数组内系数的值是相反的,因为循环向后迭代。
-
创建一个整数变量 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 规则的另一种方法。
让我们了解代码的作用:
-
第一行代码导入库包
iostream
。 -
与前面的示例类似,使用三个参数创建了一个 Horner 方法。
int Horner(int a[], int n, int x)
-
通过取消引用指针,使用数组的第一个元素创建并初始化变量结果。 指针
*a
和写arr[0]
是一样的。int result = *a;
int result = a[n];
指向最后一个元素。 在这里,它只是取消引用。 -
创建一个从 1 迭代到 n 的 for 循环。 在每次迭代中,结果变量的值都会用多项式的值更新。 结果的值在方法结束时返回。
for (int i = 1; i < n; i++) result = result * x + a[i]; return result;
-
在 main 函数中,使用系数的值创建了一个数组。 这里使用的多项式是:
该数组是通过取多项式的系数创建的 -
int arr[] = {5,3,-2,4,-6};
。
-
变量 n 保存多项式的次数。 n 的值计算如下: n = 数组的大小 -1。
int n = (*(&arr + 1) - arr) - 1; // n = size of the array - 1;
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 规则求多项式的值。 它是通过迭代循环并使用累加器变量更新计数来完成的。
在这个例子中,多项式的值是通过递归计算的。 让我们看一下代码。
-
第一行代码导入包 iostream 并将命名空间定义为 std。
#include <iostream> using namespace std;
-
创建了一个 Horner 方法,它具有三个参数 - 一个指针整数
*pi
,另一个整数变量 degree,它是多项式的次数(在前面的示例中用作 n),以及用于在 x 处传递值的 x。int Horner(int* pi, int degree, int x)
-
递归函数的特点是像循环一样不断调用自己,直到满足一个条件,这样就降低了时间复杂度。 对于条件,仅当度数的值减少到 0 时,if 语句才返回第 0 个索引处的 pi 值。
if (degree == 0) { return pi[0]; }
-
为了应用递归,再次调用 Horner 方法而不是返回值。
return Horner(pi, degree - 1, x) * x + pi[degree];
多项式的次数为 4。
这意味着递归将自身迭代 n+1 = 5 次(数组的大小)。 在每次迭代中,该方法将调用自身,直到度数的值减少到 0。
一旦它达到 0,递归将采用
*p[0]
元素并将其传递给其先前的方法调用。return Horner(pi, degree - 1, x) * x + pi[degree];
-
在 main 函数内部,创建了一个整数数组以将方程的系数传递给 Horner 方法。 然后将参数的值传递给方法。
int sol = Horner(arr, 4, -2);
- 最后,将返回的结果存储在整数变量 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 规则求多项式值的概念。
相关文章
在 C++ 中通过掷骰子生成随机值
发布时间:2023/04/09 浏览次数:169 分类:C++
-
本文解释了如何使用时间因子方法和模拟 C++ 中的掷骰子的任意数方法生成随机数。了解它是如何工作的以及它包含哪些缺点。提供了一个 C++ 程序来演示伪数生成器。
在 C++ 中使用模板的链表
发布时间:2023/04/09 浏览次数:158 分类:C++
-
本文解释了使用模板在 C++ 中创建链表所涉及的各个步骤。工作程序演示了一个链表,该链表使用模板来避免在创建新变量时声明数据类型的需要。
在 C++ 中添加定时延迟
发布时间:2023/04/09 浏览次数:142 分类:C++
-
本教程将为你提供有关在 C++ 程序中添加定时延迟的简要指南。这可以使用 C++ 库为我们提供的一些函数以多种方式完成。
在 C++ 中创建查找表
发布时间:2023/04/09 浏览次数:155 分类:C++
-
本文重点介绍如何创建查找表及其在不同场景中的用途。提供了三个代码示例以使理解更容易,并附有代码片段以详细了解代码。
如何在 C++ 中把字符串转换为小写
发布时间:2023/04/09 浏览次数:63 分类:C++
-
介绍了如何将 C++ std::string 转换为小写的方法。当我们在考虑 C++ 中的字符串转换方法时,首先要问自己的是我的输入字符串有什么样的编码
如何在 C++ 中确定一个字符串是否是数字
发布时间:2023/04/09 浏览次数:163 分类:C++
-
本文介绍了如何检查给定的 C++ 字符串是否是数字。在我们深入研究之前,需要注意的是,以下方法只与单字节字符串和十进制整数兼容。
如何在 c++ 中查找字符串中的子字符串
发布时间:2023/04/09 浏览次数:65 分类:C++
-
本文介绍了在 C++ 中检查一个字符串是否包含子字符串的多种方法。使用 find 方法在 C++ 中查找字符串中的子字符串
如何在 C++ 中把字符串转换为 Char 数组
发布时间:2023/04/09 浏览次数:107 分类:C++
-
本文介绍了在 C++ 中把字符串转换为 char 数组的多种方法。使用 std::basic_string::c_str 方法将字符串转换为 char 数组