我正在尝试编写一个程序来查找一个介于 0 和 100 之间的数字 n,使得 n! + 1 是一个完美的正方形。我正在尝试这样做,因为我知道只有三个,所以这是为了测试我的 Python 能力。
请参阅Brocard 的问题。
我正在尝试编写一个程序来查找一个介于 0 和 100 之间的数字 n,使得 n! + 1 是一个完美的正方形。我正在尝试这样做,因为我知道只有三个,所以这是为了测试我的 Python 能力。
请参阅Brocard 的问题。
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 位,但我将把它作为练习留给读者。
您可能应该解决此问题的方法是使用纯整数数学。例如,您可以通过使用牛顿法确定一个整数是否是对数时间的平方,直到您的近似误差小到足以检查两个相邻的整数。
对于非常大的数字,最好完全避免使用浮点平方根,因为您会遇到太多精度问题,甚至无法保证您将在正确答案的 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
这是另一个仅使用整数的版本,通过添加 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)
math.sqrt 返回的数字绝不是 int,即使它是整数。如何检查浮点值是否为整数