开发者

recursive method returning original value

So I'm trying to learn python on my own, and am doing coding puzzles. I came across one that pretty much ask for the best position to stand in line to win a contest. The person running the contest gets rid of people standing in odd number positions.

So for example if 1, 2, 3, 4, 5

It would get rid of the odd positions leaving 2, 4

Would get rid of the remaining odd positions leaving 4 as the winner.

When I'm debugging the code seems to be working, but it's returning [1,2,3,4,5] instead of the expected [4]

Here is my code:

def findWinner(contestants):
    if (l开发者_如何学运维en(contestants) != 1):
        remainingContestants = []
        for i, contestant in enumerate(contestants, 1):
            if (isEven(i)):
                remainingContestants.append(contestant)
        findWinner(remainingContestants)
    return contestants

Am I not seeing a logic error or is there something else that I'm not seeing?


You must return the value from the recurse function to the caller function:

return findWinner(remainingContestants)

else you would return just the original value without any changes.

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)


How about this:

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

I know its not what the questions really about but I had to =P. I cant just look at all that work for finding the greatest power of 2 less than contestants and not point it out.

or if you don't like the 'artificial' solution and would like to actually perform the process:

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


you shold use

return findWinner(remaingContestants)

otherwise, of course, your list will never be updated and so your func is gonna always return containts

however, see the PEP8 for style guide on python code: http://www.python.org/dev/peps/pep-0008/

the func isEven is probably an overkill...just write

if not num % 2

finally, recursion in python isn't recommended; make something like

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


Is there a reason you're iterating over the list instead of using a slice? Doesn't seem very python-y to not use them to me.

Additionally, you might want to do something sensible in the case of an empty list. You'll currently go into an infinite loop.

I'd write your function as

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

(much as @jon_darkstar's point, this is a bit tangential to the question you are explicitly asking, but still a good practice to engage in over what you're doing)


You are missing a return at the line where you call "findWinner"

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