编程珠玑每一章讲了编程、开发的不同的方面。

  • 第一章讲如何准确、正确的定义问题。
  • 第二章讲算法设计（灵光一现，啊哈！算法）。
  • 第三章提到数据结构和编程的关系（欸有点面向对象的感觉）。
  • 第四章运用循环不变式来证明程序的正确性。
  • 第五章运用脚手架、断言调试程序。
  • 第六章概述了加速程序的几个方向，并在第八至x章分别阐述。
  • 第七章书如其名：粗略估算。
  • 第八章重新设计算法来降低程序的渐进时间复杂度。
  • 第九章对利用率高的代码进行优化，使得渐进复杂度的常数减小。
  • 第十章强调对空间的压缩。
  • 十一章：排序算法，指快速排序
  • 十二章：取样问题，指随机从 m 个数中取 n 个数
  • 十三章：搜索，其实展示了用于存储和搜索的数组、链表、二叉搜索树、C++ set、bitset、箱（桶）这些数据结构。
  • 十四章：堆
  • 十五章：字符串，讲到了设计一个字典并压缩的过程。

将一个字符串 $S$ 的后 i 位移到前 i 位

如当 i = 3，$S = abcdefg$，则要求 $S^R = efgabcd$。

该问题出现在《编程珠玑》第二章。时间复杂度要求为 $O(n)$，空间复杂度要求为几十字节，并且算法尽量简洁。

一个方法

可以尝试以下方法：

将 x[0] 移动到临时变量 t，把 x[i] 移动到 x[0]，将 x[2*i] 移动到 x[i]，以此类推……直至取回 x[0]。
若按该法没有移动所有元素，则对 x[1]、x[2]……x[i-1] 进行同样操作。

上述算法较好的完成了时空复杂度，但是不够简洁。

更简洁的方法：基本操作的威力

更简洁的办法是先实现一个 reverse() 函数，用于翻转一个字符串（如把 qwerty 变为 (qwerty)^R = ytrewq），时间复杂度为 $O(n)$，复杂度为几个字节。
设 $S$ 串前 i 位为 $T_1$，后 (n-i) 位为 $T_0$。
注意到 ${(T_1^R T_0^R)}^R = T_0 T_1$，即可以调用三次 reverse() 函数实现该问题：

1
2
3
reverse(0,i-1);
reverse(i,n-1);
reverse(0,n-1);

该算法简洁，而且不容易出错。

格式信函编程

出现在3.2。

要写这种的话，不如手写一个把模板转为实例的函数，方便维护。

模板：

1
2
3
4
5
6
7
8
9
Welcome back, $1!
We hope that you and all the members
of the $0 family are constantly
reminding your neighbors there
on $5 to shop with us.
As usual, we will ship your order to
    $3 $1 $2. $0
    $4 $5
    $6, $7 $8

解释器（伪代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
read fields from database
loop from start to end of schema
    c = next character in schema
    if c ! ='$'
        printchar c
    else
        c = next character in schema
        case c of '$':
            printchar '$'
        '0' - '9':
            printstring field[c]
        default:
            error("bad schema")

有点像 C 的风格。在这种情形下，C++ 的 cout 风格也不一定好。

更一般性的问题也许更容易解决

第三章 3.6。

对于程序设计来说，这意味直接编写 23 种情况的问题很困难；而编写一个处理 n 种情况的通用程序，再令 n = 23 来得到最终结果，却相对要容易一些。 —— Polya: How to solve it

咖啡罐问题

David Gries 在其 Science of Programming 中将下面的问题称为“咖啡罐问题”。

给定一个盛有一些黑色豆子和一些白色豆子的咖啡罐以及一大堆“额外”的黑色豆子，重复下面的过程，直至罐中仅剩一颗豆子为止：
从罐中随机选取两颗豆子，如果颜色相同，就将它们都扔掉并且放入一个额外的黑色豆子；如果颜色不同，就将白色的豆子放回罐中，而将黑色的豆子扔掉。 证明该过程会终止。最后留在罐中的豆子颜色与最初罐中白色豆子和黑色豆子的数量有何函数关系？

这个问题看起来很有意思。
步骤会结束的证明是每次操作以后，罐子里总会减少一颗豆子；
而对于最后剩余的豆子的颜色，可以关注到每次操作会拿走 0 到 2 颗白豆子，没有改变白豆子数量的奇偶性，因此最后剩白豆子的充要条件是罐子里原有奇数颗白豆子。

循环不变式

出现在第四章。

程序验证的基本技术：精确定义不变式并在编写每一行代码时随时保持不变式的成立。

如二分搜索中， t 总在 [l, r] 中。

