⼀、实验⽬的
1. 了解分治策略算法思想
3. 了解其他分治问题典型算法
⼆、实验内容
1. 编写⼀个简单的程序，实现归并排序。
编写⼀段程序，实现快速排序。
2. 编写程序实现循环赛⽇程表。设有n=2k个运动员要进⾏⽹球循环赛。现要设计⼀个满⾜以下要求的⽐赛⽇程表：
（1）每个选⼿必须与其它n-1个选⼿各赛⼀次
（2）每个选⼿⼀天只能赛⼀场
（3）循环赛进⾏n-1天
三、算法思想分析
1. 归并排序
基本思想为先将⼀个待排序序列分成两段⼤⼩⼤致相同的段，然后对这两个段同样递归地进⾏⼆分，直到不能再分为⽌，然后把⾜够⼩的相邻序列合并成有序序列（依据最优⼦结构且各个⼦问题相互独⽴），再上溯，合并，直到整个序列有序化。 合并时需要对两个已有序的序列合并成⼀个有序队列，因此在合并操作时就需要进⾏有序化操作，在这⾥因为本⾝⼦序列已经有序，所以采⽤设置两个⼦序列的⾸尾指针，⾸指针移动来⽐较两个⼦序列中的较⼩元素并存到新序列，直到⼀⽅⾸尾指针重合，再将另⼀个序列的剩余部分直接接到新序列即可。
2. 快速排序
基本思想为通过⼀次排序将需要排序的序列分割成独⽴的两部分，⾸先设置⼀个基准数，进⾏⼀次排序后，其中⼀部分的所有数据⽐基准数⼩，另⼀部分的所有数据都⽐基准数⼤，这样基准数当前位置就是其在有序序列的位置，然后对新分出的两个序列递归地进⾏排序处理（由于两⽅互不影响，其满
⾜最优⼦结构，有独⽴性），直到序列⼤⼩最⼩，这样通过⼀次分治的排序可以将所有元素放到有序序列的正确位置上，从⽽将整个序列有序化，整体是⼀个“挖坑填数+分治”的过程。
3. 循环赛⽇程表
基本思想为将整个n * n表格分成n/2 * n/2的四部分，对左上⾓与右上⾓的部分递归地进⾏分割（独⽴性），直到⼤⼩为2 * 2的最⼩可分配部分，针对最⼩部分，将每个部分的左上⾓部分赋给右下⾓（在最优⼦结构下2 * 2的部分左上⾓和右上⾓都是⼀个元素），右上⾓部分赋给左下⾓，再上溯到4 * 4，重复合并操作，⼀直到⼤⼩为n，这样获得的表就是⼀个已分配好的表，其中第⼀列是⽐赛的每⼀⽅，后七列的每⼀列分别代表当天的对阵。
四、实验过程分析
在做本次实验的过程中，我起初对递归的理解程度不是很深，归并和快排的思想相对还好理解，实现起来也有规律可循，但当做到循环赛⽇程表时，发现分割从归并与快排的⼀维升到了⼆维，就在递归的设计上犯了难，通过⼀段时间的研究与调试，最后发现当规模没有降到最⼩时其实都是在进⾏分割，只有当规模够⼩之后才能简单进⾏合并操作，再将部分完成的矩阵升规模再合并直到完成整个矩阵。
通过分治的实验，我对分治的最优⼦结构性质，独⽴性，规模缩⼩策略等相关概念与思想的理解相对更加的深⼊，这对我在整个课程的学习中都是⼀个⼗分显著的成果，⽽且通过代码的实现，我对分治的基本策略与递归的结合的使⽤更加的娴熟了，这提⾼了我的编程能⼒。
五、算法源代码及⽤户屏幕
1.归并排序
①代码
#include<iostream>
using namespace std;
void merge(int array[],int left,int middle,int right){
int length = right - left +1;race实验
//申请空间⽤于存储合并之后的序列
int temp[right - left +1];
//设置标号
int begin1 = left;
int begin1 = left;
int end1 = middle;
int begin2 = middle +1;
int end2 = right;
//设置新数组的计数器
int i =0;
//⽐较，进⼊序列
while((begin1 <= end1)&&(begin2 <= end2)){
if(array[begin1]< array[begin2]){
temp[i]= array[begin1];
begin1++; i++;
}
else
{
temp[i]= array[begin2];
begin2++; i++;
}
}
//将剩余部分直接接到最后的序列上
while(begin1 <= end1){
temp[i]= array[begin1];
begin1++; i++;
}
while(begin2 <= end2){
temp[i]= array[begin2];
begin2++; i++;
}
for(int j =0; j < length; j++)
{
array[left + j]= temp[j];
}
}
//递归调⽤完成操作
void mergeSort(int data[],int left,int right){
if(left < right){
int middle =(left + right)/2;
//先分后合并
mergeSort(data, left, middle);
mergeSort(data, middle +1, right);
merge(data, left, middle, right);
}
}
int main(){
int n;
cout <<"Please input the number of numberSet: "; cin >> n;
int array[n];
cout <<"Please input the number: ";
for(int i =0; i < n; i++){
cin >> array[i];
}
mergeSort(array,0, n -1);
cout <<"the result is: ";
for(int i =0; i < n; i++){
cout << array[i]<<" ";
}
system("pause");
return0;
}
②⽤户界⾯
⾸先输⼊序列中数的个数，然后输⼊⽆序序列，回车之后返回有序序列
2.快速排序
①代码
#include<iostream>
using namespace std;
int splitArray(int data[],int left,int right){
//获取最左边的元素
int temp = data[left];
//从左向右查⼩于标志位的元素，换到左边，移指针while(left < right){
while((left < right)&&(data[right]>= temp)){
right--;
}
data[left]= data[right];
//从右向左查⼤于标志位的元素，换到右边，移指针while((left < right)&&(data[left]<= temp)){
left++;
}
data[right]= data[left];
}
//将标志位填到空位
data[left]= temp;
return left;
}
//先将标志位填好，然后左右递归调⽤
void quickSort(int data[],int left,int right){
if(left < right){
int middle =splitArray(data, left, right);
quickSort(data, left, middle -1);
quickSort(data, middle +1, right);
}
}
int main(){
int n;
cout <<"Please input the number of numberSet: "; cin >> n;
int array[n];
cout <<"Please input the number: ";
for(int i =0; i < n; i++){
cin >> array[i];
}
quickSort(array,0, n -1);
cout <<"the result is: ";
for(int i =0; i < n; i++){
cout << array[i]<<" ";
}
system("pause");
return0;
}
②⽤户界⾯
⾸先输⼊序列中数的个数，然后输⼊⽆序序列，回车之后返回有序序列
3.循环赛⽇程表
①代码
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议