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 in $\log _2N$ such comparisons.

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?

5

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

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 $\left(a_i, b_i\right)$ defined the $N$ lines $y_i = a_ix + b_i$. The lines were ordered in the $x$-interval [0, 1] in the sense that $y_i < y_{i+1}$ for all values of $i$ 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), where $0\leq x \leq 1$, he wanted to determine the two lines that bracket the point. How could he solve the problem quickly?

8

Binary search is fundamentally faster than sequential search: to search an N-element table, it makes roughly $\log _2N$ comparisons while sequential search makes roughly $\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.