试题 算法提高 牛顿迭代法求方程的根
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
【问题描述】
给定三次函数f(x)=ax3+bx2+cx+d的4个系数a，b，c，d，以及一个数z，请用牛顿迭代法求出函数f(x)=0在z附近的根，并给出迭代所需要次数。
牛顿迭代法的原理如下（参考下图）：
设xk是方程f(x)=0的精确解x*附近的一个猜测解，过点Pk(xk,f(xk))作f(x)的切线。该切线与x轴的交点比xk更接近方程的精确解程x*。
迭代公式为：xk+1= xk - f(xk)/f '(xk)，当f(x)的绝对值足够小的时候即可结束迭代。
注意：对于本题给定函数f(x)，f '(x)=3ax2+2bx+c，且当|f(x)| ≤10-7时，即可认为x是f(x)=0的根。
图略
【输入格式】
输入共2行。
第一行为4个整数，每2个数之间用一个空格隔开，分别是a，b，c，d
第二行为一个实数z。
【输出格式】
共一行。包含2个数，之间用一个空格隔开，第一个数是实数x，表示所求的根，精确到小数点后3位；第二个数是一个整数n，表示求得上述根需要的迭代次数。
【样例输入】
2 -9 5 3
3
【样例输出】
3.719 7
【提示】
程序中需要使用浮点数时，请用double类型
解题思路：话不多说，直接上代码。
AC代码如下：
#include <iostream>
#include <string.h>
#include <vector>
#include <math.h>
#include <iomanip>using namespace std;
#define N 4
const double ZERO=0.0000001;
//且当|f(x)| ≤10-7时，即可认为x是f(x)=0的根。class Formula{
public:vector<int> an;double x0; //求方程f(x)=0,在x=x0处的根Formula(){}void inputAn(){for(int i=0;i<N;i++){int x;cin>>x;an.push_back(x);}}void setAn(vector<int> tmp,int len){for(int i=0;i<len;i++)an.push_back(tmp[i]);}double getFx(double x){double sum=0;int len=an.size();for(int i=0;i<an.size();i++){int times=len-1-i;sum+=an[i]*pow(x,times);}return sum;}
};Formula Derivatives(Formula F){//获取F的导数Formula F2;F2.x0=F.x0;//F2.setAn(F.an,F.an.size()-1);vector<int> bn;int len=F.an.size();for(int i=0;i<len-1;i++){int x=F.an[i]*(len-i-1);bn.push_back(x);}F2.setAn(bn,bn.size());return F2;
}double precision(double x,int n){//保留到小数点后n位bool isNeg=false;if(x<0){isNeg=true;x=-x;}int x2=(int)(x*pow(10,n));if(double(x2+0.5)<=x*pow(10,n) )x2++;if(isNeg)x2=-x2;return (double)x2/pow(10,n);
}void getCorretX(){Formula F1,F2;//F1为f(x),F2为f(x)的导函数F1.inputAn();cin>>F1.x0;F2=Derivatives(F1);int i=1;double X2,X1;X2=X1=F1.x0;for(i=1;;i++){double curFx=F1.getFx(X2);//printf("x=%.7lf\t f(x)=%.7lf\n",X2,curFx);if(fabs(curFx)<=ZERO)break;X2=X1-(F1.getFx(X1))/(F2.getFx(X1));X1=X2;}cout<<precision(X2,3)<<" "<<i;
}int main()
{getCorretX();return 0;
}