【题解】【二分】——[NOIP 2001 提高组] 一元三次方程求解P1024 [NOIP 2001 提高组] 一元三次方程求解题目描述输入格式输出格式输入输出样例输入 #1输出 #1说明/提示1.思路解析2.AC代码P1024 [NOIP 2001 提高组] 一元三次方程求解通往洛谷的传送门题目描述有形如a x 3 b x 2 c x d 0 a x^3 b x^2 c x d 0ax3bx2cxd0这样的一个一元三次方程。给出该方程中各项的系数a , b , c , d a,b,c,da,b,c,d均为实数并约定该方程存在三个不同实根根的范围在− 100 -100−100至100 100100之间且根与根之差的绝对值≥ 1 \ge 1≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)并精确到小数点后2 22位。提示记方程f ( x ) 0 f(x) 0f(x)0若存在2 22个数x 1 x_1x1​和x 2 x_2x2​且x 1 x 2 x_1 x_2x1​x2​f ( x 1 ) × f ( x 2 ) 0 f(x_1) \times f(x_2) 0f(x1​)×f(x2​)0则在( x 1 , x 2 ) (x_1, x_2)(x1​,x2​)之间一定有一个根。输入格式一行4 44个实数a , b , c , d a, b, c, da,b,c,d。输出格式一行3 33个实根从小到大输出并精确到小数点后2 22位。输入输出样例输入 #11 -5 -4 20输出 #1-2.00 2.00 5.00说明/提示【题目来源】NOIP 2001 提高组第一题1.思路解析首先这道题需要用到一点“高中数学知识”。应该知道一元三次方程具有相应的求根公式但是由于其十分冗长且涉及复变函数这里不做讨论。我们观察一下这个函数f ( x ) a x 3 b x 2 c x d f(x)ax^3bx^2cxdf(x)ax3bx2cxd上过高中的同学应该都知道数学中“二分法求零点”的步骤前提函数f ( x ) f(x)f(x)在[ l , r ] [l,r][l,r]上连续且具有单调性记第i ii次二分时的左、右端点为l i , r i l_i,r_ili​,ri​。初始条件设定l 0 l , r 0 r l_0l,r_0rl0​l,r0​r计算中点m i l i r i 2 m_i\frac{l_ir_i}2mi​2li​ri​​判断是否找到零点若f ( m i ) 0 f(m_i)0f(mi​)0实际上常用f ( m i ) δ f(m_i)\deltaf(mi​)δ判断则m i m_imi​即为所求零点算法终止缩小区间若f ( l i ) ∗ f ( m i ) 0 f(l_i)*f(m_i)0f(li​)∗f(mi​)0零点在[ l i , m i ] [l_i,m_i][li​,mi​]内令l i 1 l i , r i 1 m i l_{i1}l_i,r_{i1}m_ili1​li​,ri1​mi​否则零点在[ m i , r i ] [m_i,r_i][mi​,ri​]内令l i 1 m i , r i 1 r i l_{i1}m_i,r_{i1}r_ili1​mi​,ri1​ri​如果你学过这些高中知识那么这道题就变成一道模拟题了。如果你是一位“神童”在考场上想出上述策略也不难。因为这道题本质上就是在一个区间[ l , r ] [l,r][l,r]查找满足f ( x ) 0 f(x)0f(x)0的x xx的值。只要你会二分也不难想到的。考虑缩小范围。由于题目限定且根与根之差的绝对值≥ 1 ≥1≥1那么区间[l,l1)中至多有一个零点需要放置另一个零点与右端点重合过左闭右开就可以在一个很小的区间[l,l1)中进行二分枚举可能的零点mid。这样题目就变成了一道简单的浮点数二分问题直接套用上面的步骤即可。这里根的范围也给出来了[-100,100]直接枚举这个范围之中的l即可。注意当零点与区间左端点重合需要特判浮点数二分不能直接判断像lr要r-leps其余的细节详见代码。2.AC代码#includebits/stdc.husingnamespacestd;#defineeps1e-4// 差值的接受范围doubleA,B,C,D;doublef(doublex){// 计算此方程得出来的值returnA*x*x*xB*x*xC*xD;}intmain(){scanf(%lf%lf%lf%lf,A,B,C,D);for(doublex-100;x100;x){// 枚举区间左端点doublelx,rx1,mid;if(fabs(f(l))eps)// 左端点是一个根printf(%.2lf ,l);elseif(fabs(f(r))eps)// 右端点是一个根continue;elseif(f(l)*f(r)0){// 在这个区间里面有根,执行二分while(r-leps){// 注意,此处判断条件不应该写成lrmid(lr)/2;if(f(mid)*f(r)0)lmid;// (mid,r)上有根elsermid;}printf(%.2lf ,mid);}}return0;}最后制作不易希望大家多多点赞收藏关注下微信公众号谢谢大家的关注您的支持就是我更新的最大动力公众号上会及时提供信息学奥赛的相关资讯、各地科技特长生升学动态、还会提供相关比赛的备赛资料、信息学学习攻略等。