LeetCode

本文记录LeetCode - 069. 求平方根(Sqrt)问题。

问题描述

请你手动编程实现sqrt()函数:输入一个整型数,求该整数的平方根。

注:给出的整型数保证大于0

输入:4
输出:2

注:样例1

输入:8
输出:2
解释:8 的平方根为 2.82842... 取其整数部分。

注:样例2

问题解答

平方根函数sqrt()是最常用的数学函数之一,在这个问题中,需要我们手动实现sqrt函数,而不应使用语言标准库自带的数学函数。

二分求解法

第一个思路是使用二分法,猜测一个数,平方后与原数进行比对,确定一个精度范围后即可求解。

/* 绝对值函数 */
#define ABS(x) 
    ((x) < 0 ? -(x) : (x))
/* 设置精度 */
#define LIMIT 0.01
int mySqrt(int x) {
    /* 处理非正数情况 */
    if(x <= 0) { return 0; }
    double hig = double(x);
    double low = 0;
    double lst = 0;
    double guess = (low + hig)/2;
    do {
       lst = guess;
       if(guess * guess > x) {
           hig = guess;
           guess = (low + hig)/2;
       }
       else if(guess * guess < x) {
           low = guess;
           guess = (low + hig)/2;
       }
       else if(guess * guess == x) {
           break;
       }
    } while(ABS(guess - lst) > LIMIT);

    return (int)guess;
}

代码清单:C/C++实现二分法

牛顿迭代法

另一种方法就是使用牛顿迭代法,要求根号n的近似值,先随便猜测一个数x,然后不断令x等于xa/x的平均数,迭代六七次后,结果就已经相当精确了。

/* 绝对值函数 */
#define ABS(x) 
    ((x) < 0 ? -(x) : (x))
/* 设置精度 */
#define LIMIT 0.01
int mySqrt(int x) {
    /* 处理非正数情况 */
    if(x <= 0) { return 0; }
    double guess = x;
    double last  = 0;
    do {
        last  = guess;
        guess = (guess + guess/x)/2;
    } while(ABS(guess - last) > LIMIT);
    return (int)guess;
}

代码清单:C/C++实现牛顿迭代法

参考资料