一、实验目的

1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。

二、实验任务

1、 最近对问题：
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。
（1） 分别用蛮力法和分治法求解最近对问题；
（2） 分析算法的时间性能，设计实验程序验证分析结论。带锁的门：
2、 循环赛日程安排问题：
设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能赛一次。
3、排序问题：
目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法，并分析算法的时间复杂度。比较各种算法的优劣（冒泡排序、选择排序、插入排序、二分插入排序、希尔排序、归并排序、堆排序、快速排序等，需比较分析各种算法的时间复杂度及排序的稳定性）。
4、用分治策略，设计解棋盘覆盖问题的一个简洁算法

三、实验设备及编程开发工具

笔记本，Windows10操作系统，Dev-C++

四、实验过程设计（算法设计过程）

1、最近对问题

(1)蛮力法：在蛮力法实现最近点对问题中，将问题简化为求二维平面中两点的距离，此处考虑直接用公式计算其距离（欧几里得距离）：

//最近点对问题，蛮力法实现
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
#define MAX 99999
using namespace std;
double closestPoints(double x[],double y[],int n){
    double x1,x2,y1,y2;                      //记录下标
    double dist,minDist=MAX;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++){
            dist=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);  //计算距离
            if(dist<minDist){
                minDist=dist;
                x1=x[i];y1=y[i];
                x2=x[j];y2=y[j];
            }
       }
    cout<<"最近点对为：("<<x1<<","<<y1<<")-("<<x2<<","<<y2<<")";      //输出坐标
    return minDist;
}
int main(){
    double x[100],y[100];
    double minDist;
    int n;
    cout<<"输入点的个数：\n";
    cin>>n;
    cout<<"输入点集的坐标：\n";
    for(int i=0;i<n;i++)
        cin>>x[i]>>y[i];
    minDist=closestPoints(x,y,n);
    cout<<"其距离为：\n"<<sqrt(minDist);
    return 0;
}

(2)分治法：将集合S分成两个子集S1和S2，根据平衡子问题原则，每个子集中的点数大致都为n/2。这样分治后，最近点对将会出现三种情况：在S1中，在S2中或者最近点对分别在集合S1和S2中。利用递归分析法分别计算前两种情况，第三种方法另外分析。求解出三类子情况后，再合并三类情况，比较分析后输出三者中最小的距离。分为以下三个步骤：
a) 将n个点按照横坐标排序，并按照1_{n编号，分成两部分：1}⌊n/2⌋、⌈n/2⌉~n。
b) 分别求出左右两部分中的最近点对距离，记为 d1和d2，取 d=min(d1, d2)，通常采用递归的办法。
c) 如果最近点对分别在集合S1和S2中，不能把左半部分点集中的点挨个与右半部分的所有点算距离，这样总体来看跟暴力破解就没什么区别了，所以需要优化，减少需要计算距离的点对个数。优化方法为：

1. 选出与中间结点横坐标距离内为 d 的点：遍历整个点集，筛选出一些点，这些点满足与中间结点的横坐标距离小于 d（横坐标距离大于 d，那该点到另外一个点集中任意一个点的距离肯定都大于 d）。
2. 只需计算紧随其后的 6 个点：接下来直接对筛选出的点进行暴力破解就可以了。但是筛选出来的点可能很多，所以需要继续优化：将筛选出来的点按纵坐标排序，纵坐标距离大于d时，直接break。而且对于每个点来说，最多只需要考虑紧随其后的6个点。

