编程珠玑第二章探讨

这一章给出了三个小问题,都非常有趣且实用,分别用来阐述二分法递归与抽象离散化思想。第一个问题可以认为是二分思想的巧妙运用,众所周知通常二分前数据应当是有序的,比如C++中的set或map容器的工作原理,都是维护一棵平衡树;大量常见的数据结构如:平衡二叉树、线段树、二叉堆、堆排序都合理发挥了二分法的威力。第二个问题紧扣主题,有哪些基本操作可以用来解决问题,「看起来很困难的问题也可以有一个简单的、意想不到的答案」。我觉得第二题给出的三个解决方案都很重要,第一个算法是看透了暴力算法的本质,最大限度减少了使用额外空间辅助移动带来的浪费;第二个算法的递归思想很通用也很重要;第三个最为精妙的算法向我们展示了抽象思维的可贵。第三题是一道不错的离散化题目,书中说排序也好,打标识也好都是离散化的体现。所以作者也说:

算法与其他那些深奥的思想一样重要,但在更一般的编程层面上具有更重要的影响。

问题探讨

A.说一下我的理解,首先32位整数要多于40亿,所以一定存在至少一个整数不在这个随机的表中。我们按照32位整数的位来考虑,每一位不是0就是1,所以我们先按照第一个位01区分为两个集合,这样的话一定有一半最多包含2^31个整数,肯定有至少一个部分不到2^31,我们选择更少的那一半继续用这个方法取下一位,01二分下去,一定能找到至少一个缺失数字,当数据范围缩小到足以适应几百字节的内存时,遍历这个小范围就知道缺哪个数字了(也可以继续二分到底),所以总的复杂度正比于N。在算法竞赛中还遇到过直接二分答案的题目,就是说直接二分可能的答案然后判断是否满足题目条件。

B.第一个杂技算法的实现中有一个规律可循,假设我们把这个字符串收尾相接,那么从第一个字母开始,我们每隔i个字母输出一个,直到返回到已经输出过的字母。假设返回到已经输出过的字母后,仍有剩余字母没有输出,我们就顺序找下一个继续跳,问总共几个这样的循环可以遍历完所有呢?

例如:abcde n = 5 i = 3 和 abcdef n = 6 i = 2

  1. 第一个:abcdeabcdeabcdeabcde,一趟访问了所有字母,也就是所有字母完成了旋转。
  2. 第二个:abcdefabcdef,这一趟再次访问到a的时候还有一半没有访问到。我们继续:abcdefabcdef,这样共用了两趟。

这个趟数恰好等于GCD(n, i),书中解释:所需置换群次数,「近世代数中表示旋转产生的置换群的陪集个数」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int gcd(int a, int b){ return (a % b ? gcd(b, a % b) : b); }

void acrobat(){
int rot = 2000, temp, j, k, len = str.size();
for(int i = 0; i < gcd(rot, len); i++){
temp = str[i];
j = i;
while(1){
k = j + rot;
if(k >= len)
k -= len; //equal to k %= len
if(k == i) //find the same alpha
break;
str[j] = str[k];
j = k;
}
str[j] = temp;
}
}

第二种算法的递归思路挺好理解,第一个函数实现了递归的思路,需要给出头指针,两个串的长度;第二个迭代的方法更加巧妙,书中也指出,这个方法与求最大公约数的交叉相减法同构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
inline void swap(int i, int j, int k){ //分别从i,j位置开始,翻转k个字符
for(int p = 0; p < k; p++){
char temp = str[p + i];
str[p + i] = str[p + j];
str[p + j] = temp;
}
}

void first(int i, int leni, int lenj){
if(leni == lenj){
swap(i, i + leni, leni);
return;
}
if(leni > lenj){
swap(i, i + leni, lenj);
first(i + lenj, leni - lenj, lenj);
}else{
swap(i, i + lenj, leni);
first(i, leni, lenj - leni);
}
}

void second(){
int i, j, p;
i = p = rot;
j = str.size() - i;
while(i != j){
if(i > j){
swap(p - i, p, j);
i -= j;
}else{
swap(p - i, p + j - i, i);
j -= i;
}
}
swap(p - i, p, i);
}

巧妙的数学模型可以帮助我们事半功倍,第三个「翻手」算法就是这样的例子,(a^r*b^r)^r = ba:

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void reverse(int ii,int jj){
for(int i = ii; i <= jj - (jj - ii + 1) / 2; i++){
char temp = str[i];
str[i] = str[jj - (i - ii)];
str[jj - (i - ii)] = temp;
}
}

void rev(int i){
reverse(0, i - 1);
reverse(i, str.size() - 1);
reverse(0, str.size() - 1);
}

4.实践出真知,经过试验,在i=2000的情况下(Core i7 2.8GHz L3 4MB, 8GB 1600MHz),使用了io流,可能占比较大。书中的图表反映了访存局部性问题,不过现代的机器性能比书中给定的Pentium II好很多,在如下规模的数据中不太显著。

算法名称 n = 100000 n = 1000000 n = 10000000
杂技 0.034s 0.280s 2.799s
递归 0.038s 0.298s 2.950s
迭代 0.035s 0.297s 2.845s
求逆 0.035s 0.310s 2.862s

C.离散化思想有时可以将很多问题化繁为简,正因为排序可以起到很多很好的作用,很多算法问题都反映了有序化带来的一些优良特性。这道题目还引出了打标识的想法,更高级的想法就是散列表。排序也给了问题7一些启发。

7.我不清楚磁带上的存储到底是怎样的,系统给出的排序程序应当比较高效了。这个想法很好,先提前给这个4000*4000的矩阵提前写好转置后的行号和列号,然后调用系统排序先按列排序,再按照行排序,最后删了这些行列号。(这个应该是考虑到了磁带上数据读取的特性,如果内存中转置就不用这么折腾了。)

8.这个题目就是说最小k个数加起来什么时候超过t,也就是我们要在一个无序的实数集合中快速定位第k小的数字。如何做呢?可以先排序,这样我们就得到一个正比于O(NlogN)的算法。不过我们灵活运用快排的分治策略就可以得到正比于N的线性时间算法,往后再说这个。

摘录

问题定义。第1章指出确定用户的真实需求是程序设计的根本。本章的中心思想是问题定义的下一步:使用哪些基本操作来解决问题?在本章的每个例子中,啊哈!灵机一动都定义了一个新的基本操作使得问题得到简化。

问题解决者的观点。优秀程序员都有点懒:他们坐下来并等待灵机一动的出现而不急于使用最开始的想法编程。当然,这必须通过在适当的时候开始写代码来加以平衡。真正的技能就在于对这个适当时候的把握,这只能来源于解决问题和反思答案所获得的经验。