算法分析与设计期末考试复习（更新ing）

重点内容：

绪论：
简单的递推方程求解 1.19(1)(2) 、教材例题
多个函数按照阶的大小排序 1.18

分治法：
分治法解决芯片测试问题
计算a^n的复杂度为logn的算法（快速幂）
分治法解决平面最近点对问题（增加预处理）
锦标赛算法求第二大数的步骤（链表）
分治法S中第k小元素的归约过程（m*）

动态规划：
最长公共子序列问题：蛮力法和动态规划的递归方程或递推关系、动态规划的伪码(填空)、优化函数和标记函数(填空)
矩阵链的乘法问题：蛮力法和动态规划的递归方程或递推关系、动态规划的伪码(填空)、备忘录和标记函数(填空)
最大子段和

贪心法：4.3 4.4 4.16 4.21
主要设计思想、伪码、复杂度、实例求解
贪心法：活动安排问题问题实例求解、最小延迟调度问题实例求解

回溯：
(填空)回溯算法的主要设计步骤，用回溯算法解决图的m着色问题、货郎问题(TSP)
(填空)分支界限的基本下，用分支界限算法解决最大团问题、背包问题

动态规划：

最长公共子序列问题：

蛮力法的时间复杂度O(n* $2^{m}$ )

#include <iostream>
#include <string>
using namespace std;

string lcs_bruteforce(const string& X, const string& Y) {
    int m = X.length();
    int n = Y.length();
    if (m == 0 || n == 0) {
        return "";
    } else if (X[m-1] == Y[n-1]) {
        return lcs_bruteforce(X.substr(0, m-1), Y.substr(0, n-1)) + X[m-1];
    } else {
        string lcs1 = lcs_bruteforce(X.substr(0, m-1), Y);
        string lcs2 = lcs_bruteforce(X, Y.substr(0, n-1));
        if (lcs1.length() > lcs2.length()) {
            return lcs1;
        } else {
            return lcs2;
        }
    }
}

int main() {
    string X = "ABCBDAB";
    string Y = "BDCAB";
    string lcs = lcs_bruteforce(X, Y);
    cout << "The longest common subsequence is: " << lcs << endl;
    return 0;
}

参考代码

动态规划的递归方程或递推关系

✨代码实现：

【算法设计与分析MOOC-青岛大学-张公敬教授】http:// https://www.bilibili.com/video/BV18X4y1k74c/?p=27&share_source=copy_web&vd_source=7ffbd7feaeedb3d59fb21e59435a53d8

动态规划的伪码(填空)

优化函数(填空)

X = 【1, 2, 3】, Y = 【1, 3】按照下图关系推

标记函数(填空)

b数组用来设立标记，算法结束后可以利用这些标记追踪最优解。

例子：

怎么推？
c[i][j]矩阵:

按照信息表即可推出b矩阵（数组）

如何追踪解？
b[i][j]为1时，对应X、Y序列第i行，j列中的元素

矩阵链的乘法问题：

蛮力法的时间复杂度 $\Omega$ ( $2^{2n}/{n^{\frac{3}{2}}}$ )

动态规划的递归方程或递推关系

动态规划的伪码(填空)

递归实现：

时间复杂度

迭代实现：

备忘录(填空)

看着递推方程来填空

自己复制代码，断点调试设置变量查看吧

#include <bits/stdc++.h>
using namespace std;
//输入：矩阵链Ai…j的输入为向量P=<Pi-1,Pi,…,Pj>，其中：1<=i<=j<=n.
//输出：计算Ai…j的所需最小乘法运算次数m[i,j]和最后一次运算位置s[i,j]。
const int N = 101;
int m[N][N], s[N][N];
int a[] = {30, 35, 15, 5, 10, 20};

void MatrixChain(int a[N], int n)
{
	for(int i=1; i<=n; i++)
		m[i][i] = 0;
		
	for(int r=2; r<=n; r++)
	{
		for(int i=1; i<= n-r+1; i++)
		{
			int j = i+r-1;
			m[i][j] = m[i+1][j] + a[i-1]*a[i]*a[j];
			s[i][j] = i;
			
			for(int k=i; k<=j-1; k++)
			{
				int t = m[i][k] + m[k+1][j] + a[i-1]*a[k]*a[j];
				if(t < m[i][j])
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

int main()
{
 	MatrixChain(a, 6);
 	cout << "The number of least multiplication operations:" << endl;
 	cout << m[1][5] << endl;
 	cout << "Position of the last operation:" << endl;
 	cout << s[1][5] << endl;
 	cout << "array s:" << endl;
 	for(int i=1; i<=5; i++)
 	{
 		for(int j=1; j<=5; j++)
 		{
 			cout << s[i][j] << ' ';
		}
		cout << endl;
	 }
 	return 0;
}