《算法分析与设计实验报告--分治法》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告--分治法（10页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计 实验报告 完成日期： 20011.11.10一、实验目的 (1) 了解分治策略算法思想 (2) 掌握快速排序、归并排序算法 (3) 了解其他分治问题典型算法 二实验内容： (1) 编写一个简单的程序，实现归并排序。 (2) 编写一段程序，实现快速排序。 (3) 编写程序实现循环赛日程表。设有 n=2k 个运动员要进行网球循环赛。 现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它 n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行 n-1 天 三实验要求： （1） 写出源程序，并编译运行 （2） 详细记录程序调试及运行结果 四算法思想分析：归并排序：将
2、待排序元素分成大小大致相同的两个集合，分别把对 两个子集合进行排序，最终将排序号的子集合合并成为所要求的排好序 的集合快速排序：通过一次排序将要排序的数据分割成独立的两部分，其中 一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对 这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达 到整个数据变成有序序列。按照分治策略，将所有选手分为两组，n个选手的比赛日程就可以通过 为 n/2 个选手设计的比赛日程表来决定。递归的对选手进行分割，直到 剩下两个选手时，比赛日程表的制定就变得异常简单。这时只要让这两 个选手进行比赛就可以了五算法源代码：归并排序： 源代码如下： #inc
3、lude using namespace std; void merge(int array, int p, int q, int r) int i,k; int begin1,end1,begin2,end2; int* temp = new int r-p+1; /申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后、 /的序列 /设定两个指针，最初位置分别为两个已经排序序列的起止位置 begin1= p; end1 = q; begin2 = q+1; end2 = r; k = 0; while(begin1 using namespace std; void quickso
4、rt(int number, int left, int right) int i, j, s; if(left s) ; / 向左找第一个小于轴的数 if(i = j) break; swap(numberi, numberj); quicksort(number, left, i-1); / 对左边进行递归 quicksort(number, j+1, right); / 对右边进行递归 int main() int a8=1,45,48,21,35,48,1421,98; quicksort(a,0,7); cout #include #define MAX 32 int aMAXMAX
5、; void Copy(int tox, int toy, int fromx, int fromy, int n) int i, j;for (i=0; i using namespace std; void countsort(int a, int n) int count=0;int k=0;while (kai)count+;if(count=0)k+;if(count0)swap(ak,acount);count=0; cout“排序后为:“endl;for(int j = 0 ; j n ; j+ )coutaj “ “; void swap(int temp = x; x=y;
6、y = temp; void main() int n = 8; int a8 = 100, 200, 50, 90, 150, 50, 20, 80; cout“排序前为:“endl; for (int q=0;q=7;q+) coutaq“ “; coutendl; countsort(a,8); 六实验分析：上课讲分治算法讲的透彻，上课认真听讲和下课后对算法的理解。在编 写算法代码时还是比较容易的。我觉得主要是要把算法理解清楚。虽然在编程 过程中也遇到了一些问题。通过上网参考一些资料和同学间的交流都得到了很 好的解决。算法真的很重要，一个好的算法可以节省很多时间和内存。一定要 好好加油，在以后的编程中也要逐步注意自己的算法是否用得合理 实验中遇到好多问题，不知道该如何设计二维数组的循环。通过这个实验， 也知道了分治在解决问题中确实很好用。
