陕西专业做网站站长素材网

【题目来源】
https://www.acwing.com/problem/content/792/

【题目描述】
给定一个浮点数 n，求它的三次方根。

【输入格式】
共一行，包含一个浮点数 n。

【输出格式】
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。

【数据范围】
−10000≤n≤10000

【输入样例】
1000.00

【输出样例】
10.000000

【算法分析】
二分查找，也称为折半查找，是一种高效的查找方法。它基于分治策略，利用数据的有序性，每次将搜索范围缩小一半，直至找到目标元素或搜索区间为空。二分查找要求必须采用顺序存储结构，且其中的元素按关键字有序排列。

整数二分的经典模板如下：
模板一（从大到小查找结论 ←）：当我们将区间 [le, ri] 划分成 [le, mid] 和 [mid+1, ri] 时，其更新操作是 ri=mid 或者 le=mid+1，计算 mid 时不需要加 1（ 见下文代码中的 int mid=(le+ri)>>1; ）。

void BinarySearch(vector<int> v,int target) {int le=0;int ri=v.size();while(le<ri) {int mid=(le+ri)>>1;if(v[mid]<target) le=mid+1;else ri=mid;}
}

模板二（从小到大查找结论 →）：当我们将区间 [le, ri] 划分成 [le, mid-1] 和 [mid, ri] 时，其更新操作是 ri=mid-1 或者 le=mid，此时为了防止死循环，计算 mid 时需要加 1（ 见下文代码中的 int mid=(le+ri+1)>>1; ）。

int BinarySearch(vector<int> v,int target) {int le=0;int ri=v.size();while(le<ri) {int mid=(le+ri+1)>>1;if(v[mid]<target) le=mid;else ri=mid-1;}
}

浮点数二分的经典模板如本题代码所示。
因为浮点数的精度很高，只需要逐渐逼近题目要求的精度就可以了。这里需要注意的是，需要预先设定一个阈值 eps，一般是比题目的精度还要高 2 位，比如题目要求的精度是1e-6，那么就可以设eps=1e-8。

【算法代码】

#include <bits/stdc++.h>
using namespace std;double le=-100000;
double ri=100000;int main() {double x;cin>>x;while(ri-le>1e-8) {double mid=(le+ri)/2;if(mid*mid*mid<x) le=mid;else ri=mid;}printf("%.6f",ri);return 0;
}/*
in:1000.00
out:10.000000
*/

【参考文献】
https://www.acwing.com/solution/content/17974/
https://www.acwing.com/video/232/