记录115#includebits/stdc.h using namespace std; const double eps1e-4;//浮点数会有一定的误差,epsilon浮点数比较时允许的误差范围精度容差 double a,b,c,d; double f(double x){ return a*x*x*xb*x*xc*xd; } int main(){ cinabcd; for(int i-100;i100;i){//fabs()函数浮点数的绝对值 double Li,Ri1,mid;//数1e-4 时候当它就近似是0了 if(fabs(f(L))eps) coutfixedsetprecision(2)L ;//左端点是根输出 else if(fabs(f(R))eps) continue;//右端点是根跳过,因为在下一轮循环,它是左端点(去重) else if(f(L)*f(R)0){//如果两点之间存在根 while(R-Leps){//两个界限没有重合 mid(LR)/2;//二分答案来找 if(f(mid)*f(R)0) Rmid;//向右边靠拢找 else Lmid;//向坐标左边靠拢 } coutfixedsetprecision(2)L ;//输出 } } return 0;//结束程序 }前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。题目传送门https://www.luogu.com.cn/problem/P1024突破口有形如ax3bx2cxd0 这样的一个一元三次方程。给出该方程中各项的系数a,b,c,d 均为实数并约定该方程存在三个不同实根根的范围在 −100 至 100 之间且根与根之差的绝对值 ≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)并精确到小数点后 2 位。提示记方程 f(x)0若存在 2 个数 x1​ 和 x2​且 x1​x2​f(x1​)×f(x2​)0则在 (x1​,x2​) 之间一定有一个根。 一、题目核心要求 问题本质给定一个一元三次方程f(x)ax3bx2cxd0f(x)ax3bx2cxd0已知存在三个不同的实根所有根 ∈ [−100, 100]任意两根之差的绝对值 ≥ 1关键要求从小到大输出三个实根保留两位小数✅ 这是一个数值求根问题不能用公式法卡丹公式复杂且易出错需用数值逼近方法 二、核心思路利用“根隔离” “二分法”关键提示解析若 x1x2x1​x2​ 且 f(x1)⋅f(x2)0f(x1​)⋅f(x2​)0 则 (x1,x2)(x1​,x2​) 内必有一实根。这是介值定理的直接应用函数连续 ⇒ 符号变化 ⇒ 必有零点。利用“根间距 ≥1”的性质因为任意两根距离 ≥1所以在区间长度为 1 的小区间[i, i1]中最多包含一个根不会出现多个根挤在一个小区间导致漏检 这是本题能用“步长为1扫描”的理论基础算法策略遍历所有整数区间i从 −100 到 99考察区间[i, i1]对每个区间若f(i) ≈ 0→i是根直接输出若f(i1) ≈ 0→ 跳过下一轮i1会作为左端点处理避免重复若f(i) * f(i1) 0→ 区间内有唯一根用二分法逼近由于总共只有 3 个根循环中恰好会找到 3 次按i递增顺序输出即为从小到大代码分析#includebits/stdc.h using namespace std; const double eps 1e-4; // 浮点误差容忍度eps 1e-4用于判断“是否接近0”为什么不是1e-7因为最终只需2 位小数精度1e-4足够保证四舍五入正确double a, b, c, d; double f(double x) { return a*x*x*x b*x*x c*x d; }定义多项式函数f(x)避免重复写表达式int main() { cin a b c d;读入系数均为实数for(int i -100; i 100; i) { double L i, R i 1, mid;遍历每个单位区间[i, i1]注意i从 −100 到100含但R i1最大为 101实际有效区间是[−100, 100]而根在 [−100,100] 内所以覆盖完整情况 1左端点是根if(fabs(f(L)) eps) cout fixed setprecision(2) L ;fabs(f(L)) eps判断f(L) ≈ 0直接输出L即i保留两位小数使用fixed和setprecision(2)确保格式情况 2右端点是根跳过防重复else if(fabs(f(R)) eps) continue; // 下一轮 ii1 时R 成为新的 L会被输出避免同一个根被输出两次例如根为 2.0则在i1时R2是根跳过i2时L2是根输出✅ 巧妙去重情况 3区间内有根符号变化else if(f(L) * f(R) 0) {f(L)和f(R)异号 → 中间有根while(R - L eps) { mid (L R) / 2; if(f(mid) * f(R) 0) R mid; // f(mid) 与 f(R) 同号 → 根在左半 else L mid; // f(mid) 与 f(R) 异号 → 根在右半 } 二分法细节终止条件R - L ≤ eps区间足够小更新策略若f(mid)与f(R)同号 → 说明mid和R在根的同一侧 → 根在[L, mid]→R mid否则 → 根在[mid, R]→L mid 也可以用f(L)*f(mid) 0判断左半等价。cout fixed setprecision(2) L ; } } return 0; }输出近似根L此时L ≈ R ≈ 真实根由于i从小到大遍历输出自然有序⚠️ 关键设计与易错点问题说明eps 选择1e-4足够保证两位小数正确误差 0.005去重机制右端点根跳过左端点输出避免重复根的顺序因i递增扫描找到的根自然从小到大浮点比较永远不要用比较浮点数必须用fabs(x) eps区间覆盖i到 100确保[99,100]被检查根在 [−100,100] 内全覆盖为何不用牛顿迭代或其他方法牛顿法需要导数且可能不收敛对初值敏感公式法三次方程有解析解但涉及复数运算和三角函数NOIP 环境下易出错本题特性根隔离 间距 ≥1使得简单二分扫描成为最优解稳定、可靠、易实现时间复杂度200 个区间 × log₂((1)/1e-4) ≈ 200 × 14 2800 次函数求值极快