计算数字中数字出现次数的递归函数 (python)

Question

我需要找出第一在一个数字中出现的次数。这是我拥有的：

示例输入：11001

期望输出：3

def oneCount(n):
    n = str(n)
    if n == '1':
        return 1
    else:
        return 1 + oneCount(n[:-1])

print oneCount(1100)

现在它 returns 位数而不是位数。

Answer 1

我一开始不想回答这个问题，但所有糟糕的答案都迫使我...

首先，递归作为终结案例和递归案例。终端情况是您可以立即知道结果的情况。对于您的任务，它是空字符串，因为它包含零个：

if n == '':
  return 0

在递归的情况下，你必须检查你的字符串是否以 1 开头:

if n.startswith('1'):
  return 1+oneCount(n[1:])
else:
  return oneCount(n[1:])

此外，您每次都将 n 转换为字符串，这是不必要的。

Pythonic 解决方案将使用 if not n: 而不是 if n == '':，因此完整的解决方案可能看起来像

def oneCountRecur(n):
  if not n:
    return 0

  if n.startswith('1'):
    return 1 + oneCountRecur(n[1:])
  else:
    return oneCountRecur(n[1:])

def oneCount(n):
  return oneCountRecur(str(n))

return oneCountRecur(n[1:])上面的else:可以省略，看个人口味。

Answer 2

def oneCount(n):    
    n = str(n)
    # Here, you check if the entire string is '1'.
    # Not sure if you mean to check if a single digit is '1'.
    if n == '1':
        return 1
    else:
        # If the entire string is not '1', you recur on all but the least significant digit.
        return 1 + oneCount(n[:-1])
print oneCount(1100)

步行：

oneCount(1100) -> '1100' is not '1'. recurs on 1 + oneCount('110')
1 + oneCount('100') -> '110' is not '1'. recurs on 1 + (1 + oneCount('11'))
2 + oneCount('00') -> '11' is not '1'. recurs on 2 + (1 + oneCount('1'))
3 + oneCount('0') -> '1' is '1'. return 1
4

好的，所以这是一个错误的答案，但也许更阴险，如果你的最高有效数字不是 1 怎么办？

oneCount(2)
>>> RuntimeError: maximum recursion depth exceeded while calling a Python object

你最终在空字符串上重复出现。空字符串不是'1'，所以递归是无限的！

当在字符串或列表等可迭代对象上重复出现时，一个好的经验法则是将空可迭代对象视为您的基本情况。

def oneCount(i):
    i = str(i)
    if i == '':
        return 0
    # Do not recur in the base case, above
    # The below cases are not the base case, so expect to recur
    # What is the nature of the recursion?
    car, cdr = i[0], i[1:] # silly lisp reference
    if car == '1':
        ???
    # else?

纯属娱乐

作为整数的布尔值

考虑一个布尔值相当于 Python 中的整数值 1 或 0。您可以将该值加到一个整数上。

return (car == 1) + oneCount(cdr)

激进

考虑到您无需将整数转换为字符串即可对其进行迭代。考虑 cdr, car = divmod(i, 10)，或者更简单地说，cdr, car = i // 10, i % 10。有趣的是，它使您能够计算任何基数中数字出现的次数。

def oneCount(i, base=10):
    if i == 0:
        return 0
    cdr, car = divmod(i, base)
    if car == 1:
        ???
    ???

>>> oneCount(int('111111100000', 2), 2)
7

Answer 3

既然你坚持递归解决。开始了

def oneCount(n):
    digits = str(n)
    count = 1 if digits.startswith('1') else 0
    for digit in digits[1:]:  # start looping from next digit
        count += oneCount(digit)
    return count

编辑：如果您认为上述函数不够递归：

def oneCount(n):
    digits = str(n)
    count = 1 if digits.startswith('1') else 0
    if len(digits) > 1: 
        count += oneCount(digits[1:])
    return count

Answer 4

一个简单的解决方案：

def oneCount(n):
    n = str(n)
    # if we have reached the end of n return 0
    if not n:
        return 0
    # check current n[0] is == 1 and move right one char in n
    else:
        return (n[0] == "1") + oneCount(n[1:])

Answer 5

def oneCount(n):  
    if not n:  
        return 0  
    else:  
        return (n % 10 == 1) + oneCount(n // 10)

计算数字中数字出现次数的递归函数 (python)

Recursion Function to count the occurrence of a digit in a number (python)

python

recursion

function

counting

纯属娱乐

作为整数的布尔值

激进