Solve

编程珠玑第二章探讨

这一章给出了三个小问题，都非常有趣且实用，分别用来阐述二分法，递归与抽象，离散化思想。第一个问题可以认为是二分思想的巧妙运用，众所周知通常二分前数据应当是有序的，比如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章指出确定用户的真实需求是程序设计的根本。本章的中心思想是问题定义的下一步：使用哪些基本操作来解决问题？在本章的每个例子中，啊哈！灵机一动都定义了一个新的基本操作使得问题得到简化。

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