递归函数以计算11是否划分一个数字

Question

我正在尝试编码递归函数（使用的python）以计算11是否在不使用休息的情况下将数字划分为11。我只需要使用此规则https：//en.wikipedia.org/wiki/11_(number）

代码有效，但是..我想知道是否有一种方法可以缩小它，也许无需变量" k"？

def f(n, k=0):
    if n=="" : return 0
    t = ((-1)**(len(n)-1))*int(n[0]) + f(n[1:],k+1)
    if k == 0:
        if t <= -11 or t >= 11:
            return f(str(abs(t)))
        elif t == 0:
            return True
        else:
            return False
    return t

Answer 1

让我们将设计翻转为（n不优化的）尾巴递归，因此，我们不要使用k检测到最高级别，而是向下传递t的增长值，并在最终计算时进行最终计算我们击中了基本情况：

def f(n, t=0):
    if not n:
        if -11 < t < 11:
            return t == 0
        return f(str(abs(t)))
    return f(n[1:], int(n[0]) - t)

现在，我们总是返回布尔值，而不是以前的混合布尔和整数结果！

Answer 2

它应该是严格的重新调查吗？不允许迭代吗？为了避免将k用作递归深度，您可以使用半回收的方式，并通过迭代来计算t，并使用递归减少t。

def f(n):
    t = 0
    for i in range(len(n)):
        t += (-1)**(i)*int(n[i])
    if t == 0 :
        return True
    if t < 11 and t > -11:
        return False
    return f(str(abs(t)))

Answer 3

不是您要寻找的内容，但是您可以修改功能以计算n mod m的结果，然后检查是否为零。类似的东西可以简化为：

def mod11(n):
    if not n: return 0
    diff = int(n[-1]) - mod11(n[:-1])
    if diff < 0: diff = diff and 11 - mod11(str(-diff))
    return diff

用法：

>>> mod11("242311") == 0
False
>>> not mod11("242311")
False
>>> not mod11("242308")
True

Answer 4

这是我到目前为止为纯递归（仅一个变量）所能做的最好的。如果字符串评估为零mod 11或否则，它将返回布尔值。

def f(s):
  if not s:
    return True
  r = f(s[1:])
  # If the rest of the string evaluates to
  # to zero mod 11, there's no need to
  # subtract it from the prefix.
  if isinstance(r, bool):
    return s[0]
  n = int(s[0]) - int(r)
  return True if n in [-11, 11, 0] else n
for x in ['11', '121', '54734', '1099989', '12', '65637', '1565432', '2345651']:
  print (x, f(x))

Answer 5

规则Wiki谈论的是试图测量奇数和偶数位置数字之间的差异。

如果您稍微改写一点，那就意味着只要2个方面不互相操纵，就可以同时处理它们。

（我的现有模块在awk中，但所有语言的概念方法都是相同的）：

function mod11(__, _, ___, ____, _____, ______)
{
    sub("^[^0-9+-]*[+-]?[0]*", "", __)
    if ((____ = length(substr(__, ___ *= ___ *= _ = ___ += ___ ^= ___ < ___, _))) < _) {
        return (! ____ ? __ % (--___ - _ * _) : ((substr(__, -_ < +_, ____ = _ * _) % (___ = --___ - _ * _)) (substr(__, ++____))) % (___))
    }
    ___ = ____ = _____ = ______ = ""
    ______ = gsub("...." "...." "...." "..", "&=", __)
    _____ ^= (____ = ! (___ = (_ *= _ += _ ^= _ < _) + (_ = _ * _ - ++_)))
    do {
        ____ = ((____) substr(__, _____, -_____ + (_____ += ___))) % _
    } while (--______)
    return ((____) substr(__, _____)) % _
}

基本上做的是 -

1. 如果输入足够小，只需直接使用内置的Modulo操作员

2. 否则，将十进制数字分成14位数字的块

3. 它从十进制数字的左端到右端运行，因为mod (%) 11是我所说的base-10 directionally-agnostic

   - 含义 - 水平翻转数字，mod 11保持不变。"3"是该

   的另一个例子

4. 每回合，我一次通过% 11运行一次，其余的人预先付费到下一轮的大量数字（因此14位数字是我可以从IEEE 754中挤出的最大值，而不会丢失精度）。

   - - 这是等同于将running-remainder x 10**14添加到下一轮

   的字符串-OPS

5. 设置块的方式可确保奇怪，甚至数字总是遵循自己的轨道而不是越过。该算法（可以在任何任意尺寸的输入中采用任何）是线性时间到十进制数字＃（用二进制术语来说是相当不错的）

6. 然后继续重复直到2^53 - 1下的最终块（加上剩余的预伪） - 在返回结果之前，包括1个最终模拟操作

这些想法是来自现有最佳实践的来源的零件，并将其调整为在基本10中直接进行处理，而无需过度转换为二进制。

（无需访问本机位移动操作员，不断将ASCII字符串除以2的量相当昂贵。这全都基于没有字符串slices的语言，这在此特定用例中可能是有益的）