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.
精彩评论