清华的一道复试上机题，高手请解,该如何解决

清华的一道复试上机题，高手请解
二、数的分解：任何数都能分解成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亿)的此类划分数

[解决办法]
假设结果为f(n)，有递推公式f(2m+1)=f(2m)，f(2m)=f(2m-1)+f(m)，考虑分解中是否有1就很容易证明上述递推公式。
[解决办法]

C/C++ code

#include <stdio.h>unsigned long f(long n){  if (n <= 1) return 1;  if ((n & 1) == 1) return f(n - 1);  return f(n - 1) + f(n >> 1);}void main(){  long i;  for (i = 1; i < 21; i++)  {    printf("f(%ld) = %lu\n", i, f(i));  }}
[解决办法]
用double算了一个近似，可能已经溢出了

1 1
2 2
4 4
8 10
16 36
32 202
64 1828
128 27338
256 692004
512 30251722
1024 2320518948
2048 316359580362
4096 77477180493604
8192 3.43948699429834E+16
16384 3.53287171195276E+19
32768 6.73918495069097E+22
65536 2.39968178877809E+26
131072 1.60214274691412E+30
262144 2.01349157777264E+34
524288 4.77974622192621E+38
1048576 2.14985297217792E+43
2097152 1.83724164757586E+48
4194304 2.99064249666006E+53
8388608 9.29371453258517E+58
16777216 5.52508542464127E+64
33554432 6.29557287866179E+70
67108864 1.37731330581882E+77
134217728 5.79464569464248E+83
268435456 4.69527041818826E+90
536870912 7.33719500311418E+97
1073741824 2.21406079783977E+105
2147483648 1.29168245920552E+113
4294967296 1.45851714324846E+121
8589934592 3.1908693726185E+129
17179869184 1.3538562272705E+138
[解决办法]
探讨

请教楼上各位：
f(2m)=f(2m-1)+f(m)怎么来的啊？

[解决办法]
C/C++ code
#include <stdio.h>typedef unsigned long bigint;// f(2m + 1) = f(2m)// f(2m) = f(2m - 2) + f(m) = Σ(i=0→m)f(i)// f(0) = f(1) = 1bigint f(long n){  long i, m = n >> 1;  bigint s = 1, *f = (bigint *)calloc(m + 1, sizeof(bigint));  f[0] = 1;  for (i = 1; i <= m; i++)  {    f[i] = s += f[i >> 1];  }  return s;}void main(){  long i;  for (i = 1; i < 101; i++)  {    printf("f(%ld) = %lu\n", i, f(i));  }}
[解决办法]
稍微改进一下，可以节省一半的数组存储空间：
C/C++ code
#include <stdio.h>typedef unsigned long bigint;// f(2m + 1) = f(2m)// f(2m) = f(2m - 2) + f(m) = Σ(i=0→m)f(i)// f(0) = f(1) = 1bigint f(long n){  long i, m = n >> 1, m2 = m >> 1;  bigint s = 1, *f = (bigint *)calloc(m2 + 1, sizeof(bigint));  f[0] = 1;  for (i = 1; i <= m2; i++)    f[i] = s += f[i >> 1];  for (; i <= m; i++)    s += f[i >> 1];  return s;}void main(){  long i;  for (i = 1; i < 101; i++)  {    printf("f(%ld) = %lu\n", i, f(i));  }}
[解决办法]
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
f(21) = 60
f(22) = 74
f(23) = 74
f(24) = 94
f(25) = 94
f(26) = 114
f(27) = 114
f(28) = 140
f(29) = 140
f(30) = 166
f(31) = 166
f(32) = 202
f(33) = 202
f(34) = 238
f(35) = 238
f(36) = 284
f(37) = 284
f(38) = 330 
 
