首页 来点算法

# 牛顿迭代法

牛顿迭代法推导

  • 367. 有效的完全平方数 - 力扣（LeetCode）
  • 69. x 的平方根 - 力扣（LeetCode）

# 367

class Solution {
public:
    bool isPerfectSquare(int num) {
        // 初始的值用 num
        double x0 = num;
        while (true) {
            // 牛顿迭代法找零点
            double x1 = (x0 + num / x0) / 2;
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        int x = (int) x0;
        if (x * x == num) return true;
        return false;
    }
};

# 69

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        // 初始的值用 x
        double x0 = x;
        while (true) {
            // 牛顿迭代法找零点
            double x1 = (x0 + x / x0) / 2;
            if (x0 - x1 < 1e-7) {
                break;
            }
            x0 = x1;
        }
        return (int) x0;        
    }
};