首页 > 代码库 > NOIP2001 一元三次方程求解[导数+牛顿迭代法]
NOIP2001 一元三次方程求解[导数+牛顿迭代法]
题目描述
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*f(x2)<0，则在(x1，x2)之间一定有一个根。
输入输出格式
输入格式：
一行，4个实数A，B，C，D。
输出格式：
一行，三个实根，并精确到小数点后2位。
输入输出样例
输入样例#1：
1 -5 -4 20
输出样例#1：
-2.00 2.00 5.00
数据规模太小，可以随便暴力
但为了证明我这几天微积分没白学，用一个高级的方法
首先 f(x)=ax3+bx2+cx+d 求导得到 df/dx=3ax2+2bx+c
求这个导数的零点(就是二次函数求根公式了)得到f(x)的最值点
最值点组成的三个区间一定各有一个f(x)零点，使用牛顿迭代法求得这个零点即可
牛顿迭代法就是不停的用一个点的切线拟合曲线，那个点的导数就是切线斜率
依次类推，可以得到求高次函数零点的一种迭代法：
求n次函数零点，需要极值点来划分区间，也就需要求其导数(n-1次函数)的零点，依次迭代到n=2直接通过公式(当然n=3或4也可以)
最后的复杂度依赖于求零点算法的复杂读
貌似没有人发表过，那么就叫Candy迭代法吧
不过这和三分法求极值相比有优势吗?
//// main.cpp// 一元三次方程//// Created by Candy on 2016/12/10.// Copyright © 2016年 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const double eps=1e-3;double a,b,c,d;inline double f(double x){return ((a*x+b)*x+c)*x+d;}inline double df(double x){return (3*a*x+2*b)*x+c;}double sol(double l,double r){//printf("sol %lf %lf\n",l,r); int step=20;double x=(l+r)/2; while(step--){ x=x-f(x)/df(x); } return x;}int main(int argc, const char * argv[]) { scanf("%lf%lf%lf%lf",&a,&b,&c,&d); double p1=(-sqrt(b*b-3*a*c)-b)/(3*a), p2=(+sqrt(b*b-3*a*c)-b)/(3*a); printf("%.2f %.2f %.2f\n",sol(-100,p1),sol(p1,p2),sol(p2,100)); return 0;}
NOIP2001 一元三次方程求解[导数+牛顿迭代法]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。