学步园

1.给定一个包含大量不同的30位二进制字x₁,....,x_N的文件，找出其中所有补码对{x_i,x_j}的好方法是什么？（互补的充要条件为和为（11...111)₂ ）

    解法：记c=2³¹-1，首先对文件进行排序，使得x₁<x₂<.....<x_N.  记i=1,j=N;重复下列步骤直到j<=i:

   if x_i+x_j = c,print{x_i,x_j },i += 1;j -= 1;

   if x_i+x_j < c,i + = 1;

   if x_i+x_j > c,i -= 1;

最后，如果j=i且2x_i = c,则输出{x_i,x_j }.

2.给定一个含有1000个30位二进制字x₁,....,x_N的文件，如何编制一份所有对偶{x_i,x_j }的表，使得除最多两个二进数位外，x_i = x_j ?

解法：

方案a:对于满足1<=i<j<=1000的499 500个对偶i,j的每一个，置m=x_i ^ x_{j ,}n = m & (m -1) ,r = n & (n -1 ),当且仅当r = 0时，输出对偶{x_i,x_j}。

方案b:由原来的字x_i形成31个项，其中包括x_i本身及在一个位置上不同于x_i的另外30个字，这样得到一个共有31000个项的文件。对这个文件进行排序，考察其中的重复性。

3.在有4096个人的某人群中，每个人大约有100个相识者。一个文件已经列出所有相识的对偶。怎样设计一个算法，对于给定的K，列出这群人中所有K个人的团体（一个团体是互相认识的一组人，每个人都与其它人相识）？假定不存在人数是25的团体，因此团体的总数不可能很多。

解法：一个方法是形成包含所有三个人的集体的一个文件，然后把它变换为含有所有四个人的集体的文件，等等；如果没有很大的集体，则这个方法将是十分令人满意的。（另一方面，如果有n个人的集体，则至少有C_nk个K个人的集体，所以甚至当n仅仅是25人左右时，这个方法仍可能失败。）

    以（a₁,....a_k-1)的形式列举出k个人的集体的一个文件，其中a₁ <...< a_k-1,我们可以通过（i）对于使b<c，其分别的形式为(a₁,...,a_k-2,b),(a₁,...,a_k-2,c)的每对k-1个人的集体，建立包含项(b,c,a₁,...,a_k-2)的一个新文件；（ii）按其头两个分量对这个文件进行排序；（iii）在同原来给定的文件中的一对相识者（b,c）匹配的新文件中的每个项(b,c,a₁,...,a_k-2)，输出k个人的团体(a₁,...,a_k-2,b,c)。

4.你是美国国内税收服务人员，你收到了来自各单位的数百万“信息”表格，报告他们已向人们支付了多少钱；同时，又从人们那里收到了数百万“税收”表格，报告他们已经得到了多少收入。你如何发现没有报告收入的所有人？

解法：

给每一个人指定一个标识号，这个号必须在所有涉及他的表格中出现。以这个标识号为键码，分别对信息表格和赋税表格进行排序。以R1,...,RN表示排好序的赋税表格，其键码为K1<...<kN。增加一个键码为无穷大的记录，这是第N+1个记录，并且置i=1;然后对于信息文件中的每个记录，校验它是否已经报告如下：设K表示正在处理的信息表上的键码。

a)如果K>ki,则i+=1,重复这个步骤

b)如果k<ki或者k=ki,而且信息不反映到赋税表格Ri上，则标出一个错误，表示该人没有纳税。

参考书目：《计算机程序设计与艺术》第三卷 Donald E.Knuth 著 苏云霖 译 国防工业出版社2002.9