根据视频整理, 结合视频理解效果更佳
浮点数二分模板
浮点数二分的本质也是边界, 唯一区别是浮点数没有整除, 区间长度可以严格的缩小一半
当区间长度足够小时, 便可以认为是一个数
模板
double bsearch(double l, double r) {
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求, 一般比所求精度高 2
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
题目解答
方法一
注意 r - l的取值与所求答案要求精度, 一般比要求高的 2
对正负数进行转换
代码一
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double n = in.nextDouble();
double l = 0, r = Math.abs(n); // 考虑 n为负数的情况
while (r - l > 1e-8) { // // 精度比所求精度高 2位
double mid = (l + r) / 2;
if (mid * mid * mid >= Math.abs(n)) // 不需要考虑边界问题
r = mid;
else
l = mid;
}
if (n >= 0)
System.out.println(String.format("%.6f", l)); // 保留 6位小数
else
System.out.println("-" + String.format("%.6f", l));
}
}
题目给出了查找范围, 直接在范围中进行查找
代码二
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double target = in.nextDouble();
double l = -10000, r = 10000;
while (r - l > 1e-8) { // 精度比所求精度高 2位
double mid = (l + r) / 2;
if (mid * mid * mid >= target) // 左边
r = mid; // 不需要进行 +1或者 -1
else
l = mid;
}
System.out.println(String.format("%.6f", l)); // 保留 6位小数
}
}
方法二
在 100循环中进行寻找
代码三
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double n = in.nextDouble();
double l = 0, r = Math.abs(n); // 考虑 n为 负数的情况
for(int i = 0; i < 100; i++) { // 在 100次中进行寻找
double mid = (l + r) / 2;
if (mid * mid * mid >= Math.abs(n)) // 不需要考虑边界问题
r = mid;
else
l = mid;
}
if (n >= 0)
System.out.println(String.format("%.6f", l)); // 保留 6位小数
else
System.out.println("-" + String.format("%.6f", l));
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double f = sc.nextDouble();
System.out.printf(“%.6f”,Math.cbrt(f));
}
}
你是会玩Math包的
代码1过不了0.001的用例把
个人感觉是因为:,首先只考虑n>0的情况
n>1,n的三次幂大于n
n<1,n的三次幂小于n
因此r的值不能一概而论为Math.abs(n)
整数左右区间是正常取得,-1到1之间,左右区间需要从自身取到1
第一个过不了-0.001,-0.001的三次方根是-0.1,r = Math.abs(n),使得,从0-0.001中找答案,肯定找不到,因此得设置为r = Math.abs(n+1)
啥也不会
我吐了呀,-0.001这个测试数据通不过
给r+1就好了
为什么加1可以通过呀
不需要二分,直接干就完事了
niubi
这样样例过不去啊 - 43.42过不去
能ac啊 也能出结果-3.514768
有点奇怪,我之前用这代码提交过不去,今天就可以了
直接在0~100中找应该就可以,因为最大值才10000