返回原始值的遞歸方法

所以我試圖自己學習python，並且正在編寫謎題。我遇到了一個非常需要排隊贏得比賽的最佳位置。運行比賽的人擺脫了站在奇數位置的人。返回原始值的遞歸方法

因此，舉例來說，如果1，2，3，4，5

這將擺脫奇數位置留下2，4

就會改掉其餘奇數位置留下4作爲勝利者的。

當我調試的代碼似乎是工作，但它的返回[1,2,3,4,5]而不是預期的[4]

這裏是我的代碼：

def findWinner(contestants): 
    if (len(contestants) != 1): 
     remainingContestants = [] 
     for i, contestant in enumerate(contestants, 1): 
      if (isEven(i)): 
       remainingContestants.append(contestant) 
     findWinner(remainingContestants) 
    return contestants

難道我沒有看到一個邏輯錯誤或者是還有別的，我沒有看到？

來源

2010-11-09 Ryan

必須從遞歸函數來調用程序函數返回值：

return findWinner(remainingContestants)

否則你將只返回原始值無任何變化。

def findWinner(contestants): 
    if (len(contestants) != 1): 
     remainingContestants = [] 
     for i, contestant in enumerate(contestants, 1): 
      if (isEven(i)): 
       remainingContestants.append(contestant) 
     return findWinner(remainingContestants) # here the value must be return 
    return contestants # without the return above, it will just return this value(original)

來源

2010-11-09 16:50:38 olivervbk

嗯，那有效。謝謝，我不確定你是什麼意思，我仍然需要刪除偶數的選手，但我刪除了那些奇怪的選項。我現在得到了我的預期結果，我沒有看到邏輯上的其他錯誤... – Ryan 2010-11-09 17:12:42

你缺少在該行一回，你所說的「findWinner」

來源

2010-11-09 16:51:01 Vincent

你shold使用

return findWinner(remaingContestants)

否則，當然，你的清單將不會被更新，所以你的FUNC是會永遠返回containts

但是，請參閱PEP8風格指南上的蟒蛇代碼：http://www.python.org/dev/peps/pep-0008/

的FUNC ISEVEN可能是矯枉過正...只寫

if not num % 2

最後，不建議在遞歸蟒;製造類似

def find_winner(alist): 
    while len(alist) > 1: 
     to_get_rid = [] 
     for pos, obj in enumerate(alist, 1): 
      if pos % 2: 
       to_get_rid.append(obj) 
     alist = [x for x in alist if not (x in to_get_rid)] 
    return alist

來源

2010-11-09 16:52:17 Ant

如何：

def findWinner(contestants): 
    return [contestants[2**int(math.log(len(contestants),2))-1]]

我知道它不是真正的問題，您來，但我不得不= P。我不能只看看所有這些工作，找出比參賽者少2倍的最大力量，而不是指出。

，或者如果你不喜歡的「人爲」的解決方案，並希望實際執行過程：

def findWinner2(c): 
    while len(c) > 1: 
     c = [obj for index, obj in enumerate(c, 1) if index % 2 == 0] #or c = c[1::2] thanks desfido 
    return c

來源

2010-11-09 17:19:50

我測試了所有不同的解決方案，第一種數學方法絕對是最快的，第二種方法實際上是第二快，切片略微落後。我真的不明白你所做的背後的數學。第二種（也是desfido的方法）這樣做我明白髮現，它不是我想到的第一件事情，因爲我剛剛從一兩天前開始學習python。感謝您的建議！ – Ryan 2010-11-09 18:36:35

切片慢？我不會想到。創造不必要的枚舉看起來像是浪費，但我想我不知道當你切片時在幕後發生了什麼。我會盡快在下面的評論中以我的第一種方式向你解釋數學。 – 2010-11-09 18:41:27

每次傳球你都會排除奇數位置的參賽者，並將偶數位置的參賽者減少一半。那些處於2（2^4 = 16,2^5 = 32等）更高冪的位置在變得奇怪之前可以減半數次。第一遍 - 消除奇數位置（可被2^0 == 1整除，不能被2^1 == 2整除）。第N次傳球 - 原地排除參賽者可以被2^n-1整除但不是2^n的位置。所以...... len（c）的log base 2表示find 2其中2^x = len（c）。這可能不是整數，所以在w/int（x）的下面得到整數。 2^int（x）是贏家的位置，但是我們減去1，因爲數組從0開始。 – 2010-11-09 18:45:55

有你遍歷列表，而不是使用的切片的原因是什麼？似乎不是非常蟒蛇 - 不使用它們給我。

此外，您可能想要在空列表的情況下做一些明智的事情。你現在將進入一個無限循環。

我會寫你的功能

def findWinner(contestants): 
    if not contestants: 
     raise Exception 
    if len(contestants)==1: 
     return contestants[0] 
    return findWinner(contestants[1::2])

（就像@ jon_darkstar的角度來看，這是一個有點切給你明確地提出這個問題，但仍然是一個很好的做法，在你搞」重做）

來源

2010-11-09 17:53:33 desfido

等等呢？是的，他們清理了遞歸問題，但這也很好。該切片是一個奇妙的想法，比我在第二個例子中做的列表更好。 +1（順便說一句pythonic！） – 2010-11-09 17:59:57

我覺得有一個更簡單的方法，顯然我仍然有很多東西要學習Python！謝謝！ – Ryan 2010-11-09 18:37:19

返回原始值的遞歸方法

回答

相關問題