我要分享技术
0%

ARTS-9

发表于 更新于 分类于

ARTS-9

Algorithm

Description

69. Sqrt(x)

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.

大意

实现一个开平方的函数, 它输入一个整数x, 输出一个整数y 满足 \(y^2<=x\) 且 \((y+1)^2>x\)

思路

开平方的普遍简单做法一般有两种, 一个是二分法逼近, 一个是牛顿迭代开平方法。因为之前已经做过了太多的二分法了, 所以决定这次使用牛顿开平方法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==0:
            return 0
        if x==1:
            return 1

        y = x/2.0
        while abs(x-y**2) > 0.5:
            y=((y*1.0)+(1.0*x)/y)/2.0000
        return int(y)

Result

Time Submitted Status Runtime Memory Language
2 hours ago Accepted 20 ms 11.8 MB python

Review

Learning Python: From Zero to Hero

引言

之前medium老是给我推送javascript的文, 我越是看, 它越是推, 然而,我几乎从不写js, 这次我自己主动去看python文, 让它学习下, 以后换个口味给我推。

内容

Learning Python: From Zero to Hero

“high-level programming language, and its core design philosophy is all
about code readability and a syntax which allows programmers to express
concepts in a few lines of code.”

“高级编程语言，其核心设计理念是代码可读性和一个允许程序员用稍几行代码表达概念的语法。”

变量

1
2
3
one = 1

print(one)

数组

1
2
3
4
5
6
array = [1, 2, 3]

array[1] = 5

for v in array:
    print(v)

字典

1
2
3
4
5
6
dictionary = { "one" : 1, "two" : 2, "three" : 3}
dictionary["four"] = 4

for k, v in dictionary.items():
    print(k)
    pirnt(v)

循环

1
2
while Condition:
    doSomething()
1
2
for key in dictionary:
    doSomething(dictionary[key])
1
2
for k, v in dictionary.items():
    doSomething(k, v)

类和对象

类是对象的模板, 对象是程序使用类复刻的产物。

类中定义构造方法为 init, 它第一个参数为代表当前对象的self 类可以有对公属性和非对公属性, 对公属性普通命名, 以下划线开头的名字为非对公属性, 除了本类定义的方法外不可以访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Model:
    def __init__(self, attr1, attr2):
        self.attr1 = attr1
        self._attr2 = attr2
    
    def getAttr1():
        return self.attr1
        
    def getAttr2():
        return self._attr2

object = Model('a', 'b')
print(object.getAttr1())
print(object.getAttr2())

本篇出错

有趣的是, 在本篇评论上有个网友指出了作者在文中的一处错误

作者原文:

For a Python class, we can initialize a public instance variable within our constructor method or just inside the class.

网友评论:

That is not true!

Variables declared at class level are not instance variables, they are class attributes. Class attributes are defined outside of all the methods, usually they are placed at the top, right below the class header.

意思大意为, 作者说对于python类, 我们可以在构造函数或者类内部直接初始化一个对公变量。 网友说作者错了, 应该为, 在构造函数中初始化的是对象变量, 而类中进行声明的则为类变量。

Tips

牛顿迭代

牛顿法使用迭代来求解一个方程, 其原理大致如下:

对于一个函数 \(f(x)\) ,它的泰勒级数展开式是这样的,

\[ f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{1}{2}f''(x_0)(x-x_0)^2+...+\frac{1}{n!}f^n(x0)(x-x_0)^n \]

牛顿法使用泰勒级数前两项来代替这个函数，即用ϕ(x)代替f(x):

\[ \phi(x)=f(x_0)+f'(x_0)(x-x_0) \]

令 \(\phi\left(x\right)=0\) , 则 \(x = x_0 - \frac{f(x_0)}{f'(x_0)}\)

所以,牛顿迭代式为 \(f(x_{n+1})=x_n - \frac{f(x_n)}{f'(x_n)}\)

牛顿迭代法开平方

开平方即为求解 \(f(x)=x^2-n\) 在 \(f(x)=0\) 时的解。

代入牛顿迭代式

\[ x_{n+1} = \frac{x_n^2-n} {2x_n} \\ = \frac{x_n}{2} - \frac{n}{2x_n} \\ = \frac{1}{2}\left(x_n-\frac{n}{x_n} \right) \]

牛顿迭代开平方在代码中的写法

1
2
3
4
5
6
7
8
9
10
11
const EPS = 0.0001
func sqrt(x double) {
    reuslt := x
iteration:
    last := x
    result = (result - (x-result))/2.0
    if abs(last-result)>EPS {
        goto iteration
    }
    return result
}

Share

[直观详解]泰勒级数

End