2017-04-26 45 views
0

我對我寫的一段代碼有疑問。這是爲了獲得數組中片數的合計爲零。不過,我希望能夠使用遞歸在Python中執行此操作。請看看我的代碼,並讓我知道,如果你看到的東西關閉。與迭代方法相比,我沒有得到正確答案。分而治之 - 獲取零和切片的數量

def sumzeros(A, low, mid, high): 
    leftsum = 0 
    rightsum = 0 
    counter = 0 

    for i in range(low, mid+1): 
     leftsum += A[i] 

    for j in range(mid+1, high+1): 
     rightsum += A[j] 

    if leftsum + rightsum == 0: 
     counter += 1 

    return counter 


def solution(A, low, high): 
    if low == high: 
     if A[low] == 0: 
      return 1 
     else: 
      return 0 
    else: 
     mid = (low + high) // 2 

     left = solution(A, low, mid) 
     right = solution(A, mid+1, high) 
     cross = sumzeros(A, low, mid, high) 

     return cross + left + right 

print('Recursive solution: Number of sum zeros = {}'.format(solution(A, 0, len(A) - 1))) 

回答

0

使用MID =(低+高)/ 2MID =高 - (高 - 低)/ 2

+0

無論那些,得到正確的答案。第二個選項實際上導致了最大遞歸問題。 我使用了下面的例子[0,0,0]和[2,-2,3,0,4,-7],並且都給出了錯誤的答案。 [0,0,0]的正確答案是6,[2,-2,3,0,4,-7]的正確答案是4。 – Butcher