集訓(xùn)隊作業(yè)解題報告

1、題目來源Ural 1503 Polynomial問題描述求解一元 n 次方程的 n 個根。（重根重復(fù)輸出） n5算法求出 f(x)的導(dǎo)函數(shù) f(x)=0 的實根，設(shè)共有 k 個實根 x1、x2xk，對于每一對相鄰的極點 xt、xt+1，若 f(xt)f(xt+1)0 則二分法尋找區(qū)間xt,xt+1中的唯一解。若 f(xt)f(xt+1)0則在區(qū)間xt,xt+1中無解。其中，t=0,2k，xk+1=+，當(dāng) n 為奇數(shù) x0=-，當(dāng) n 為奇數(shù)x0=+。f(x)=0 的根同樣方法遞歸求解。yX3=+X1xX2X0= -算法證明熟知，xt,xt+1都是函數(shù) f(x)的單調(diào)區(qū)間。則在這些區(qū)間中，每個至

2、多只有唯一解。故沒有 f(x)的事跟會被遺漏，從而只需證明：f(x)的重根計算次數(shù)都正確。當(dāng) y0 是 f(x)的一個一重根，則 y0 一定不是 f(x)=0 的實根，故 y0 只屬于上面這些區(qū)間中的一個。所以 y0 只被統(tǒng)計了一次。當(dāng) y0 是 f(x)的一個 s 重根，則 y0 一定是 f(x)的一個 s-1 重根，不妨設(shè) y0=xt=xt+1=xt+s-2。故 y0 同時屬于xt-1,xt,xt,xt+1xt+s-2,xt+s-1，所以y0 恰好被統(tǒng)計了 s 次。算法實現(xiàn)此外定義 zero=2e-8，避免相等比較時的精度誤差。對于區(qū)間xt,xt+1，若 xt=0 或 xt+1=0，則xt

3、,xt+1 就是這個區(qū)間中的根，不再用二分法求解（否則實數(shù)計算誤差可能導(dǎo)致遺漏這個解）。重根區(qū)間中唯一解區(qū)間中二分源代碼const maxn=10; zero=2e-8;var a,b:array0.maxn,0.maxnof extended;n,i,t:longfunction f(k:long;x:extended):extended;var i:longbegin; s:extended;s:=ak,n-k;for i:=n-k-1 downto 0 do s:=s*x+ak,i; if abs(s)1 then exit(s);if s0 then f:=-1 else f:=1;

4、end;function sqt(x:extended;n:long):extended; beginif abs(x)zero then exit(0); x:=abs(x); sqt:=exp(ln(x)/n);end;procedure solve(k:long;var s:long);var ss,i:long;l,r,mid,f1,f2,ff:extended; beginif k=n-1 then begin s:=1;if abs(ak,0)zero then continue;abs(f1)1e-10 then begin inc(s); bk,s:=bk+1,i; conti

5、nue; end; abs(f2)zero do beginmid:=(r+l)/2; ff:=f(k,mid);iend;*f10 then l:=mid else r:=mid;inc(s); bk,s:=(l+r)/2;end;for i:=1 to send;f abs(bk,i)5e-7 then bk,i:=0;beginreadln(n); for while a0,n=0 solve(0,t);for i:=1 to ti:=0 to n do readln(a0,n-i);do dec(n);f abs(b0,i)zero then b0,i:=0;for i:=1 to t

6、 do wriend.n(b0,i:6:6);原題描述：1503. PolynomialTime Limit: 1.0 secondMemoryLimit: 16 MBEvery New Russian wants to give education, in particular. For exhis children all the best. The best le, Kolyan has asked the math teacherto teach his son to solve not only quadratic equations, but also cubicones, and

7、 quaternary The teacher knows solved in radicals fifth degree is alsoones, and altogether all the equations there are.t equations of degrees highern five cannot beeral form. But to solve equations up to thevery hard. It is better to checksolutions using acomputer. Hereyour help is needed.Inputcontai

8、ns the degree of a polynomial N(1 N 5). In100, a0 0). TheThelinethe next N + 1 lines there areegers (-100 ai i+2nd line contains thecoefficient of the polynomial a xn +0+ an.ithn1a1x+ OutputOutput all real roots of the polynomial takingo account theirmultiplicity. The roots must be givenhe ascending order. The accuracyn 106.must