我正在解决一个问题,我必须确定给定的数字是否是斐波那契数。
它涉及一个步骤,我们必须检查 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
}
上述两种寻找完美正方形的方法有什么区别?
它是否也会影响程序的时间复杂度?