算法分析与设计——实验1： 递归与分治

实验一  递归与分治

一、实验目的

        1、理解分治算法的概念和基本要素；

        2、理解递归的概念；

        3、掌握设计有效算法的分治策略。

二、实验内容和要求

实验要求：通过上机实验进行算法实现，保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告和程序文件。

实验内容：

1、归并排序问题：对n个元素组成的序列进行排序。

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

2、使用二分搜索算法查找任意n个有序数列中的指定元素。至少使用两种方法进行编程。

三、算法思想分析

（1）实验内容一（归并排序算法思想）

归并排序包括分解数组、递归求解、合并排序三个步骤。

• 分解原问题：将待排序的数组序列A[1,n] 分解成两个子序列A[1,|n/2|]和A[|n/2|+1,n]，每个子序列包括n/2个元素；
• 解决子问题：递归解决子问题，对每个子序列分别调用归并排序MergeSort,得到两个有序的子数组；
• 合并问题解：将两个有序子序列合并为一个有序数组。

（2）实验内容二（二分搜索算法思想）

采用分治策略，其基本思想为：将n个元素分成个数大致相同的两半，取有序数列的中点位置a[n/2]与需查找的x作比较，如果x=a[n/2]则找到x，算法终止；如果x<a[n/2]，则在数组a的左半区间继续搜索x；如果x>a[n/2]，则在数组a的右半区间继续搜索x。直到找到相同元素，或者查找范围为空。需要特别注意的是，二分搜索要求待查数列必须采用顺序存储结构，而且元素必须有序排列。

二分搜索算法的优点是比较次数少，查找速度快，平均性能好；缺点是要求待查的数列必须为有序数列，且插入删除困难。

四、程序代码

（1）实验内容一

#include <bits/stdc++.h>
using namespace std;

float temp[10000];

//归并
void mergeArrays(float ar[], int left, int right)
{
    int mid= (left + right) / 2;
    int i=left;  int j= mid + 1;
    int t=left;
    while(i<=mid && j <= right)
    {
        if(ar[i] < ar[j])
        {
            temp[t++]=ar[i];
            i++;
        }
        else
        {
            temp[t++]=ar[j];
            j++;
        }
    }

    while(i <= mid)
    {
        temp[t++]=ar[i];
        i++;
    }
    while(j <= right)
    {
        temp[t++]=ar[j];
        j++;
    }

    for(int i=left; i <= right; i++) ar[i]=temp[i];
}

//归并排序
void mergeSort(float ar[],int left,int right)
{
    int mid=(left+right)/2;

    if(left>=right) return ;

    mergeSort(ar,left,mid);        //递归排序前一半数组
    mergeSort(ar,mid+1,right);   //递归排序后一半数组
    mergeArrays(ar,left,right);        //合并
}

int main()
{
    int n;
    float ar[10000];

    cout<<"请输入要排序的元素个数: "<<endl;
    while(~scanf("%d",&n))
    {
        cout<<"请输入要排序的元素: "<<endl;
        for(int i=0;i<n;i++) cin>>ar[i];

        mergeSort(ar,0,n-1);         //归并排序

        cout<<"从小到大排序后结果："<<endl;
        for(int i=0;i<n;i++) cout<<ar[i]<<" ";
        cout<<endl;
        cout<<"请输入要排序的元素个数: "<<endl;
    }
        return 0;
}

（2）实验内容二

#include <bits/stdc++.h>
using namespace std;

int a[1000];

//方法一:
int BinarySearch1 (int a[], int left, int right, int x)
{
    int mid;
    mid = (left + right) / 2;
    if(left < right) {
        if (x == a[mid])  return mid;
        else if (x < a[mid]) {
            return BinarySearch1(a, left, mid - 1, x);     //递归调用前一半数组
        }
        else {
            return BinarySearch1(a, mid + 1, right, x);     //递归调用后一半数组
        }
    }
    return 0;
}

//方法二:
int BinarySearch2 (int a[], int left, int right, int x)
{
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (x == a[mid]) return mid;
        else if (x < a[mid]){
            right = mid - 1;  //递归调用前一半数组
        }
        else{
            left = mid + 1;   //递归调用后一半数组
        }
    }
    return 0;
}

int main()
{
    int n, x;

    cout<<"请输入有序数列元素个数: "<<endl;
    cin >> n;
    cout<< "请输入要查找的元素: " <<endl;
    cin >> x;

    cout<< "请输入有序数列（从小到大）: " <<endl;
    for (int i = 0; i < n; i++)  cin >> a[i];

    cout<< "方法一查找结果: "<<endl;
    int flag1 = BinarySearch1(a, 0, n-1 , x);
    if (flag1){
        cout<<"要查找的元素在数组的位置为: " << flag1 + 1 <<endl;
    }
    else{
        cout<<"没有找到！" <<endl;
    }

    cout<< "方法二查找结果: " <<endl;
    int flag2 = BinarySearch2(a, 0 , n-1 , x);
    if (flag2){
        cout<<"要查找的元素在数组的位置为: " << flag1 + 1 <<endl;
    }
    else{
        cout<<"没有找到！" <<endl;
    }
    return 0;
}

五、结果运行与分析

（1）实验内容一

运行结果：

分析：

运行结果正确。

时间复杂度O(nlogn)：归并排序主要分为拆分和对有序数组进行排序，拆分操作的时间复杂度为logn，排序的复杂度为n，所以归并排序的时间复杂度为O(nlogn)；

空间复杂度O(n)：临时数组和递归时压如栈的数据占用的空间为n + logn，所以空间复杂度为O(n)。

（2）实验内容一

运行结果：

分析：

运行结果正确。

每执行依次算法的while循环，待搜索数组的大小减小一半。在最坏情况下，while循环被只需O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的时间复杂度为O(logn)。

六、心得与体会

通过本次实验，我理解了分治算法的概念和基本要素，对递归的概念有了更深的理解，分治法在每一层递归上有三个步骤：分解原问题、解决子问题和合并问题解。同时，通过设计有效算法（归并排序和二分搜索）的分治策略，计算其时间和空间复杂度，学习不同方式的二分算法，增进了我对分治算法的理解。