[擂台] [转载]整数分解为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

有点意思   看看