求 sqrt (2)精确到小数点后 10 位。 收藏 阅读:66
2020-10-27 11:33:25

题目:已知 sqrt (2)约等于 1.414,要求不用数学库,求 sqrt (2)精确到小数点后 10 位。

出题人:——阿里巴巴出题专家:文景/阿里云 CDN 资深技术专家

参考答案

* 考察点

  1. 基础算法的灵活应用能力(二分法学过数据结构的同学都知道,但不一定往这个方向考虑;如果学过数值计算的同学,应该还要能想到牛顿迭代法并解释清楚)

  2. 退出条件设计

二分法

1. 已知 sqrt(2)约等于 1.414,那么就可以在(1.4, 1.5)区间做二分

查找,如:a) high=>1.5b) low=>1.4c) mid => (high+low)/2=1.45d) 1.45*1.45>2 ? high=>1.45 : low => 1.45e) 循环到 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)

对于本题,需要求解的问题为: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

© 版权归知否网(zhifou.net)所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权知否网将依法追究其法律责任。
读后有收获,请作者喝杯咖啡


全部评论

发表评论