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。以下は、ヘルパー関数を使用して因数を記憶/計算する方法の 1 つです。

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 に答える