数的三次方根--二分 审核通过

Horizon 摸鱼 2024-02-25 21:01:17 2024-04-18 10:42:48 22

给刚刚学习二分的同学讲解一下,为什么这题使用二分?

1.单调性

题目对应数学函数为f(x) = x^3,该函数在整个作用域范围内为单调递增。

那么,如果中间值的 3 次方小于目标值,那么答案肯定在中间值左侧区间;反之,则肯定在右侧区间。

据此,我们可以通过比较中间值的 3 次方和目标值来决定搜索的方向。

2.有界性

对于正数,它的 3 次方根一定在 0 到它本身之间。

对于负数,它的 3 次方根一定在它本身到 0 之间。这为二分查找提供了明确的搜索范围。

3.高效性

二分法通过不断缩小搜索范围,每次将搜索空间减半,因此可以快速收敛,逼近答案范围。

相比于其他方法,二分法通常具有更好的时间复杂度,尤其在需要高精度计算时表现更为出色。

4.精度问题

答案范围是浮点数构成的序列,我们在求解三次方根的时候(尤其这个三次方根不是整数的时候),其解一定是浮点数。

考虑到浮点数的精度问题,我们难以使用枚举或者搜索来控制小数位后规律变化,同样也就难以实现将每一种情况都完全遍历。

那么我们使用合法范围的数据不断尝试逼近目标值,当查找范围内任意两点达到我们设置的误差值内时,即认为找到解。

以上!我们选择二分比较合理高效。

核心代码

1.确定二分范围

记n变量代表目标值

当 ,查找范围在 之间

当 ,查找范围在 之间

if (n > 0) 
    l = 0, r = n;
else 
    l = n, r = 0;

2.check 函数

检查中间值,与目标值之间的关系,并对应收敛范围。

bool check(double x) {
	return x*x*x > n;
}

3.二分模板

进入二分的条件:左右边界差尚未达到误差值

进入二分后:

检查 mid 是否满足上述查找需求,根据返回值划分左右区域并收敛一半。

注意:移动左右边界时,无法像整数的形式一样加 1 或者减 1,那么我们就移动到 mid 位置即可。

while (r-l >= 1e-8) {  //开始二分 
	mid = (l+r)/2; //求中间值
	if (check(mid)) { //判断答案满足要求 
		r = mid;  //移动右边界
	} else {  //此时,中间值3次方<=当前目标值,那么左端点也可能为答案
		l = mid, ans = l;  //移动左边界并记录答案
	}
}

接下来只需要补全代码完成输入输出即可。

{{ vote && vote.total.up }}

共 5 条回复

Horizon 摸鱼

好的 多谢啦

root 站长

我帮你把这个改到题解区哈~

Horizon 摸鱼

@root 多谢站长指导哈哈

root 站长

数字,字母和汉字之间加空格

root 站长

写的很好啊,赵老师