《编程珠玑》第 4 章──编写正确的程序

编程技巧仅仅是编写正确程序的很小一部分,更重要的还是前三章的主题:问题定义算法设计数据结构选择

本章节以二分搜索为例子,讲解了如何对程序进行验证及正确性分析。

得出的一般性原理:

  1. 断言。
  2. 顺序控制结构。
  3. 选择控制分支。
  4. 迭代控制结构。每次迭代保持不变式为真。
  5. 函数。使用前置条件和后置条件来验证函数。

习题

2. If the original binary search was too easy for you, try the variant that returns in P the first occurrence of T in the array X (if there are multiple occurrences of T, the original algorithm returns an arbitrary one). Your code should make a logarithmic number of comparisons of array elements; it is possible to do the job inlog2N\log _2N such comparisons.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int search(std::vector<int> &nums, int target) {
if (nums.empty()) {
return -1;
}
int l = 0;
auto r = static_cast<int>(nums.size() - 1);
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid;
}
}
if (nums[l] == target) {
return l;
}
return -1;
}
};

先找到第一个大于等于 target 的下标,然后判断是不是相等。

3. Write and verify a recursive binary search program. Which parts of the code and proof stay the same as in the iterative version, and which parts change?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int search(std::vector<int> &nums, int target) {
if (nums.empty()) {
return -1;
}
int start = 0;
auto end = static_cast<int>(nums.size() - 1);
return search(nums, target, start, end);
}

int search(std::vector<int> &nums, int target, int start, int end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
} else if (target > nums[mid]) {
return search(nums, target, mid + 1, end);
} else {
return search(nums, target, start, mid - 1);
}
}
};

5. Prove that this program terminates when its input is a positive integer.

1
2
3
4
5
while x !=1 do
if even(x)
x = x/2
else
x = 3 * x + 1

拉兹猜想又名 3n+1 猜想或冰雹猜想。不明觉厉!

6. [C. Scholten] David Gries calls this the “Coffee Can Problem” in his Science of programming. You are initially given a coffee can that contains some black beans and some white beans and a large pile of “extra” black beans. You then repeat the following process until there is a single bean left in the can.

Randomly select two beans from the can. If they are the same color, throw them both out and insert an extra black bean. If they are different colors, return the white bean to the can and throw out the black.

Prove that the process terminates. What can you say about the color of the final remaining bean as a function of the numbers of black and white beans originally in the can?

每次都减少一个豆子,最终肯定要仅剩一个豆子。白色豆子都是一对一对的减少,所以如果白色豆子一开始个数是偶数,那么剩下黑色豆子;如果白色豆子个数是奇数,那么剩下白色豆子。

7. A colleague faced the following problem in a problem to draw lines on a bitmapped display. An array of N pairs of reals(ai,bi)\left(a_i, b_i\right) defined the N linesyi=aix+biy_i = a_ix + b_i. The lines were ordered in the x-interval [0, 1] in the sense thatyi<yi+1y_i < y_{i+1} for all values ofii between 1 and N-1 and all values of x in [0, 1]:

Less formally, the lines don’t touch in the vertical slabs. Given a point (x, y), where0x10\leq x \leq 1, he wanted to determine the two lines that bracket the point. How could he solve the problem quickly?

固定 x 的值,然后比较y0y_0 的值,用二分搜索来确定在哪个区间。因为yiy_i 已经是排序的,然后找到第一个大于或者等于y0y_0 的线段。

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
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>

using namespace std;
typedef pair<double, double> line;
typedef pair<double, double> point;

double getDistance(vector<line> &lines, int index, point &p) {
return p.second - (lines[index].first * p.first + lines[index].second);
}

pair<int, int> search(vector<line> &lines, point &p) {
auto n = static_cast<int>(lines.size());
int left = 0;
int right = n - 1;
pair<int, int> result = {INT_MIN, INT_MIN};
if (getDistance(lines, 0, p) < 0) {
return {INT_MIN, 0};
} else if (getDistance(lines, n - 1, p) > 0) {
return {n, INT_MAX};
}
// 找到第一个大于等于 p 的
while (left < right) {
int mid = left + (right - left) / 2;
if (getDistance(lines, mid, p) > 0) {
left = mid + 1;
} else {
right = mid;
}
}
if (getDistance(lines, right, p) == 0) {
result = {right, right};
} else {
result = {right - 1, right};
}
return result;
};

int main() {
vector<line>
lines = {line{0, 1}, line{1, 1}, line{0, 2}, line{-1, 3}, line{0, 3}, line{1, 3}};
point p = {0.5, 2.2};
auto a = search(lines, p);
cout << a.first << " " << a.second << endl;
return 0;
}

8. Binary search is fundamentally faster than sequential search: to search an N-element table, it makes roughlylog2N\log _2N comparisons while sequential search makes roughlyN2\frac{N}{2}. While it is often fast enough, in a few cases binary search must be made faster yet. Althought you can’t reduce the logarighmic number of comparisons made by the algotighm, can you rewrite the binary search code to be faster? For definiteness, assume that you are to search a sorted table of N=1000 integers.

将二分扩展成 k 分,比如四分搜索,可以提升速度。