开放性实验报告
目 录
1 概述 ................................................... 1
1.1 设计思想 ......................................... 1 1.2 一般求解过程 ..................................... 2 2 算法描述 ............................................... 2
2.1 排序问题中的分治法 ............................... 2 2.2 组合问题中的分治法 ............................... 2 2.3 几何问题中的分治法 ............................... 3 3 算法应用 ............................................... 4
3.1 快速排序问题 .................................... 4 3.2 棋盘覆盖问题 .................................... 6 3.3 最近对问题 ..................................... 11 4 实验结果分析 .......................................... 17
4.1 快速排序问题运行结果及分析 ...................... 17 4.2 棋盘覆盖问题运行结果及分析 ...................... 19 4.3 最近对问题运行结果及分析 ........................ 22 5 实验总结 .............................................. 22 参考文献 ................................................ 23
1 概述
1.1 设计思想
将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。
启发式规则：
1. 平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。
2. 独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。
分治法的典型情况：如图1.1所示。
子问题1的解 原问题的解 图1.1分治法的典型情况
子问题1的规模是子问题2的规模是原问题的规模是n n/2 n/2 子问题2的解 1
1.2 一般求解过程
一般来说，分治法的求解过程由以下三个阶段组成：
（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。
（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。
（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。
2 算法描述
2.1 排序问题中的分治法
快速排序问题
快速排序的分治策略是：
（1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1 ? ri-1和ri+1 ? rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；
（2）求解子问题：分别对划分后的每一个子序列递归处理；
（3）合并：由于对子序列r1 ? ri-1和ri+1 ? rn的排序是就地进行的，所以合并不需要执行任何操作。
2.2 组合问题中的分治法
棋盘覆盖问题
在一个2×2 （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。棋盘覆盖问题要求用图2.1（b）所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
k
k
2
(a) k=2时的一种棋盘 (b) 4种不同形状的L型骨牌
图2.1棋盘覆盖骨牌
分治法求解棋盘覆盖问题的技巧在于划分棋盘，使划分后的子棋盘的大小相同且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。
k>0时，可将2k×2k的棋盘划分为4个2k-1×2k-1的子棋盘，这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。
2k-1×2k-1 k2k-1×2k-1 k2-1 2-1× 2k-1×2k-1 (a)棋盘分割 (b) 构造相同子问题
图2.2棋盘的划分
2.3几何问题中的分治法
最近对问题
设p1=(x1, y1), p2=(x2, y2), ?, pn=(xn, yn)是平面上N个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。严格地讲，最接近点对可能多于一对，简单起见，只找出其中的一对作为问题的解。
3
用分治法解决最近对问题，很自然的想法就是将集合S分成两个子集 S1和 S2，每个子集中有N/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合 S 中最接近的两个点都在子集 S1或
S2中，则问题很容易解决，如果这两个点分别在 S1和 N2中，问题就比较复杂。
3 算法应用
3.1 快速排序问题
1.问题描述
利用快速排序算法将读入的10个数从小到大顺序输出。第一行给出提示语“输入N个整数”，第二行包含N个空格隔开的整数a[i]，为需要进行排序的数，数据
a[i]不超过10000000000。将给定的N个数从小到大输出，数之间空格隔开。
2.解题思路
以第一个记录作为轴值，对待排序序列进行划分的过程为：
（1）初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；
（2）右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若i＜j，则将基准记录与j指向的记录进行交换；
（3）左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若i＜j，则将基准记录与i指向的记录交换；
（4）重复（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。 一次划分示例，如图3.1所示： 65 38 4 图3.1（a） 55 27 50 49 13
分治法开放性实验报告-正文