证明二分搜索的正确性的方法分为三个部分：

  1. 初始化。循环初次执行的时候不变式为真。
  2. 保持。如果在某次迭代开始的时候以及循环执行的时候，不变式都为真，那么循环体执行完后，不变式仍为真。
  3. 终止。即循环一定能停止。

话说 1 和 2 就是数学归纳法你看隔壁叔叔，都二十岁了还在打数理基础。证明了 1 和 2，我们就能证明，如果循环能够停止，那么其结果一定是正确的。因此我们还需要证明 3。

对于二分搜索算法，初始化和保持只要按照流程分类讨论就不难。停机的证明是停止条件是 [l, r] 内没有元素，而每次循环以后，范围必定减小至少 1（说必定减少都不行，减少的序列可能是一个收敛级数）。

顺便一提，后来我才知道，循环不变式是《算法导论》从第一章就开始强调的概念。

断言

出现在第四、五章。

上面提到的循环不变式也是一种断言。

断言在程序维护过程中至关重要：当你拿到一段你从未见过而且多年来也没有其他人见过的代码时，有关该程序状态的断言对于理解程序时很有帮助的。

而断言这种东西，在 C 语言还真的有：assert。关于该语法，放到另一篇博客。

总之工程开发要多用。

程序调试

在第五章。

调试不仅可以验证程序的正确性，还能验证其理论时间复杂度。

附一份我写的二分实现的 lower_bound() 函数，及用 assert 验证其正确性的代码，以及验证其时间复杂度的代码。但是时间复杂度的验证貌似不稳定。

粗略估算

出自于第七章。也是我认为非常难的一章，因为涉及到大量的“常识”。
下面就列举一下本书中出现过的应该掌握的常识。

换算法则

1. 72法则

如果增长率为 $x\%$，那么在 $y$ 年后将会翻倍，其中 $xy = 72$。

即 $f(x)=(1+x\%)^{\frac{72}{x}} \approx 2$。$1 \leq x \leq 15$ 时，误差在 $5\%$ 内； $6 \leq x \leq 9$ 时，误差在 $1\%$ 内。

$x$ 1 2 3 4 5 6
$(1+x\%)^{\frac{72}{x}}$ 2.0471 2.03989 2.03279 2.02582 2.01895 2.0122
$x$ 7 8 9 10 15 20
$(1+x\%)^{\frac{72}{x}}$ 2.00555 1.999 1.99256 1.98622 1.95591 1.92776

2. “π 秒就是一个纳世纪”

一世纪有 $3.155 \times 10 ^ 7$ 秒。

生活常识

常见的河流的流速：不到 2 英里（3.21 公里）/小时

Little 定理

系统中物体的平均数量等于物体离开系统的平均速率和每个物体在系统中停留的平均时间的乘积。

原定理没有提进入速率，但是如果物体离开和进入系统的总体出入流是平衡的，那么离开速率就是进入速率。

Little 定理简单的说来就是：

队列中物体的平均数量 = 进入速率 × 平均停留时间

例1：排队

一个夜总会需要排队进入。这个夜总会能容纳 60 人，每个人在里面呆三小时，那么进入夜总会的速率是 20 人/小时。这样你就能从队伍前面有多少人来判断大概还有多少时间进去。

例2：死亡率和平均寿命

由 Little 定理可知：

每年的死亡率 × 平均寿命 = 1

如死亡率为 1.4%，则平均寿命为 71 岁。

自己的电脑的运算速度

对于一个程序员，知道现在电脑的运算量也非常重要。我就花了一天的时间，测试了一下 C 语言中各种运算的时间。由于内容过长，另开文章以阐述。

安全系数

出现自第七章。

在做出可靠性、可用性保证时，给出和我们的目标差十倍的结果；
在估算规模、开销和时间进度时，应该给出 2-4 倍保守的结果。

随机序列的最大连续子序列和的期望

出自于第八章。习题 8.6。

这是个挺有意思的题目，但是很少有人研究：

假定输入数组的各个元素是从 $[-1,1]$ 中均匀选出的随实数，那么最大子序列和的期望值是多少？

我手算了 $n=1$ 时期望为 1/4， $n=2$ 时期望为 1/2。

以下是几个相关链接：

https://stackoverflow.com/questions/11261066/expectation-of-the-maximum-consecutive-subsequence-sum-of-a-random-sequence
https://www.quora.com/What-is-the-expected-value-of-the-sum-of-the-maximum-sum-subvector-if-the-arrays-elements-are-random-real-numbers-chosen-uniformly-from-1-1#

链接中有人用 Mathematica 模拟，跑出了 $n \leq 5$ 的精确解为：1/2，1/4，23/32，291/320，4141/3840。

