1

我正在尝试记住数字的除数总和。

divisorSums = {}

def sumDivisors(num):

    global divisorSums

    total = 0

    if num == 1:
        return 0

    for i in xrange(num/2, 0, -1):
        if i in divisorSums:
            return divisorSums[i]
        else:
            if not num % i:
                total += i

    divisorSums[num] = total

    return total

但是，当我遍历数字时，这将为所有数字返回 1。单独使用时是正确的，所以问题是我的查找系统。我很确定我不明白如何在字典中查找值。有人可以帮我吗？

4

2 回答 2

3

memoize 的常用捷径技巧是使用可变的默认参数

def sumDivisors(num, divisorSums={}):

    if num in divisorSums:          # Check if you have
        return divisorSums[num]     # memoized the answer here

    total = 0

    if num == 1:
        return 0

    for i in xrange(num/2, 0, -1):
        if not num % i:
            total += i

    divisorSums[num] = total

    return total

除此之外，您的代码似乎工作正常。你是如何运行它以获得公正的1？

于 2013-05-19T23:49:33.897 回答
2

这里：

if i in divisorSums:
            return divisorSums[i]

返回 divisorSums[i] 不是正确的做法，因为可能有一些质因数小于i. 这是使用辅助函数来记住/计算数字因子的一种方法：

from itertools import groupby
divisorC={}
def divisors(num):
    if num in divisorC:
        return divisorC[num]
    l = {1:1}
    for i in xrange(num/2, 1, -1):
        if num % i == 0:
            l[i] = 1 
            l.update(divisors(i))
            l.update(divisors(num/i))
            break
    divisorC[num] = l 
    return divisorC[num]
def sumDivisors(num):
    if num == 1: return 0
    l = {}
    for i in xrange(num/2, 0, -1):
        if num % i == 0:
            l.update(divisors(i))
            l.update(divisors(num/i))
            l[i] = 1 
            l[num/i] = 1 
            break
    return sum(v for v in l)
于 2013-05-19T23:51:32.810 回答