2013-05-19 71 views
1

我試圖記憶除數的和數。在Python中尋找值字典

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。當它單獨使用時是正確的,所以問題是我的查找系統。我很確定我不明白如何在字典中查找價值。有人可以幫我嗎?

+0

並不適用於所有數字,嘗試'100',它返回'117' – enginefree

+0

當我通過1環到100,他們都回到1 ,其中包括100. – Tetramputechture

+0

對於'98'我得到'73' – enginefree

回答

3

的常用快捷鍵的伎倆memoize的是使用mutuable默認參數

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 

比你的代碼似乎工作OK等。你如何運行它只得到1

+0

不知道你能做到這一點!謝啦! – Tetramputechture

+0

此代碼不完全正確地記憶。請參閱當它循環時,它不會在divisorSums中查找值。 – Tetramputechture

+0

@Tetramputechture,我明白你在說什麼。 memoize是好的,但你在divisorSums詞典中查看的地方,最好是遞歸地調用函數。不幸的是,我現在沒有時間寫這個版本 –

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) 
+0

當我運行這個時,它返回6的除數總和爲4,當它應該是6.嗯。 – Tetramputechture

+0

@Tetramputechture,用不同的邏輯更新:) – perreal

+0

哇,這是一個非常大的變化 – Tetramputechture