2010-11-09 213 views
0

所以我试图自己学习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 

难道我没有看到一个逻辑错误或者是还有别的,我没有看到?

回答

3

必须从递归函数来调用程序函数返回值:

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) 
+0

嗯,那有效。谢谢,我不确定你是什么意思,我仍然需要删除偶数的选手,但我删除了那些奇怪的选项。我现在得到了我的预期结果,我没有看到逻辑上的其他错误... – Ryan 2010-11-09 17:12:42

0

你缺少在该行一回,你所说的“findWinner”

1

你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 
3

如何:

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 
+0

我测试了所有不同的解决方案,第一种数学方法绝对是最快的,第二种方法实际上是第二快,切片略微落后。我真的不明白你所做的背后的数学。第二种(也是desfido的方法)这样做我明白发现,它不是我想到的第一件事情,因为我刚刚从一两天前开始学习python。感谢您的建议! – Ryan 2010-11-09 18:36:35

+0

切片慢?我不会想到。创造不必要的枚举看起来像是浪费,但我想我不知道当你切片时在幕后发生了什么。我会尽快在下面的评论中以我的第一种方式向你解释数学。 – 2010-11-09 18:41:27

+0

每次传球你都会排除奇数位置的参赛者,并将偶数位置的参赛者减少一半。那些处于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

1

有你遍历列表,而不是使用的切片的原因是什么?似乎不是非常蟒蛇 - 不使用它们给我。

此外,您可能想要在空列表的情况下做一些明智的事情。你现在将进入一个无限循环。

我会写你的功能

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

(就像@ jon_darkstar的角度来看,这是一个有点切给你明确地提出这个问题,但仍然是一个很好的做法,在你搞”重做)

+0

等等呢?是的,他们清理了递归问题,但这也很好。该切片是一个奇妙的想法,比我在第二个例子中做的列表更好。 +1(顺便说一句pythonic!) – 2010-11-09 17:59:57

+0

我觉得有一个更简单的方法,显然我仍然有很多东西要学习Python!谢谢! – Ryan 2010-11-09 18:37:19