论坛 › 编程擂台 › [转载]整数分解为2的幂的和

mathe 发表于 2010-3-31 09:00:22

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

http://topic.csdn.net/u/20100325/20/38e39935-9463-452c-a194-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 发表于 2010-3-31 09:52:18

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 发表于 2010-3-31 09:55:14

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

mathe 发表于 2010-3-31 10:17:43

只要把数转化为2进制，然后把对应位为1的值相加即可
qianyb 发表于 2010-3-31 09:55 http://bbs.emath.ac.cn/images/common/back.gif
显然错误，给出链接处的参考数据：

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 发表于 2010-3-31 10:19:01

关键是找出 递推式子f(n)

设其生成函数为G(x),那么
G(x^2)=(1-x)G(x)
wayne 发表于 2010-3-31 09:52 http://bbs.emath.ac.cn/images/common/back.gif
这个公式还是比较容易得出的。
但是在n比较大的时候要有效计算还是有点困难的。

qianyb 发表于 2010-3-31 10:51:50

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

qianyb 发表于 2010-3-31 10:55:31

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 发表于 2010-3-31 11:11:01

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

qianyb 发表于 2010-3-31 12:17:40

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

dalaopeng 发表于 2010-3-31 22:14:06

有点意思   看看

查看完整版本: [转载]整数分解为2的幂的和