算法分析实验报告--分治策略(共8页).doc
《算法分析实验报告--分治策略(共8页).doc》由会员分享,可在线阅读,更多相关《算法分析实验报告--分治策略(共8页).doc(8页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上算法设计与分析实验报告分治策略姓 名:XXX专 业 班 级:XXX学 号: XXX指导教师:XXX完成日期:XXX一、试验名称:分治策略(1) 写出源程序,并编译运行(2) 详细记录程序调试及运行结果二、实验目的(1) 了解分治策略算法思想(2) 掌握快速排序、归并排序算法(3) 了解其他分治问题典型算法三、实验内容(1) 编写一个简单的程序,实现归并排序。(2) 编写一段程序,实现快速排序。(3) 编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其它n-1个选手各赛一次(2)每个选手一天只能赛
2、一场(3)循环赛进行n-1天四、算法思想分析(1) 编写一个简单的程序,实现归并排序。将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。(2) 编写一段程序,实现快速排序。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 (3) 编写程序实现循环日赛表。按分治策略,将所有的选手分为两组,n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割,
3、直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。五、算法源代码及用户程序(1) 编写一个简单的程序,实现归并排序。#include#include#define MAX 10using namespace std;void merge(int array,int p,int q,int r)int i,k;int begin1,end1,begin2,end2; int* temp = new intr-p+1;begin1 = p;end1 = q;begin2 = q+1;end2 = r;k = 0;while(begin1 = end1)&(b
4、egin2 = end2)if(arraybegin1 arraybegin2)tempk = arraybegin1;begin1+;elsetempk = arraybegin2;begin2+;k+;while(begin1 = end1)tempk+ = arraybegin1+;while(begin2 = end2) tempk+ = arraybegin2+;for(i = 0;i (r-p+1);i+)arrayp+i = tempi;delete(temp);void merge_sort(int data,int left,int right)if(left right)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 实验 报告 分治 策略
限制150内