写在前面

由于本课程是第一次面向本科专业开设，我身为第一届应考生，承担的考试压力要大许多。一是因为没有历年的真题供参考，另一方面是自己也并没有把太多心思放在这门课程的学习上。好在老师给出了复习提纲和样卷。那么我们就按照复习提纲和样卷来做一个全面的复习。

2021考题预测

1.插入算法

2.Master定理

3.DFS/BFS

4.回溯方法解决子集树/排列树的搜索问题

5.分支界限方法解决旅行商问题(较难暂时放弃)

6.Las解决0/1背包问题

7.动态规划方法解决多段图问题

8.贪心算法求解装载问题

9.归并排序/快速排序/二分排序

10.回溯方法解决最大团问题/子集和问题

2021期末预测题目全解

必须背下来的算法：

DFS

1
2
3
4
5
6
7
8
9
10
11
12
void DFS(Matrix<bool> &G,int v,vector<bool> visited,Func Visit){
    int n = G.Rows();//求出顶点数
    Visit(v);//访问根
    Visited(v)=1;//已访问
    
    for(int w =0;w<n;++w){
        if(not Visited[w] and G(v,w)){
            DFS(G,w,Visited,Visit);
        }
    }
    
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void BFS(Matrix <bool> &G,int v,vector<bool> Visited,Func Visit){
    int n = G.Rows();
    queue <int> Q;
    //根节点
    Visit(v);
    Visited[v]=1;
    Q.push(v);
    
    while(not empty(Q)){
        v = Q.front();
        Q.pop();
        for(int w=0;w<n;++w){
        	if(not Visited[w] and G(v,w)==1){
            	Visit(w);
            	Visited[w]=1;
                push(w);
        }
    }
    }
}

回溯方法解决子集树搜索问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <dummy.h>
void B_SubSet(int n){
    vector<int> X(n);//解向量
    function <void(int)> SubSet = [&](int){
        if(t>=n)
            Print X;
        else{
            if(legal(t)){
                X[t]=1;
                SubSet(t+1);
            }
            if(bound(t)){
                X[t]=0;
                SubSet(t+1);
            }
        }
    }
}

回溯方法解决排列数搜索问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <dummy.h>
void B_Perm(int n){
    vector <int> X(n);
    iota(X);//解向量需要初始化为自然排列
    function<void(int)>Perm=[&](int t){
        if(t>=n-1)
            cout<<X<<endl;
        else{
            for(int i =t;i<n;++i){
                swap(X[t],X[i]);
                if(legal(t) and bound(t))
                    Perm(t+1);
                swap(X[t],X[i]);
            }
        }
    }
}

Las解决0/1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <LasVegas.h>
bool Knap(vector<double> &V,vector<double> &W,double c,double t,vector<bool> &X){
    //参数说明：效益数组V。重量数组W 背包容量c
    static mt19937g;
    int n = min(size(V),size(W));
    double fv = 0,fw = 0;
    for(int i =0;i<n;++i){
        X[i]=g()%2;
        fv+=V[i]*X[i];
        fw+=W[i]*X[i];
        if(fw>c)
            return false;
    }
    return fv>=t;
}

贪心算法求解装载问题

1
2
3
4
5
6
7
8
9
10
11
auto Load(vector<double> &W,double M){
    int n =size(W);
    sort(W);
    vector<bool>X(n,0);
    double rc = M;
    for(int i=0;i<n and W[i]<=rc;++i){
        X[i] = 1;
        rc- = W[i];
    return X;
    }
}

回溯方法解决最大团问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Clique(t,cn)//用 cn 记录当前团顶点数
{
    if(t>=n and cn >fn){ // 答案 ( 更优 )
        fn = cn;
        BX = X;
    }else if(t<n){
        if(Connected(G,X,t))// 可行 ( 当前成团 )
        {
            X[t]=1;
            Clique(t+1,cn+1);
        }
        if(cn+n-t>fn){// 界限 ( 可能有更大的团 )
            X[t]=0;
            Clique(t+1,cn);
        }
    }
}

回溯方法解决子集和问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SetSum(t,s,r){
    if(not Y.empty())
        return; // 已经记录答案 , 不再继续寻找
     // 已经找到答案
    if(s==M)// s 为已选整数的和 ( 和 ), r 为待处理的所有整数的和 ( 余额 )
        print X;
    else if(t<n){
        if(s+W[t]<=M){ // 可行 , t+1 号数 , 和增加 , 余额减少
            X[t]=1;
            SetSum(t+1,s+W[t],r-W[t+1]);
        }
        if(s+r-W[t]>=M){// 界限 , t+1 号数 , 和不变 , 余额减少
            X[t] = 0;
            SetSum(t+1,s,r-w[t+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
31
32
33
34
35
#include <algorithm.h>
template<class T>
//合并两个有序组
void Merge(T X[],int low,int m,int up){
    T W[up-low];//一个缓冲区
    int i = low,j = m,k=0;//左指针，右指针，结果游标k
    for(;i<m and j<up;k++)
    {
        if(X[i]<X[j])
        {
            W[k] = X[i];
            i++;
        }else 
        {
            W[k] = X[j];
            j++;
        }
    }
    for(;i<m;i++){//剩余的左侧
        W[k] = X[i];
        k++;
    }
    for(;j<up;j++){//剩余的右侧
        W[k] = X[j];
        j++;
    }
    
void MergeSort(T X[],int low,int up){//归并排序
    if(up-low<=1)
        return;
    int m =(low+up)/2;//计算分割点
    MergeSort(X,low,m);//左排序
    Mergesort(X,m,up);//右排序
    Merge(X,low,m,up);//合并
}

快速排序

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
#include <algorithm.h>
//以一个数为基准,将序列中的其他数往它两边“扔“，即是分治思想
//首先要写一个划分程序
//非常漂亮的算法，省去了左右指针
template<class T> // 划分 , 待划分区间为 [low, up), 左侧存放小元素
int Partition(T X[], int low, int up){
    //我们从尾部开始划分,不用移动元素
    int key = up-1;
    int m = low;//划分位置
    for(int i =low;i<up;i++){
        if(X[i]<X[key]){//小元素调整到左侧
            swap(X[i],X[m]);
            m++;//左侧元素增加，划分位置后移
        }
    }
    swap(X[key],X[m]);//将划分元素调整到划分位置
    return m;//返回划分位置
}

void QuickSort(T X[],int low,int up){//快排主程序
    if(up-low<=1)
        return;	
    //要标志划分位置m
    int m =Partition(X,low,up);
    QuickSort(X,low,m);//左排序
    QuickSort(X,m+1,up);//右排序
}

二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm.h>
template<class T1,class T2>
int search(T x[],int n,const T2 &v){
    //分治之思想，把元素丢到两边然后重复
    int low = 0;
    int up = n;
    while(low < up){
        int m =(low+up)/2;
        if(X[v]<X[m]){
            up = m;
        }
        if(X[v]>X[m])
            low = m+1；
        if(X[v]==X[m])
            return m;
    }
        return -1;
}

插入算法

1
2
3
4
5
6
7
8
9
10
11
12
template <class T,class T2>
int insert(T X[],int m,const T2 &V){
    int p;
    for(p = m-1;p>0 and X[p]>v;--p)
        if(X[p]==v)
            return m;
    for(int i=m-1;i>=p;--i){
        X[i+1]=X[i];
    X[p+1] = v;
    return m+1;
    }
}

图的遍历

二叉树的遍历

二叉树的C++表示

1
2
3
4
5
6
7
#include <algorithm.h>
template<class T>
struct BtNode//二叉树结点
{
    T data;
    BtNode *left = 0,*right = 0;//左子树，右子树
};

二叉树的先根次序遍历

1
2
3
4
5
6
7
8
9
template<class T,class Func>//先根遍历
void PreOrder(BtNode<T> *x ,Func Visit)
{
    if(x==0)
        return;
    Visit(x)//访问根
    PreOrder(x->left,Visit);//遍历左子树
    PreOrder(x->right,Visit);//遍历右子树
}

中根遍历与后根遍历只是调换了顺序，故不再赘述。

二叉树的按层次遍历

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
template<class T,class Func>
void LevelOrder(BtNode<T> *x,Func Visit)
{
    queue<BtNode<T> *> Q;
    if(x!=0){
        Visit(x);
        Q.push(x);//访问根并将根加入队列
    }
 	while(not empty(Q)){
        x = Q.front();
        Q.pop();
        //访问x的左右儿子并将左右儿子加入队列
        auto left = x->left;
        auto right = x->right;
        if(left!=0)
        {
            Visit(left)
            Q.push(left);
        }
        if(right!=0）{
            Visit(right)
            Q.push(right);
        }
    }
}

一般树的遍历

树的C++表示

1
2
3
4
5
6
#include <algorithm.h>
template<class T>//树节点类
struct TreeNode{
    T data;
    TreeNode *first = 0,next = 0;//第一棵子树，下一棵树(兄弟)
}

树的先根遍历

1
2
3
4
5
6
7
8
9
10
template<class T,class Func>
void PreOrder(TreeNode<T> *x,Func Visit){
    if(x==0)
        return;
    Visit(x);//访问根
    PreOrder(x->first,Visit);//遍历第一棵子树
    for(x=x->first;x!=0;x=x->next){
        PreOrder(x->next,Visit);//遍历其余子树
    }
}

树的中根遍历只是与先根遍历的顺序不同，不再赘述。

树的后根遍历

1
2
3
4
5
6
7
8
9
10
11
template<class T,class Func>
void PostOrder(TreeNode<T> *x,Func Visit){
    if(x==0)
        return;
    auto t = x->first;
    PostOrder(t,Visit);
    for(;t!=0;t=t->next){
        PostOrder(t>next,Visit);
    Visit(x);
    }
}

树的按层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class T,class Func>
void LevelOrder(TreeNode<T> *x,Func Visit){
    queue<TreeNode<T> *> Q;
    if(x!=0){
        Visit(x);
        Q.push(x);//访问根并将根加入队列
    }
    while(not empty(Q)){
        x = Q.front();
        Q.pop();
        //访问x的所有儿子并将所有儿子加入队列
        for(x=x->first;x!=0;x=x->next){
            Visit(x);
            Q.push(x);
        }
    }
}

连通图的两种遍历方法

宽度优先搜索BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm.h>
template<class Fun>
void BFS(Matrix<bool> &G,int v,vector<bool> &Visited,Fun Visit){
    //参数：邻接矩阵，开始顶点，访问标记(已经初始化为0），访问函数
    int n =G.Rows();//获取矩阵的行数,即顶点数
    queue<int> Q;//创建空队列
    Visit(v);
    Visited[v] = 1;
    Q.push(v);//访问v并加入队列
    while(not empty(Q)){
        v = Q.front();
        Q.pop();//取出队首元素v
        for(int w=0;w<n;++w){//遍历所有顶点，康康有无有与自己相连的边
            if(not Visited[w] and G(v,w)==1){
                //w与v相邻且未访问
                Visit(w);
                Visited[w]=1;
                Q.push(w);//访问w，入队
            }
        }
    }
}

深度优先搜索DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <algorithm.h>
template<class Fun>//搜索一个连通分支
void DFS(Matrix<bool> &G,int v,vector<bool> &Visited,Fun Visit){
    //参数：邻接矩阵，开始顶点，访问标记，访问函数
    int n =G.Rows();
    Visit(v);
    Visited[v]=1;
    for(int w =0;w<n;++w){
        if(not Visited[w] and G(v,w)==1){
            //w与v相邻且未访问
            DFS(G，w，Visited，Visit);//访问w
        }
    }
}

分治方法

折半搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <algorithm.h>
template<class T1,class T2>
int search(T x[],int n,const T2 &v){
    //在升序数组X中搜索v所在的位置
    int low = 0;
    int up = n;
    while(low<up){
        int m = (low+up)/2;
        if(v==X[m])
            reuturn m;
        else if(v<X[m])
            up=m;//左侧继续搜索
        else
            low = m+1;//右侧继续搜索
    }
    return -1;//-1表示未找到v
}

归并排序

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
31
32
33
34
35
36
#include <algorithm.h>
template<class T>
//合并两个有序组
void Merge(T X[],int low,int m,int up){
    T W[up-low];//缓冲区
    int i=low ,j=m,k=0;//左侧游标i，右侧游标j，结果游标k；
    for(;i<m and j<up;++k){//当两侧都未取尽时
        if(X[i]<X[j])//左侧元素较小
        {
            W[k] = X[i];
            ++i;
        }else{//右侧元素较小
            W[k]=X[j];
            ++j;
        }
        for(;i<m;++k){//左侧剩余部分添加到W
            W[k]=X[i];
            ++i;
        }
        for(;j<up;++k){//右侧剩余部分添加到W
            W[k]=X[j];
            ++j;
        }
    }
}
//这个算法是有错的，请自行鉴别

void MergeSort(T X[],int low,int up){
    if(up-low<=1)
        return;//最多一个元素
    int m = (low+up)/2;//分割点
    MergeSort(X,low,m);//左侧排序
    MergeSort(X,m,up);//右侧排序
    Merge(X,low,m,up);//合并
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#pragma once
#include <algorithm.h>

template<class T> // 划分 , 待划分区间为 [low, up), 左侧存放小元素
int Partition(T X[], int low, int up)
{
    int key = up - 1, m = low; // 划分元素选用尾部元素 , 用 m 记录划分位置
	for(int i = low; i < key; ++i) // 小元素调整到左侧 ( 划分元素不参与比较 )
	if(X[i] < X[key])
		swap(X[i], X[m]), ++m; // 左侧元素增加 , 划分位置后移
	swap(X[key], X[m]); // 将划分元素调整到划分位置
	return m; // 返回划分位置
} /

void QuickSort(T X[],int low,int up){
	if(low>=up)
        return;//没有元素
    int m =Partition(X,up,low);//划分位置
    QuickSort(X,low,m);//左侧排序
    QuickSort(X,m+1,up);//右侧排序
}

贪心方法

装载问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <algorithm.h>
auto Load(vector<double> &W,double M){
    //参数：重量数组，货船容量
    int n = size(W);//货箱个数
    sort(W);//重量数组W升序排列
    vector<bool> X(n,0);//解向量初始化为0
    double rc = M;//背包剩余容量
    for(int i=0;i<n and W[i]<=rc;++i){
        X[i] = 1;
        rc- = W[i];
        //装入货箱i
    }
    return X;
}

背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
auto Knap(vector<double> &V,vector<double> &W,double M){
    //参数：价值数组，重量数组，背包容量
    int n = min(size(V),size(W));//物品数
    Sort(V,W);//将物品按单价降序排列；
    vector<double> X(n,0);//解向量初始化为零
    double rc = M;//背包剩余容量
    int t;//当前物品
    for(t = 0;t<n and W[t]<=rc;++t){
        X[t] = 1;
        rc - =W[t];//可完整装包的物品完整装包
     }
    if(t<n){
         X[t]=rc/W[t];//不能完整装包的物品部分装包
     return X;
    }
}

活动安排问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <algorithm.h>

auto Action(vector<double> &S,vector<double> &F){
    //参数：开始时间数组，结束时间数组
    int n = min(size(S),sieze(F));
    Sort(S,F);//将活动按照结束时间升序排列
    vector<bool> X(n,0);//解向量初始化为零
    X[0] = 1;//将活动0加入解中
    for(int i =1,j=0;i<n;++i){
        if(S[i]>=F[j]){
            X[i] = 1;
            j = i;//将活动i加入解中
        }
    }
    return X;
}

最小生成树问题

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
bool Prim(const Matrix<double> &G,int v,vector<int> &prev){
    int n = G.Rows();//G是加权图，顶点数为n
    prev.assign(n,v);//prev用于保存各顶点的父亲，初始根为v
    vector<bool> S(n,false);//S标志顶点是否已选，初始为0
    S[v] = true;//选取v
    for(int i =0;i<n-1;++i){
        //寻找已选项点到未选项点权值最小的顶点
        double min = inf;//min初始为无穷大
        for(int w=0;w<n;++w){
            if(not S[w] and G(prev[w],w)<min)
            {
                min = G(prev[w],w);
                v=w;
            }
        }
        if(isinf(min))
            return false;//不连通
        S[v] = true;//选取v
        for(int w = 0;w<n;++w){//更新未选顶点父亲
            if(not S[w] and G(v,w)<G(prev[w],w))
                prev[w] = v;
        }
    }
    return true;//连通
}

动态规划方法

矩阵连乘问题的动态规划方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
auto MatrixChain(int r[],int n){
    //动态规划方法
    Matrix<int> c(n,n,0);//c(i,j)初始为0
    Matrix<int> kay(n,n);//用于构造最优次序
    for(int i =n-2;i>=0;--i){
        //计算c(i,j)和kay(i,j).其中j>i
        for(int j = i+1;j<n;++j){
            //从k = i开始计算最小项，并更新kay
            c(i,j) = (int)inf;
            for(int k =i;k<j;++k){
                int t = c(i,k)+c(k+1,j)+r[i]*r[k+1]*r[j+1];
                if(t<c(i,j)){
                    c(i,j) = t;
                    kay(i,j) = k;//找到更小项
                }
            }
        }
    }
}

多段图问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
auto MultiGraph(Matrix<double> &G){
    //邻接矩阵G，顶点按段序统一编号
    int n = G.Rows();
    t = n-1;//顶点数，汇点
    vector<double> C(n,0);//C[j]是j到汇点的最小成本，初始为0
    vector<int> Next(n);//Next[j]是j到汇点的最短路径中j的后继顶点
    for(int j =t-1;j>=0;--j){
        //从j的后一个阶段中选择顶点r，使G(j,r)+C[r]最小
        int r = j+1;
        for(int i =r;i<n;++i){
            if(G(i,j)+C[i]<G(j,r)+C[r])
                r = i;
            C[j] = G(j,r)+C[r];
            Next[j] = r;
        }
    }
 	vector<int> X(m);//X[i]是最短路径中第i阶段选取的顶点
    X[0] = 0;
    for(int i = 0;i<m-1;++i){
        X[i+1] = Next[X[i]];
    }
    return X;
}

回溯方法

子集和问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
SetSum(t,s,r){
    if(s==M)
        print X;
    else if(t<n){
        if(s+W[t]<=M){
            X[t] = 1;
            SetSum(t+1,s+W[t],r-W[t+1]);
              }
         if(s+r>=M){
             X[t] = 0;
             SetSum(t+1,s,r-W[t+1]);
        }
    }
}

旅行商问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm.h>
auto TSP(Matrix<double>&G){
    int n = G.Rows();//顶点个数
    vector<int> X(n),BX;//到当前结点的路经，最优路径
    iota(X);//解向量X需初始化为自然排列
    double BC = inf;//最优耗费
    function<void(int,double)> TSP=[&](int t,double C){
        auto LC = C+G(X[t-1],X[t])+G(X[t],0);//当前回路耗费
        if(t>=n-1 and LC<BC){
            BC = LC;
            BX = X;//答案，更优
        }else if(t<n-1){
            for(int i = t;i<n;++i){
                swap(X[t],X[i]);
                auto CC = C +G(X[t-1],X[t]);//当前路经耗费
                if(CC<BC){
                    TSP(t+1,CC);//可行(当前路径可能更优)
                }
                swap(X[t],X[i]);
            }
        }
    }
}

最大团问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function Clique(t,cn)
{
    if(t>=n and cn>fn)
    {
        fn = cn;
        BX = X;
    }else if(t<n){
        if(Connected(G,X,t)){
            X[t] = 1;
            Clique(t+1,cn+1);
        }
        if(cn+n-t>fn){
            X[t]=0;
            Clique(t+1,cn);
        }
    }
}

概率方法

0/1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <LasVegas.h>
bool Knap(vector<double> &V,vector<double> &W,double c,double t,vector<bool> &X){
    //参数：效益数组V 重量数组W 背包容量c
    static mt19937g;//随机数产生器
    int n =min(size(V),size(W));
    double fv = 0;//最后效益
    double fw = 0;//最后重量
    for(int i = 0;i<n;++i){//随即决定物品i的选取
        X[i] = g()%2;
        fv+=V[i]*X[i];
        fw+=W[i]*X[i];
        if(fw>c)
            return false;
    }
    return fv>=t;
}