时间戳

首页 > 解决方案 > 这些检查完美正方形的算法有什么区别？

python - 这些检查完美正方形的算法有什么区别？

问题描述

我正在解决一个问题，我必须确定给定的数字是否是斐波那契数。

它涉及一个步骤，我们必须检查 5*n*n-4 或 5*n*n+4（n 是给定的数字并且总是大于 0）是否是完美的正方形。如果这些术语中的任何一个或两者都是完美的正方形，那么它就是斐波那契数，否则不是。

我使用下面的语句来检查一个完美的正方形。

def isPerfectSquare(n):
    x = 5*n**2-4
    y = 5*n**2+4
    r1 = int(math.sqrt(x))
    r2 = int(math.sqrt(y))
    return r1*r1==x or r2*r2==y
}

但是这种方法对 4 个测试用例显示了错误的答案。

而当我使用这个（下面）方法时，它通过了所有测试用例。

def isPerfectSquare(n):
    r1 = math.sqrt(5*n**2-4)
    r2 = math.sqrt(5*n**2+4)
    return r1%1==0 or r2%1==0
}

上述两种寻找完美正方形的方法有什么区别？

它是否也会影响程序的时间复杂度？

标签： pythonfibonacciperfect-square

解决方案

long long 会自动将您的数字四舍五入，这就是为什么它无法通过某些测试尝试将 sqrt 存储在 double 或 long double 中

推荐阅读