1

我正在尝试编写一个程序来查找一个介于 0 和 100 之间的数字 n,使得 n! + 1 是一个完美的正方形。我正在尝试这样做,因为我知道只有三个,所以这是为了测试我的 Python 能力。

请参阅Brocard 的问题

4

4 回答 4

5

math.sqrt始终返回 a float,即使该浮点数恰好是4.0. 正如文档所说,“除非另有明确说明,否则所有返回值都是浮点数。”

所以,你的测试type(math.sqrt(x)) == int永远不会是真的。

您可以尝试通过检查浮点数是否表示整数来解决此问题,如下所示:

sx = math.sqrt(x)
if round(sx) == sx:

甚至还有一个内置方法可以做到这一点:

if sx.is_integer():

但请记住,float值并不是实数的完美表示,并且总是存在四舍五入的问题。例如,对于一个太大的数字,sqrt可能会四舍五入为整数,即使它确实不是一个完美的正方形。例如,如果math.sqrt(10000000000**2 + 1).is_integer()True,即使这个数字显然不是一个完美的平方。

我可以告诉你这在你的价值观范围内是否安全,但你能说服自己吗?如果不是,你不应该只是假设它是。

那么,有没有一种方法可以检查不受float道路问题的影响?当然,我们可以使用整数算术来检查:

sx = int(round(math.sqrt(x)))
if sx*sx == x:

但是,正如 Stefan Pochmann 所指出的,即使这个检查是安全的,这是否意味着整个算法是安全的?不; sqrt本身可能已经四舍五入到您失去整数精度的地步。

所以,你需要一个精确的sqrt. 您可以通过使用decimal.Decimal巨大的配置精度来做到这一点。这将需要一些工作和大量内存,但这是可行的。像这样:

decimal.getcontext().prec = ENOUGH_DIGITS
sx = decimal.Decimal(x).sqrt()

但是数字是ENOUGH_DIGITS多少?那么,您需要精确表示多少位数字100!+1

所以:

decimal.getcontext().prec = 156
while n <= 100:
    x = math.factorial(n) + 1
    sx = decimal.Decimal(x).sqrt()
    if int(sx) ** 2 == x:
        print(sx)
    n = n + 1

如果您考虑一下,有一种方法可以将所需的精度降低到 79 位,但我将把它作为练习留给读者。


您可能应该解决此问题的方法是使用纯整数数学。例如,您可以通过使用牛顿法确定一个整数是否是对数时间的平方,直到您的近似误差小到足以检查两个相邻的整数。

于 2015-05-26T01:19:03.440 回答
3

对于非常大的数字,最好完全避免使用浮点平方根,因为您会遇到太多精度问题,甚至无法保证您将在正确答案的 1 个整数值范围内。幸运的是,Python 本身支持任意大小的整数,因此您可以编写一个整数平方根检查函数,如下所示:

def isSquare(x):
    if x == 1:
        return True
    low = 0
    high = x // 2
    root = high
    while root * root != x:
       root = (low + high) // 2
       if low + 1 >= high:
          return False
       if root * root > x:
          high = root
       else:
          low = root
    return True

然后你可以像这样遍历从 0 到 100 的整数:

n = 0
while n <= 100:
    x = math.factorial(n) + 1
    if isSquare(x):
        print n
    n = n + 1
于 2015-05-26T01:50:01.587 回答
1

这是另一个仅使用整数的版本,通过添加 2 的递减幂来计算平方根,例如intsqrt(24680)将计算为 128+16+8+4+1。

 def intsqrt(n):
    pow2 = 1
    while pow2 < n:
        pow2 *= 2
    sqrt = 0
    while pow2:
        if (sqrt + pow2) ** 2 <= n:
            sqrt += pow2
        pow2 //= 2
    return sqrt

factorial = 1
for n in range(1, 101):
    factorial *= n
    if intsqrt(factorial + 1) ** 2 == factorial + 1:
        print(n)
于 2015-05-26T02:09:37.933 回答
0

math.sqrt 返回的数字绝不是 int,即使它是整数。如何检查浮点值是否为整数

于 2015-05-26T01:18:00.160 回答