分治习题汇总

《分治习题汇总》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分治习题汇总4.1取余运算源程序名mod.???（pas,c,cpp）可执行文件名mod.exe输入文件名mod.in输出文件名mod.out【问题描述】输入b，p，k的值，求bpmodk的值。其中b，p，k*k为长整型数。【样例】mod.inmod.out21092^10mod9=7【知识准备】进制转换的思想、二分法。【算法分析】本题主要的难点在于数据规模很大(b,p都是长整型数)，对于bp显然不能死算，那样的话时间复杂度和编程复杂度都很大。下面先介绍一个原理：a*bmodk＝(amodk)*(bmodk)modk

2、。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢?显然对于任何一个自然数P，有p＝2*pdiv2+pmod2，如19＝2*19div2十19mod2＝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

3、+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地毯填补问题源程序名blan

4、k.???（pas,c,cpp）可执行文件名blank.exe输入文件名blank.in输出文件名blank.out【问题描述】相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择(如图4-l)：（1）（2）（3）（4）并且每一方格只能用一层地毯，迷宫的大小为(2k)2的方形。当然，也不

5、能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为1s。【输入】输入文件共2行。第一行：k，即给定被填补迷宫的大小为2k(0

6、273154183363481722514632812841771661583852881【知识准备】分治思想和递归程序设计。【算法分析】拿到这个问题后，便有一种递归重复的感觉。首先对最简单的情况(即k＝1)进行分析：公主只会在4个方格中的一个：左上角：则使用3号毯子补，毯子拐角坐标位于(2,2)；{下面就简称为毯子坐标}左下角：则使用2号毯子补，毯子拐角坐标位于(1,2)；右上角：则使用1号毯子补，毯子拐角坐标位于(2,1)；右下角：则使用4号毯子补，毯子拐角坐标位于(1,1)；其实这样不能说明什么问题，但是继续讨

7、论就会有收获，即讨论k＝2的情况(如图4-1)：###●#○###○○#####我们假设公主所在的位置用实心圆表示，即上图中的(1,4)，那么我们就可以把1号毯子放在(2,3)处，这样就将(1,3)至(2,4)的k＝1见方全部覆盖(#表示地毯)。接下来就是3个k=1的见方继续填满，这样问题就归结为k＝1的情况了，但是有一点不同的是：没有“公主”了，每一个k=1的小见方都会留下一个空白(即上图中的空心圆)，那么空白就有：1*3＝3个，组合后便又是一个地毯形状。好了，现在有感觉了吧，我们用分治法来解决它！对于任意k>1的

8、宫殿，均可以将其化分为4个k/2大小的宫殿，先看一下公主站的位置是属于哪一块，因为根据公主所在的位置，我们可以确定中间位置所放的毯子类型，再递归处理公主所站的那一块，直到出现边界条件k＝1的情况，然后在公主边上铺上一块合适的地毯，递归结束。由于要递归到每一格，复杂度就是面积，就是O(22*k*k)。4.3平面上的最接近点对源程序名nearest