Python递归程序

Question

我在编程方面相对较新，因为我受过数学家教育，对Python没有经验。我想知道如何用Python解决这个问题，这是在我自学一道数学题时出现的：

程序要求一个正整数m。如果m的形式是2^n-1，则返回T（m）=n*2^{n-1}。否则，它将m写入格式2^n+x，其中-1<；x<；2^n，并返回T（m）=T（2^n-1）+x+1+T（x）。最后输出答案。在

Answer 1

我认为这是一个简单的问题，所以我尝试了一个解决办法。据我所知，这满足了原始问题中的参数。在

#!/usr/bin/python

import math

def calculate(m: int) -> int:
    """
    >>> calculate(10)
    20
    >>> calculate(100)
    329
    >>> calculate(1.2)
    >>> calculate(-1)
    """
    if (m <= 0 or math.modf(m)[0] != 0):
        return None
    n, x = decompose(m + 1)
    if (x == 0):
        return n * 2**(n - 1)
    else:
        return calculate(2**n - 1) + x + 1 + calculate(x)


def decompose(m: int) -> (int, int):
    """
    Returns two numbers (n, x), where
    m = 2**n + x and -1 < x < 2^n
    """
    n = int(math.log(m, 2))
    return (n, m - 2**n)


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = True)

假设calculate函数的单元测试中包含的数字是问题的正确结果，那么这个解决方案应该是准确的。当然，反馈是最受欢迎的。在