数的三次方根(二分查找的应用)

简介: 数的三次方根(二分查找的应用)

题目描述:

给定一个浮点数 n,求它的三次方根。

输入格式

共一行,包含一个浮点数 n。

输出格式

共一行,包含一个浮点数,表示问题的解。

注意,结果保留 6位小数。

数据范围

−10000≤n≤10000

输入样例:

1000.00

输出样例:

10.000000

题目分析:

关键点

1、查找n的三次方根,本质是查找一个数。

2、浮点数的查找

3、保留6位小数

分析

1、查找一个数,所以想到二分法。二分法最直接的应用就是在确定精度下的查找

2、浮点数,所以在应用二分法时,和整数的处理不同

3、保留6位小数,所以while循环退出的条件确立

4、整数的二分查找一定会找到确定的一个数,而浮点数的二分查找不会找到确定的数吗,而是在精度要求内找到一个近似值

核心代码分析:

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
//问题1
double r=100;
double l=-100;
int main(){
    double n=0;
    cin>>n;
    while(r-l>1e-8){//问题2
        double mid=(r+l)/2;//问题3
        if(pow(mid,3)>n)
            r=mid;
        else
            l=mid;
    }
    cout<<fixed<<setprecision(6)<<l<<endl;//问题4

问题1:

由于是浮点数的二分法,所以变量需要是double类型

问题2:

主要针对的是分析3中的问题保留6位小数。首先保留6位小数,所以至少要是1e-6,但是由于保留6位,<1e-6本身取不到1e-6,所以需要1e-7。又由于1e-7在计算机内部是由1e-8舍入来的,所以第七位本身是不准确的,再舍入到六位小数时会导致更不准确。所以这里往后取两位,取到10的负八位,此时第八位不准确但是第七位是准确的,舍入到第六位仍然准确。

问题3:

对于浮点数的二分法和整数的不同。整数会出现+1或者-1,因为其变化都是以1为单位的,所以mid只会在其中一边,另一边不包括mid。如下图:

但是对于浮点数的二分法,紧贴这mid两边的结果都可能是所要查找的答案,所以它的情况是如下图所示:

 

问题4:

iomanip库中的c++格式化输出方法

最后:

喵又来求赞啦~~

相关文章
|
4月前
|
算法 测试技术 C#
【单调队列】LeetCode1499:满足不等式的最大值
【单调队列】LeetCode1499:满足不等式的最大值
【单调队列】LeetCode1499:满足不等式的最大值
|
5月前
杨氏矩阵( 时间复杂度要求小于O(N) )
有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在,且程序的时间复杂度要小于O(N);
|
5月前
|
算法 测试技术 C#
C++前缀和算法的应用:统计中位数为 K 的子数组
C++前缀和算法的应用:统计中位数为 K 的子数组
|
7月前
|
算法
【算法专题突破】二分查找 - x 的平方根(18)
【算法专题突破】二分查找 - x 的平方根(18)
37 0
|
4月前
|
算法 测试技术 C#
二分查找|前缀和|滑动窗口|2302:统计得分小于 K 的子数组数目
二分查找|前缀和|滑动窗口|2302:统计得分小于 K 的子数组数目
|
4月前
leetcode-6118:最小差值平方和
leetcode-6118:最小差值平方和
21 0
|
5月前
|
算法 测试技术 C#
C++ 算法:区间和的个数
C++ 算法:区间和的个数
|
5月前
|
机器学习/深度学习 算法 测试技术
C++二分算法: 找出第 K 小的数对距离
C++二分算法: 找出第 K 小的数对距离
|
10月前
|
算法
【二分查找】数的范围/数的三次方根
【二分查找】数的范围/数的三次方根
【二分查找】数的范围/数的三次方根
|
11月前
二分法求三次方根
二分法求三次方根
43 0