题目描述
给定一个浮点数n,求它的三次方根。
输入格式
共一行,包含一个浮点数n。
输出格式
共一行,包含一个浮点数,表示问题的解。
注意,结果保留6位小数。
数据范围
−10000≤n≤10000
样例
输入样例:
1000.00
输出样例:
10.000000
实数二分法
用实数的二分法不断地取中值
然后我们判断他缩小范围的标准就是
mid的三次方判断是否大于或等与原数n
大了就说明根的范围在[l,mid]
小了就说明在[mid,r]上
不断缩小范围
当范围r-l的长度小于0.0000001时
退出循环
返回l即为其三次方根
注意这个是求正数的
所以我们需要在之前判断输入的数是否大于零
小于0的认为加符号
然后再在输出的时候带上符号(三次方同符号);
时间复杂度分析:时间复杂度应该是同二分法的复杂度O(logn);
C++ 代码
#include <iostream>
using namespace std;
double n;
const double e=0.000000001;
double bsearch_3(double l,double r){
double res=r;
while((r-l)>e){//跳出条件(求精确度)
double mid= (l+r)/2;
if(mid*mid*mid>=res) r=mid;//判断并缩小范围
else l=mid;
}
return l;
}
int main(){
cin>>n;
if(n>=0&&n>=1){
double res= bsearch_3(0,n);
printf("%.6f",res);
} else if(n<0&&n<=-1){
double res= bsearch_3(0,-n);
printf("%.6f",-res);
}else if(n<0&&n>-1){//特判它是否是(-1,0),如果是则它的三次方根取值是在-1-n得
double res= bsearch_3(-1,n);
printf("%.6f",res);
}else{
double res= bsearch_3(-1,-n);
printf("%.6f",-res);
}
return 0;
}
大佬,是不是-1到1没法实现呀?
不会鸭,我记得输入1和-1 是可以实现的,还是我没搞懂你问的意思qaq
比如我输入0.001,输出的结果是0.001
而实际三次方根是0.1
卧槽??等我康康
我也发现了。。。。,卑微,看来我得改代码了
我好像没有感觉出错误,我太菜了
我觉得二分解决不了(-1,1)的开方,之前问过yxc,他的意思好像是:二分是求(l,r)中最接近的结果的那个数,这是我的理解哈,我还是没整懂咋整,hhhh
我重新看课又刷到这道题了,我改进了一下代码,特判(-1,1)之间得数就行,因为这个范围得数求三次方是比它本身大得,二分得范围需要改变一下。