【蓝桥杯知识点】浮点数二分（开n次方根再也不会超时啦！）

今天继续学习基础算法！这篇文章介绍了二分的另一种应用——浮点数二分，可以用于开n次方根的计算，会使时间大大缩短！我偷偷问过电脑编译器了，它说它喜欢优化过的算法哈哈哈哈~相信你也会喜欢的！

PS：文章主要参考：b站一只会code的小金鱼的视频（真的讲得超级超级详细！！！很适合大一没接触过算法的小白学习，而且up的声音也很好听很好听！！！墙裂推荐！）

先来一道题

你会怎么做呢？

暴力枚举法

是不是先想到了for循环？一个一个比较就好了！

这个思路虽然是正确的，但往往会面临着超时的问题，毕竟是六位小数啊，0.0000001一个一个加，电脑都要算累了~

不过为了对比，我还是试验了一下——

#include<iostream>
using namespace std;
double n;bool check(double x)
{if(x*x*x<=n){return true;}else return false;
}int main()
{scanf("%lf",&n);double l=-100,r=100;for(double i=-22;i<=22;i+=0.00000001){if(check(i)){l=i;}else r=i;}printf("%lf\n",l);//printf("%lf\n",r);return 0;}

经过漫长长长的等待之后，电脑终于通过枚举找到了答案

优化1

如上面所示，如果一个一个加，那每次加0.000001就太多次了，会超时的！

那该怎么办呢？

刚刚学习的二分法就派上用场啦

快把原来的for循环换成二分！

#include<iostream>
using namespace std;
double n;bool check(double x)
{if(x*x*x<=n){return true;}else return false;
}int main()
{scanf("%lf",&n);//枚举 double l=-100,r=100;/*常用的那种i++的for循环是枚举不出来的因为只能加整数 如果一个一个加，那每次加0.000001就太多次了，会超时的！ 所以二分法就派上用场啦 关于精度：计算时精确到e^-8，这样e^-6一定是准的 for(double i=-22;i<=22;i+=0.00000001){if(check(i)){l=i;}}else r=i;*/while(r-l>1e-8){double mid=(l+r)/2;if(check(mid)){l=mid;}elser=mid;}printf("%lf\n",l);printf("%lf\n",r);return 0;}

真的快了很多！

细节优化2

while(r-1>1e-8)还可以换成另一个for循环

for(int i=0;i<=100;i++)

//二分100次，一定找出来了，可以把答案精度控制在e^-30

#include<iostream>
using namespace std;
double n;bool check(double x)
{if(x*x*x<=n){return true;}else return false;
}int main()
{scanf("%lf",&n);//枚举 double l=-100,r=100;/*常用的那种i++的for循环是枚举不出来的因为只能加整数 如果一个一个加，那每次加0.000001就太多次了，会超时的！ 所以二分法就派上用场啦 关于精度：计算时精确到e^-8，这样e^-6一定是准的 for(double i=-22;i<=22;i+=0.00000001){if(check(i)){l=i;}}else r=i;*///容易出错while(r-1>1e-8)//while(r-l<1e-8)//{ for(int i=0;i<=100;i++)//二分100次，一定找出来了，可以把答案精度控制在e^-30 {double mid=(l+r)/2;if(check(mid)){l=mid;}elser=mid;}//} printf("%lf\n",l);printf("%lf\n",r);return 0;}

依然是那么quickly!!!