编程珠玑 第四章 习题解答

1.为了保证范围不超过范围，我们需要在初始化的时候，让变量不超出范围。这样每次循环得到的新的范围是慢慢缩小的，不会越界。

2.迭代的二分查找。

int bs( int *a, int l, int r, int v ){
while( l <= r ){
if( a[l] == v ) return l;
int mid = (l+r)/2;
if( a[mid] < v ) l = mid+1;
if( a[mid] == v )r = mid;
if( a[mid] > v ) r = mid-1;
}
return -1;
}

这个二分可以返回所需要查询的元素第一次出现的位置，如果不存在，则返回-1.在每个循环内，我们假定元素第一次出现的范围是闭区间[l，r]内，当循环体内语句执行完之后，我们得到了一个新的区间。新的区间的范围是一直在收敛的（不会存在r，l执行完循环之后大小没有变化。），所以程序可以终止，得到正确结果。

3.将2的二分程序改写成递归的形式。

int bss( int *a, int l, int r, int v ){
if( l > r ) return -1;
if( a[l] == v ) return l;
int mid = (l+r)/2;
if( a[mid] < v ) return bss( a, mid+1, r, v );
if( a[mid] == v )return bss( a, l, mid, v );
if( a[mid] > v ) return bss( a, l, mid-1, v );
}

递归每加深一层，[l,r]的范围就减小。本层的后置条件要和下一层的前置条件吻合。
4.以下是所做测试查找范围和循环的次数的关系，很明显，当查找范围是指数级的时候，循环次数是线性的。

1	1
2	2
4	3
8	4
16	5
32	6
64	7
128	8
256	9
512	10
1024	11
2048	12
4096	13
8192	14
16384	15
32768	15
65536	17
131072	15
262144	18
524288	19

5.无法证明。
6.每次执行一次，罐子中的豆子数量就减去1,所以此过程可以终止。
如果最后留下的是白色的，那么开始时候白色的个数为奇数，否则为偶数。
7。先是给一个线段的范围。然后选取中间的线，看点在他上面还是下面，然后可以缩小一半的查找范围。类似于二分查找.
8.略

9.（1）两个n维的向量相加。初开始时：i=0表示前i个维度的都已经计算好了。在循环之中，计算一个维度，然后i加一，计算下一个维度，每个循环结束表明前i个维度已经计算完毕。i一直在增大，证明这个过程是可以终止的。当最后一个循环执行完毕的时候，i的值是n，表明前n个维度已经计算好了。所以其代码是正确的。

（2）求x数组的最大值。初开始时候，max=x[0]表示最大值是第一个数，i=1表示前i个数的最大值已经求出。每次循环时候，如果有比max大的数，就替换，当循环结束时候，前i个数的最大值就知道了。当整个过程结束时，i==n，所以前n个数的最大值可以求出。

（3）当循环找个一个t的时候，就停止循环，或者当i超出范围的时候停止。i在每一次循环的时候值都增加，所以这个算法是可以结束的。当超出范围的时候，返回-1，否则返回的就是第一次出现的位置，因为i的值是从小到大递增的。

（4）每次递归，问题的规模都是缩小的，所以问题可以在有限步骤内结束。每次递归完成一次，就可以得到上次层想要的运算结果，接着向上传递。

10.