分治习题汇总.docx

《分治习题汇总.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人整理精品文档，仅供个人学习使用分治习题汇总取余运算源程序名.???（,,）可执行文件名输入文件名输出文件名【问题描述】输入，，的值，求的值。其中，，*为长整型数。【样例】^【知识准备】进制转换的思想、二分法。【算法分析】本题主要的难点在于数据规模很大(,都是长整型数)，对于显然不能死算，那样的话时间复杂度和编程复杂度都很大。下面先介绍一个原理：*＝()*()。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢?显然对于任何一个自然数，有＝*，如＝*十＝*，利用上述原

2、理就可以把的次方除以的余数转换为求的次方除以的余数，即*＝**，再进一步分解下去就不难求得整个问题的解。这是一个典型的分治问题，具体实现的时候是用递推的方法来处理的，如，有*，*，*，*，＝*，反过来，我们可以从出发，通过乘以再加上一个或而推出，，，，，这样就逐步得到了原来的指数，进而递推出以为底，依次以这些数为指数的自然数除以的余数。不难看出这里每一次乘以后要加的数就是对应的二进制数的各位数字，即，，，，，而＝()，求解的过程也就是将二进制数还原为十进制数的过程。具体实现请看下面的程序，程序中用数组存放对应的二进制

3、数，总位数为，[]存放最底位。变量记录每一步求得的余数。地毯填补问题源程序名.???（,,）可执行文件名输入文件名输出文件名【问题描述】相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择(如图)：1/13个人整理精品文档，仅供个人学习使用（）（）（）（）并且每一方格只能用一层地毯，迷宫

4、的大小为()的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为。【输入】输入文件共行。第一行：，即给定被填补迷宫的大小为(<≤)；第二行：，即给出公主所在方格的坐标(为行坐标，为列坐标)，和之间有一个空格隔开。【输出】将迷宫填补完整的方案：每一补(行)为(，为毯子拐角的行坐标和列坐标，为使用毯子的形状，具体见上面的图，毯子形状分别用、、、表示，、、之间用一个空格隔开)。【样例】【知识准备】分治思想和递归程序设计。【算法分析】拿到这个问题后，便有一种递归重复的感觉。首先对最简单的情况

5、(即＝)进行分析：公主只会在个方格中的一个：左上角：则使用号毯子补，毯子拐角坐标位于(,)；{下面就简称为毯子坐标}左下角：则使用号毯子补，毯子拐角坐标位于(,)；右上角：则使用号毯子补，毯子拐角坐标位于(,)；右下角：则使用号毯子补，毯子拐角坐标位于(,)；2/13个人整理精品文档，仅供个人学习使用其实这样不能说明什么问题，但是继续讨论就会有收获，即讨论＝的情况(如图)：●○○○我们假设公主所在的位置用实心圆表示，即上图中的(,)，那么我们就可以把号毯子放在(,)处，这样就将(,)至(,)的＝见方全部覆盖(表示地毯

6、)。接下来就是个的见方继续填满，这样问题就归结为＝的情况了，但是有一点不同的是：没有“公主”了，每一个的小见方都会留下一个空白(即上图中的空心圆)，那么空白就有：*＝个，组合后便又是一个地毯形状。好了，现在有感觉了吧，我们用分治法来解决它！对于任意>的宫殿，均可以将其化分为个大小的宫殿，先看一下公主站的位置是属于哪一块，因为根据公主所在的位置，我们可以确定中间位置所放的毯子类型，再递归处理公主所站的那一块，直到出现边界条件＝的情况，然后在公主边上铺上一块合适的地毯，递归结束。由于要递归到每一格，复杂度就是面积，就是*

7、(*)。平面上的最接近点对源程序名.???（,,）可执行文件名输入文件名输出文件名【问题描述】给定平面上个点，找出其中的一对点的距离，使得在这个点的所有点对中，该距离为所有点对中最小的。【输入】第一行：；≤≤接下来行：每行两个实数：，表示一个点的行坐标和列坐标，中间用一个空格隔开。【输出】仅一行，一个实数，表示最短距离，精确到小数点后面位。【样例】【参考程序】中位数、解析几何、时间复杂度、二分法【算法分析】如果很小，那么本题很容易。我们只要将每一点对于其它个点的距离算出，找出最小距离即可。时间复杂度()。但本题很大，

8、显然会超时。所以我们要寻找更快的解决问题的方法。我们首先想到能不能缩小计算的规模，即把个点的问题分治成一些小规模的问题呢?由于二维情况下的问题计算过于复杂，所以先讨论一维的情况，假设点集为。我们用轴上某个点将点集划分为个子集和，使得＝{∈≤}；＝{∈>}。这样一来，对于所3/13个人整理精品文档，仅供个人学习使用有∈和∈有<。递归地在和上找出其