算法分析实验报告--分治策略(共8页).doc
精选优质文档-倾情为你奉上算法设计与分析实验报告分治策略姓 名：XXX专 业 班 级：XXX学 号： XXX指导教师：XXX完成日期：XXX一、试验名称：分治策略（1） 写出源程序，并编译运行（2） 详细记录程序调试及运行结果二、实验目的(1) 了解分治策略算法思想(2) 掌握快速排序、归并排序算法(3) 了解其他分治问题典型算法三、实验内容(1) 编写一个简单的程序，实现归并排序。(2) 编写一段程序，实现快速排序。(3) 编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天四、算法思想分析(1) 编写一个简单的程序，实现归并排序。将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。(2) 编写一段程序，实现快速排序。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 (3) 编写程序实现循环日赛表。按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。五、算法源代码及用户程序(1) 编写一个简单的程序，实现归并排序。#include<iostream>#include<time.h>#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)&&(begin2 <= 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) int mid = (left + right)/2;merge_sort(data,left,mid);merge_sort(data,mid + 1,right);merge(data,left,mid,right);void main()int numberMAX = 0;srand(time(NULL); printf("排序前："); for(int i = 0; i < MAX; i+) numberi = rand() % 100; printf("%d ", numberi); cout<<endl;merge_sort(number,0,9);printf("排序后："); for(int j = 0; j < MAX; j+) printf("%d ", numberj); (2) 编写一段程序，实现快速排序。#include<iostream>#include<time.h>#define MAX 10#define SWAP(x,y) int t; t = x; x = y; y = t;using namespace std;void quicksort(int number,int left,int right)int i,j,s;if(left < right)s = number(left + right)/2;i = left - 1;j = right + 1;while(1)while(number+i < s);while(number-j > s);if(i>=j)break;SWAP(numberi,numberj);quicksort(number,left,i-1);quicksort(number,j+1,right);void main()int numberMAX = 0;srand(time(NULL); printf("排序前："); for(int i = 0; i < MAX; i+) numberi = rand() % 100; printf("%d ", numberi);cout<<endl; quicksort(number,0,9);printf("排序后："); for(int j = 0; j < MAX; j+) printf("%d ", numberj); (3) 编写程序实现循环赛日程表。#define MAXN 64/*日程表数组*/#include <stdio.h>#include <stdlib.h> #define MAX 32 int aMAXMAX; void Copy(int tox, int toy, int fromx, int fromy, int n) int i, j; for (i=0; i<n; i+) for (j=0; j<n; j+) atox + itoy + j = afromx + ifromy + j; void Table(int k, int aMAX) int i, n = 1 << k; int r; for (i=0; i<n; i+) a0i = i + 1; for (r=1; r<n; r<<=1) for (i=0; i<n; i+=2*r) Copy(r, i + r, 0, i, r); Copy(r, i, 0, i + r, r); void Out(int aMAX, int n) int i, j; for (i=0; i<n; i+) for (j=0; j<n; j+) printf("%3d", aij); printf("n"); printf("n");getch(); int main() int i; for (i=0; i<5; i+) int len = 1 << i; Table(i, a); Out(a, len); return 0;六 试验结果及分析分治策略对于解决排序，循环日赛表起着很优越的作用，应该熟练掌握归并排序和快速排序。而且应该认真搞懂递归的思想。专心-专注-专业
