1 题目
给定接口double sqrt(int x, double delta)请你实现开平方，其中x为底数，delta为最大误差
2 分析实现
- 直觉—>二分法
- 为了方便处理，将范围砍掉一半，认为0 =< x^0.5 - sqrt(x) < delta
- 设计 递归 接口，设计递归基，递归逻辑
#include <iostream>
// #include <cstdlib>
// #include <vector>
// #include <algorithm>
using namespace std;
double f(double x, double delta, double begin, double end)
{
double mid = (begin + end) / 2;
if (x < mid * mid)
{
return f(x, delta, begin, mid);
}
else if (x >= (mid + delta) * (mid + delta))
{
return f(x, delta, mid, end);
}
else
{
return mid;
} //对比这个递归 和 斐波那契的 递归
//不同之处在于 此处 是单分支 递归 --->好递归
//而 斐波那契 是多分支 递归 指数级增长 --->坏递归
}
double sqrt(int x, double delta)
{
if (x < 0)
{
return -1;//简单地异常处理
}
//x是被开方数字，delta是最大允许误差
//为了方便处理，姑且认为0 =< x^0.5 - sqrt(x) < delta
//这相当于是 将 范围 限制得更严格 了
double begin = 0, end = double(x);
//因为x is a int ,so x^0.5 < x
//开始 递归
return f(double(x), delta, begin, end);
}
int main(int argc, char** argv)
{
int x = 0;
if(2 == argc){
sscanf(argv[1],"%d",&x);
}
printf("%f\n",sqrt(x, 0.00000001));
//printf和cout打印出来的位数并不同
cout << sqrt(x, 0.00000001) << endl;
//这里 值得讨论的地方就是 delta精度取到多少以后，就没有意义了？
//double的 内部结构 构成 浮点数 的 机制
return 0;
}
3 值得深究的点
-
double的精度问题(float 阶码 移码 底数是怎么组成的 计算机组成原理)
-
递归的 更高抽象层面 --> 多分支递归 vs 单分支 递归 --> 转换成为 迭代
-
printf与cout内部的打印位数不一致
-
更高级的解法 （划线表示我已经掌握，未划线表示我还不懂）更高级解法的来自 公众号文章 从一道面试题谈谈一线大厂码农应该具备的基本能力