//分治法求解最近点对问题(C++)
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct point{           //点结构
    double x,y;
};
double Distance(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b){          //按y升排序辅助函数
    return a.y<b.y;
}
bool cmp2(point a,point b){          //按x升排序辅助函数
    return a.x<b.x;
}
double closestPoint(point s[],int low,int high,point rec[]){
    double d1,d2,d3,d;
    int mid,i,j,index;
    double x1,y1,x2,y2;         //记录点对的位置
    point P[high-low+1],temp1[2],temp2[2],temp3[2];         //辅助空间
    if(high-low==1){             //两个点的情况
        rec[0].x=s[low].x;rec[0].y=s[low].y;
        rec[1].x=s[high].x;rec[1].y=s[high].y;
        return Distance(s[low],s[high]);
        }
    if(high-low==2){            //三个点的情况
        d1=Distance(s[low],s[low+1]);
        d2=Distance(s[low+1],s[high]);
        d3=Distance(s[low],s[high]);
        if((d1<d2)&&(d1<d3)){
            rec[0].x=s[low].x;rec[0].y=s[low].y;
            rec[1].x=s[low+1].x;rec[1].y=s[low+1].y;
            return d1;
        }
        else if(d2<d3){
            rec[0].x=s[low+1].x;rec[0].y=s[low+1].y;
            rec[1].x=s[high].x;rec[1].y=s[high].y;
            return d2;
        }
        else {
            rec[0].x=s[low].x;rec[0].y=s[low].y;
            rec[1].x=s[high].x;rec[1].y=s[high].y;
            return d3;
        }
    }
    mid=(low+high)/2;       //其他情况递归
    d1=closestPoint(s,low,mid,rec);
    temp1[0]=rec[0];
    temp1[1]=rec[1];
    d2=closestPoint(s,mid+1,high,rec);
    temp2[0]=rec[0];
    temp2[1]=rec[1];
    if(d1<d2){
        d=d1;
        rec[0]=temp1[0];
        rec[1]=temp1[1];
    }
    else {
        d=d2;
        rec[0]=temp2[0];
        rec[1]=temp2[1];
    }
    index=0;
    for(i=mid;(i>=low)&&((s[mid].x-s[i].x)<d);i--)      //点集合p1
        P[index++]=s[i];
    for(i=mid+1;(i<=high)&&((s[i].x-s[mid].x)<d);i++)      //点集合p2
        P[index++]=s[i];
    sort(P,P+index,cmp);                    //升序排列
    for(i=0;i<index;i++){
        for(j=j+1;j<index;i++){
            if((P[j].y-P[i].y)>=d)
                break;
            else {
                d3=Distance(P[i],P[j]);
                if(d3<d){
                    rec[0].x=P[i].x;rec[0].y=P[i].y;
                    rec[1].x=P[j].x;rec[1].y=P[j].y;
                    d=d3;
                }
            }
        }
    }
    return d;
}
int main(){
    point p[10];            //设定点的集合
    int n;
    double minDist;
    cout<<"输入点的个数：\n";      //输入点的个数
    cin>>n;
    cout<<"输入点集:（x,y）\n";
    for(int i=0;i<n;i++)
        cin>>p[i].x>>p[i].y;
    sort(p,p+n,cmp2);      //对输入的点先排序
    point index[2];
    minDist=closestPoint(p,0,n-1,index);
cout<<"最小距离点对为：
("<<index[0].x<<","<<index[0].y<<"),("<<index[1].x<<","<<index[1].y<<")\n";
    cout<<"最小距离为：\n"<<minDist;      //输出点对的最小问题
    return 0;
}

2、循环赛日程安排问题

(1)问题分析：

按照要求，可以将比赛表设计成一个n行n-1列的二维表，其中第i行第j列的元素表示和第i个选手在第j天比赛的选手号。采用分治策略，可将所有参加比赛的选手分成两部分，n=2^{k个选手的比赛日程表就可以通过n=2}（k-1）个选手的的比赛日程表来决定。递归的执行这样的分割，直到只剩下两个选手，比赛日程表的就可以通过这样的分治策略逐步构建。

假设有2^1个选手，其安排如下：

1	2
2	1

假设有2^2个选手，其安排如下：

1	2	3	4
2	1	4	3
3	4	1	2
4	3	2	1

