你知道怎么改进Python 二分法和牛顿迭代法求算术平方根吗

目录
  • 二分法
  • 二分法原理
  • 牛顿迭代法
  • 牛顿迭代法原理
  • 总结

二分法

def sqrtb(n):
    if n<0: raise ValueError('n>=0')
    left,right,x=0,n,n/2
    while not -1e-15<x*x-n<1e-15:
        if x*x>n:
            right,x = x,left+(x-left)/2
        else:
            left,x = x,right-(right-x)/2
    return x

求最接近算术平方根的整数

def sqrtB(x):
    if x==0: return 0
    #y,x=x,round(x)
    left,right,ret = 1,x,0
    while left<=right:
        mid = left + (right-left)//2
        if mid<x/mid:
            left = mid+1
            ret = mid
        elif mid==x/mid:
            ret = mid
            break
        else:
            right = mid-1
    return ret

>>> sqrtB(9)
3
>>> sqrtB(8)
2
>>> sqrtB(9.2)
3.0
>>> sqrtB(7.8)
2.0
>>> sqrtB(4)
2
>>>

二分法原理

牛顿迭代法

def sqrtn(n):
    if n<0: raise ValueError('n>=0')
    x = n/2
    while not -1e-15<x*x-n<1e-15:
        x = (x+n/x)/2
    return x

一点小改进：不用1e-15来比较

def sqrt2(n):
    x = n
    while x*x>n:
        x = (x+n/x)/2
    return x

缺点：碰到n=7,13,...等，会进入死循环

增加判断跳出循环：

def sqrt(n):
    x = n
    while x*x>n:
        y,x = x,(x+n/x)/2
        if y==x: break
    return x

# sqrt(n) n=1~25的精度测试：

0.0
-2.220446049250313e-16
0.0
0.0
0.0
0.0
0.0
-4.440892098500626e-16
0.0
-4.440892098500626e-16
0.0
0.0
4.440892098500626e-16
0.0
0.0
0.0
0.0
8.881784197001252e-16
-8.881784197001252e-16
0.0
0.0
0.0
0.0
0.0
0.0
>>>

牛顿迭代法原理

从函数意义上理解：要求函数f(x)=x²，使f(x)=num的近似解，即x²-num=0的近似解。

从几何意义上理解：要求抛物线g(x)=x²-num与x轴交点（g(x)=0）最接近的点。

假设g(x0)=0，即x0是正解，让近似解x不断逼近x0，x0 ~ x - f(x)/f'(x)

def cubeN(n):
    x,y = n/3,0
    while not -1e-15<x-y<1e-15:
        y,x = x,(2/3)*x+n/(3*x*x)
    return x
'''
>>> cubeN(27)
3.0
>>> cubeN(9)
2.080083823051904
>>>
'''

总结

