欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基础算法六:求平方根的问题

程序员文章站 2024-02-27 19:04:21
...

求解基础算法六:求平方根的问题,也是面试中经常问的一个问题。该问题有两种解法:二分法和牛顿法。

首先说二分法,首先给定个初始区间范围[0,n],因为基础算法六:求平方根的问题一定是在这个范围内,然后比较这个区间的中值的平方基础算法六:求平方根的问题和n,如果基础算法六:求平方根的问题小于n,将范围缩小为[m,n],如果基础算法六:求平方根的问题大于n,将范围缩小为[0,基础算法六:求平方根的问题​​​​​​​]。然后重复这个步骤,直到误差小于设定的阈值。

代码如下:

def binary_search(n, e=1e-5):
    '''
    二分法计算平方根
    '''
    max = n
    min = 0.
    mid = (max + min) / 2.
    while abs(mid * mid - n) > e:
        if mid * mid > n:
            max = mid
        elif mid * mid < n:
            min = mid
        else:
            return mid
        mid = (max + min) / 2.
    return mid

然后是牛顿法,牛顿法是一种求函数基础算法六:求平方根的问题的0点的方法,对于我们这个问题,如果我们要求的值为基础算法六:求平方根的问题,那么基础算法六:求平方根的问题,于是就转化成了求基础算法六:求平方根的问题的0点。牛顿法的做法是给定基础算法六:求平方根的问题的初始值基础算法六:求平方根的问题,对基础算法六:求平方根的问题求导求出基础算法六:求平方根的问题基础算法六:求平方根的问题处的切线,该切线和y轴交点处为基础算法六:求平方根的问题,将基础算法六:求平方根的问题更新为基础算法六:求平方根的问题,重复刚才的过程,使基础算法六:求平方根的问题不断逼近基础算法六:求平方根的问题的点。

如下图所示:

基础算法六:求平方根的问题

基础算法六:求平方根的问题的更新公式推导过程为:

基础算法六:求平方根的问题基础算法六:求平方根的问题处的切线方程为:基础算法六:求平方根的问题

基础算法六:求平方根的问题

于是基础算法六:求平方根的问题

代码如下:

def newton_search(n, e=1e-5):
    '''
    牛顿法计算平方根
    '''
    x = n
    while abs(x * x - n) > e:
        x = (x + n / x) / 2.
    return x

运行结果如下所示:

if __name__ == '__main__':
    print(binary_search(2))
    print(newton_search(2))


1.414215087890625
1.4142156862745097