假设有2^3个选手，其安排如下：

1	2	3	4	5	6	7	8
2	1	4	4	6	5	8	7
3	4	1	2	7	8	5	6
4	3	2	1	8	7	6	5
5	6	7	8	1	2	3	4
6	5	8	7	2	1	4	3
7	8	5	6	3	4	1	2
8	7	6	5	4	3	2	1

根据以上的规律，求解过程可以看作四个部分：

\1) 求左上角子表：左上角子表是前2^(k-1)个选手的比赛前半程的比赛日程。

\2) 求左下角子表：左下角子表是剩余的2^{(k-1)个选手的比赛前半程比赛日程。这个子表和左上角子表的对应关系式，对应元素等于左上角子表对应元素加2}(k-1)。

\3) 求右上角子表：等于左下角子表的对应元素。

\4) 求右下角子表：等于左上角子表的对应元素。

(2)算法实现

#include<iostream>
#include<vector>
using namespace std;
void GameTable(vector<vector<int> > &vec){
	if(vec.size() == 0){
		return;
	}
	size_t s = vec.size();
	int k = 0;
	while(s = s >> 1){
		//s = s >> 1;
		k++;
	}
    //初始化
	vec[0][0] = 1;
	vec[0][1] = 2;
	vec[1][0] = 2;
	vec[1][1] = 1;
 
	for(int i = 2; i <= k; i++){
		int length = 0x1 << i;
		int half = length >> 1;
		//左下角的子表中项为左上角子表对应项加half=2^(i-1)
		for(int row = 0; row < half; row++){
			for(int col = 0; col < half; col++){
				vec[row + half][col] = vec[row][col] + half;
			}
		}
		//右上角的子表等于左下角子表
		for(int row = 0; row < half; row++){
			for(int col = 0; col < half; col++){
				vec[row][col + half] = vec[row + half][col];
			}
		}
		//右下角的子表等于左上角子表
		for(int row = 0; row < half; row++){
			for(int col = 0; col < half; col++){
				vec[row + half][col + half] = vec[row][col];
			}
		}
	}
}
 
int main(void){
	cout << "共有2^k个选手参加比赛，输入k（k>0）：" << endl;
	int k;
	do{
		cin >> k;
	}while(k < 0 || k > 31);
 
	int s = 0x1 << k;
	vector<vector<int> > vec(s, vector<int>(s, 0));
 
	GameTable(vec);
 
	for(size_t i = 0; i < vec.size(); i++){
		for(size_t j = 0; j < vec[i].size(); j++){
			cout << vec[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

3、 排序问题

(1) 问题分析：

1. 冒泡排序
   冒泡排序算法的原理如下：
   a) 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
   b) 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
   c) 针对所有的元素重复以上的步骤，除了最后一个。
   d) 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2. 选择排序
   选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

3. 插入排序
   在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。插入排序是稳定的排序方法。

4. 二分插入排序
   二分插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
   二分插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1)。

5. 希尔排序
   先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1（dt<dt-1…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。希尔排序是不稳定的排序。

6. 归并排序
   归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之)。归并排序是稳定排序，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

7. 堆排序
   利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序是不稳定的排序方法，时间复杂度为O(nlog2n)。

8. 快速排序
   a.从数列中挑出一个元素，称为 “基准”（pivot）；
   b.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
   c.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
   d.不稳定，最坏时间复杂度O(n2)，最好、平均时间复杂度为O(nlog2n)。

(2) 算法实现

//	1、冒泡排序 
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void bubble_sort (int A[], int n) {
    for (int j = 0; j < n - 1; j++)         // 每次最大元素就像气泡一样"浮"到数组的最后
    {
        for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移
        {
            if (A[i] > A[i + 1])            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
            {
                Swap(A, i, i + 1);
            }
        }
    }
    printf("\n冒泡排序结果：\n");
    printSort(A,n);
}

