开发者

Python recursive program

I'm relatively newcomer on programming as I'm educated a mathematician and have no experience on Python. I would like to know how to solve this problem in Python which appeared as I was studying one maths problem on my own:

Program asks a positive integer m. If m is of the form 2^n-1 it returns T(m)=n*2^{n-1}. Otherwise it writes m to the form 2^n+x, where -1 <开发者_运维技巧; x < 2^n, and returns T(m)=T(2^n-1)+x+1+T(x). Finally it outputs the answer.


I thought this was a neat problem so I attempted a solution. As far as I can tell, this satisfies the parameters in the original question.

#!/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)

Assuming the numbers included in the calculate function's unit tests are the correct results for the problem, this solution should be accurate. Feedback is most welcome, of course.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