Python 是一种面向对象解释型计算机程序设计语言, 由 Guido van Rossum 于 1989 年底发明, 第一个公开发行版发行于 1991 年 Python 语法简洁而清晰, 具有丰富和强大的类库它常被昵称为胶水语言, 它能够把用其他语言制作的各种模块 (尤其是 C/C++) 很轻松地联结在一起
这篇文章主要介绍了 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-(2.5-1.25)/2=1.875
f: 平方校验: 1.875*1.875=3.515625<5, 得到当前下限 1.875
每次得到当前值和 5 进行比较, 并且记下下下限和上限, 依次迭代, 逐渐逼近平方根:
- import math
- from math import sqrt
- def sqrt_binary(num):
- x=sqrt(num)
- y=num/2.0
- low=0.0
- up=num*1.0
- count=1
- while abs(y-x)>0.00000001:
- print count,y
- count+=1
- if (y*y>num):
- up=y
- y=low+(y-low)/2
- else:
- low=y
- y=up-(up-y)/2
- return y
- print(sqrt_binary(5))
- print(sqrt(5))
运行结果:
- 1 2.5
- 2 1.25
- 3 1.875
- 4 2.1875
- 5 2.34375
- 6 2.265625
- 7 2.2265625
- 8 2.24609375
- 9 2.236328125
- 10 2.2314453125
- 11 2.23388671875
- 12 2.23510742188
- 13 2.23571777344
- 14 2.23602294922
- 15 2.23617553711
- 16 2.23609924316
- 17 2.23606109619
- 18 2.23608016968
- 19 2.23607063293
- 20 2.23606586456
- 21 2.23606824875
- 22 2.23606705666
- 23 2.2360676527
- 24 2.23606795073
- 25 2.23606809974
- 26 2.23606802523
- 27 2.23606798798
- 2.23606796935
- 2.2360679775
- [Finished in 0.1s]
经过 27 次二分法迭代, 得到的值和系统 sqrt()差别在 0.00000001, 精度在亿分之一,
0.001 需要迭代 8 次
因此, 在对精度要求不高的情况下, 二分法也算比较高效的算法
2: 牛顿迭代
仔细思考一下就能发现, 我们需要解决的问题可以简单化理解
从函数意义上理解: 我们是要求函数 f(x)=x², 使 f(x)=num 的近似解, 即 x²-num=0 的近似解
从几何意义上理解: 我们是要求抛物线 g(x)=x²-num 与 x 轴交点 (g(x)=0) 最接近的点
我们假设 g(x0)=0, 即 x0 是正解, 那么我们要做的就是让近似解 x 不断逼近 x0, 这是函数导数的定义:
可以由此得到
从几何图形上看, 因为导数是切线, 通过不断迭代, 导数与 x 轴的交点会不断逼近 x0
对于一般情况:
将 m=2 代入:
- def sqrt_newton(num):
- x=sqrt(num)
- y=num/2.0
- count=1
- while abs(y-x)>0.00000001:
- print count,y
- count+=1
- y=((y*1.0)+(1.0*num)/y)/2.0000
- return y
- print(sqrt_newton(5))
- print(sqrt(5))
运行结果:
- 1 2.5
- 2 2.25
- 3 2.23611111111
- 2.23606797792
- 2.2360679775
精确到亿分之一, 牛顿法只迭代了 3 次, 是二分法的十倍
3: 利用牛顿法求开立方
- def cube_newton(num):
- x=num/3.0
- y=0
- count=1
- while abs(x-y)>0.00000001:
- print count,x
- count+=1
- y=x
- x=(2.0/3.0)*x+(num*1.0)/(x*x*3.0)
- return x
- print(cube_newton(27))
微积分概率线代是高级算法的基础课可是, 这么多年, 已经忘得差不多了..............................
来源: http://www.phperz.com/article/18/0219/361487.html