检查数字是否是一个完美的平方

本文介绍了检查数字是否是一个完美的平方的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如何检查数字是否是一个完美的平方?

How could I check if a number is a perfect square?

速度无关紧要，目前，只是工作而已.

Speed is of no concern, for now, just working.

推荐答案

依赖任何浮点计算(math.sqrt(x)或x**0.5)的问题是您不能真正确定它的准确性(对于足够大整数x，它不会，甚至可能溢出).幸运的是(如果您不着急；-)有很多纯整数方法，例如:...

The problem with relying on any floating point computation (math.sqrt(x), or x**0.5) is that you can't really be sure it's exact (for sufficiently large integers x, it won't be, and might even overflow). Fortunately (if one's in no hurry;-) there are many pure integer approaches, such as the following...:

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)

提示:它基于平方根的巴比伦算法"，请参见维基百科.它可以为任何正数工作，您有足够的内存来完成计算；-).

Hint: it's based on the "Babylonian algorithm" for square root, see wikipedia. It does work for any positive number for which you have enough memory for the computation to proceed to completion;-).

编辑:让我们看一个示例...

Edit: let's see an example...

x = 12345678987654321234567 ** 2 for i in range(x, x+2): print i, is_square(i)

这会根据需要(在合理的时间内；-)打印:

this prints, as desired (and in a reasonable amount of time, too;-):

152415789666209426002111556165263283035677489 True 152415789666209426002111556165263283035677490 False

请在基于浮点中间结果提出解决方案之前，请确保它们在此简单示例上正常工作-并不是 难(您需要做一些额外的检查，以防sqrt计算有点差)，只需多加注意.

Please, before you propose solutions based on floating point intermediate results, make sure they work correctly on this simple example -- it's not that hard (you just need a few extra checks in case the sqrt computed is a little off), just takes a bit of care.

然后尝试使用x**7并找到解决您将遇到的问题的聪明方法，

And then try with x**7 and find clever way to work around the problem you'll get,

OverflowError: long int too large to convert to float

当然，随着数字的增长，您将变得越来越聪明.

you'll have to get more and more clever as the numbers keep growing, of course.

当然，如果我急忙，我会使用 gmpy -但是，我显然有偏见；-).

If I was in a hurry, of course, I'd use gmpy -- but then, I'm clearly biased;-).

>>> import gmpy >>> gmpy.is_square(x**7) 1 >>> gmpy.is_square(x**7 + 1) 0

是的，我知道，这很容易，就像作弊一样(有点像我对Python的一般感觉；-)-一点也不聪明，只有完美的直接性和简单性(如果是俗气的话) ，绝对的速度；-)...

Yeah, I know, that's just so easy it feels like cheating (a bit the way I feel towards Python in general;-) -- no cleverness at all, just perfect directness and simplicity (and, in the case of gmpy, sheer speed;-)...