python中可能存在整数溢出

2024-03-29 13:14:31 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在完成hackerrank的euler问题1计划。 我写了一个暴力解决方案来检查我的答案。它似乎是正确的,除了输入10^9。 我被告知正确答案是:

2333331666668

我回来了:

2333331666680

n = 1000000000
sum_of_multiples_3 = int((int((n-1)/3.0)+1) * (int((n-1)/3.0)/2.0) * 3)
sum_of_multiples_5 = int((int((n-1)/5.0)+1) * (int((n-1)/5.0)/2.0) * 5)
sum_of_multiples_15 = int((int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0) * 15)
print(sum_of_multiples_3 + sum_of_multiples_5 - sum_of_multiples_15)

Tags: of答案解决方案计划intsumprinteuler
1条回答
网友
1楼 · 发布于 2024-03-29 13:14:31

您使用的是浮点除法,整数除法可以:

int((n-1)/3.0)

更好地表达为

(n-1)//3

例如,使用Python的floor division操作符,不要使用float,然后使用floor。你知道吗

当您将浮点运算扩展到极限之外时,使用整数楼层除法不会遇到舍入问题。你知道吗

当您将n推得足够大时,可以看到这种舍入错误:

>>> n = 100000000
>>> int((int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0) * 15)
333333316666665
>>> ((n-1)//15+1) * ((n-1)//15//2) * 15
333333316666665
>>> n = 1000000000
>>> int((int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0) * 15)
33333333166666664
>>> ((n-1)//15+1) * ((n-1)//15//2) * 15
33333333166666665

额外的1纯粹是因为您遇到了浮动的限制:

>>> (int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0)
2222222211111111.0
>>> ((n-1)//15+1) * ((n-1)//15//2)
2222222211111111
>>> (int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0) * 15
3.3333333166666664e+16

我不知道你为什么总是从n中减去一个;这根本不需要,而且会导致错误的结果。也许你是想补偿浮动舍入误差?正确的公式是:

(((n // 3) + 1) * (n // 3)) // 2 * 3
(((n // 5) + 1) * (n // 5)) // 2 * 5
(((n // 15) + 1) * (n // 15)) // 2 * 15

为任何n提供正确的输出:

>>> n = 1000000000
>>> sum_of_multiples_3 = (((n // 3) + 1) * (n // 3)) // 2 * 3
>>> sum_of_multiples_5 = (((n // 5) + 1) * (n // 5)) // 2 * 5
>>> sum_of_multiples_15 = (((n // 15) + 1) * (n // 15)) // 2 * 15
>>> sum_of_multiples_3 + sum_of_multiples_5 - sum_of_multiples_15
233333334166666668

我会用一个函数来计算倍数:

def sum_of_multiples(n, k):
    k_in_n = n // k
    return ((k_in_n + 1) * k_in_n) // 2 * k

因此,您可以通过与暴力总和进行比较来验证它是否有效:

>>> sum(range(0, 10000 + 1, 3)) == sum_of_multiples(10000, 3)
True
>>> sum(range(0, 10000 + 1, 5)) == sum_of_multiples(10000, 5)
True
>>> sum(range(0, 10000 + 1, 15)) == sum_of_multiples(10000, 15)
True

然后用它来计算答案:

>>> sum_of_multiples(n, 3) + sum_of_multiples(n, 5) - sum_of_multiples(n, 15)
233333334166666668

相关问题 更多 >