分而治之算法的sumlist

Question

我想对总和使用分而治之算法，但是当我运行我的代码时，我收到以下消息

Traceback (most recent call last): File ".py", line 8, in print(Sumlist([10,80,30,60,120,150])) File ".py", line 6, in Sumlist return Sumlist(thelist[:mid])+Sumlist(thelist[mid:]) File ".py", line 6, in Sumlist return Sumlist(thelist[:mid])+Sumlist(thelist[mid:]) File ".py", line 6, in Sumlist return Sumlist(thelist[:mid])+Sumlist(thelist[mid:]) [Previous line repeated 995 more times] File "***.py", line 2, in Sumlist if thelist==[]: RecursionError: maximum recursion depth exceeded in comparison

def Sumlist(thelist):
    if thelist==[]:
        return 0
    else:
        mid=len(thelist)//2
        return Sumlist(thelist[:mid])+Sumlist(thelist[mid:])
print(Sumlist([10,80,30,60,120,150]))

Answer 1

您的代码正在进入无限递归，因为当列表中有 1 个元素时没有基本情况。

对于len(thelist) == 1，它无限分为2个长度为0和1的列表。

以下代码应该有效：

def Sumlist(thelist):
    if not thelist:
        return 0
    if len(thelist) == 1:
        return thelist[0]
    
    mid=len(thelist)//2
    return Sumlist(thelist[:mid]) + Sumlist(thelist[mid:])
        
print(Sumlist([10,80,30,60,120,150]))

Answer 2

基本情况还可以检查是否“mid == 0”并终止递归调用。代码可以是；

def sum_list(the_list):
    if  the_list == []:
        return 0
    mid = int(len(the_list) / 2)
    if  mid == 0:
        return the_list[mid]
    else:
        return sum_list(the_list[:mid]) + sum_list(the_list[mid:])

分而治之算法的sumlist

sumlist by divide and conquer algorithm

python

algorithm