//	2、选择排序
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
void selection_sort (int a[], int length) {
	int i,j; //为循环做准备
	int min; //存储每次最小值
	int tmp; //作为临时存储值
	for(i=0;i<length-1;i++){ //进行length-1趟比较即可
		min = i; // 存储每次最小值
		for(j=i+1;j<length;j++){ // 第i次需要与之比较的数据
			if(a[min] > a[j]){
				min = j; // 记录最小值的位置
			}
		}
		tmp = a[i]; // 交换
		a[i] = a[min];
		a[min] = tmp;
	} 
    printf("\n选择排序结果：\n");
    printSort(a,length);
}


//	3、插入排序 
// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void insertion_sort (int a[], int length) {
    int i;
    int j;
    int tmp;  //定义一个临时变量，用于交换数据时存储 
    for(i=1;i<length;i++){  //因为我们要对该待排序列的每一个元素都和前面的已排好序的序列进行插入，所以我们会对序列进行遍历 
        for(j=0;j<i;j++){  //第二层循环主要用于对已排好序的序列进行扫描，和要插入进来的数据进行逐一比较，然后决定插入到哪里 
            if(a[j]>a[i]){//从前往后对已排好序的元素和待插入元素进行大小比较，然后直到找到一个元素比被插入元素大，则交换位置 
                tmp=a[i];
                a[i]=a[j];
                a[j]=tmp;
            }
        }
    }
    printf("\n插入排序结果：\n");
    printSort(a,length);
}

//	4、二分插入排序 
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void InsertionSortDichotomy(int A[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int get = A[i];                    // 右手抓到一张扑克牌
        int left = 0;                    // 拿在左手上的牌总是排序好的，所以可以用二分法
        int right = i - 1;                // 手牌左右边界进行初始化
        while (left <= right)            // 采用二分法定位新牌的位置
        {
            int mid = (left + right) / 2;
            if (A[mid] > get)
                right = mid - 1;
            else
                left = mid + 1;
        }
        for (int j = i - 1; j >= left; j--)    // 将欲插入新牌位置右边的牌整体向右移动一个单位
        {
            A[j + 1] = A[j];
        }
        A[left] = get;                    // 将抓到的牌插入手牌
    }
    printf("\n二分插入排序结果：\n");
    printSort(A,n);
}

//	5、希尔排序 
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
// 最优时间复杂度 ---- O(n)
// 平均时间复杂度 ---- 根据步长序列的不同而不同。
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定

void shell_sort(int a[], int n)
{
    int d, i, j, temp; //d为增量
    for(d = n/2;d >= 1;d = d/2) //增量递减到1使完成排序
    {
        for(i = d; i < n;i++)   //插入排序的一轮
        {
            temp = a[i];
            for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d)
            {
                a[j + d] = a[j];
            }
        a[j + d] = temp;
        }
    }
    
	printf("\n希尔排序结果：\n");
	printSort(a, n);
}

// 	6、归并排序
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(n)
// 稳定性 ------------ 稳定
void Merge(int A[], int left, int mid, int right)// 合并两个已排好序的数组A[left...mid]和A[mid+1...right]
{
    int len = right - left + 1;
    int *temp = new int[len];       // 辅助空间O(n)
    int index = 0;
    int i = left;                   // 前一数组的起始元素
    int j = mid + 1;                // 后一数组的起始元素
    while (i <= mid && j <= right){
        temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];  // 带等号保证归并排序的稳定性
    }
    while (i <= mid){
        temp[index++] = A[i++];
    }
    while (j <= right){
        temp[index++] = A[j++];
    }
    for (int k = 0; k < len; k++){
        A[left++] = temp[k];
    }
}

