python 计算列表中的奇数

Question

这是我家庭作业的一部分，我已经接近最终答案，但还没有完全实现。我需要编写一个计算列表中奇数的函数。

创建一个递归函数 count_odd(l) ，它将整数列表作为其唯一参数。该函数将返回奇数列表元素的数量，即不能被 2 整除的列表元素的数量。\

>>> print count_odd([])  
0  
>>> print count_odd([1, 3, 5])  
3  
>>> print count_odd([2, 4, 6])  
0  
>>> print count_odd([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144])  
8  

这是我到目前为止所拥有的： #- 递归函数 count_odd -#

def count_odd(l):
    """returns a count of the odd integers in l.
    PRE: l is a list of integers.
    POST: l is unchanged."""
    count_odd=0

    while count_odd<len(l):
        if l[count_odd]%2==0:
            count_odd=count_odd
        else:
            l[count_odd]%2!=0
            count_odd=count_odd+1
    return count_odd

#- test harness  
print count_odd([])  
print count_odd([1, 3, 5])  
print count_odd([2, 4, 6])  
print count_odd([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144])  

你能帮忙解释一下我缺少什么吗？前两个测试工具工作正常，但我无法获得最后两个。谢谢！

Answer 1

由于这是作业，请考虑这个仅对列表进行计数的伪代码：

function count (LIST)
    if LIST has more items
        // recursive case.
        // Add one for the current item we are counting,
        // and call count() again to process the *remaining* items.
        remaining = everything in LIST except the first item
        return 1 + count(remaining)
    else
        // base case -- what "ends" the recursion
        // If an item is removed each time, the list will eventually be empty.
        return 0

这与作业要求的非常相似，但需要将其转换为 Python，并且您必须计算出正确的递归案例逻辑。

快乐编码。

Answer 2

def count_odd(L):
    return (L[0]%2) + count_odd(L[1:]) if L else 0

Answer 3

切片好吗？对我来说，感觉不到递归，但我想整个事情有点违反通常的习惯用法（即 - Python 中的这种递归）：

def countOdd(l):
    if l == list(): return 0           # base case, empty list means we're done
    return l[0] % 2 + countOdd(l[1:])  # add 1 (or don't) depending on odd/even of element 0.  recurse on the rest

x%2 is < code>1 为赔率，0 为偶数。如果您对此感到不舒服或只是不理解它，请使用以下内容代替上面的最后一行：

   thisElement = l[0]
   restOfList = l[1:]
   if thisElement % 2 == 0: currentElementOdd = 0
   else: currentElementOdd = 1
   return currentElementOdd + countOdd(restOfList)

PS - 这是相当递归的，如果您将其转入=P，请看看您的老师怎么说

>>> def countOdd(l):
...     return fold(lambda x,y: x+(y&1),l,0)
... 
>>> def fold(f,l,a):
...     if l == list(): return a
...     return fold(f,l[1:],f(a,l[0]))

Answer 4

所有先前的答案都将问题细分为大小为 1 和大小为 n-1 的子问题。有几个人指出，递归堆栈可能很容易崩溃。此解决方案应将递归堆栈大小保持在 O(log n)：

def count_odd(series):
    l = len(series) >> 1
    if l < 1:
        return series[0] & 1 if series else 0
    else:
        return count_odd(series[:l]) + count_odd(series[l:])

Answer 5

递归的目标是将问题分成更小的部分，并将解决方案应用于更小的部分。在这种情况下，我们可以检查列表的第一个数字 (l[0]) 是否为奇数，然后使用列表的其余部分 ( l[1:])，将当前结果添加到递归结果中。

Answer 6

def count_odd(series):
    if not series:
        return 0
    else:
        left, right = series[0], series[1:]
        return count_odd(right) + (1 if (left & 1) else 0)

Answer 7

尾部递归

def count_odd(integers):
    def iter_(lst, count):
        return iter_(rest(lst), count + is_odd(first(lst))) if lst else count
    return iter_(integers, 0)

def is_odd(integer):
    """Whether the `integer` is odd."""
    return integer % 2 != 0 # or `return integer & 1`

def first(lst):
    """Get the first element from the `lst` list.

    Return `None` if there are no elements.
    """
    return lst[0] if lst else None

def rest(lst):
    """Return `lst` list without the first element."""
    return lst[1:]

Python 中没有尾部调用优化，因此上述版本纯粹是教育性的。

该调用可以可视化为：

count_odd([1,2,3])    # returns
iter_([1,2,3], 0)      # could be replaced by; depth=1
iter_([2,3], 0 + is_odd(1)) if [1,2,3] else 0 # `bool([1,2,3])` is True in Python
iter_([2,3], 0 + True) # `True == 1` in Python
iter_([2,3], 1)        # depth=2
iter_([3], 1 + is_odd(2)) if [2,3] else 1
iter_([3], 1 + False)  # `False == 0` in Python
iter_([3], 1)          # depth=3
iter_([], 1 + is_odd(3)) if [3] else 1
iter_([], 2)           # depth=4
iter_(rest([]), 2 + is_odd(first([])) if [] else 2 # bool([]) is False in Python
2 # the answer

简单的蹦床

为了避免大型数组的“超出最大递归深度”错误，递归函数中的所有尾部调用都可以包装在 lambda: 表达式中；并且可以使用特殊的 Trampoline() 函数来解包此类表达式。它有效地将递归转换为简单循环的迭代：

import functools

def trampoline(function):
    """Resolve delayed calls."""
    @functools.wraps(function)
    def wrapper(*args):
        f = function(*args)
        while callable(f):
            f = f()
        return f
    return wrapper

def iter_(lst, count):
    #NOTE: added `lambda:` before the tail call
    return (lambda:iter_(rest(lst), count+is_odd(first(lst)))) if lst else count

@trampoline
def count_odd(integers):
    return iter_(integers, 0)

示例：

count_odd([1,2,3])
iter_([1,2,3], 0)         # returns callable
lambda:iter_(rest(lst), count+is_odd(first(lst))) # f = f()
iter_([2,3], 0+is_odd(1)) # returns callable
lambda:iter_(rest(lst), count+is_odd(first(lst))) # f = f()
iter_([3], 1+is_odd(2))   # returns callable
lambda:iter_(rest(lst), count+is_odd(first(lst))) # f = f()
iter_([], 1+is_odd(3))
2                         # callable(2) is False

Answer 8

我会这样写：

def countOddNumbers(numbers): 
    sum = 0
    for num in numbers:
        if num%2!=0:
            sum += numbers.count(num)
    return sum 

Answer 9

不确定我是否收到你的问题，但与上面类似：

def countOddNumbers(numbers): 
    count=0
    for i in numbers:
        if i%2!=0:
            count+=1
    return count

Answer 10

生成器可以用一行代码快速给出结果：

sum((x%2 for x in nums))