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.

我会做什么(假设你正在寻找解决方程的三元组值)是等式:f(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

如果要重复添加列表中的元素:

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

希望能帮助到你.

UPDATE

从评论和原始问题编辑来看,我们似乎正在寻找整数方程式的INTEGER解决方案.非负值.那是完全不同的.

1)第一步找到界限:使用方程ax + by + cz <= 20,a,b,c> 0和x,y,z> = 0

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)