分治习题汇总课件.doc

分治习题汇总4.1取余运算源程序名 mod.?（pas, c, cpp）可执行文件名 mod.exe输入文件名 mod.in输出文件名 mod.out【问题描述】输入b，p，k的值，求b p mod k的值。其中b，p，k*k为长整型数。【样例】mod.inmod.out2 10 9210 mod 9=7【知识准备】进制转换的思想、二分法。【算法分析】本题主要的难点在于数据规模很大(b, p都是长整型数)，对于bp显然不能死算，那样的话时间复杂度和编程复杂度都很大。 下面先介绍一个原理：a*b mod k(a mod k)*(b mod k)mod k。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢?显然对于任何一个自然数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再加上一个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输入文件名 blank.in输出文件名 blank.out【问题描述】 相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择(如图4-l)：（1） （2）（3）（4）并且每一方格只能用一层地毯，迷宫的大小为(2k)2的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为1s。【输入】输入文件共2行。第一行：k，即给定被填补迷宫的大小为2k(01的宫殿，均可以将其化分为4个k/2大小的宫殿，先看一下公主站的位置是属于哪一块，因为根据公主所在的位置，我们可以确定中间位置所放的毯子类型，再递归处理公主所站的那一块，直到出现边界条件k1的情况，然后在公主边上铺上一块合适的地毯，递归结束。 由于要递归到每一格，复杂度就是面积，就是O(22*k*k)。4.3平面上的最接近点对源程序名 nearest.?（pas, c, cpp）可执行文件名 nearest.exe输入文件名 nearest.in输出文件名 nearest.out【问题描述】 给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的。【输入】第一行：n；2n60000接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。【输出】仅一行，一个实数，表示最短距离，精确到小数点后面4位。【样例】nearest.innearest.out31.00001 11 22 2【参考程序】中位数、解析几何、时间复杂度、二分法【算法分析】 如果n很小，那么本题很容易。我们只要将每一点对于其它n-1个点的距离算出，找出最小距离即可。时间复杂度O(n2)。但本题n很大，显然会超时。所以我们要寻找更快的解决问题的方法。我们首先想到能不能缩小计算的规模，即把n个点的问题分治成一些小规模的问题呢? 由于二维情况下的问题计算过于复杂，所以先讨论一维的情况，假设点集为S。 我们用X轴上某个点m将点集S划分为2个子集S1和S2，使得S1xS|xm；S2xS|xm。这样一来，对于所有pS1和qS2有pq。 递归地在S1和S2上找出其最接近的点对p1, p2和q1, q2，并设MIN|p2-p1|，|q2-q1|，S中的最接近点对或者是p1, p2，或者是q1, q2，或者是某个p3, q3，其中p3S1且q3S2。如图4-2所示：图 4-2 一维情形的分治法 我们注意到，如果S的最接近点对是p3, q3，即|p3-q3|，则p3和q3两者与m的距离不超过，即|p3-m|，|q3-m|m。容易看出，如果选取m(MAX(S)+MIN(S)/2，可以满足线性分割的要求。选取分割点后，再用O(n)时间即可将S划分成S1xS|xm和S2xS|xm。然而，这样选取分割点m，有可能造成划分出的子集S1和S2的不平衡。例如在最坏情况下，S1只有1个，S2有n-1个，由此产生的分治在最坏情况下所需的时间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); Begin If S中只有2个点 Then :=|x2-x1| Else if S中只有1个点 Then := Else begin M:=S中各点的坐标值的中位数； 构造S1和S2；S1x|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)1 T(n)=2T(n/2)+O(n)； 解此递归方程可得T(n)=O(n*Log2n)。 这个一维问题的算法看上去比用排序加扫描更加复杂，然而它可以推广到二维。 假设S为平面上的点集，每个点都有2个坐标值x和y。为了将点集S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l：xm来作为分割直线。其中m为S中各点X坐标的中位数。由此将S分割为S1pS|x(p)m和S2pS|x(p)m。从而使S1和S2分别位于直线l的左侧和右侧，且SS1S2。由于m是S中各点X坐标值的中位数，因此S1和S2中的点数大致相等。S1S2P2P1L12 递归地在S1和S2上求解最接近点对问题，我们分别得到S1和S2中的最小距离1和2。现设=min(1, 2)。若S的最接近点对(p, q)之间的距离d(p, q)，则p和q必分属于S1和S2。不妨设pS1，qS2。那么，p和q距直线L的距离均小于。 因此，我们若用P1和P2分别表示直线L的左边和右边的宽为的2个垂直长条，则pP1且qP2，如图4-3所示：据直线L的距离小于的所有点 在一维的情形下，距分割点距离为的2个区间(m-, m)，(m, m+)中最多各有S中一个点，因而这2点成为惟一的未检查过的最接近点对候选者。二维的情形则要复杂一些，此时，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。在最坏情况下有对这样的候选者。但是P1和P2中的点具有以下的稀疏性质，它使我们不必检查所有这对候选者。考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有d(p, q)。满足这个条件的P2中的点有多少个呢？容易看出这样的点一定落在一个*2的矩形R中(如图4-4所示)。 由的意义可知，P2中任何2个S中的点的距离都不小于。由此而来可以推出矩形R中最多只有6个/2*2/3*的矩形(如图4-5所示)。P1P2LpRR 图 4-4 包含点q的*2矩形R 图 4-5 图4-6 若矩形R中有多于6个S中的点，则由鸽笼原理易知至少有一个/2*2/3*的小矩形中有2个以上S中的点。设U，V是这样2个点，它们位于同一小矩形中，则： 因此，。这与的意义相矛盾。也就是说矩形R中最多只有6个S中的点。 图4-6是矩形R中含有S中的6个点的极端情形。由于这种稀疏性质，对于P1中任一点p，P2中最多只有6个点与它构成最接近点对的候选者。因此，在分治的合并步骤中，我们最多需要检查对候选者，而不是对候选者。这是否就意味着我们可以在O(n)时间内完成分治法的合并步骤呢？现在还不能确定，因为我们还不知道要检查哪6个点。为了解决这个问题，我们可以将p和P2中所有S2的点投影到垂线L上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线L上的投影距p在L上投影点的距离小于。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S的点按其Y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P1中每一点最多只要检查P2中排好序的相继6个点。至此，我们得出用分治法求二维最接近点对距离的算法：Function npair(s); Begin If S中只有2个点 Then :=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之内的所 有点（最多6个）可以完成合并。当P1*中的扫描指针可在宽为2*m 的一个区间内移动。设1是按这种扫描方式找到的点对间的最小距 离； （6）:=min(m, t)； end; Exit() End;下面我们来分析上述算法的时间复杂性。设对于n个点的平面点集S，在（1）和（5）步用了O(n)时间，（3）和（6）用的是常数时间，（2）则用了时间，而在（4），最坏情况要O(nlog2n)时间，仍然无法承受，所以我们在整个程序的开始时，就先将S中的点对按Y座标值排序，这样一来（4）和（5）两步的时间就只需O(n)的时间了，所以总的计算时间同样满足：T(2)=1,由此，该问题的时间复杂度为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-px0在a,b内的根。m，n，p，a，b均为整数，且ab；m，n，p都大于等于1。如果有根，则输出，精确到1E-11；如果无方程根，则输出“NO”。【样例】equation.inequation.out2 3 4 1 21.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(xln(y)。4.5小车问题 源程序名 car.?（pas, c, cpp）可执行文件名 car.exe输入文件名 car.in输出文件名 car.out【问题描述】甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。【输入】仅一行，三个数据分别表示AB两地的距离s，人的步行速度a，车的速度b。【输出】两人同时到达B地需要的最短时间。【样例】car.incar.out120 5 259.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)满足精度要求（即小于误差标准）。4.6黑白棋子的移动源程序名 chessman.?（pas, c, cpp）可执行文件名 chessman.exe输入文件名 chessman.in输出文件名 chessman.out【问题描述】有2n个棋子（n4）排成一行，开始为位置白子全部在左边，黑子全部在右边，如下图为n=5的情况：移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为：任务：编程打印出移动过程。【样例】chessman.inchessman.out7step 0：ooooooo*- step 1：oooooo-*o* step 2：oooooo-*o* step 3：ooooo-*o*o* step 4：ooooo*-o*o* step 5：oooo-*o*o*o* step 6：oooo*-o*o*o* step 7：ooo-*o*o*o*o* step 8：ooo*o*-*o*o*o* step 9：o-*o*oo*o*o*o* step 10：o*o*o*-o*o*o*o* step 11：-o*o*o*o*o*o*o*【问题分析】我们先从n=4开始试试看，初始时：第1步：（表示空位）第2步：第3步：第4步：第5步：如果n=5呢？我们继续尝试，希望看出一些规律，初始时：第1步：第2步：这样，n=5的问题又分解成了n=4的情况，下面只要再做一下n=4的5个步骤就行了。同理，n=6的情况又可以分解成n=5的情况，所以，对于一个规模为n的问题，我们很容易地就把它分治成了规模为n-1的相同类型子问题。数据结构如下：数组c1.max用来作为棋子移动的场所，初始时，c1cn存放白子（用字符o表示），cn+1c2n存放黑子（用字符*表示），c2n+1，c2n+2为空位置（用字符表示）。最后结果在c3c2n+2中。4.7麦森数（NOIP2003）源程序名 mason.?（pas, c, cpp）可执行文件名 mason.exe输入文件名 mason.in输出文件名 mason.out【问题描述】 形如2p-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2p-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 任务：从文件中输入P(1000P3100000)，计算2p-1的位数和最后500位数字(用十进制高精度数表示)。【输入】文件中只包含一个整数P(1000P3100000)。【输出】第一行：十进制高精度数2p-1的位数；第211行：十进制高精度数2p-1的最后500位数字(每行输出50位，共输出10行，不足500位时高位补0)； 不必验证2p-1与P是否为素数。【样例】mason.in1279mason.out38600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087【问题分析】本题的解题方法很多，其中分治也是一种巧妙的方法。首先可以想到：2n=(2 n div 2)2*2 n mod 2，即：如果要计算2n，就要先算出2 n div 2，然后用高精度乘法算它的平方，如果n是奇数还要再乘以2，写成递归公式就是：f(n)=(f(n div 2)2*2(n mod 2)。当然，递归是要有边界值的，这就是当n=0时，f(n)=1。还要补充一点，该数的长度是可以用公式计算的，所以在做高精度乘法时，只要取最后500位运算就行了。4.8旅行家的预算(NOIP1999)源程序名 trip.?（pas, c, cpp）可执行文件名 trip.exe输入文件名 trip.in输出文件名 trip.out【问题描述】 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离D1、汽车油箱的容量C(以升为单位)、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N(N可以为零)，油站i离出发点的距离Di、每升汽油价格Pi(i1，2，N)。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。【样例】trip.in 275.6 11.9 27.4 2.8 2 (分别表示D1，C，D2，P，N) 102.0 2.9 (以下共N行，分别表示油站i离出发点的距离Di和每升汽油价格Pi) 220.0 2.2trip.out 26.95(该数据表示最小费用)【问题分析】看到这道题，许多人都马上判断出穷举是不可行的，因为数据都是以实数的形式给出的。但是，不用穷举，有什么更好的方法呢？比较容易想到的是分治法。 首先找到(从后向前)油价最低的加油站，显然车至该站油箱应为空，这样就可将起点至该站与该站至终点作为两段独立考虑，分别求其最小费用，二者之和即为总费用，