已知 sqrt (2)约等于 1.414，要求不用数学库，求 sqrt (2)精确到小数点后 10 位
该题的考点如下
- 基础算法的灵活应用能力（二分法学过数据结构的同学都知道，但不一定往这个方向考虑；如果学过数值计算的同学，应该还要能想到牛顿迭代法并解释清楚）
- 退出条件设计
查找，如： a) high=> 1.5 b) low=> 1.4 c) mid => (high+low)/2=1.45 d) 1.45*1.45> 2 ? high=> 1.45 : low => 1.45 e) 循环到 c)
2. 退出条件
a) 前后两次的差值的绝对值< =0.0000000001, 则可退出
const double EPSILON = 0.0000000001;
double sqrt2() {
double low = 1.4, high = 1.5;
double mid = (low + high) / 2;
while (high - low > EPSILON) {
if (mid * mid > 2) {
high = mid;
} else {
low = mid;
}
mid = (high + low) / 2;
}return mid;
}
牛顿迭代法1.牛顿迭代法的公式为：xn+1 = xn-f(xn)/f'(xn)
【大厂面试题（已知 sqrt (2)约等于 1.414，要求不用数学库，求 sqrt (2)精确到小数点后 10 位）】对于本题，需要求解的问题为：f(x)=x2-2 的零点
EPSILON = 0.1 ** 10
def newton(x):
if abs(x ** 2 - 2) > EPSILON:
return newton(x - (x ** 2 - 2) / (2 * x))
else:
return x
推荐阅读
- 给定一个二叉搜索树(BST)，找到树中第 K 小的节点
- 大厂面试题（如何实现一个高效的单向链表逆序输出（））
- 深入浅出Node.js高清版PDF百度网盘下载
- Effective.Modern.C++中英文版PDF超清版百度网盘下载
- 图论(graph theory)算法原理、实现和应用全解
- 不相交集（disjoint set）原理和实现图文详解
- 9大经典排序算法原理和实现代码详解
- C/C++中的rand()和srand()用法指南
- 位与量子位之间的差异