提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

69. Sqrt(x)

69
2023-09-11 14:22:45 时间

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.
 

my code:

class Solution {
public:
    int mySqrt(int x) {
        for (int i = 1; i <= x; i++) {
            if ((long)i*i > x)
                return i-1;
            else if ((long)i*i == x)
                return i;
        }   
        return 0;
    }
};
Runtime: 36 ms, faster than 8.63% of C++ online submissions for Sqrt(x).

 

2. Newton's Iterative Method in C++

首先，选择一个接近函数{\displaystyle f(x)}f(x)零点的{\displaystyle x_{0}}x_{0}，计算相应的{\displaystyle f(x_{0})}f(x_0)和切线斜率{\displaystyle f'(x_{0})}f'(x_0)（这里{\displaystyle f'}f'表示函数{\displaystyle f}f的导数）。然后我们计算穿过点{\displaystyle (x_{0},f(x_{0}))}(x_{0},f(x_{0}))并且斜率为{\displaystyle f'(x_{0})}f'(x_0)的直线和{\displaystyle x}x轴的交点的{\displaystyle x}x坐标，也就是求如下方程的解：

{\displaystyle 0=(x-x_{0})\cdot f'(x_{0})+f(x_{0})}{\displaystyle 0=(x-x_{0})\cdot f'(x_{0})+f(x_{0})}

我们将新求得的点的{\displaystyle x}x坐标命名为{\displaystyle x_{1}}x_1，通常{\displaystyle x_{1}}x_1会比{\displaystyle x_{0}}x_{0}更接近方程{\displaystyle f(x)=0}f(x)=0的解。因此我们现在可以利用{\displaystyle x_{1}}x_1开始下一轮迭代。迭代公式可化简为如下所示：

{\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}x_{{n+1}}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}

已有证明牛顿迭代法的二次收敛[1]必须满足以下条件：
{\displaystyle f'(x)\neq 0}{\displaystyle f'(x)\neq 0}; 对于所有{\displaystyle x\in I}{\displaystyle x\in I}，其中{\displaystyle I}I为区间[α − r, α + r]，且{\displaystyle x_{0}}x_{0}在区间其中{\displaystyle I}I内，即 {\displaystyle r\geqslant \left|a-x_{0}\right|}{\displaystyle r\geqslant \left|a-x_{0}\right|} 的; 
对于所有{\displaystyle x\in I}{\displaystyle x\in I}，{\displaystyle f''(x)}f''(x)是连续的; 
{\displaystyle x_{0}}x_{0}足够接近根 α。

 

3. binary search:

class Solution {
public:
    int mySqrt(int x) {
        int low = 0,  high = x, mid;
        if(x<2) return x; // to avoid mid = 0
        while(low<high)
        {
            mid = (low + high)/2;
            if(x/mid >= mid) low = mid+1;
            else high = mid;
        }
        return high-1;
        
    }
};

　　

Runtime: 16 ms, faster than 53.68% of C++ online submissions for Sqrt(x).

 

相关文章