题目描述

C++中提供了 sqrt() 用于计算算术平方根：

#include <iostream>
#include <cmath>


int main() {
  int n = 17;
  double res = std::sqrt(n);
  
  std::cout << res << std::endl;

  return 0;
}

现在要求不使用 sqrt()，手动实现一个函数用于计算算术平方根。

题解

牛顿迭代法：

#include <iostream>

double Sqrt(int n) {
  if (x == 0) {
    return 0;
  }
  double guess = n;
  double precision = 1e-10;
  while (std::abs(guess * guess - n) > precision) {
    guess = (guess + n / guess) / 2;
  }
  return guess;
}

int main() {
  int n = 17;
  double res = Sqrt(n);

  std::cout << res << std::endl;

  return 0;
}

有一种优雅的写法，有空了可以研究一下，顺便看一下牛顿迭代的几何表示。

double mySqrt(int x) {
  if (x == 0) {
    return 0;
  }
  double r = x;
  while (r > x / r) {
    r = x / r + (r - x / r) / 2;
  }
  return r;
}

二分法：

int mySqrt(int x) {
  if (x == 0 || x == 1) {
    return x;
  }
  int left = 0;
  int right = x;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (mid <= x / mid) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return right;
}