也有人提到，经过 $n \leq 10000$ 的模拟，答案应该是 $O(\sqrt n)$ 的。从理论上来说，可以把问题类比为 random walk，从而化归为布朗运动，得到 $O(\sqrt n)$ 的证明。

这题放在这里也太硬核了吧。。。。

从 n 元序列随机取 m 个

出自第 12 章。

程序的输入包含整数 m < n。输出是 [0, n-1] 范围内 m 个随机整数的有序列表，不允许重复。从概率的角度说，我们希望每个数出现的概率相同。

下面写一下书上的三种算法。

  1. 动态计算概率，然后用随机数取数，时间复杂度为 $O(n)$：
1
2
3
4
5
6
7
8
9
10
11
void gen1(int m, int n)
{
    for (int i = 0; i < n; i++)
    {
        if (rand() % (n-1) < m)
        {
            cout << i << "\n";
            m--;
        }
    }
}

显然该算法不适合用于生成 1 个 32 位随机整数（m=1, n=2^32）。

  1. 向集合里塞随机数，直至集合大小为 m。当 m 远小于 n 时，算法复杂度为 $O(m \log m)$。
1
2
3
4
5
6
7
8
void gen2(int m, int n)
{
    set s;
    while(s.size() < m)
        s.insert(rand() % n);
    for (int i : s)
        cout << i  << "\n";
}
  1. Floyd 算法（习题 12.9），基于算法 2 改良，保证在任何情况下，算法复杂度都是 $O(m \log m)$。

这里仅给出递归版，实际上也可以改为非递归版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void gen3(int m, int n, set<int> & s)
{
    if (m == 0)
        return;

    gen3(m-1, n-1, s);
    int t = rand() % n;
    if (!s.insert(t).second)
        s.insert(n - 1);
}

void gen3(int m, int n)
{
    set<int> s;
    gen3(m, n, s);
    for (int i : s)
        cout << i  << "\n";
}

算法正确性的证明可以用 循环不变式 的方法：第六行之后的循环不变式为 “$[0, n-2]$ 之间的整数被选到的概率为 $\frac{m-1}{n-1}$”，证明一次循环以后不变式仍然成立，需要用到概率论中的条件概率，讨论 $t \in [0, n-2]$ 且已被选中、$t$ 没有被选中这两种情况，详细过程略。

  1. 使用 shuffle 算法。由于算法需要完整生成 n 个数的序列，以及进行排序，所以算法时间复杂度为 $O(n + m\log m)$。
1
2
3
4
5
6
7
8
9
10
11
int gen4(int m, int n)
{
    int * arr = new int[n];
    for (int i = 0; i < n; i++)
        arr[i] = i;
    for (int i = 0; i < m; i++)
        swap(arr[i], arr[ randint(i, n-i) ]);
    sort(arr, arr + m);
    for (int i = 0; i < m; i++)
        cout << arr[i] << "\n";
}

习题 12.10

如何从 n 个对象（可以依次看到这 n 个对象，但事先不知道 n 的值）中随机选择一个？具体来说，如何在事先不知道文本文件行数的情况下读取该文件，从中随机选择并输出一行？

这一章全是概率题啊。。。。

算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
string genline()
{
    string str, tempstr;
    int k = 1;
    while(!eof())
    {
        tempstr = getline();
        //在 1/k 的概率下执行 if 后的语句
        if (rand() % k == 0)
            str = tempstr;
    }
    return str;
}

简单的用文字描述算法就是：存储第一行。在读入第 $k$ 行时，使用随机数使得，有 $1/k$ 的概率将第 $k$ 行替换存储的行，否则保存存储的行不变。算法的正确性同样可由 循环不变式 证得。

习题 12.11

在一种彩票游戏中，每位玩家有一张包含 16 个覆盖点的自拍，覆盖点下面隐藏着一个 1-16 的随机排列。玩家翻开覆盖点则出现下面的整数。只要整数 3 出现，则盼玩家负；否则，如果 1 和 2 都出现（顺序不限），则玩家获胜。随机选择覆盖点的顺序就能够获胜的概率如何计算？请列出详细步骤，假定你最多可以使用一个小时的 CPU 时间。

看到最后一句话我以为是要枚举，但实际上可以用 $O(mn)$ 的动态规划来做。算完答案以后，我发现，其实这就是一个概率题！

原题等价于列举 1-16 的全排列，共 16! 种情况。计算其中 3 先于 1 或 2 出现的种数（输的种数），以及 1 和 2 都先于 3 出现的种数（赢的种数）。

由于 1、2、3 并无特殊意义，我们可以考虑用两张 key 牌来称呼 1 和 2，lose 牌称呼 3。

