NOIP2001 提高组 一元三次方程求解 - C++ 牛顿迭代法详解

NOIP2001 提高组 一元三次方程求解 - C++ 牛顿迭代法详解/n/n### 题目描述/n/n有形如：$a x^3 + b x^2 + c x + d = 0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a, b, c, d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 -100 至 100 之间），且根与根之差的绝对值 $/ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2 位。/n/n提示：记方程 $f(x) = 0$，若存在 2 个数 $x_1$ 和 $x_2$，且 $x_1 < x_2$，$f(x_1) /times f(x_2) < 0$，则在 $(x_1, x_2)$ 之间一定有一个根。/n/n### 输入格式/n/n一行，4 个实数 $a, b, c, d$。/n/n### 输出格式/n/n一行，3 个实根，从小到大输出，并精确到小数点后 2 位。/n/n### 样例 #1/n/n#### 样例输入 #1/n/n/n1 -5 -4 20/n/n/n#### 样例输出 #1/n/n/n-2.00 2.00 5.00/n/n/n### 解题思路/n/n根据提示，我们可以使用牛顿迭代法来逐步逼近方程的根。/n/n具体步骤如下：/n/n1. 初始化三个变量 x1、x2、x3 分别为 -100、0、100。/n2. 根据方程计算 f(x1)、f(x2)、f(x3) 的值。/n3. 判断 f(x1) 和 f(x2) 的乘积是否小于 0，如果成立，则在 (x1, x2) 之间存在一个根。/n - 如果 f(x1) 和 f(x2) 的乘积大于 0，则更新 x1 为 x2，x2 为 x3，x3 为 x3 + 1，并重复步骤 2。/n - 如果 f(x1) 和 f(x2) 的乘积小于 0，则在 (x1, x2) 之间存在一个根。我们可以使用二分法来进一步逼近这个根。/n - 初始化 left 为 x1，right 为 x2。/n - 循环直到 right - left 小于等于 0.01。/n - 计算 mid 为 left 和 right 的平均值。/n - 计算 f(mid) 的值。/n - 如果 f(mid) 的绝对值小于等于 0.01，则将 mid 作为一个根，并结束循环。/n - 如果 f(mid) 的值大于 0，则更新 right 为 mid。/n - 如果 f(mid) 的值小于 0，则更新 left 为 mid。/n4. 重复步骤 3，直到找到三个根为止。/n5. 将三个根按照从小到大的顺序输出，并精确到小数点后两位。/n/n### 代码示例/n/nc++/n#include <iostream>/n#include <cmath>/n#include <iomanip>/n/nusing namespace std;/n/n// 计算方程的值/ndouble f(double x, double a, double b, double c, double d) {/n return a * pow(x, 3) + b * pow(x, 2) + c * x + d;/n}/n/n// 牛顿迭代法求解方程根/ndouble newton(double x, double a, double b, double c, double d) {/n double eps = 0.01; // 误差范围/n while (abs(f(x, a, b, c, d)) > eps) {/n x = x - f(x, a, b, c, d) / (3 * a * pow(x, 2) + 2 * b * x + c);/n }/n return x;/n}/n/nint main() {/n double a, b, c, d;/n cin >> a >> b >> c >> d;/n/n double x1 = -100, x2 = 0, x3 = 100;/n/n // 寻找第一个根/n while (f(x1, a, b, c, d) * f(x2, a, b, c, d) > 0) {/n x1 = x2;/n x2 = x3;/n x3 += 1;/n }/n double root1 = newton(x1, a, b, c, d);/n/n // 寻找第二个根/n x1 = x2;/n x2 = x3;/n while (f(x1, a, b, c, d) * f(x2, a, b, c, d) > 0) {/n x1 = x2;/n x2 = x3;/n x3 += 1;/n }/n double root2 = newton(x1, a, b, c, d);/n/n // 寻找第三个根/n x1 = x2;/n x2 = x3;/n while (f(x1, a, b, c, d) * f(x2, a, b, c, d) > 0) {/n x1 = x2;/n x2 = x3;/n x3 += 1;/n }/n double root3 = newton(x1, a, b, c, d);/n/n // 输出三个根，从小到大排序/n double roots[] = {root1, root2, root3};/n sort(roots, roots + 3);/n cout << fixed << setprecision(2) << roots[0] << ' ' << roots[1] << ' ' << roots[2] << endl;/n/n return 0;/n}/n/n/n### 注意事项/n/n1. 在计算方程的值时，可以使用如下公式：/n/n$$f(x) = a x^3 + b x^2 + c x + d$$ /n/n$$f'(x) = 3 a x^2 + 2 b x + c$$ /n/n2. 牛顿迭代法的更新公式为：/n/n$$x_{n+1} = x_n - /frac{f(x_n)}{f'(x_n)}$$ /n/n3. 在每次更新后，需要判断更新后的 x 是否在给定的范围内，如果超出范围，则将 x 设置为范围的边界。/n/n### 总结/n/n本题详解NOIP2001 提高组第一题 - 一元三次方程求解，使用C++语言，并采用牛顿迭代法逐步逼近方程的根。文章包含详细的解题思路、代码示例和注意事项，帮助你更好地理解和解决此类问题。/n