遞歸方法來查找鑑於這種樣品列表編號

列表的最低數量：遞歸方法來查找鑑於這種樣品列表編號

[5, 3, 9, 10, 8, 2, 7]

如何使用遞歸找到的最低數量？答案是2。

我在遞歸練習時發現了這個問題。我找不出解決這個問題的方法。要找到它，我必須首先對列表進行排序，然後再遞歸地執行任何操作。任何人都可以告訴我一條路嗎？

來源

2015-06-03 Blogger

如果列表中只有一個元素，則min是該元素。否則，比較第一個元素和列表中其餘部分的最小值。祝你好運！ – georg

@georg感謝您的提示先生！我如何開始遞歸？拿第一個元素？ – Blogger

你想要一個通用算法還是特定的語言？我認爲考慮到可用/允許的工具（如排序），這種方法會有很大差異。 – Molx

這是一個遞歸執行min：

l=[5, 3, 9, 10, 8, 2, 7] 
def find_min(l,current_minimum = None): 
    if not l: 
     return current_minimum 
    candidate=l.pop() 
    if current_minimum==None or candidate<current_minimum: 
     return find_min(l,candidate) 
    return find_min(l,current_minimum) 
print find_min(l) 
>>> 
2

要考慮到這不應該在實際程序中使用，並應被視爲鍛鍊。性能會比內置的min差幾個數量級。

來源

2015-06-03 14:59:00

這是我正在尋找的人！除了使用內置插件以外的遞歸方法！這就像選擇排序！ – Blogger

我猜你爲什麼得到更好的定時遞歸版本的原因是它銷燬列表，因此實際上只運行一次;） – georg

謝謝，我知道我錯了某處。 –

>>> import random 
>>> arr=[random.randint(0,8) for r in xrange(10)] 
>>> arr 
[8, 2, 5, 1, 2, 4, 0, 3, 1, 1] 
>>> def func(arr): 
    if len(arr) == 1: 
     return arr[0] 
    else: 
     return min(arr[0],func(arr[1:])) 


>>> f(arr) 
0

NB是不是真的在這裏需要遞歸。

來源

2015-06-03 14:55:05 0x90

謝謝@ 0x90！這是有道理的。我想知道在解決這個問題時，除了使用min（）方法以外沒有別的辦法嗎？：/（我的意思是我們可以不經過遞歸就直接使用min（）） – Blogger

我的答案顯示了一個遞歸實現，不用調用'min' –

@Blogger簡單地用'if'替換'min（..）'if [0 ] <..;返回一個[0];否則......' - 我會讓你填補空白。 – deceze

此答案使用累加器來存儲整個遞歸中的最小值。

list = [5, 3, 9, 10, 8, 2, 7] 

def min_list(list, min=None): 
    if len(list) < 1: 
     return min 
    return min_list(list[1:], list[0] if min is None or list[0] < min else min) 

print(min_list(list))

來源

2015-06-03 15:03:29

是的，就像在選擇排序！：D感謝支持@詹姆斯 – Blogger

這也適用，但只適用於長度爲2的冪的列表。對於其他長度，你只需要調整分割成更小的數組。該方法取自merge sort。

def findCloseToZero(l): 
    if len(l) == 1: 
     return l[0] 
    else: 
     first = findCloseToZero(l[0:int(len(l)/2)]) 
     sec = findCloseToZero(l[int(len(l)/2):]) 

     return first if abs(first) < abs(sec) else sec

來源

2017-10-04 15:50:17

遞歸方法來查找鑑於這種樣品列表編號

回答

相關問題