文档章节

python 二分法,牛顿拉浮生求平方根笔记(MIT视频学习)

风吹死
 风吹死
发布于 2017/02/19 19:31
字数 354
阅读 67
收藏 0

二分法即对猜想值在一个闭合区间内,通过判断区间的中点与猜想值的大小来不断地缩小猜想值的区间从来无限接近猜想值的办法。但是

def BinarySearch(array,t):
    low = 0
    height = len(array)-1
    while low < height:
        mid = (low+height)/2
        if array[mid] < t:
            low = mid + 1

            elif array[mid] > t:
            height = mid - 1

        else:
            return array[mid]

    return -1


if __name__ == "__main__":
    print BinarySearch([1,2,3,34,56,57,78,87],57)

t为猜想数,若mid<t时low+1,若(low+1)>t了,猜想数就不在判断的区间了,难道只能为整数不能为浮点数?

牛顿拉浮生办法求平方数:

 f(x)=x**2-a #a为被开方数

Xn+1=Xn-f(x)/2Xn

Xn+1在不断循环下去最终接近实际值的方法

例如,求16的开方数,猜想数为3

f(3)=9-16=-7,Xn+1=3-(-7)/2*3=4.111

f(4.11)继续下去,但是代码中

def SquarerootNR(x,eplison):

    assert x>=0, 'x must be non negtive not'+str(x)

    assert eplison>0,'eplison must be positive not'+str(eplison)

    x=float(x)

    guess=x

    diff=guess**2-x

    ctr=1(是否为迭代次数?)

    while abs(diff)>eplison and ctr<=100:(为何要用此判断条件?)eplison为最小整数,绝对值了都是最小的正数啊?

        guess=guess-diff/(2*guess)

        diff=guess**2-x

        ctr+=1

    assert ctr<=100 ,'the times of iteration is too much'

    print 'NR method:'

    print 'guess: %f iteration: %d' %(guess,ctr)

    return guess

© 著作权归作者所有

上一篇: python 学习总结
下一篇: python 学习总结
风吹死
粉丝 0
博文 2
码字总数 446
作品 0
成都
私信 提问
[LeetCode]牛顿迭代法求平方根

题目 Implement int sqrt(int x). Compute and return the square root of x. 思路 用Math.sqrt就没什么意义了 二分法估计也行,但是估计没有牛顿下山法快 牛顿下山法 公式推导: 在x0处的值...

Finley.Hamilton
2014/11/03
349
0
有了这套模板,女朋友再也不用担心我刷不动 LeetCode 了 - 知乎

作者 | 李威 来源 | https://www.liwei.party/ 整理 | 公众号:五分钟学算法 个人网站 | 五分钟学算法-和程序员小吴一起学算法 全文包含 12000+ 字、30 张高清图片,预计阅读时间为 40 分钟,...

和程序员小吴一起学算法
10/21
0
0
69. Sqrt(x) - LeetCode

Question 69. Sqrt(x) Solution 题目大意: 求一个数的平方根 思路: 二分查找 Python实现:

yysue
2018/10/01
24
0
LeetCode算法题-Sqrt(Java实现)

这是悦乐书的第158次更新,第160篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第17题(顺位题号是69)。 计算并返回x的平方根,其中x保证为非负整数。 由于返回类型是整数,...

小川94
2018/11/01
0
0
【转帖】一个Sqrt函数引发的血案

源码下载地址:http://blog.redfox66.com/post/2010/10/06/sotry-about-sqrt.aspx 好吧,我承认我标题党了,不过既然你来了,就认真看下去吧,保证你有收获。 我们平时经常会有一些数据运算的...

戴威
2011/11/25
225
2

没有更多内容

加载失败,请刷新页面

加载更多

PostgreSQL 11.3 locking

rudi
41分钟前
5
0
Mybatis Plus sql注入器

一、继承AbstractMethod /** * @author beth * @data 2019-10-23 20:39 */public class DeleteAllMethod extends AbstractMethod { @Override public MappedStatement injectMap......

一个yuanbeth
今天
8
1
一次写shell脚本的经历记录——特殊字符惹的祸

本文首发于微信公众号“我的小碗汤”,扫码文末二维码即可关注,欢迎一起交流! redis在容器化的过程中,涉及到纵向扩pod实例cpu、内存以及redis实例的maxmemory值,statefulset管理的pod需要...

码农实战
今天
4
0
为什么阿里巴巴Java开发手册中不建议在循环体中使用+进行字符串拼接?

之前在阅读《阿里巴巴Java开发手册》时,发现有一条是关于循环体中字符串拼接的建议,具体内容如下: 那么我们首先来用例子来看看在循环体中用 + 或者用 StringBuilder 进行字符串拼接的效率...

武培轩
今天
8
0
队列-链式(c/c++实现)

队列是在线性表功能稍作修改形成的,在生活中排队是不能插队的吧,先排队先得到对待,慢来得排在最后面,这样来就形成了”先进先出“的队列。作用就是通过伟大的程序员来实现算法解决现实生活...

白客C
今天
78
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部