清华大学计算机系复试资料.pdfVIP

2010清华计算机上机题简单回忆

一、特殊乘法，123*45=1*4+1*5+2*4+2*5+3*4+3*5

写个算法，对个小于的输，求结果

21000000000

二、数的分解：任何数都能分解成的幂，比如

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

共有种分解方式，设为任意正整数可能分解总数，比如

6f(n)f(7)=6

写个算法，输数，大于10000000000的按除以10000000000所得余数计算，求结果

三、时，，否则，为的进制表示的各

Nkroot(N,k)=Nroot(N,k)=root(N,k).NNk

位数字之和

输，输出的值这里为乘方，不是异或，，

x,y,kroot(x^y,k)(^)2=k=16

0x,y2000000000,

有一半的测试点里会溢出的范围

x^ynt(=2000000000)

题目只是大概回忆一下，可能不太准确，另外上机的输和输出都不是从文件，都是从控制

台输输出，每考完一题就将源程序的单个文件提交到指定网站，总共可以提交次，以随

50

后提交的结果为准。

感谢confucusl纠正第三题的部分错误

提供机试第二题——数的分解sum.c的另一种解法

谢谢jerryz920师兄帮我查到了机试成绩。

题目如下：

一个整数总可以拆分为的幂的和，例如：

2

7=1+2+4

7=1+2+2+2

7=1+1+1+4

7=1+1+1+2+2

7=1+1+1+1+1+2

7=1+1+1+1+1+1+1

总共有六种不同的拆分方式。

用表示的不同拆分的种数，例如

f(n)nf(7)=6.

要求编写程序，读n(不超过1000000)，输出f(n)%1000000000.

先给出代码：

#ncludestdo.h

ntf[1000001];

ntman()

{

nt,n;

scanf(%d,n);

f[0]=f[1]=1;

for(=2;=n;++){

f(%2)

f[]=f[-1];

else

f[]=(f[-1]+f[/2])%1000000000;

}

prntf(%d\n,f[n]);

return0;

}

当然，还可以优化，比如的长度和循环次数都可以半，这里略去。

f

思路如下：

对于奇数：它的拆分的第一项一定是，考虑去掉这个，其实就一一对应于

n=2k+111

2k的拆分，因此f(2k+1)=f(2k).

对于偶数：考虑有和没有的拆分。有的拆分，与的拆分一一对应，与上面

n=2k11