void MergeSortIteration(int A[], int len)    // 非递归(迭代)实现的归并排序(自底向上)
{
    int left, mid, right;// 子数组索引,前一个为A[left...mid]，后一个子数组为A[mid+1...right]
    for (int i = 1; i < len; i *= 2)        // 子数组的大小i初始为1，每轮翻倍
    {
        left = 0;
        while (left + i < len)              // 后一个子数组存在(需要归并)
        {
            mid = left + i - 1;
            right = mid + i < len ? mid + i : len - 1;// 后一个子数组大小可能不够
            Merge(A, left, mid, right);
            left = right + 1;               // 前一个子数组索引向后移动
        }
    }
    printf("\n归并排序结果：\n");
    printSort(A,len);
}

//	7、堆排序 
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
void heapAdjust(int a[], int i, int nLength)
{
    int nChild;
    int nTemp;
    for (nTemp = a[i]; 2 * i + 1 < nLength; i = nChild)
    {
        // 子结点的位置=2*（父结点位置）+ 1
        nChild = 2 * i + 1;
        // 得到子结点中较大的结点
        if ( nChild < nLength-1 && a[nChild + 1] > a[nChild])
            ++nChild;
        // 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
        if (nTemp < a[nChild])
        {
            a[i] = a[nChild];
            a[nChild]= nTemp;
        }
        else
        // 否则退出循环
            break;
    }
}

void heap_sort(int a[],int length)
{
    int tmp;
    // 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
    //length/2-1是第一个非叶节点，此处"/"为整除
    for (int i = length / 2 - 1; i >= 0; --i)
        heapAdjust(a, i, length);
    // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
    for (int i = length - 1; i > 0; --i)
    {
        // 把第一个元素和当前的最后一个元素交换，
        // 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
      ///  Swap(&a[0], &a[i]);
          tmp = a[i];
          a[i] = a[0];
          a[0] = tmp;
        // 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
        heapAdjust(a, 0, i);
    }
    printf("\n堆排序结果：\n");
    printSort(a,length);
}

//	8、快速排序 
// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)       
// 稳定性 ---------- 不稳定

void quickSort(int a[],int left,int right)
{
	int i=left;
	int j=right;
	int temp=a[left];
	if(left>=right)
		return;
	while(i!=j)
	{
		while(i<j&&a[j]>=temp) 
		j--;
		if(j>i)
			a[i]=a[j];//a[i]已经赋值给temp,所以直接将a[j]赋值给a[i],赋值完之后a[j],有空位
		while(i<j&&a[i]<=temp)
		i++;
		if(i<j)
			a[j]=a[i];
	}
	a[i]=temp;//把基准插入,此时i与j已经相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
	quickSort(a,left,i-1);/*递归左边*/
	quickSort(a,i+1,right);/*递归右边*/

}

4、棋盘覆盖问题

(1) 问题分析

1. 划分问题：将2k∗2k的棋盘划分为2k−1∗2k−1这样的子棋盘4块。
2. 递归求解：递归填充各个格子，填充分为四个情况，在下面会有解释，递归出口为k=0也就是子棋盘方格数为1。
3. 合并问题：不需要合并子问题。

递归填充的四种情况:
如果黑方块在左上子棋盘，则递归填充左上子棋盘；否则填充左上子棋盘的右下角，将右下角看做黑色方块，然后递归填充左上子棋盘。
如果黑方块在右上子棋盘，则递归填充右上子棋盘；否则填充右上子棋盘的左下角，将左下角看做黑色方块，然后递归填充右上子棋盘。
如果黑方块在左下子棋盘，则递归填充左下子棋盘；否则填充左下子棋盘的右上角，将右上角看做黑色方块，然后递归填充左下子棋盘。
如果黑方块在右下子棋盘，则递归填充右下子棋盘；否则填充右下子棋盘的右下角，将左上角看做黑色方块，然后递归填充右下子棋盘。

(2) 算法实现

#include <iostream>
#include <stdio.h>
using namespace std;
int def[101][101]={0};
static int t=0;

