习 题 2

2-1 分别用蛮力法和分治法求数组a[n]的最大值。

2-2 在一个序列中出现次数最多的元素称为众数。设计算法寻找众数。

2-3 恺撒加密。恺撒加密的基本思想是将待加密信息（称为明文）中每个字母在字母表中向后移动常量key，得到加密信息（称为密文）。例如，假设字母表为英文字母表，key等于3，则对于明文computer将加密为frpsxwhu。设计算法实现恺撒加密。

2-4 付款问题。在面值为（v1，v2，…，vn）的n种货币中，需要支付y值的货币，应如何支付才能使货币支付的张数最少？设计贪心法求解付款问题。

2-5 子序列。给定序列X=（x1，x2，…，xm）和序列Z=（z1，z2，…，zk），Z是X的子序列当且仅当存在一个严格递增下标序列（i1，i2，…，ik），使得对于j=1，2，…，k，有zj=xij（1≤i，j≤m）。例如，对于序列X=（a，b，c，b，d，a，b），序列（b，c，d，b）是X的一个长度为4的子序列，相应的递增下标序列为（2，3，5，7）。设计算法判断给定的序列是否为某个序列的子序列。

2-6 设M是一个n×n的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元素都按升序排列。分别用蛮力法和分治法确定一个给定的整数x是否在M中。

2-7 设p1=（x1，y1），p2=（x2，y2），…，pn=（xn，yn）是平面上n个点构成的集合S，最近对问题是找出集合S中距离最近的点对。严格地讲，最接近点对可能多于1对，简单起见，只找出其中的1对作为问题的解。分别用蛮力法和分治法求解最近对问题。

2-8 最大子段和问题。给定由n个整数（可能有负整数）组成的序列（a1，a2，…，an），最大子段和问题要求该序列形如的最大值（1≤i≤j≤n），当序列中所有整数均为负整数时，其最大子段和为0。例如，序列（-20，11，-4，13，-5，-2）的最大子段和为。分别用蛮力法、分治法和动态规划法求最大子段和问题。