有沒有辦法編寫一個遞歸函數來查看列表中的所有整數，並查看是否有任何兩個等於負和？

所以問題是，你有一個整數列表，你必須找到列表中的任何兩個和爲負數。有沒有辦法編寫一個遞歸函數來查看列表中的所有整數，並查看是否有任何兩個等於負和？

現在我有這個

def negsum(L): 
    if len(L) <= 2: 
     if L[0] + L[1] >= -1: #Here is my base case 
      return False 
     else: 
      return True 
    else: 
     if L[0] + L[1] <= -1: 
      return True 
     else: 
      return negsum(L[1:]) #Recursive portion

我的代碼的問題是它僅在列表中檢查第2。因此，在列表 [-10,15,30,5]中，當它應該爲真時，您會得到False，因爲-5 + -10是負值。我的函數只檢查：

-10 + 15

15 + 30

30 - 5

我怎樣才能得到它，以便它檢查-10 + 30，-10 -5 15-5使用遞歸？

編輯，我忘了提及，只有len（）[]和：操作符是允許的。沒有循環。這甚至可能沒有循環？

來源

2014-10-10 J0hn

難道你只是對它們進行排序並檢查兩個最小值是否總和爲「<0」？ – khelwood 2014-10-10 22:36:00

或者，如果算法的複雜性是最重要的，'返回和（heapq.nsmallest（2，L））<0' – roippi 2014-10-10 22:41:30

這裏是沒有循環的溶液（隱式或顯式）：

def negsum(lst, sub=True): 
    return len(lst) > 1 \ 
     and ((lst[0] + lst[1]) < 0 
       or negsum([lst[0]]+lst[2:], False) 
       or (sub and negsum(lst[1:])))

，或者可選地，下面的版本更清潔的過程分離成2子功能，並且不需要額外的參數「子」：

def negsum(lst): 
    def first_with_others(lst): # compare lst[0] with all later values 
     if len(lst) > 1: 
      #print("summing", lst[0], "and", lst[1]) 
      return ((lst[0] + lst[1]) < 0) or first_with_others([lst[0]]+lst[2:]) 
    def drop_first(lst): # successively drop first element 
     if lst: 
      return first_with_others(lst) or drop_first(lst[1:]) 
    return drop_first(lst) or False # converts None to False

在取消對呼叫到打印功能示出了計算總和：

>>> negsum([1,2,3,4,5]) 
summing 1 and 2 
summing 1 and 3 
summing 1 and 4 
summing 1 and 5 
summing 2 and 3 
summing 2 and 4 
summing 2 and 5 
summing 3 and 4 
summing 3 and 5 
summing 4 and 5 
False 
>>> negsum([-1,2,3,4,5]) 
summing -1 and 2 
summing -1 and 3 
summing -1 and 4 
summing -1 and 5 
summing 2 and 3 
summing 2 and 4 
summing 2 and 5 
summing 3 and 4 
summing 3 and 5 
summing 4 and 5 
False 
>>> negsum([-1,2,3,-4,5]) 
summing -1 and 2 
summing -1 and 3 
summing -1 and -4 
True 
>>> negsum([-2,1]) 
summing -2 and 1 
True

來源

2014-10-10 22:40:17 uselpa

下面是做到這一點的一種方法：

def negsum(L): 
    if len(L)<2: return False 
    if len(L) == 2: 
     if sum(L)<0: return True 
     else: return False 
    for i,elem in enumerate(L): 
     if elem < 0: 
      return negsum(L[i+1:]+[elem])

輸出：

In [39]: negsum([1,2,3,4,5]) 
Out[39]: False 

In [40]: negsum([-1,2,3,4,5]) 
Out[40]: False 

In [41]: negsum([-1,2,3,-4,5]) 
Out[41]: True

來源

2014-10-10 22:40:40 inspectorG4dget

@ Smac89：好抓！固定:) – inspectorG4dget 2014-10-10 22:48:46

在編輯中，OP規定「無循環」 – 2014-10-10 23:07:31

的想法是將列表intwo部分：第一件L[0]其餘L[1:]和遞歸的使用功能L[1:]部分：

def negsum(L): 
    if len(L) == 2:  # base case 
     return True if L[0] + L[1] < 0 else False 
    elif negsum(L[1:]): # recursion on the L[1:] part 
     return True 
    else:    # check L[1:] part pairwise against the first element 
     return any(x + L[0]<0 for x in L[1:])

來源

2014-10-10 22:45:15 elyase

有沒有辦法編寫一個遞歸函數來查看列表中的所有整數，並查看是否有任何兩個等於負和？

回答

相關問題