分治习题汇总课件.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(0k≤10)； 第二行：x y，即给出公主所在方格的坐标(x为行坐标，y为列坐标)，x和y之间有一个空格隔开。 【输出】 将迷宫填补完整的方案：每一补(行)为x y c (x，y为毯子拐角的行坐标和列坐标，c为使用毯子的形状，具体见上面的图1，毯子形状分别用1、2、3、4表示，x、y、c之间用一个空格隔开)。 【样例】 blank.in blank.out 3 5 5 1 3 3 2 2 4 1 1 4 1 4 3 4 1 2 4 4 1 2 7 3 1 5 4 1 8 3 3 6 3 4 8 1 7 2 2 5 1 4 6 3 2 8 1 2 8 4 1 7 7 1 6 6 1 5 8 3 8 5 2 8 8 1 【知识准备】 分治思想和递归程序设计。 【算法分析】 拿到这个问题后，便有一种递归重复的感觉。首先对最简单的情况(即k＝1)进行分析：公主只会在4个方格中的一个： 左上角：则使用3号毯子补，毯子拐角坐标位于(2, 2)；{下面就简称为毯子坐标} 左下角：则使用2号毯子补，毯子拐角坐标位于(1, 2)； 右上角：则使用1号毯子补，毯子拐角坐标位于(2, 1)； 右下角：则使用4号毯子补，毯子拐角坐标位于(1, 1)； 其实这样不能说明什么问题，但是继续讨论就会