我对如何加快将给定范围内的倍数求和的算法感到困惑。这是针对codewars.com上的问题的，这里是该问题的链接codewars链接
这是代码，我将在底部解释发生了什么
import itertools
def solution(number):
return multiples(3, number) + multiples(5, number) - multiples(15, number)
def multiples(m, count):
l = 0
for i in itertools.count(m, m):
if i < count:
l += i
else:
break
return l
print solution(50000000) #takes 41.8 seconds
#one of the testers takes 50000000000000000000000000000000000000000 as input
# def multiples(m, count):
# l = 0
# for i in xrange(m,count ,m):
# l += i
# return l
所以基本上这个问题要求用户返回一个数字中3和5的所有倍数的和。这是测试人员。
test.assert_equals(solution(10), 23)
test.assert_equals(solution(20), 78)
test.assert_equals(solution(100), 2318)
test.assert_equals(solution(200), 9168)
test.assert_equals(solution(1000), 233168)
test.assert_equals(solution(10000), 23331668)
我的程序没有问题，没有找到正确的答案。当输入较大时会出现问题。当传递数字（例如50000000）时，需要40秒钟以上的时间才能返回答案。我被要求接受的输入之一是50000000000000000000000000000000000000000000000，这是一个巨大的数字。这也是itertools.count()我使用xrange我的第一次尝试但范围不能处理大于ac类型的数字的原因。我知道问题最慢的部分是倍数方法...但是它仍然比我第一次尝试使用列表理解并检查是否i % 3 == 0 or i % 5 == 0有想法的速度更快。
对于大量用户，此解决方案应该更快。
def solution(number):
number -= 1
a, b, c = number // 3, number // 5, number // 15
asum, bsum, csum = a*(a+1) // 2, b*(b+1) // 2, c*(c+1) // 2
return 3*asum + 5*bsum - 15*csum
解释：
取从1到n的任何顺序：
1, 2, 3, 4, ..., n
它的总和将始终由公式给出n(n+1)/2。如果您认为表达式(1 + n) / 2只是计算此特定数字序列的平均值或算术平均值的捷径，则可以轻松证明这一点。因为average(S) = sum(S) / length(S)，如果取任何数字序列的平均值，然后将其乘以序列的长度，则得出序列的总和。
如果给定一个数字n，并且我们希望某个给定k的倍数之和等于n，包括n，那么我们想求和：
k + 2k + 3k + 4k + ... xk
其中xk是k的小于或等于n的最高倍数。现在注意，该总和可以分解为：
k(1 + 2 + 3 + 4 + ... + x)
我们已经有了k，所以现在我们需要寻找的只是x。如果将x定义为最大数，则可以将k乘以得到小于或等于n的自然数，那么我们可以使用Python的整数除法来获得数x：
n // k == x
一旦找到x，就可以使用以前的公式找到任何给定的k到给定的n的倍数之和：
k(x(x+1)/2)
我们给定的三个k是3、5和15。
我们在这行中找到x：
a, b, c = number // 3, number // 5, number // 15
在此行中计算它们的倍数之和，直到n：
asum, bsum, csum = a*(a+1) // 2, b*(b+1) // 2, c*(c+1) // 2
最后，在这行中将它们的总和乘以k：
return 3*asum + 5*bsum - 15*csum
我们有我们的答案！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句