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, []))