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-;
double a,b,c,d;
inline double f(double x){return ((a*x+b)*x+c)*x+d;}
inline double df(double x){return (*a*x+*b)*x+c;}
double sol(double l,double r){//printf("sol %lf %lf\n",l,r);
int step=;double x=(l+r)/;
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-*a*c)-b)/(*a),
p2=(+sqrt(b*b-*a*c)-b)/(*a);
printf("%.2f %.2f %.2f\n",sol(-,p1),sol(p1,p2),sol(p2,));
return ;
}

上一篇:Kettle提高表输出写入速度(每秒万条记录)


下一篇:基于visual Studio2013解决C语言竞赛题之0422牛顿迭代法