本次算法期中考内容如下

五道选择题，四道简答题，四道算法设计题

时长为一个半小时

下面先进行复习，之后对复习内容进行分类整理。

选择题

Q1：什么是算法？

C1：算法是由若干条指令组成的有穷序列，它满足4条性质

（1）输入

（2）输出

（3）确定性

（4）有限性

Q2：程序和算法的区别是什么？

C2：程序是算法用某种程序设计语言的具体实现，算法具有有限性，而程序可以没有。

Q3：分治法和动态规划的区别是什么？

C3：（1）分治是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立并且与原问题相同，通过递归地求解这些子问题，然后再将各个子问题的解合并，就可实现对原问题的求解。

Q4：分治法的作用是什么？

C4：分治法通过把问题化为较小的问题来解决原问题，从而简化或减少了原问题的复杂度。

Q5：在快速排序算法中引入随机过程的主要目的是什么？

C5：改善了确定性算法最坏情形下的平均运行时间。

引入随机过程，在每次划分过程中，主元素是随机选取的，在平均情况下，对输入数组的划分是比较均衡的，从而使算法的期望运行时间为O（nlogn）

关于Tn

简答题

渐进式各种符号的认识与互化

自己的理解：

例一：

答：（1）fn=1（gn）

（2）fn=2（gn）

（3）fn=2（gn）

注意：log为底的对数之间等阶，但a^n之间是O的关系

递归函数的优缺点

递归函数的两个要素：边界条件和递归方程

优点：结构清晰，可读性强，容易用数学归纳法证明算法的正确性，设计算法十分便捷。

缺点：运行效率较低，耗费的计算时间和占用的存储空间都比非递归算法要多。

分治算法的特点

（1）该问题的规模缩小到一定的程度就可以容易的解决

（2）该问题可以分解为若干个规模较小的相同问题

（3）分解出的子问题的解可以合并为原问题的解

（4）分解出的各个子问题是相互独立的

动态规划算法的一般步骤

（1）找出最优解的性质，并刻画其结构特征

最优子结构性质：问题的最优解包含了其子问题的最优解

（2）递归地定义最优值

（3）以自底向上的方式计算出最优值

（4）根据最优值构造最优解

代码填空题

二分搜索问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int BinarySearch(int a[], int x,int left,int right)
{
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(x==a[mid])
            return mid;
        if(x<a[mid])
            right=mid-1;
        else
            left=mid+1;
    }
    return -1;
}

归并排序问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void mergesort(int a[],int left,int right)
{
    if(left<right)
    {
        int mid=(left+right)/2;
        mergesort(a,left,mid);
        mergesort(a,mid+1,right);
        merge(a,b,left,mid,right);
    }
}
void merge(int a[],int b[],int left,int mid,int right)
{
    int i=left;
    int j=mid+1;
    int t=0;
    while(i<=mid && j<=right)
    {
        if(a[i]<=a[j])
            b[t++]=a[i++];
        else
            b[t++]=a[j++];
    }
    while(i<=mid)
        temp[t++]=a[i++];
    while(j<=right)
        temp[t++]=a[j++];
    t=0;
    while(left<=right)
        a[left++]=temp[t++];
}

快速排序问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void quicksort(int a[],int low,int high)
{
    if(low<high)
    {
        int pivot=Paritition(a,low,high);
        quicksort(a,low,pivot-1);
        quicksort(a,pivot+1,high);
    }
}
int Paritition(int a[],int low ,int high)
{
    int pivot=a[low];
    while(low<high)
    {
        while(low<high&&a[high]>=pivot)
            --high;
        a[low]=a[high];
        while(low<high &&a[low]<=pivot)
            ++low;
        a[high]=a[low];
    }
    a[low]=pivot;
    return low;
}

算法设计题

线性时间选择问题

题目：给定线性续集中的n个元素和一个整数k，要求找出这n个元素中第k小的元素

k=1时，找最小元素

k=n时，找最大元素

k=（n+1）/2时，找中位数

对输入数组进行递归划分.

例：请在不排序的情况下，用分治法解最大最小问题，写出算法代码，并解释A=（48，12，61，3，5，19，32，7）中求最大最小的过程。

1
2
3
4
5
6
7
int part(int a[],int left,int right)
{
    if(left==right)
        return a[left];
    int mid = (left + right) / 2;
    return min(part(a, left, mid), part(a, mid + 1, right));
}

求x在数组出现次数问题

题目：给定n个整数的数组A[1,…,n]，以及一个整数x，设计一个分治算法，求出x在数组A中的出现的次数，并分析所设计算法的时间复杂度。

答：本题采用分治算法

（1）先将问题划分为大小近似相等的两个子问题

（2）对子问题递归调用该算法进行处理，递归出口为子问题只含一个元素，若该元素等于x，则返回x的出现次数1，若不等于则返回0.

（3）原问题的结果为这两个子问题所得结果之和。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int countX(int A[],int x,int p,int r)
{
    if(p==r)
    {
        if(A[p]==x)
            return 1;
        else
            return 0;
    }
    else
    {
        int q=(p+r)/2;
        return (countX(A,p,q,x)+countX(A,q+1,r,x));
    }
}

时间复杂度：O(n^2)

最长单调递增子序列

题目：分别从O（n方）和O（nlogn）两方面设计算法

On方

1
2
3
4
int LISdyna()
{
    
}

Onlogn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int LIS()
{
    b[1]=a[0];
    for(int i=1,k=1;i<n;++i)
    {
        if(a[i]>=b[k])
            b[++k]=a[i];
        else
            b[binary(i,k)]=a[i];
    }
    return k;
}
int binary(int i,int k)
{
    if(a[i]<b[1])
        return 1;
    for(int h=1,j=k;h!=j-1;)
    {
        if(b[k=(h+j)/2]<=a[i])
            h=k;
        else
            j=k;
    }
    return j;
}