问题:
任何数都能分解成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))
相关推荐
十进制数字拆分成4字节十六进制数.vi十进制数字拆分成4字节十六进制数.vi
基于单片机数字拆分的一种高效算法.pdf
把一个数 分解成2的次幂 有listView 输出,简单的实现
一个字拆分成高低字节 西门子1200的库,添加到博图v14sp1及以上版本软件的全局库文件夹中,在程序中即可调用;
这是一个数字查分的代码源程序,初学者的天堂,非常好懂,里面有解释。
按列将表拆分成单独的Excel文件 将Excel表按照指定的列分组拆分并另存为单独的Excel文件 例如:A列有10条数据,汇总后是三个员工,使用小工具可以将表按照每个员工拆分成单独的Excel文件 关键点: 1、小工具要与...
CSV表格拆分,可以把一个CSV文件按固定行数拆分成多个文件
本文主要讲了数码管多位数字拆分的方法,下面一起来学习一下
任意正整数都能拆成若干唯一的2的幂指数之和,php版本和js版本都有。
将这个线性表拆分成一个奇数线性表和一个偶数线性表线,性表的最大长度为20.
Map拆分和List拆分在对于大数据处理的时候起到了很大的作用。
整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分
按行把一个txt文件平均拆分成N个txt文件,结果是一行文本组成一个txt文件,适用于语料的按行切分。
excel文件工作薄拆分成单独文件,将工作表信息按特定的信息拆分成单独的文件
数字分组和拆分.doc
本资源是个各种数字证书查看工具,以及各种证书转换工具,将keystore拆成crt和key
将一个整数线性表拆分成奇数和偶数线性表,课后习题,完整好用
把大的PDF文件拆分成指定大小文件,但是因为每页的文件大小不一定,就不能通过固定页数来拆分文件,这样子的话就需要我们通过计算来将文件拆分这指定大小的文件
1.该软件用于按列拆分excel,如第一列有三种取值,使用该软件即可拆分为3个以取值...4.该软件使用指定需要拆分的列时需要输入两个列的数字序号或列字母序号,并以空格分隔,如:1 2,对于一列则输入两个相同数字:1 1
可以将Excel文件按Sheet拆分成多个,支持批量拆分Excel文件,需要安装jre支持;适合批量拆分Excel需求;