python巴比伦函数 巴比伦算法求平方根python

巴比伦方法求平方根

思路:

创新互联建站是一家朝气蓬勃的网站建设公司。公司专注于为企业提供信息化建设解决方案。从事网站开发,网站制作,网站设计,网站模板,微信公众号开发,软件开发,小程序设计,十余年建站对成都木制凉亭等多个行业,拥有多年建站经验。

巴比伦算法的原理说白了就是求这么一个x使得x * x = n.

但问题是为什么迭代可以求得x的值呢?

原理如下:

假设最终返回的结果是x(n), 那么按照迭代算法来看显然是从x(n - 1)推导过来的。

即:

x(n) = (x(n - 1) + N / x(n - 1)) / 2

做个变形就可以得到:

x(n - 1) ^ 2 - 2 * x(n) * x(n - 1) + N = 0

将N用a * a 替换,就得到了如下式子:

x(n - 1) ^ 2 - 2 * x(n) * x(n - 1) + a ^ 2 = 0

因为x(n) = a,所以有:

x(n - 1) ^ 2 - 2 * a * x(n - 1) + a ^ 2 = 0;

即:

(x(n - 1) - a) ^ 2 = 0;

因为x(n - 1) 和 x(n) 是很接近的,为了解释这点可以从两个角度着手:

第一个角度:数学角度

x(n) = ( x(n - 1) + N / x(n - 1)) / 2

令函数G(x) = x(n)

那么,G(x)这个函数是一个对勾函数,在第一象限有一个最小值等于x,该最小值的位置为(x, N / x),

所以只要找到这个点求出该点的G(x)那么我们就能解决该问题,而我们的解决方法便是从x 0的位置起,

逐步逼近这个极值点。因此,当lim(n-无穷大)x(n) = x(n - 1)

另外一个角度:程序角度

当跳出while(y + eps x)循环时,这时候x(n)和x(n - 1)无限接近

正是由于x(n)接近于x(n - 1),才得到如下的式子:

(x(n) - a) ^ 2 = 0

最后便得到了x(n) = a

题目连接:leetcode Sqrt(x)

class GetRoot {

public:

constdouble eps = 1e-9;

public:

double RootNumber(double n) {

double x = n;

double y = 1;

while (x y + eps) {

x = (x + y) / 2;

y = n / x;

}

return x;

}

};

int main(void) {

GetRoot ans;

double n;

while (cin n) {

cout ans.RootNumber(n) endl;

}

return 0;

}

几何是哪发明的?为什么发明他?

在我国古代,这门数学分科并不叫“几何”,而是叫作“形学”。“几何”二字,在中文里原先也不是一个数学专有名词,而是个虚词,意思是“多少”。比如三国时曹操那首著名的《短歌行》诗,有这么两句:“对酒当歌,人生几何?”这里的“几何”就是多少的意思。明末杰出的科学家徐光启首先把“几何”一词作为数学的专业名词来使用的。

几何最早的有记录的开端可以追溯到古埃及(参看古埃及数学),古印度(参看古印度数学),和古巴比伦(参看古巴比伦数学),其年代大约始于公元前3000年。早期的几何学是关于长度,角度,面积和体积的经验原理,被用于满足在测绘,建筑,天文,和各种工艺制作中的实际需要。在它们中间,有令人惊讶的复杂的原理,以至于现代的数学家很难不用微积分来推导它们。例如,埃及和巴比伦人都在毕达哥拉斯之前1500年就知道了毕达哥拉斯定理(勾股定理);埃及人有方形棱锥的锥台(截头金字塔形)的体积的正确公式;而巴比伦有一个三角函数表。

中国文明和其对应时期的文明发达程度相当,因此它可能也有同样发达的数学,但是没有那个时代的遗迹可以使我们确认这一点。也许这是部分由于中国早期对于原始的纸的使用,而不是用陶土或者石刻来记录他们的成就。

python确定一个数是不是完全平方数

1. 与依赖于任何浮动的问题(math.sqrt(x)或x**0.5)是你不能真正确定它的准确(对充分大的整数x,它不会是,甚至有可能溢出)。幸运的(如果是不急于;-)有很多纯整数的方法,如下面的...:

def is_square(apositiveint):

x = apositiveint // 2

seen = set([x])

while x * x != apositiveint:

