1、第四章 分治4.1 取余运算源程序名 mod.?（pas, c, cpp）可执行文件名 mod.exe输入文件名 mod.in输出文件名 mod.out【问题描述】输入 b，p，k 的值，求 b p mod k 的值。其中 b，p，k*k 为长整型数。【样例】mod.in mod.out2 10 9 210 mod 9=7【知识准备】进制转换的思想、二分法。【算法分析】本题主要的难点在于数据规模很大(b, p 都是长整型数 )，对于 bp 显然不能死算，那样的话时间复杂度和编程复杂度都很大。下面先介绍一个原理：a*b mod k(a mod k)*(b mod k)mod k。显然有了这个原理
2、，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢?显然对于任何一个自然数 P，有 p2*p div 2+p mod 2，如 192*19 div 2 十 19 mod 22*9+1，利用上述原理就可以把 b 的 19 次方除以 k 的余数转换为求 b 的 9 次方除以 k的余数，即 b19=b2*9+1b*b9*b9，再进一步分解下去就不难求得整个问题的解。这是一个典型的分治问题，具体实现的时候是用递推的方法来处理的，如 p=19，有19=2*9+1，9=2*4+1，4=2*2+0 ，2=2*1+0 ，12*0+1 ，反过来，我们可以从 0 出发，通过乘以 2
3、 再加上一个 0 或 1 而推出 1，2，4，9，19，这样就逐步得到了原来的指数，进而递推出以 b 为底，依次以这些数为指数的自然数除以 k 的余数。不难看出这里每一次乘以 2后要加的数就是 19 对应的二进制数的各位数字，即 1，0，0，1，1，而 19(10011)2，求解的过程也就是将二进制数还原为十进制数的过程。具体实现请看下面的程序，程序中用数组 binary 存放 p 对应的二进制数，总位数为len，binary1存放最底位。变量 rest 记录每一步求得的余数。4.2 地毯填补问题源程序名 blank.?（pas, c, cpp）可执行文件名 blank.exe输入文件名 bl
4、ank.in输出文件名 blank.out【问题描述】相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择(如图 4-l)：（1） （2） （3） （4）并且每一方格只能用一层地毯，迷宫的大小为(2k)2 的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为 1s。【输入】输入文件共 2 行。第一行：k，即给定被填补迷宫的大小为
5、2k(01 的宫殿，均可以将其化分为 4 个 k/2 大小的宫殿，先看一下公主站的位置是属于哪一块，因为根据公主所在的位置，我们可以确定中间位置所放的毯子类型，再递归处理公主所站的那一块，直到出现边界条件 k1 的情况，然后在公主边上铺上一块合适的地毯，递归结束。由于要递归到每一格，复杂度就是面积，就是 O(22*k*k)。4.3 平面上的最接近点对源程序名 nearest.?（pas, c, cpp）可执行文件名 nearest.exe输入文件名 nearest.in输出文件名 nearest.out【问题描述】给定平面上 n 个点，找出其中的一对点的距离，使得在这 n 个点的所有点对中，该
6、距离为所有点对中最小的。【输入】第一行：n；2n60000接下来 n 行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。【输出】仅一行，一个实数，表示最短距离，精确到小数点后面 4 位。【样例】nearest.in nearest.out3 1.00001 11 22 2【参考程序】中位数、解析几何、时间复杂度、二分法【算法分析】如果 n 很小，那么本题很容易。我们只要将每一点对于其它 n-1 个点的距离算出，找出最小距离即可。时间复杂度 O(n2)。但本题 n 很大，显然会超时。所以我们要寻找更快的解决问题的方法。我们首先想到能不能缩小计算的规模，即把 n 个点的问题
7、分治成一些小规模的问题呢?由于二维情况下的问题计算过于复杂，所以先讨论一维的情况，假设点集为 S。我们用 X 轴上某个点 m 将点集 S 划分为 2 个子集 S1 和 S2，使得 S1xS|x m；S2x S|xm。这样一来，对于所有 pS1 和 qS2 有 pm。容易看出，如果选取m(MAX(S)+MIN(S)/2，可以满足线性分割的要求。选取分割点后，再用 O(n)时间即可将 S 划分成 S1xS|xm和 S2xS|xm。然而，这样选取分割点 m，有可能造成划分出的子集 S1 和 S2 的不平衡。例如在最坏情况下，S1 只有 1 个，S2 有 n-1 个，由此产生的分治在最坏情况下所需的时
8、间 T(n)应满足递归方程：T(n)T(n-1)+O(n)它的解是 T(n)O(n2)。这种效率降低的现象可以通过分治中“平衡子问题”的方法加以解决。也就是说，我们可以通过适当选择分割点 m，使 S1 和 S2 中有大致相等个数的点。自然地，我们会想到用 S 的 n 个点的坐标的中位数来作分割点。这样一来，我们就能在O(n)的时间里确定 m(证明略 )，从而得到效率相对较高的分割点。至此，我们可以设计出一个求一维点集 S 中最接近点对的距离的算法：Function npair1(S);BeginIf S 中只有 2 个点Then :=|x2-x1|Else if S 中只有 1 个点 Then
9、 := Else beginM:=S 中各点的坐标值的中位数；构造 S1 和 S2；S1 x|xm ， S2x|xm 1:=npair1(S1)； 2:=npair1(S2)；P:=max(S1)； Q:=min(S2)；:=min(1, 2, q-p)；end;Exit()End;由以上的分析可知，该算法的分割步骤总共耗时 O(n)。因此，算法耗费的计算时间 T(n)满足递归方程：T(2)1T(n)=2T(n/2)+O(n)；解此递归方程可得 T(n)=O(n*Log2n)。这个一维问题的算法看上去比用排序加扫描更加复杂，然而它可以推广到二维。假设 S 为平面上的点集，每个点都有 2 个坐标
10、值 x 和 y。为了将点集 S 线性分割为大小大致相等的 2 个子集 S1 和 S2，我们选取一垂直线 l：xm 来作为分割直线。其中 m 为S 中各点 X 坐标的中位数。由此将 S 分割为 S1p S|x(p)m和 S2pS|x(p)m。从而使 S1 和 S2 分别位于直线 l 的左侧和右侧，且 SS1S2。由于 m 是 S 中各点 X 坐标值的中位数，因此 S1 和 S2 中的点数大致相等。递归地在 S1 和 S2 上求解最接近点对问题，我们分别得到 S1 和 S2 中的最小距离 1和 2。现设 =min(1, 2) 。若 S 的最接近点对(p, q)之间的距离 d(p, q)，则 p 和
11、 q必分属于 S1 和 S2。不妨设 pS1 ，qS2。那么，p 和 q 距直线 L 的距离均小于 。 因S1 S2P2P1 L 1 2此，我们若用 P1 和 P2 分别表示直线 L 的左边和右边的宽为 的 2 个垂直长条，则 pP1且 qP2，如图 4-3 所示：据直线 L 的距离小于 的所有点在一维的情形下，距分割点距离为 的 2 个区间(m-, m)，(m, m+) 中最多各有 S中一个点，因而这 2 点成为惟一的未检查过的最接近点对候选者。二维的情形则要复杂一些，此时，P1 中所有点与 P2 中所有点构成的点对均为最接近点对的候选者。在最坏情况下有241n对这样的候选者。但是 P1 和
12、 P2 中的点具有以下的稀疏性质，它使我们不必检查所有这2对候选者。考虑 P1 中任意一点 p，它若与 P2 中的点 q 构成最接近点对的候选者，则必有 d(p, q)。满足这个条件的 P2 中的点有多少个呢？容易看出这样的点一定落在一个 *2 的矩形 R 中(如图 4-4 所示) 。由 的意义可知，P2 中任何 2 个 S 中的点的距离都不小于 。由此而来可以推出矩形 R 中最多只有 6 个 /2*2/3* 的矩形(如图 4-5 所示) 。图 4-4 包含点 q 的 *2 矩形 R 图 4-5 图 4-6若矩形 R 中有多于 6 个 S 中的点，则由鸽笼原理易知至少有一个 /2*2/3* 的
13、小矩形中有 2 个以上 S 中的点。设 U，V 是这样 2 个点，它们位于同一小矩形中，则：2)()(YXU22365)(P1 P2LpR32322R因此， ),(VUD65。这与 的意义相矛盾。也就是说矩形 R 中最多只有 6个 S 中的点。图 4-6 是矩形 R 中含有 S 中的 6 个点的极端情形。由于这种稀疏性质，对于 P1 中任一点 p，P2 中最多只有 6 个点与它构成最接近点对的候选者。因此，在分治的合并步骤中，我们最多需要检查n32对候选者，而不是241n对候选者。这是否就意味着我们可以在O(n)时间内完成分治法的合并步骤呢？现在还不能确定，因为我们还不知道要检查哪 6 个点。
14、为了解决这个问题，我们可以将 p 和 P2 中所有 S2 的点投影到垂线 L 上。由于能与 p点一起构成最接近点对候选者的 S2 中点一定在矩形 R 中，所以它们在直线 L 上的投影距p 在 L 上投影点的距离小于 。由上面的分析可知，这种投影点最多只有 6 个。因此，若将 P1 和 P2 中所有 S 的点按其 Y 坐标排好序，则对 P1 中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对 P1 中每一点最多只要检查 P2 中排好序的相继 6 个点。至此，我们得出用分治法求二维最接近点对距离的算法：Function npair(s);BeginIf S 中只有 2 个点T
15、hen :=S 中这 2 点的距离Else if S 中只有 1 个点Then := Else begin（1）m:=S 中各点 X 坐标值的中位数；构造 S1 和 S2；（2）1:=npair1(S1)；2:=npair1(S2)；（3）m:=min(1, 2)；（4）设 P1 是 S1 中距垂直分割线 L 的距离在 m 之间的所有点组成的集合，P2 是 S2 中距分割线 L 的距离在 m 之间的所有点组成的集合。将 P1和 P2 中的点依其 Y 坐标值从小到大排序，并设 P1*和 P2*是相应的已排好序的点列；（5）通过扫描 P1*，对于 P1*中每个点检查 P2*中与其距离在 m 之内的
16、所有点（最多 6 个）可以完成合并。当 P1*中的扫描指针可在宽为2*m的一个区间内移动。设 1 是按这种扫描方式找到的点对间的最小距离；（6）:=min(m, t)；end;Exit()End;下面我们来分析上述算法的时间复杂性。设对于 n 个点的平面点集 S，在（1）和（5）步用了 O(n)时间， （3）和（ 6）用的是常数时间， （2）则用了)2(nT时间，而在（4） ，最坏情况要 O(nlog2n)时间，仍然无法承受，所以我们在整个程序的开始时，就先将 S 中的点对按 Y 座标值排序，这样一来（ 4）和（5）两步的时间就只需 O(n)的时间了，所以总的计算时间同样满足：T(2)=1,
17、);(2)(nOTn由此，该问题的时间复杂度为 O(nlog2n)，在渐进的意义下为最优算法了。空间复杂度为 O(n)。4.4 求方程的根源程序名 equation.?（pas, c, cpp）可执行文件名 equation.exe输入文件名 equation.in输出文件名 equation.out【问题描述】输入 m，n，p，a ，b，求方程 f(x)mx+nx-px 0 在 a,b内的根。m，n，p，a，b 均为整数，且 ab；m，n，p 都大于等于 1。如果有根，则输出，精确到 1E-11；如果无方程根，则输出“NO” 。【样例】equation.in equation.out2 3
18、4 1 2 1.5071265916E+002.9103830457E-11【算法分析】首先这是一个单调递增函数，对于一个单调递增(或递减)函数，如图 4-7 所示，判断在a, b 范围内是否有解，解是多少。方法有多种，常用的一种方法叫“迭代法” ，也就是“二分法” 。先判断 f(a)f(b)0，如果满足则说明在a, b范围内有解，否则无解。如果有解再判断x(a+b)/2 是不是解，如果是则输出解结束程序，否则我们采用二分法，将范围缩小到a, x)或(x, b，究竟在哪一半区间里有解，则要看是 f(a)f(x)0 还是 f(x)f(b)0。当然对于 yx，我们需要用换底公式把它换成 exp(x
19、ln(y)。4.5 小车问题 源程序名 car.?（pas, c, cpp）可执行文件名 car.exe输入文件名 car.in输出文件名 car.out【问题描述】甲、乙两人同时从 A 地出发要尽快同时赶到 B 地。出发时 A 地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。【输入】仅一行，三个数据分别表示 AB 两地的距离 s，人的步行速度 a，车的速度 b。【输出】两人同时到达 B 地需要的最短时间。【样例】car.in car.out120 5 25 9.6000000000E+00【算法分析】最佳方案为：甲先乘车到达 K 处后下车步行，小车再回头接已走到 C 处的乙，在 D处相遇后，乙再乘车赶往 B，最后甲、乙一起到达 B 地。这样问题就转换成了求 K 处的位置，我们用二分法，不断尝试，直到满足同时到达的时间精度。算法框架如下：（1）输入 s，a，b；（2）c0:0；c1: s；c: (c0+c1)/2；（3）求 t1，t2；（4）如果 t1t2，那么 c:=(c0+c)/2否则 c:(c+c1)/2；反复执行(3)和(4) ，直到 abs(t1-t2)满足精度要求（即小于误差标准） 。