这个题可以用动态规划来做，二维为剩余牌的总张数 n ，和剩余 key 牌的张数（由于输掉游戏只需要一张牌，因此不需要单独一维来计算，当然，作为本题的延伸，可以考虑有需要抓到多张牌才算输的情况）。
转移状态时，讨论三种情况：抓到 lose 牌，抓到 key 牌，抓到其他牌。
另外要注意，如果游戏还没结束，必须至少有一张 key 牌和一张 lose 牌在场上，即 $n \geq 1 + key$。这是边界条件。

存储赢的种数为 $answer[n][key].win$，存储输的种数为 $answer[n][key].lose$，最终赢/输的比值为 $answer[16][2].win / answer[16][2].lose$。

转移方程为：

$$\begin{split}
answer[n][key].win &=
\begin{cases}
0 & n < 1 + key \\
n! & n \geq 1 + key \space and \space key = 0 \\
0 \\
\quad + key \cdot answer[n-1][key-1].win & otherwise\\
\quad + (n - 1 - key) answer[n-1][key].win
\end{cases} \\ \\
answer[n][key].lose &=
\begin{cases}
0 & key = n < 1 + key \space or \space 0 \\
(n-1)! \\
\quad + key \cdot answer[n-1][key-1].lose & otherwise\\
\quad + (n - 1 - key) answer[n-1][key].lose
\end{cases} \\
\end{split}$$

实现的 C++ 代码为：

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
struct posibility
{
    long long win = 0;
    long long lose = 0;
};

const int nMax = 20, keyMax = 2;
void LotteryGame(const int N, int Key)
{
    posibility answer[nMax][keyMax + 1];
    long long Factorial[nMax];
    Factorial[0] = 1;
    for (int i = 1; i <= N; i++)
        Factorial[i] = i * Factorial[i - 1];

    for (int n = 1; n <= N; n++)
    {
        answer[n][0].win = Factorial[n];
        for (int key = 1; key <= min(Key, n - 1); key++)
        {
            answer[n][key].win =
                key * answer[n - 1][key - 1].win +
                (n - 1 - key) * answer[n - 1][key].win;
            answer[n][key].lose =
                Factorial[n - 1] +
                key * answer[n - 1][key - 1].lose +
                (n - 1 - key) * answer[n - 1][key].lose;
        }
    }

    cout << "Win/Lose = " << answer[N][Key].win << "/" << answer[N][Key].lose
        << " = " << double(answer[N][Key].win) / answer[N][Key].lose; //注意这不是赢的概率，这是赢输的比值
}

有意思的是，程序的结果正好为 1/2（即赢的概率为 1/3）。我怀疑是程序或者转移方程写错了，打开调试，发现，无论 $n$ 为何值，$answer[n][2]$ 中 win 总是 lose 的一半！

那么从简单的情况验证一下：$n = 3$ 时 $win/lose$ 确实是 $2/4$。举到 $n=4$ 时，我明白了这个题目确实和 n 没有关系！

我们不考虑其他数，只考虑 1 2 3 的相对位置，即，从所有全排列抽出 1 2 3。
3 在前的排列有 3 1 2 3 2 1 1 3 2 2 3 1 四种；
1 2 在前的排列有 1 2 3 2 1 3 两种。
再将这些情况插回上述全排列所空出的位置，则输的种数就是 $4 \times 16!/3!$，赢的种数就是 $2 \times 16!/3!$。无论一共有多少张卡，赢的概率都为 1/3！

被概率题教育了

桶的小细节

如果有 bins 个桶，最大值为 maxval，那么直观地，元素 t 可以放在第 t*bins/maxval 个桶中。然而，这容易导致数值溢出。

推荐使用 t/(1 + maxvalue/bins)，防止溢出，并且也没有使用浮点数，造成可能的误差。

后缀数组计算最大重复子串

这里我们讨论单词 banana 的最大重复子串。定义字符串 c 和字符指针数组 a：

1
2
3
char c[MAXN] = "banana", a*[MAXN];
for (int n = 0; c[n] != 0; n++)
    a[n] = &c[n];

实现的效果如下：

a[0] -> banana
a[1] -> anana
a[2] -> nana
a[3] -> ana
a[4] -> na
a[5] -> a

然后，对 a 数组按字典序进行排序得到：

a[0] -> a
a[1] -> ana
a[2] -> anana
a[3] -> banana
a[4] -> na
a[5] -> nana

然后对相邻字符串比较即可。

在常见字符串上有 $O(n \log n)$ 的复杂度（排序不分），当然如果使用 aaaaaaaaaaa 一类的字符串，比较的复杂度也会被卡到 $O(n^2)$。