x = (x + (apositiveint // x)) // 2

if x in seen: return False

seen.add(x)

return True

for i in range(110, 130):

print i, is_square(i)

提示:它是基于“巴比伦算法”的平方根,请参阅维基百科。它适用于任何正数,而您有继续 编辑:让我们看一个例子...

x = 12345678987654321234567 ** 2

for i in range(x, x+2):

print i, is_square(i)

这种版画,根据需要(和太;-)一个合理的金额:

152415789666209426002111556165263283035677489 True

152415789666209426002111556165263283035677490 False

请您提出了一种基于浮点结果的解决方案之前 CodeGo.net,确保他们正确地工作在这个简单的例子-它不是那么难(你只需要一些额外的检查,以防是有点过),只是需要多一点的关怀。 然后尝试用x**7并找到解决您会得到这个问题巧妙的方式,

OverflowError: long int too large to convert to float

你必须得到越来越多的聪明的数量不断增加,当然。 如果我很着急,当然,我gmpy-但后来,我明显偏向;-)。

import gmpy

gmpy.is_square(x**7)

1

gmpy.is_square(x**7 + 1)

是啊,我知道,这只是很容易感觉像作弊(有点我总体感觉对Python的;-)的方式-没有聪明可言,只是完美的直接和简单(和,在gmpy,绝对速度的情况下;-) ...

2. 用牛顿的快速零最接近的整数的平方根,那么它平方,看看它是否是你的号码。见isqrt。

3. 因为你永远无法靠当浮动(如计算平方根的这些方式),一个不易出错将是对处理

import math

def is_square(integer):

root = math.sqrt(integer)

if int(root + 0.5) ** 2 == integer:

return True

else:

return False

想像integer是9。math.sqrt(9)可能是3.0的,但它也可以是像2.99999或3.00001,因此现蕾结果马上是不可靠的。知道int取整数值,通过增加浮点值0.5我们会得到我们要找的,如果我们是在一个范围内的值,其中float仍然有足够细的分辨率来表示附近的一个为我们所期待的数字。

4. 我是新来的堆栈溢出,并做了一个快速脱脂找到解决的办法。我只是张贴在另一个线程(寻找完美的正方形)上的例子,一个细微的变化上面,我想我会包括什么,我贴在这里有一个细微的变化(使用nsqrt作为一个临时变量),如果它的利益/使用:

import math

def is_perfect_square(n):

if not ( ( isinstance(n, int) or isinstance(n, long) ) and ( n = 0 ) ):

return False

else:

nsqrt = math.sqrt(n)

return nsqrt == math.trunc(nsqrt)

5. 你可以二进制搜索的圆形平方根。平方的结果,以确定它的原始值相匹配。 你可能会更好过与FogleBirds回答-虽然小心,因为浮点数是近似的,它可以抛出这种方法了。你可以在原则上得到一个假阳性从一个大的整数,较完美的正方形,例如,由于丢失精度1以上。

6.

def f(x):

... x = x ** 0.5

... return int(x) == x

...

for i in range(10):

... print i, f(i)

...

0 True

1 True

2 False

3 False

4 True

5 False

6 False

7 False

8 False

9 True

7. 决定多久的数量就越大。 采取增量0.000000000000 ....... 000001 见,如果(SQRT(X))^ 2-x是大于/等于/大于δ较小并且基于增量误差决定。

8. 我不知道Python的,但你可以不喜欢:

function isSquare(x) = x == floor(sqrt(x) + 0.5)^2

也就是说,拿一个数,求平方根,四舍五入到最接近的整数,它平方,并测试它是作为原来的号码。 (floor并加入0.5做是为了防止类似案件sqrt(4)回国1.9999999...由于浮点运算,麦克grahams指出。) 如果你有兴趣,曾经有一个很好的判断以最快的方式,如果一个整数的平方根是一个整数。 编辑澄清。

9. 该回复不属于你的declarative的问题,而是一个隐含的问题,我在您发布的代码中看到,即“如何检查是否是整数?” 优先个回答你通常得到这个问题是“不要!”并且这是真的,在Python,类型检查不应该做的事情。 对于那些极少数的异常,不过,不是寻找数字的字符串表示小数点,那东西做isinstance函数:

isinstance(5,int)

True

isinstance(5.0,int)

False

当然适用于变量,而不是一个值。如果我想确定该值是否是一个整数,我会做到这一点:

x=5.0

round(x) == x

True

但正如其他人已经详细介绍,也有这种事情的大多数非玩具的例子来加以考虑浮点问题。

10. 我有轻微的原始巴比伦的方法。取而代之的是一套以存储每个生成的近似,只是最近的两个近似的存储和核对电流近似。这保存了大量的通过整套的近似值的浪费检查。我的java,而不是python和BigInteger类,而不是一个正常的原始整数。

BigInteger S = BigInteger.ZERO;

BigInteger x = BigInteger.ZERO;

BigInteger prev1 = BigInteger.ZERO;

BigInteger prev2 = BigInteger.ZERO;

Boolean isInt = null;

x = S.divide(BigInteger.valueOf(2));

while (true) {

x = x.add(preA.divide(x)).divide(BigInteger.valueOf(2));

if (x.pow(2).equals(S)) {

isInt = true;

break;

}

if (prev1.equals(x) || prev2.equals(x)) {

isInt = false;

break;

}

prev2 = prev1;

prev1 = x;

}


分享题目:python巴比伦函数 巴比伦算法求平方根python
新闻来源:http://pwwzsj.com/article/dooogpo.html