Python中的遞歸函數，但奇怪的返回

Question

我想解決與幾個變量的主要方程。例如：11x + 7y + 3z = 20。只有非負整數結果。

我在python 3.5.1中使用下面的代碼，但結果包含類似[...]的東西。我想知道它是什麼？ 我有的代碼是測試從0到最大[總值除以相應變量]的每個變量。由於變量可能數量很大，我想使用遞歸來解決它。

def equation (a,b,relist): 
    global total 
    if len(a)>1: 
     for i in range(b//a[0]+1): 
      corelist=relist.copy() 
      corelist+=[i] 
      testrest=equation(a[1:],b-a[0]*i,corelist) 
      if testrest: 
       total+=[testrest] 

     return total 
    else: 

     if b%a[0]==0: 
      relist+=[b//a[0]]    
      return relist 
     else: 
      return False 


total=[] 
re=equation([11,7,3],20,[]) 

print(re) 

結果是

[[0, 2, 2], [...], [1, 0, 3], [...]] 

變化到一個新的可以得到乾淨的結果，但我仍然需要一個全局變量：

def equation (a,b,relist): 
global total 
if len(a)>1: 
    for i in range(b//a[0]+1): 
     corelist=relist.copy() 
     corelist+=[i] 
     equation(a[1:],b-a[0]*i,corelist) 

    return total 
else: 

    if b%a[0]==0: 
     relist+=[b//a[0]] 
     total+=[relist] 
     return 
    else: 
     return 

total=[] 
print(equation([11,7,3],20,[])) 

Answer 1

我看到這裏的問題三層。

1）似乎有一個關於遞歸的誤解。

2）似乎是你正在試圖解決（建模問題）

3）你的主要問題暴露了一些缺乏技能在Python本身存在問題的複雜性估計不足。

考慮到您的實際問題是「結果中包含像[...]之類的東西，我會解釋這些問題，我不知道它是什麼嗎？」

「[]」在Python中指定一個列表。

例如：

var = [ 1, 2 ,3 ,4 ] 

創建參考 「var」，以含有4個整數的值1，2，3和4的分別的列表。

var2 = [ "hello", ["foo", "bar"], "world" ] 

在另一方面var2是至3層的元件，一個字符串，另一個列表和一個字符串的複合列表的引用。第二個元素是2個字符串的列表。

所以你的結果是一個整數列表的列表（假設2個列表中的「...」是整數）。如果每個子列表具有相同的大小，您也可以將其視爲矩陣。而函數寫入的方式，最終可能會包含整數列表的組合列表，值爲「False」（或最新版本中的值「None」）

現在討論建模問題。等式11x + 7y + 3z = 20是具有3個未知數的一個方程。我不清楚你想用這個程序達到什麼目的，但是除非你通過選擇2個獨立變量來解決方程，否則你不會取得多大成就。對我而言，根本不清楚程序和公式之間的關係，除了你提供的參數值爲11,7和3之外，還有什麼關係。

我會做什麼（假設你正在尋找三胞胎（x，y）=（20/3） - （11/3）x - （7/3）y。然後我寧願寫的代碼是：

def func_f(x, y): 
    return 20.0/3.0 - (11.0/3.0) * x - (7.0/3.0) * y 

list_of_list_of_triplets = [] 
for (x, y) in zip(range(100),range(100)): 
    list_of_triplet = [x, y, func_f(x,y)] 
    list_of_list_of_triplets += [list_of_triplet] # or .append(list_of_triplet) 

請注意，該方程的解的數量是無限的。如果你限制了變量，你可以把它想象成直角棱鏡中的一條直線。如果你想代表尺寸的一個抽象的數字相同的線，你可以把上面的爲：

def func_multi_f(nthc, const, coeffs, vars): 
    return const - sum([a*b/nth for a,b in zip(coeffs, vars)]) 

哪裏nthc是第N個變量的係數，const是偏移常數，coeffs是名單系數和vars的值的N-1個其他變量。例如，我們可以將func_f重寫爲：

def func_f(x,y): 
    return func_multi_f(3.0, 20.0, [11.0, 7.0], [x,y]) 

現在講述遞歸。遞歸是爲了達到最終結果而可以被重複調用的可簡化輸入的表達式。在僞碼遞歸算法可以用公式表示爲：

input = a reduced value or input items 
if input has reached final state: return final value 
operation = perform something on input and reduce it, combine with return value of this algorithm with reduced input. 

例如，斐波那契數套房：

def fibonacci(val): 
    if val == 1: 
     return 1 
    return fibonacci(val - 1) + val 

如果你想recusively從列表中添加元素：

def sum_recursive(list): 
    if len(list) == 1: 
     return list[0] 
    return sum_recursive(list[:-1]) + list[-1] 

希望能幫助到你。

UPDATE

從意見和原來的問題編輯，我們似乎是相當尋找整數解的方程。非負值。這是完全不同的。

1）步驟一找到邊界：使用由+ CZ < = 20與方程ax +，B，C> 0並且x，y和z> = 0

2）步驟2，簡單地做如果x * 11 + y * 7 + z * 3 - 20 == 0]，則表示zip（bounds_x，bounds_y，bounds_z）中x，y，z的[（x，y，z）），並且您將得到一個有效三元組列表。

代碼：

def bounds(coeff, const): 
    return [val for val in range(const) if coeff * val <= const] 

def combine_bounds(bounds_list): 
    # here you have to write your recusive function to build 
    # all possible combinations assuming N dimensions 

def sols(coeffs, const): 
    bounds_lists = [bounds(a, const) for a in coeffs] 
    return [vals for vals in combine_bounds(bounds_lists) if sum([a*b for a,b in zip(coeff, vals)] - const == 0) 

Answer 2

這裏是你的第二個建立了一個解決方案，但沒有全局變量。相反，每個呼叫都會返回一個解決方案列表;父調用將每個解決方案附加到當前元素，使新的列表返回。

def equation (a, b): 
    result = [] 
    if len(a) > 1: 
     # For each valid value of the current coefficient, 
     # recur on the remainder of the list. 
     for i in range(b // a[0]+1): 
      soln = equation(a[1:], b-a[0]*i) 

      # prepend the current coefficient 
      # to each solution of the recursive call. 
      for item in soln: 
       result.append([i] + item) 
    else: 
     # Only one item left: is it a solution? 
     if b%a[0] == 0: 
      # Success: return a list of the one element 
      result = [[b // a[0]]] 
     else: 
      # Failure: return empty list 
      result = [] 

    return result 

print(equation([11, 7, 3], 20, []))