算法分析与设计实验报告--分治法

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

完成日期： 20011.11.10

一、实验目的

(1) 了解分治策略算法思想

(2) 掌握快速排序、归并排序算法

(3) 了解其他分治问题典型算法

二．实验内容：

(1) 编写一个简单的程序，实现归并排序。

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

(3) 编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天

三．实验要求：

（1） 写出源程序，并编译运行

（2） 详细记录程序调试及运行结果

四．算法思想分析：

①归并排序：将待排序元素分成大小大致相同的两个集合，分别把对两个子集合进行排序，最终将排序号的子集合合并成为所要求的排好序的集合

②快速排序：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

③按照分治策略，将所有选手分为两组，n个选手的比赛日程就可以通过为n/2个选手设计的比赛日程表来决定。递归的对选手进行分割，直到剩下两个选手时，比赛日程表的制定就变得异常简单。这时只要让这两个选手进行比赛就可以了

五．算法源代码：

⑴归并排序：

源代码如下：

#include<iostream>

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);

}

}

int main()

{

int a[8]={10,8,98,56,42,40,7,5};

merge(a,0,3,7);

merge_sort(a,0,7);

cout<<"归并排序后的数组为："<<endl;

int z=0;

for (z;z<8;z++)

{

cout<<a[z]<<" ";

}

cout<<endl;

return 0;

}

截图如下：

2.快速排序：

算法实验代码如下：

#include <iostream>

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); // 对右边进行递归

}

}

int main()

{

int a[8]={1,45,48,21,35,48,1421,98};

quicksort(a,0,7);

cout<<"经快速排序后的数组为："<<endl;

int i=0;

for (i;i<8;i++)

{

cout<<a[i]<<" ";

}

cout<<endl;

return 0;

}

截图如下：

3.循环赛日程表：

算法实验代码如下：

#define MAXN 64

/*日程表数组*/

#include <stdio.h>

#include <stdlib.h>

#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<n; i++)

{ for (j=0; j<n; j++)

a[tox + i][toy + j] = a[fromx + i][fromy + j];

}

}

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

{

int i, n = 1 << k;

int r;

for (i=0; i<n; i++)

a[0][i] = 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 a[][MAX], int n)

{

int i, j;

for (i=0; i<n; i++)

{ for (j=0; j<n; j++)

printf("%3d", a[i][j]);

printf("\n");

}

printf("\n");

}

int main()

{ int i;

for (i=0; i<5; i++)

{ int len = 1 << i;

Table(i, a);

Out(a, len);

}

return 0;

}

截图所示：

作业：

线性时间排序：

#include <iostream>

using namespace std;

void countsort(int a[], int n)

{

int count=0;

int k=0;

while (k<n-1)

{

for(int i=k+1; i<n; i++)

{

if(a[k]>a[i])

count++;

}

if(count==0)

k++;

if(count>0)

{

swap(a[k],a[count]);

count=0;

}

}

cout<<"排序后为:"<<endl;

for(int j = 0 ; j < n ; j++ )

cout<<a[j] << " ";

}

void swap(int &x, int &y)

{

int temp;

temp = x;

x=y;

y = temp;

}

void main()

{

int n = 8;

int a[8] = {100, 200, 50, 90, 150, 50, 20, 80};

cout<<"排序前为:"<<endl;

for (int q=0;q<=7;q++)

{

cout<<a[q]<<" ";

}

cout<<endl;

countsort(a,8);

}

六．实验分析：

上课讲分治算法讲的透彻，上课认真听讲和下课后对算法的理解。在编写算法代码时还是比较容易的。我觉得主要是要把算法理解清楚。虽然在编程过程中也遇到了一些问题。通过上网参考一些资料和同学间的交流都得到了很好的解决。算法真的很重要，一个好的算法可以节省很多时间和内存。一定要好好加油，在以后的编程中也要逐步注意自己的算法是否用得合理

实验中遇到好多问题，不知道该如何设计二维数组的循环。通过这个实验，也知道了分治在解决问题中确实很好用。

本文来源：https://www.bwwdw.com/article/96n1.html