Skip to main content
 首页 » 编程设计

python之接受一个列表并返回两个列表的递归函数

2024年12月31日12lidabo

我被要求定义一个递归函数,它接受一个列表,然后将那个列表的值以这样的方式分配给其他两个列表,当你采取将这两个列表中的每一个相加,您将得到两个彼此非常接近的结果。

示例:

如果我运行:

print(proximity_lists([5, 8, 8, 9, 17, 21, 24, 27, 31, 41])) 

我得到两个列表:

[31, 27, 21, 9, 8]          #sum = 96 
 
[41, 24, 17, 8, 5]          #sum = 95 

我就是这样做的,但是我无法理解如何在递归函数中返回两个列表。到目前为止,我对必须返回一个列表的条件感到满意。

到目前为止,这是我的代码:

def proximity_lists(lst, lst1 = [], lst2 = []): 
    """ 
    parameters : lst of type list; 
    returns : returns two lists such that the sum of the elements in the lst1 
              is in the proximity of the sum of the elements in the lst2 
    """ 
    if not lst: 
        if abs(sum(lst1)-sum(lst2)) in range(5):          
            return lst1, lst2 
    else: 
        return {Not sure what to put here} + proximity_lists(lst[1:]) 

就 range() 而言,它可以接受任何参数,只要它是它们可以彼此接近的最接近值。我选择了 5,因为根据上面的示例输出,它们之间的差异是 1。

我需要补充一点,这必须在没有任何模块帮助的情况下完成。它是使用简单的函数完成的。

请您参考如下方法:

就性能(指数复杂度)而言,这可能不是最佳解决方案,但也许它可以帮助您入门:

def proximity_lists(values): 
    def _recursion(values, list1, list2): 
        if len(values) == 0: 
            return list1, list2 
        head, tail = values[0], values[1:] 
        r1, r2 = _recursion(tail, list1 + [head], list2) 
        s1, s2 = _recursion(tail, list1, list2 + [head]) 
        if abs(sum(r1) - sum(r2)) < abs(sum(s1) - sum(s2)): 
            return r1, r2 
        return s1, s2 
 
    return _recursion(values, [], []) 
 
values = [5, 8, 8, 9, 17, 21, 24, 27, 31, 41] 
s1, s2 = proximity_lists(values) 
print(sum(s1), sum(s2)) 
print(s1) 
print(s2) 
 
96 95 
[24, 31, 41] 
[5, 8, 8, 9, 17, 21, 27] 

如果包装函数不行,直接调用_recursion(values, [], [])就可以了。