遞歸邏輯計算硬幣變化/足球比分

Question

我想了解question張貼在stackflow中。

我試圖用給出的答案之一來計算遞歸的邏輯NFL比分

score = 10 
points = [7, 3, 2] 
names = {7: "touchdown", 3: "field goals", 2 : "safeties"} 

def count_combs(left, i, comb, add): 
    if add: comb.append(add) 
    if left == 0 or (i+1) == len(points): 

     if (i+1) == len(points) and left > 0: 
      comb.append((left, points[i])) 
      i += 1 
     while i < len(points): 
      comb.append((0, points[i])) 
      i += 1 
     print " ".join("%d %s" % (n,names[c]) for (n,c) in comb) 
     return 1 
    cur = points[i] 
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1)) 

print count_combs(score, 0, [], None) 

值出來是不正確。

0 touchdown 0 field goals 10 safeties 

它必須是安全裝置5不10.

Answer 1

的代碼錯誤地假定的points最後的值總是要1。在處理金錢時這可能是一個很好的假設，因爲幾乎總是會有一個面額硬幣1，但它不適合您的足球版本的代碼。

的錯誤是在此塊中：

 if (i+1) == len(points) and left > 0: 
     comb.append((left, points[i])) 
     i += 1 

更正確地執行該塊的需要做兩件事情是不同的。首先，它需要確保left可以被points[i]整除，否則你將無法獲得所需的分數。它還需要在append調用中使用left/points[i]，因爲它不能依賴最後一個值爲1。

下面的代碼的固定版本，對新東西的評論：

def count_combs(left, i, comb, add): 
    if add: comb.append(add) 
    if left == 0 or (i+1) == len(points): 
     if (i+1) == len(points) and left > 0: 
      if left % points[i]: # can't get the exact score with this kind of points 
       return 0   # so give up on this recursive branch 
      comb.append((left/points[i], points[i])) # fix the amount here 
      i += 1 
     while i < len(points): 
      comb.append((0, points[i])) 
      i += 1 
     print " ".join("%d %s" % (n,names[c]) for (n,c) in comb) 
     return 1 
    cur = points[i] 
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))