时间戳

首页 > 解决方案 > 当数字除以 11 时找到余数的递归函数

python - 当数字除以 11 时找到余数的递归函数

问题描述

我应该编写一个递归函数来查找除以 11 时的余数，我必须使用以下规则：

例如，对于号码 918392：

F(918392) = F(2-9+3-8+1-9) = F(-20) = 11 - F(20) = 11 - F(0-2) = 11 - F(-2) = 11 - (11 - F(2)) = 11 - (11-2) = 2

我相信我的代码是正确的，但是在提交时，它给出了 4/9 测试用例的运行时错误。有什么建议可以改进我的代码吗？？；< 谢谢！

def rem(number):
    sum = 0
    j = -1
    for i in range(0, len(number)):
        sum = sum + (-1)**(i) * int(number[j])
        j = j - 1
        
        
    if 0 <= sum < 11:
        return sum
    
    else:
        return 11 - rem(str(abs(sum)))
    
    
    
number = str(input())
print(rem(number))

标签： pythonalgorithmrecursion

解决方案

有两个问题：

  • 11 的减法应该只在sum为负数时发生，如果sum是 11 或更多（正数），那么你应该进行递归调用，但不要通过从 11 中减去它来“反转”它。

  • 在您必须从 11 中减去它的情况下，递归调用有可能返回 0，因此 11 - 0 变为 11，这不是可接受的返回值。在这种情况下，您应该返回 0。所以您需要检测这种情况。

这是该if...else构造的更正版本：

if 0 <= sum < 11:
    return sum
elif sum < 0:
    sum = 11 - rem(str(-sum))
    return 0 if sum == 11 else sum
else:
    return rem(str(sum))

旁注：sum是一个原生 Python 函数。考虑为您的变量使用不同的名称。

考虑到这一点，一些优化，对负数的支持，并允许参数是字符串或数字类型，代码可以变成：

def rem(number):
    total = int(number)
    if total >= 0:
        total = 0
        sign = 1
        for dig in reversed(str(number)):
            total += sign * int(dig)
            sign = -sign
        
    if total < 0:
        total = 11 - rem(-total)
        return 0 if total == 11 else total
    return total if total < 11 else rem(total)

推荐阅读