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.in mod.out

2 10

9 2^10 mod 9=7 【知识准备】 进制转换的思想、二分法. 【算法分析】 本题主要的难点在于数据规模很大(b, p都是长整型数),对于bp显然不能死算,那样的话时间复杂度和编程复杂度都很大. 下面先介绍一个原理:a*b mod k=(a mod k)*(b mod k)mod k.显然有了这个原理,就可以把较大的幂分解成较小的,因而免去高精度计算等复杂过程.那么怎样分解最有效呢?显然对于任何一个自然数P,有p=2*p div 2+p mod 2,如19=2*19 div 2十19 mod 2=2*9+1,利用上述原理就可以把b的19次方除以k的余数转换为求b的9次方除以k的余数,即b19=b2*9+1=b*b9*b9,再进一步分解下去就不难求得整个问题的解. 这是一个典型的分治问题,具体实现的时候是用递推的方法来处理的,如p=19,有19=2*9+1,9=2*4+1,4=2*2+0,2=2*1+0,1=2*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,binary[1]存放最底位.变量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大小的宫殿,先看一下公主站的位置是属于哪一块,因为根据公主所在的位置,我们可以确定中间位置所放的毯子类型,再递归处理公主所站的那一块,直到出现边界条件k=1的情况,然后在公主边上铺上一块合适的地毯,递归结束. 由于要递归到每一格,复杂度就是面积,就是O(22*k*k). 4.3 平面上的最接近点对 源程序名 nearest.???(pas, c, cpp) 可执行文件名 nearest.exe 输入文件名 nearest.in 输出文件名 nearest.out 【问题描述】 给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的. 【输入】 第一行:n;

2≤n≤60000 接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开. 【输出】 仅一行,一个实数,表示最短距离,精确到小数点后面4位. 【样例】 nearest.in nearest.out

3 1.0000

1 1

1 2

2 2 【参考程序】 中位数、解析几何、时间复杂度、二分法 【算法分析】 如果n很小,那么本题很容易.我们只要将每一点对于其它n-1个点的距离算出,找出最小距离即可.时间复杂度O(n2).但本题n很大,显然会超时.所以我们要寻找更快的解决问题的方法.我们首先想到能不能缩小计算的规模,即把n个点的问题分治成一些小规模的问题呢? 由于二维情况下的问题计算过于复杂,所以先讨论一维的情况,假设点集为S. 我们用X轴上某个点m将点集S划分为2个子集S1和S2,使得S1={x∈S|x≤m};