f(39) = 330
f(40) = 390
f(41) = 390
f(42) = 450
f(43) = 450
f(44) = 524
f(45) = 524
f(46) = 598
f(47) = 598
f(48) = 692
f(49) = 692
f(50) = 786
f(51) = 786
f(52) = 900
f(53) = 900
f(54) = 1014
f(55) = 1014
f(56) = 1154
f(57) = 1154
f(58) = 1294
f(59) = 1294
f(60) = 1460
f(61) = 1460
f(62) = 1626
f(63) = 1626
f(64) = 1828
f(65) = 1828
f(66) = 2030
f(67) = 2030
f(68) = 2268
f(69) = 2268
f(70) = 2506
f(71) = 2506
f(72) = 2790
f(73) = 2790
f(74) = 3074
f(75) = 3074
f(76) = 3404
f(77) = 3404
f(78) = 3734
f(79) = 3734
f(80) = 4124
f(81) = 4124
f(82) = 4514
f(83) = 4514
f(84) = 4964
f(85) = 4964
f(86) = 5414
f(87) = 5414
f(88) = 5938
f(89) = 5938
f(90) = 6462
f(91) = 6462
f(92) = 7060
f(93) = 7060
f(94) = 7658
f(95) = 7658
f(96) = 8350
f(97) = 8350
f(98) = 9042
f(99) = 9042
f(100) = 9828

[解决办法]
我说的是计算后的结果用int64装不下，这题问的是拆分的种类，大概在n=16000的时候，
用int64记录结果就已经溢出了。

这种整数划分的问题，其结果的数量真的很大，不知道用泰勒展开能不能求。

探讨

何出此言呢？
32位int的取值范围是-2147483648 to +2147483648 
这就已经21亿了，100亿只比21亿大了约5倍
64位int的取值范围是-9,223,372,036,854,775,808 ~ +9,223,372,036,854,775,808
这比21亿大了约21亿倍（怎么100亿用int64存不下？）

[解决办法]
我试了求一下生成函数G(x)，有如下关系：G(x^2)=(1-x)G(x)，G(0)=1，大概求得
G(x)=1/{(1-x)(1-x^2)(1-x^4)(1-x^8)(1-x^16)...}，好像找不到G(x)的解析式，所以泰勒展开可能没用
探讨

我说的是计算后的结果用int64装不下，这题问的是拆分的种类，大概在n=16000的时候，
用int64记录结果就已经溢出了。

这种整数划分的问题，其结果的数量真的很大，不知道用泰勒展开能不能求。


引用:
何出此言呢？
32位int的取值范围是-2147483648 to +2147483648
这就已经21亿了，100亿只比21亿大了约5倍
……

[解决办法]
一年是3.15*10^7秒
如果一秒输出一万个结果就是一年能输出3.15*10^11个结果
按你说的如果int64都存不下你的结果
int64约是 10^18 ，按上面的速度输出你算算输出这个结果要多少年？保存结果要多少内存？
清华的教授再NB他估计也看不完啊！


[解决办法]
膜拜7楼：hblac  
回复于：2010-03-25 21:52:44
假设结果为f(n)，有递推公式f(2m+1)=f(2m)，f(2m)=f(2m-1)+f(m)，考虑分解中是否有1就很容易证明上述递推公式。  
  

这条推导公式出来，注定这个贴已经没有新的亮点了....
  
[解决办法]
探讨


膜拜7楼：hblac
回复于：2010-03-25 21:52:44
假设结果为f(n)，有递推公式f(2m+1)=f(2m)，f(2m)=f(2m-1)+f(m)，考虑分解中是否有1就很容易证明上述递推公式。


这条推导公式出来，注定这个贴已经没有新的亮点了....

[解决办法]
探讨


to:wuyi8808

如何计算还是个问题...


请参考22楼。

知道结果很大，但是已经不重要了啊。

[解决办法]
C# code
using System;using Skyiv.Numeric;class Program{  // f(2m + 1) = f(2m)  // f(2m) = f(2m - 2) + f(m)  // f(2m) = f(0) + f(1) + ... + f(m)  // f(0) = f(1) = 1  static BigInteger f(long n)  {    long i = 1, m = n >> 1, m1 = m >> 1, m2 = m1 >> 1;    BigInteger[] f = new BigInteger[m2 + 1];    f[0] = 1;    BigInteger s = 1, r = 1;    for (; i <= m2; i++)      r += f[i] = s += f[i >> 1];    for (; i < m1; i++)      r += s += f[i >> 1];    BigInteger r0 = m < 1 ? 0 : r;    if (i == m1) r += s += f[i >> 1];    return r + ((m & 1) == 0 ? r0 : r);  }  static void Main()  {    foreach (long n in new long[]{ 33554432, 67108864, 134217728 })    {      Console.WriteLine("f({0}) = {1}", n, f(n));    }  }}