Codevs 1038 一元三次方程求解 NOIP 2001(導(dǎo)數(shù) 牛頓迭代)

2019-11-11 05:29:43

字體：大中小

供稿：網(wǎng)友

1038 一元三次方程求解 2001年NOip全國聯(lián)賽提高組時(shí)間限制: 1 s 空間限制: 128000 KB 題目等級(jí) : 白銀 Silver 題目描述 Description 有形如：ax3+bx2+cx+d=0 這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a，b，c，d 均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對(duì)值>=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后2位。提示：記方程f(x)=0，若存在2個(gè)數(shù)x1和x2，且x1

/*導(dǎo)數(shù)+勘根定理+牛頓迭代.先對(duì)函數(shù)求導(dǎo),f'(x)=3ax^2+2*bx+c.然后直接求根公式求f'(x)=0的點(diǎn),也就是函數(shù)極點(diǎn).(我們可以順便求一下凸形函數(shù)極值hhh)這題保證有三個(gè)不定根,所以有兩個(gè)單峰. 我們分別設(shè)這兩個(gè)點(diǎn)為p,q.然后顯然的必有三個(gè)根分別在[-100,p),[p,q],(q,100]三個(gè)區(qū)間內(nèi)(兩極點(diǎn)間必定存在零點(diǎn),勘根定理).然后用神奇的牛頓迭代法多次迭代就好了.證明請(qǐng)自行百度,本蒟蒻只能感性的認(rèn)識(shí)orz.*/#include<iostream>#include<cstdio>#include<cmath>#define eps 1e-4using namespace std;double x1,x2,x3,a,b,c,d;double f(double x){return a*x*x*x+b*x*x+c*x+d;}double df(double x){return 3*a*x*x+2*b*x+c;}double slove(double l,double r){ double x,x0=(l+r)/2; while(abs(x0-x)>eps) x=x0-f(x0)/df(x0),swap(x0,x); return x;}int main(){ cin>>a>>b>>c>>d; double p=(-b-sqrt(b*b-3*a*c))/(3*a); double q=(-b+sqrt(b*b-3*a*c))/(3*a); x1=slove(-100,p),x2=slove(p,q),x3=slove(q,100);