把数字拆分成2的幂的和

问题：

    任何数都能分解成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))