[转载]整数分解为2的幂的和

mathe

http://topic.csdn.net/u/20100325 ... 4-1ed8f6b49c99.html 数的分解：任何数都能分解成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 求任意整数n(n<100亿)的此类划分数 如果对于更加大的n呢？比如$n=10^20$

wayne

f(2m+1)=f(2m)，f(2m)=f(2m-1)+f(m),f(1)=1,f(2)=2

关键是找出 递推式子f(n) 设其生成函数为G(x),那么 $G(x^2)=(1-x)G(x)$

qianyb

只要把数转化为2进制，然后把对应位为1的值相加即可

mathe

只要把数转化为2进制，然后把对应位为1的值相加即可 qianyb 发表于 2010-3-31 09:55

显然错误，给出链接处的参考数据： f(1) = 1 f(2) = 2 f(3) = 2 f(4) = 4 f(5) = 4 f(6) = 6 f(7) = 6 f(8) = 10 f(9) = 10 f(10) = 14 f(11) = 14 f(12) = 20 f(13) = 20 f(14) = 26 f(15) = 26 f(16) = 36 f(17) = 36 f(18) = 46 f(19) = 46 f(20) = 60

mathe

关键是找出 递推式子f(n) 设其生成函数为G(x),那么 G(x^2)=(1-x)G(x) wayne 发表于 2010-3-31 09:52

这个公式还是比较容易得出的。 但是在n比较大的时候要有效计算还是有点困难的。

qianyb

我以为题目是说把一个数怎么分为由2的幂次数组成（如7＝1+2+4），没看链接内容

qianyb

f(1) = 1 f(2) = 2 f(3) = 2 f(4) = 4 f(5) = 4 f(6) = 6 f(7) = 6 f(8) = 10 f(9) = 10 f(10) = 14 f(11) = 14 f(12) = 20 f(13) = 20 f(14) = 26 f(15) = 26 f(16) = 36 f(17) = 36 f(18) = 46 f(19) = 46 f(20) = 60 这个数是怎么算出来的？ 题目不是要计算N由2的幂次数组成的不同方法的数量吗 如 2＝1+1, D（2）＝1 3＝1+1+1＝1+2，D（3）＝2 4＝1+1+1+1＝1+1+2＝2+2,D（4）＝3

mathe

2=2 2=1+1 4=1+1+1+1 4=1+1+2 4=2+2 4=4

qianyb

原来2＝2，4＝4也算一种的话啊

dalaopeng

有点意思 看看