本片文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • Python中利用sqrt()方法进行平方根计算的教程

    sqrt()方法返回x的平方根(x>0). 语法 以下是sqrt()方法的语法: import math math.sqrt( x ) 注意:此函数是无法直接访问的,所以我们需要导入math模块,然后需要用math的静态对象来调用这个函数. 参数 x -- 这是一个数值表达式. 返回值 此方法返回x的平方根,对于x>0. 例子 下面的例子显示了sqrt()方法的使用. #!/usr/bin/python import math # This will import math module pr

  • Python求算数平方根和约数的方法汇总

    一.求算术平方根 a= x=int(raw_input('Enter a number:')) if x >= : while a*a < x: a = a + if a*a != x: print x,'is not a perfect square' else: print a else: print x,'is a negative number' 二.求约数 方法一: divisor = [ ] x=int(raw_input('Enter a number:')) i= while

  • Python基于二分查找实现求整数平方根的方法

    本文实例讲述了Python基于二分查找实现求整数平方根的方法.分享给大家供大家参考,具体如下: x=int(raw_input('please input a int:')) if x<0: retrun -1 low=0 high=x ans=(low+high)/2.0 sign=ans while ans**2 !=x: if ans**2>x: high=ans else: low=ans ans=(low+high)/2.0 if sign==ans: break print ans

  • Python编程实现二分法和牛顿迭代法求平方根代码

    求一个数的平方根函数sqrt(int num) ,在大多数语言中都提供实现.那么要求一个数的平方根,是怎么实现的呢? 实际上求平方根的算法方法主要有两种:二分法(binary search)和牛顿迭代法(Newton iteration) 1:二分法 求根号5 a:折半: 5/2=2.5 b:平方校验: 2.5*2.5=6.25>5,并且得到当前上限2.5 c:再次向下折半:2.5/2=1.25 d:平方校验:1.25*1.25=1.5625<5,得到当前下限1.25 e:再次折半:2.5-(

  • Python用二分法求平方根的案例

    我就废话不多说了,大家还是直接看代码吧~ def sq2(x,e): e = e #误差范围 low= 0 high = max(x,1.0) #处理大于0小于1的数 guess = (low + high) / 2.0 ctr = 1 while abs(guess**2 - x) > e and ctr<= 1000: if guess**2 < x: low = guess else: high = guess guess = (low + high) / 2.0 ctr += 1

  • 你知道怎么改进Python 二分法和牛顿迭代法求算术平方根吗

    你知道怎么改进Python 二分法和牛顿迭代法求算术平方根吗

    目录 二分法 二分法原理 牛顿迭代法 牛顿迭代法原理 总结 二分法 def sqrtb(n): if n<0: raise ValueError('n>=0') left,right,x=0,n,n/2 while not -1e-15<x*x-n<1e-15: if x*x>n: right,x = x,left+(x-left)/2 else: left,x = x,right-(right-x)/2 return x 求最接近算术平方根的整数 def sqrtB(x):

  • 牛顿迭代法求多项式在1.5附近的值2*x的3次幂--4x平方+3*x-6=0的实现代码

    代码如下所示: 复制代码 代码如下: #include <stdio.h>#include <math.h> int main(){   float x,x0,f,f0;   x=1.5;   do   {    x0=x;      f0=((2*x-4)*x+3)*x-6;  //求得在x0处解    f=(6*x0-8)*x0+3;     // 在(x0 ,f0)处导数    x=x0-f0/f;        }while(fabs(x-x0)>=1e-6);   

  • javascript基于牛顿迭代法实现求浮点数的平方根【递归原理】

    本文实例讲述了javascript基于牛顿迭代法实现求浮点数的平方根.分享给大家供大家参考,具体如下: 今天在网上看到一则利用牛顿迭代法求浮点数的平方根的方法,发现很好,比一些语言自带的sqrt方法运行要快,在这里备份一下,以待后用,这里稍微做了些改动. 首先是牛顿迭代法原理: 比如我们要求a的平方根,首先随便猜一个近似值x,然后不断令x等于x和a/x的平均数,迭代几次后x的值就已经相当精确了. 如我们要求的数学假设为 a=7, var x=a; ( 7  + 7/7 ) / 2 = 3.642

  • C语言实现牛顿迭代法解方程详解

    C语言实现牛顿迭代法解方程详解

     C语言实现牛顿迭代法解方程详解 利用迭代算法解决问题,需要做好以下三个方面的工作: 一.确定迭代变量 在可以用迭代算法解决的问题中,我们可以确定至少存在一个可直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量. 二.建立迭代关系式 所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系).迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成. 三.对迭代过程进行控制 在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题.不能让迭代过程无休止地执行下去

  • python 二分查找和快速排序实例详解

    思想简单,细节颇多:本以为很简单的两个小程序,写起来发现bug频出,留此纪念. #usr/bin/env python def binary_search(lst,t): low=0 height=len(lst)-1 quicksort(lst,0,height) print lst while low<=height: mid = (low+height)/2 if lst[mid] == t: return lst[mid] elif lst[mid]>t: height=mid-1 e

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

  • Python二分查找+字符串模板+textwrap模块,

    Python二分查找+字符串模板+textwrap模块,

    目录 二分查找 字符串模板 textwrap 模块 按照空格统计词组个数 用 “0” 填充字符串 前言: 这个系列的专栏是为了保持 Python 手感而创建的,也可以用来学习 Python,因为存在知识跨越难度,所以先学习滚雪球系列为佳. 二分查找 问题场景 在一个升序的数组中(其实就是一个只有整数的列表),查找一个目标数的下标,不存在返回 -1 . 解决思路 因为数组是升序的,所以二分查找就能落地了 先取出数组中的中间值,与目标数比较大小,确定一半的范围 然后重复上述步骤不断缩小范围即可. 编

随机推荐