你好,游客 登录 注册 搜索
背景:
阅读新闻

【leetcode】sqrt(int x) - IT-Homer 专栏

[日期:2013-04-13] 来源:  作者: [字体: ]

Question:

Implement int sqrt(int x).

Compute and return the square root of x.


Anwser  1: 二分法

class Solution {
public:
    int sqrt(int x) {
        
        if(x < 0) return -1; // assert(x >= 0);
        
        long long x2 = (long long)x;
        long long left = 0;
        long long right = x2;
        long long mid = 0;
        
        while(left <= right){
            mid = left + (right - left) / 2;
            
            if(mid * mid == x2 || (mid * mid < x2 && (mid + 1) * (mid + 1) > x2)){
               return (int)mid;
            } else if(mid * mid < x2){
                left = mid + 1;
            } else{
                right = mid - 1;
            }
        }
    }
};
注意点:

1) 非负数判断,负数没有开平方根

2) 取值范围,mid = left + (right - left) / 2; 可能会超过int最大取值范围,因此需设mid类型为long long(C++没ulong)




Anwser  2: 牛顿迭代法

class Solution {
public:
    int sqrt(int x) {
        if(x < 0) return -1; // assert(x >= 0);
        
        double n = x;
        while(abs(n * n - x) > 0.0001){
            n = (n + x / n) / 2;
        }
        
        return (int)n;
    }
};
注意点:

求a的平方根问题,可以转化为x^2 - a = 0 求x值,进而 abc(x^2 -a) < 0.0001 (0.0001为接近精度)

令 f(x) = x^2 - a, f(x) 即是精度取值范围(无限趋近于0)


对 函数 f(x) 求导:


变换公式,得: 


把 f(x) = x^2 - a 公式求导,导入得: Xn+1 = Xn - (Xn^2 - a) / (2Xn) = Xn - (Xn - a/Xn) / 2 = (Xn + a/Xn) / 2

其中, Xn+1 无限接近于 Xn, 即有: Xn = (Xn + a/Xn) / 2




Anwser  3: 火星人算法

#include <stdio.h>

int InvSqrt(int x)
{
    float x2 = (float)x;
    float xhalf = x2 / 2;
    int i = *(int*) & x2;         // get bits for floating VALUE 
    i = 0x5f375a86 - (i>>1);     // gives initial guess y0
    x2 = *(float*) & i;           // convert bits BACK to float
    x2 = x2 * (1.5f - xhalf * x2 * x2); // Newton step, repeating increases accuracy
    x2 = x2 * (1.5f - xhalf * x2 * x2); // Newton step, repeating increases accuracy
    x2 = x2 * (1.5f - xhalf * x2 * x2); // Newton step, repeating increases accuracy

    printf("\n\n1/x = %d\n", (int)(1/x2));
    return (int)(1/x2);
}



int main(){

    //InvSqrt(65535);
    InvSqrt(10);
    InvSqrt(2147395599);
    InvSqrt(1297532724);

    return 0;

}
说明:

此方法传说非常高效,我是参考别人的float写的int(参数)

在gcc(linux)下编译通过,且测试结果都正确,但在leetcode编译没通过,编译显示信息如下:

Run Status: Internal Error


参考推荐:

leetcode.com

一个Sqrt函数引发的血案

利用牛顿迭代法求平方根






收藏 推荐 打印 | 录入:admin | 阅读:
相关新闻