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 函数的单元测试中包含的数字是问题的正确结果，则此解决方案应该是准确的。当然，我们非常欢迎您提供反馈。