整容说文库 > 程序代码 > 教育资讯

清华的一道复试上机题,高手请解

来源:学生作业帮助网 编辑:整容说文库 时间:2021/06/18 10:46:37 程序代码
清华的一道复试上机题,高手请解程序代码
二、数的分解:任何数都能分解成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亿)的此类划分数
换成2进制看就知道
10011=2^4+2^1+2^0
引用 1 楼 leonardwang 的回复:
换成2进制看就知道

估计楼主也是一下被懵住了吧。。。
引用楼主 herechaos 的回复:
二、数的分解:任何数都能分解成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亿)的此类划分数


划分数, 这个要想一想.
我想, 首先应该考虑2的幂(如: 1、2、4、8、16、32、...)的划分数的情况.
n这么大说明不能用动态规划了,所以必定有规律

我猜测如下:
考虑n二进制表
n=a[k]*2^k       k=0,1,2...  其中的a[k]=0或者1
则划分数h[n]=Σh[a[k]*2^k]
然后对2^k的划分数就转化为
对求整数k的划分数,这个就是经典的划分数了。
假设结果为f(n),有递推公式f(2m+1)=f(2m),f(2m)=f(2m-1)+f(m),考虑分解中是否有1就很容易证明上述递推公式。
上面不是求和,应该是求积哈 ∏
很简单,其实就是换算成2进制。
引用 7 楼 hblac 的回复:
假设结果为f(n),有递推公式f(2m+1)=f(2m),f(2m)=f(2m-1)+f(m),考虑分解中是否有1就很容易证明上述递推公式。


高, 实在是高!

我5楼的想法想得过于复杂了, 方向性错误.
试着写了一个递归程序:

class Program
{
  static void Main()
  {
    for (int i = 1; i < 21; i++)
    {
      System.Console.WriteLine("f({0}) = {1}", i, f(i));
    }
  }
  
  static ulong f(long n)
  {
    if (n <= 1) return 1;
    if ((n & 1) == 1) return f(n - 1);
    return f(n - 1) + f(n >> 1);
  }
}
/* 程序输出:
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 达到100亿可能会超时, 程序要进行优化.
用DP也可以,就是100元钱换零钱的变种。
#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));
  }
}
引用 7 楼 hblac 的回复:
假设结果为f(n),有递推公式f(2m+1)=f(2m),f(2m)=f(2m-1)+f(m),考虑分解中是否有1就很容易证明上述递推公式。

能不能解释一下
f(2m)=f(2m-1)+f(m) 这个是怎么来的?!!
请教!
不用了.
引用 7 楼 hblac 的回复:
假设结果为f(n),有递推公式f(2m+1)=f(2m),f(2m)=f(2m-1)+f(m),考虑分解中是否有1就很容易证明上述递推公式。


巧妙!学习了
用贪心算法?
理解错了 原来是划分数
f(2m)=f(2m-1)+f(m)这个怎么理解?
刚才简单试了一下,发现100亿用int64存不下,这下平添了不少难度。
7楼的递推很巧妙,看看能不能利用这个递推,找出通项来,否则算100亿恐怕算不了。
这个数的规模基本上大于log(n)^log(n),因此以100亿来算,应该大于3.4*10^50
这里的高手还真的是不少啊
同问:
f(2m)=f(2m-1)+f(m)这个怎么理解?

引用 18 楼 leonardwang 的回复:
理解错了 原来是划分数
f(2m)=f(2m-1)+f(m)这个怎么理解?
用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)怎么来的啊?
引用 21 楼 leontown 的回复:
同问:
f(2m)=f(2m-1)+f(m)这个怎么理解?

引用 18 楼 leonardwang 的回复:
理解错了 原来是划分数
f(2m)=f(2m-1)+f(m)这个怎么理解?


2m的分解可以分为两种,有1的和没有1的
f(2m-1)是有1的数目,f(m)是没有1的数目
引用 19 楼 litaoye 的回复:
刚才简单试了一下,发现100亿用int64存不下,这下平添了不少难度。
7楼的递推很巧妙,看看能不能利用这个递推,找出通项来,否则算100亿恐怕算不了。
这个数的规模基本上大于log(n)^log(n),因此以100亿来算,应该大于3.4*10^50


通项公式不一定能找出
即使找出了,大数的表示也是不可避免的
令f(0)=1
则f(n)=f(n-1)  n是奇数
  f(n)=f(0)+f(1)+...+f(n/2) n是偶数
根据这个式子一个一个算吧,线性复杂度
用大数库去表示
引用 23 楼 leontown 的回复:
请教楼上各位:
f(2m)=f(2m-1)+f(m)怎么来的啊?


f(2m+1)=f(2m) ,奇数必然要拆分出1.
f(2m) = f(2m-1) + f(m),偶数如果拆分出1,那么就有f(2m-1)种方法,如果不拆分出1,那么拆分出的必然都是偶数,也就是说,拆分数相当于f(m)的每个拆分项乘以2.

其实由上面两个式子推出:
f(0)=f(1)=1
f(2m)=sigma(k from 0 to m)f(k)

但是对于这个求和公式不知道是否有直接公式。
至少需要找到Sqrt(n)的方法,并且空间占用也是这个规模的,否则即使时间上可以等,
空间上恐怕还是放不下100亿。

引用 25 楼 michael122 的回复:
通项公式不一定能找出
即使找出了,大数的表示也是不可避免的
令f(0)=1
则……
请问怎么估算结果是多少十进制位?
#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) = 1
bigint 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));
  }
}
稍微改进一下,可以节省一半的数组存储空间:
#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) = 1
bigint 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));
  }
}


但这个空间还是O(n)的,而不是O(sqrt(n))的,不知litaoye和各位大侠有什么好办法没有?
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
高手真多啊,来学习了。
f(2n) 约等于 f(n) * n / log(n) * k

大家可以估算一个k值,然后推算结果,当n很大时,这个k趋近于常数,这样的话,可以有一个log(n)的估值方法。

引用 28 楼 gogdizzy 的回复:
请问怎么估算结果是多少十进制位?
to:空军,我也没找到什么好的方法,不过我觉得应该有
fgag afdsfsaf fasd
友情关注下。
好难啊  我怎么看不懂啊  新手看来得好好学习一下子 
学习了。原以为就是换算成2进制。
学习了。
呵呵。不错不错。学习学习
来学习的````
划分数。
PUOUP
考虑下时间和空间效率!!!
XUEXI
我是来学习的
应该是用递推的方法,不过10亿,还是蛮大的...压力很大...
晕!转化成二进制就行了,动态规划都来了....
哇 这也太难了吧
真的要学习学习
程序代码