#AcWing系列课程Level-2笔记——4. 浮点数二分算法
2024-09-05 19:30:57
一、浮点数二分算法
1.1 编写浮点数二分,记住下面的内容,代码也就游刃有余了!
(1) 首先找到数组的中间值,mid=(left+right)>>1,区间[left, right]被划分成[left, mid]和[mid , right]。
(2) 然后通过check(mid)判断中间值是不是满足这个性质,保证落到区间里就对了,check是根据不同的题型编写的。
(3) 最后就能使用折半,缩小区间了,当认为区间已经很小的时候,比如<=10^-6,其实就找到了答案。
二、浮点数二分算法的核心
2.1 浮点数二分的本质也是边界
2.2 浮点数二分因为没有整除,每次都可以严格的缩小一半,所以不需要处理边界,相对简单
三、浮点数二分算法的代码模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)//如果让你保留四位小数,则eps写成1e-6;如果是保留五位小数,则eps写成1e-7
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;//不需要处理边界了
}
return l;
}
最新文章
- xdebug所有相关方法函数详解(中文翻译版)
- HR函数学习03——维护信息类型1008
- Python源代码目录组织结构
- SharePoint 2013 Nintex Workflow 工作流帮助(二)
- 跟我一起玩转FineUI之嵌套表格
- RSS阅读器(一)——dom4j读取xml(opml)文件
- Eclipse 配置SSH 详解
- ZOJ 1091 (HDU 1372) Knight Moves(BFS)
- Microsoft HoloLens 技术解谜(上)
- SuperSocket应用之FTP源码解析
- ubuntu16.04, Matlab2016b caffe编译安装
- Hive管理表,外部表及外部分区表的深入探讨
- SpringBoot2 集成三种连接池 c3p0 hikari druid
- Ubuntu下安装MySQL及简单操作
- C博客作业03—函数
- 使用引用类型变量来访问所引用对象的属性和方法时,Java 虚拟机绑定规则
- Python【yagmail】模块发邮件
- hdu 3389 阶梯博弈
- 几行JavaScript代码搞定Iframe 自动适应
- 最全android Demo