問題：
任何數都能分解成2的冪，比如
7=1+1+1+1+1+1+1
=1+1+1+1+1+2
=1+1+1+2+2
=1+2+2+2
=1+1+1+4
=1+2+4
共有6種分解方式，設f(n)為任意正整數可能分解總數，比如f(7)=6
寫個算法，輸入數，求出其分解的總數。
思路：
先按照樹形結構，把一個數可能的2的冪的子數記錄下來，比如7拆分成7個1，3個2，1個4。從高到底遍歷所有可能的搭配。
import math
import copy
def get_distribute_for_number(number):
distribute = {}
distribute[0] = number
for i in range(0, int(math.log(number, 2) + 1)):
if i not in distribute:
break
count_i = distribute[i]
while count_i >= 2:
count_i -= 2
if i + 1 not in distribute:
distribute[i + 1] = 0
distribute[i + 1] += 1
return distribute
def count_by_distribute(distribute, number, parent_expr):
if number == 0:
print("expr : %s"%parent_expr[:-3])
return 1
max_leaf = len(distribute) - 1
if max_leaf == 0:
print("expr : %s"%(parent_expr + " 1 * %d"%number))
return 1
curr_distribute = copy.copy(distribute)
max_leaf_value = 2 ** max_leaf
max_leaf_num = curr_distribute.pop(max_leaf)
count = 0
for i in range(0, max_leaf_num + 1):
left = number - max_leaf_value * i
expr = parent_expr
expr += "%d * %d"%(max_leaf_value, i)
expr += " + "
if left < 0:
break
count_left = count_by_distribute(curr_distribute, left, expr)
count += count_left
#print("current distribute is ")
#print(curr_distribute)
#print("kept %d leaves of %d"%(i, max_leaf_value))
#print("distributing num for %d is %d"%(left, count_left))
return count
number = input("Input Number:")
distribute = get_distribute_for_number(number)
print("Distribute for num is")
print(distribute)
count = count_by_distribute(distribute, number, "")
print("Number %d can be distributed by %d ways"%(number, count)) 
