算法分析实验报告--分治策略

《算法设计与分析》实验报告

分治策略

姓名：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

#include

#define MAX 10

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 <= end1)&&(begin2 <= end2))

{

if(array[begin1] < array[begin2])

{

temp[k] = array[begin1];

begin1++;

}

else

{

temp[k] = array[begin2];

begin2++;

}

k++;

}

while(begin1 <= end1)

{

temp[k++] = array[begin1++];

}

while(begin2 <= end2)

{

temp[k++] = array[begin2++];

}

for(i = 0;i < (r-p+1);i++)

{

array[p+i] = temp[i];

}

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 number[MAX] = {0};

srand(time(NULL));

printf("排序前：");

for(int i = 0; i < MAX; i++) {

number[i] = rand() % 100;

printf("%d ", number[i]);

}

cout<

merge_sort(number,0,9);

printf("排序后：");

for(int j = 0; j < MAX; j++) {

printf("%d ", number[j]);

}

}

(2)编写一段程序，实现快速排序。#include

#include

#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(number[i],number[j]);

}

quicksort(number,left,i-1);

quicksort(number,j+1,right);

}

}

void main()

{

int number[MAX] = {0};

srand(time(NULL));

printf("排序前：");

for(int i = 0; i < MAX; i++) {

number[i] = rand() % 100;

printf("%d ", number[i]);

cout<

}

quicksort(number,0,9);

printf("排序后：");

for(int j = 0; j < MAX; j++) {

printf("%d ", number[j]);

}

}

(3)编写程序实现循环赛日程表。

#define MAXN 64

/*日程表数组*/

#include

#include

#define MAX 32

int a[MAX][MAX];

void Copy(int tox, int toy, int fromx, int fromy, int n)

{ int i, j;

for (i=0; i

{ for (j=0; j

}

}

void Table(int k, int a[][MAX])

{ int i, n = 1 << k; int r;

for (i=0; i

a[0][i] = i + 1;

for (r=1; r

{ for (i=0; i

{ Copy(r, i + r, 0, i, r);

Copy(r, i, 0, i + r, r);

}

}

}

void Out(int a[][MAX], int n)

{ int i, j;

for (i=0; i