1.6 习题
1．假设数组X[1..1000]中散布着随机实数。下面这个例程计算最小值和最大值：
Max := Min := X[1]
for I := 2 to 1000 do
if X[I] > Max then Max := X[I]
if X[I] < Min then Min := X[I]
B. C. Dull先生注意到，如果一个元素是新的最大值，则这个元素不可能是最小值。因而他把两次比较写成
if X[I] > Max then Max := X[I]
else if X[I] < Min then Min := X[I]
这样平均起来将节省多少次比较？先猜猜答案，再通过实现和监视程序性能来找出答案。你猜得怎么样？
2．下列问题与计算素数有关。
a．程序P1到P6把运行时间缩短了两个数量级。你能进一步提高性能吗？
b．实现简单的埃氏筛法（Sieve of Eratosthenes）来计算所有小于n的素数。这个程序的主要数据结构是一个n比特的数组，初始值都为真。每发现一个素数时，数组中所有这个素数的倍数就设置为假。下一个素数就是数组中下一个为真的比特。
c．上述筛法的运行时间作为n的函数是什么样子的？找出一个运行时间为O(n)的算法。
d．给出一个非常大的整数（比如说几百比特长），你如何检验其是否为素数？
3．一种简单的语句计数性能监视工具为每条语句设置一个计数器。描述一下如何使用更少的计数器来减少内存和运行时间。（我曾经用过Pascal系统监视一个程序的性能，结果把程序变慢为原来的1/100；本章描述的行计数性能监视工具采用了本题的技巧，只让程序变慢几个百分点。）
4．一种简单的过程时间性能监视工具这样估计每个过程所花的时间：在有规律的间隔下观察程序计数器（在我的系统上是每秒60次）。这个信息给出了程序文本每个部分所花的时间，但是没有给出哪个过程最费时间。有些性能监视工具给出了每个函数及其动态调用的子函数所花的时间。说明如何从运行时栈中搜集更多信息，以区分出调用函数和被调用函数所花的时间。给定这些数据后，你如何以有用的形式来显示这些数据？
5．准确的数值有助于解释程序在单个数据集上的性能监视结果。但是当有很多数据时，长长的一串数字则可能掩盖数值中的信息。你如何显示程序或管道在100个不同输入上的性能监视结果？特别考虑一下数据的图形显示。
6．1.4节中的程序P6是个正确的程序，其正确性却难以证明。问题出在哪里？如何解决这个问题？