void chess(int a,int b,int aa,int bb,int length){//a,b为子棋盘左上角坐标，aa,bb为特殊点坐标，length为子棋盘长度
    if(length==1){
        return;
    }
    t++;
    int tem =t;
    int l=length/2;

    if(aa<a+l && bb<b+l){ //特殊点在左上的正方形中
        chess(a,b,aa,bb,l);
    }
    else{
        def[a+l-1][b+l-1]=tem;
        //cout<<"左上  "<<l<<"  "<<l<<"  "<<def[l][l]<<endl;
        chess(a,b,a+l-1,b+l-1,l);
    }

    if(aa>=a+l && bb<b+l){//左下角的子棋盘
        chess(a+l,b,aa,bb,l);
    }
    else{
        def[a+l][b+l-1]=tem;
        //cout<<"左下  "<<a+l<<" "<<b+l-1<<"  "<<def[a+l-1][b+l]<<endl;
        chess(a+l,b,a+l,b+l-1,l);
    }

    if(aa<a+l && bb>=b+l){//右上角的子棋盘
        chess(a,b+l,aa,bb,l);
    }
    else{
        def[a+l-1][b+l]=tem;
        //cout<<"右上  "<<a+l-1<<"  "<<b+l<<"  "<<def[a+l][b+l-1]<<endl;
        chess(a,b+l,a+l-1,b+l,l);
    }

    if(aa>=a+l && bb>=b+l){
        chess(a+l,b+l,aa,bb,l);
    }
    else{
        def[a+l][b+l]=tem;
        //cout<<"右下  "<<a+l<<"  "<<b+l<<"  "<<def[a+l][b+l]<<endl;
        chess(a+l,b+l,a+l,b+l,l);
    }
}

int main(){
    int n,a,b,aa,bb,length,m;
    //a,b是子棋盘左上角的行号和列号
    //aa,bb是特殊点的行号和列号
    cout<<"请输入1-100之间的整数：";
    cin>>length;
    cout<<"请输入特殊点行号aa:";
    cin>>aa;
    cout<<"请输入特殊点列号bb:";
    cin>>bb;
    a=b=1;
    m=length;

    chess(a,b,aa,bb,length);

    for(int i=1;i<=m;i++){ //输出结果
        for(int j=1;j<=m;j++){
            cout.width(3);
            cout<<def[i][j];
            if(j==m){
                cout<<endl;
            }
        }
    }
}

五、实验结果及算法复杂度分析
1、最近对问题
(1) 蛮力法

蛮力法算法时间复杂度：算法一共要执行 n(n-1)/2次循环，因此算法复杂度为$O(n^2)$
(2) 分治法

分治法算法时间复杂度递归式子是$T(n)=2T(n^2)+O(n)+O(nlogn)$，所以总算法时间复杂度为O(nlogn)。

2、循环赛日程安排问题

复杂度：整个过程就是一个填表的过程，因此其时间、空间复杂度为$O(2^k\ast 2^k)$。

3、排序问题

(1)各排序方法复杂度：

4、棋盘覆盖问题

算法的时间复杂度的递推式为：

实验小结（包括问题和解决方法、心得体会等）

通过本次实验，利用C/C++语言编程实现解决了最近对问题，循环赛日程安排问题，排序算法的比较，棋盘覆盖问题。对于排序问题，为了方便比较各个排序算法的性能，在实现上对随机生成的一个整数数组分别进行八种排序，对排序时间进行比较，以此来简单地比较一下排序算法的排序速度。但是待排序的数组，经一次排序之后，则已经排好序，再进行其它排序的时候，初始数据就是已经排好序的数组序列，最简单的方法是再复制七个同样的待排序序列数组，但是考虑到浪费内存，编程能力以及经验的不足，一直在寻找合适的方法。

本次实验增加了动手编码能力，对算法设计有了更进一步的认识，但是技术上的缺陷，编码能力上存在的短板，在今后的实验中还需要加大练习力度。