第4章-分治法2

1、第四章是分治法，1，2，3，4，分治法的设计思想，排序问题中的分治法，组合问题中的蛮力法，5，几何问题中的蛮力法，小结，1，分治法的设计思想，人少人多，分数一样；水桶和水桶一样多，名字也是。把一个很难直接解决的大问题分成几个小问题，这样就可以互相分而治之。1分治法的设计思想，1分治法的设计思想，(1)划分：既然是分治法，当然有必要把原来规模n的问题划分成k个更小的子问题，并尽量使这k个子问题的规模大致相同。(2)求解子问题：每个子问题的解通常与原问题的解相同，每个子问题都可以用递归方法求解，有时递归处理也可以用循环实现。(3)合并：合并每个子问题的解，合并的代价根据不同的情况有很大的不同，分治

2、算法的有效性很大程度上取决于合并的实现。从大量实践中发现，用分治法设计算法时，最好使子问题的规模大致相同。将一个问题分成大小相等的k个子问题是有效的。这种使子问题在规模上大致相等的方法来自于平衡子问题的思想，它几乎总是优于子问题规模不等的方法。分而治之方法的求解步骤，分而治之如果规模足够小就直接求解；否则分解成k个子问题P1，P2，Pk；对于(I=1；I=k；I)yi=Divisonquer(Pi)；返回合并(y1，yk)；分而治之方法的时间复杂度，以及子问题的输入规模大致相等且分为两个，则分而治之方法的计算时间可以表示为：g(n) n足够小T(n)=2T(n/2) f(n)，表示：T(n)输

3、入规模为n的分而治之方法的计算时间；G(n)是直接求解足够小的n的时间；F(n)是合并的计算时间。当问题的规模缩小到一定程度时，问题就很容易解决；2.该问题可分解为几个较小的相同问题，即问题具有最优子结构性质；3.由问题分解的子问题的解可以组合成问题的解；4.由问题分解的子问题相互独立，即子问题之间没有共同的子问题。分而治之方法的适用条件，因为问题的计算复杂性一般随着问题规模的增加而增加，所以大多数问题满足条件1的特征。第二个特点是应用分治法的前提，体现了递归思想的应用。当问题的规模缩小到一定程度时，问题就很容易解决；2.该问题可分解为几个较小的相同问题，即问题具有最优子结构性质；3.由问题分

4、解的子问题的解可以组合成问题的解；4.由问题分解的子问题相互独立，即子问题之间没有共同的子问题。分治法的适用条件完全取决于问题是否具有第三个特征。如果它有前两个特征，但没有第三个特征，可以考虑贪婪算法或动态规划。第四个特点涉及分而治之方法的效率。如果每个子问题不是独立的，分而治之的方法应该做大量的重复工作，反复解决常见的子问题。此时，虽然也可以使用分治法，但通常最好使用动态编程。2数字旋转方阵的简单示例，问题描述：输出下图所示的数字旋转方阵NN(1N10)。1 20 19 18 17 16 2 21 31 30 15 3 22 36 29 14 23 34 35 28 13 5 24 26 2

5、7 12 67 8 9 10 11，想：A，B，C，D用二维数组数据表示神经网络的方阵，并观察。让变量大小表示方阵的大小，那么大小在开始时=N，大小=size-2；填充一层后；让变量begin代表每个层的起始位置，变量I和j分别代表行号和列号，那么i=begi每层的填充过程分为四个区域：a、b、c和d，因此每个区域需要填充1个尺寸的数字。填写a区时，列号将增加1；填写区域b时，列号将增加1；填写c区时，列号将减少1。显然，递归的结束条件是大小等于0或大小等于1。2一个简单的数字旋转正方形矩阵的例子，2一个简单的数字旋转正方形矩阵的例子，算法4.1:数字旋转正方形矩阵全输入：数字要填入当前层的左

6、上角，坐标从左上角开始，正方形矩阵的大小顺序输出：数字旋转正方形矩阵1。如果大小等于0，算法结束；2.如果大小等于1，则databeginbegin=number，算法结束；3.初始化行和列下标i=开始，j=开始；4.重复以下操作大小1次，并填写区域A 4.1数据=数字；数量；4.2行下标I；列下标保持不变；5.重复以下操作大小1次，并填写区域B 5.1数据=数字；数量；5.2行下标保持不变；列下标j。6.重复以下操作大小1次，并填写区域C 6.1数据=数字；数量；6.2行下标I-；列下标保持不变；7.重复下列操作尺寸1次，并填写区域D 7.1数据=数字；数量；7.2行下标不变，列下标j-；8

7、.调用Full函数，从大小为2的正方形矩阵左上角的从1开始的数字开始填充数字；在排序问题中，采用分治法进行合并和排序。请注意，只有一条记录的序列显然是有序序列。将两个有序序列合并成一个有序序列的过程称为双向合并。双向合并排序，分治合并排序在排序问题中，已知关键字序列85，92，43，25，76，20，3，58，15，请给出双向合并排序的每个结果。合并两个有序表，并从相邻的有序表a0A和a0A中获取有序表a0A。算法如下：1 .从每个数组中取一个最小的数，分别为AsAm和Am1ae；2.将取出的两个数字进行比较，将较小的数字依次放入数组R中；3.从与较小数字对应的数组中取出下一个最小数字；4.重

8、复步骤2和3，直到两个序列中的所有数据都被取走；5.如果AsAm或Am 1Ae有未被取走的数据，所有剩余数据将依次复制到r中的现有数据；6.将R中的数据逐个复制回A；并且长度为n的序列a中的每个有序序列的长度是len。双向合并应该考虑以下问题：如果n可以被2*len整除，那么a就可以合并长度为2*len的n/(2*len)个有序表。如果n不能被2*len整除，则有两种情况：n/(2*len)余数小于或等于len，且还有一个有序表。此时，不需要将剩余的元素与n/(2*len)合并。剩余的两个有序表，一个大的和一个小的，被合并成一个有序表，其中len=1，n/2*len=9/2=4，剩余的1len=2，n/2*len=9/4=2，剩余的