第一章 算法概述
算法的定义：算法是解决问题的过程
算法的三要素：操作，控制结构，数据结构
-
算法的五大基本特征：
- 有穷性
- 确定性
- 可行性
- 零个或多个输入
- 一个或多个输出
算法的复杂性：时间复杂度&空间复杂度
时间复杂度的衡量方法：事前分析估算法，事后分析法
-
常数级-阶乘级，至顶向下复杂度越来越大
IMG_20211221_234601.jpg 大O表示法中的大O是复杂度的上界
第二章 迭代与蛮力
迭代法的定义：是一种用旧值推出新值的算法
-
迭代法的实现步骤：
- 确定迭代模型
- 确定迭代关系式
- 对迭代过程进行控制
-
迭代法有两种：
- 正推法（递推法）
- 倒推法
正推法的示例：兔子繁殖
倒推法：猴子吃桃
蛮力法定义：枚举法（穷举法）是蛮力法的一种表现形式，它是根据问题中的条件将可能的情况一一列举出来，逐步尝试求解
-
蛮力法的步骤：
- 找出枚举范围
- 找出约束条件
蛮力法的应用：百钱百鸡
-
百钱百鸡算法：
for(int x = 1; x <= 20; x++){ // 公鸡 for(int y = 1; y<= 33; y++){ // 母鸡 int z = 100 - x - y; // 小鸡 if((z % 3 == 0) && (x * 5 + y * 3 + z / 3 == 100)) //核心 } }
第三章 分治法
分治法是用递归实现的
分治法的定义：将一个难以直接解决的大问题分割为几个规模较小的相似问题，再逐个击破
-
分治法的步骤：
- 分解
- 解决
- 合并
-
适用于分治法的问题所应具备的特征：
- 问题能够被分解，且分解后最好相互独立
- 每个小问题都是相似的
- 合并之后能够推出原问题的解
分治法的应用：金砖问题
-
金砖问题算法：
float a[n]; maxmin(int i, int j, float & fmax, float & fmin){ int mid; float lmax, lmin, rmax, rmin; if (i=j){ fmax=a[i]; fmin=a[i]; }else if (i=j-1){ if(a[i] < a[j]){ fmax = a[j]; fmin = a[i]; }else{ fmax = a[i]; fmin = a[j]; } }else{ mid = (i+j)/2; //核心 maxmin(i, mid ,lmax,lmin); maxmin(i, mid, lmax, lmin); //核心 if(lmax>rmax) fmax = lmax; else fmax = rmax; if(lmin>rmin) fmin = rmin; else fmin = lmin; } } 最大子段和问题是用分治法解决的
第四章 贪心算法
- 贪心算法又叫贪婪算法，登山算法
- 贪心算法的根本思想以逐步的局部最优，达到最终的全局最优
- 选择贪心算法需要具有无后向性
- 贪心算法的应用：付款问题，币种统计问题，取数游戏问题
- 贪心算法的基本思想：从问题的某一个初始解出发，逐步逼近给定的目标，每一步都做一个不可回溯的决策，尽可能的求出最好的解，当达到某算法中的某一步，不需要再前进时，算法停止
第五章 动态规划
动态规划的基本思想（动态规划和分治法的异同点）：动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合用于动态规划求解的问题，经分解得到的子问题，往往不是互相独立的，若用分治法来解决这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次
最长公共子序列问题是使用动态规划来解决的
最大子段和不仅可以用动态规划来解决，也可以用分治法解决
仅需知道对于p(i,j)或者p(k,w)都是指i的最优值
- 递推关系式的推导方法：（掌握如何推导）
-
求解最优值
int w[4] = {2,3,4,5}; int v[4] = {3,4,5,6}; for(int i=1; i<=n; i++){ for(int j=1;j<=c,j++){ if(w[i-1]>j){ //核心代码 p[i][j] = p[i-1][j]; }else{ p[i][j] = max(p[i-1][j-w[i-1]]+v[i-1],p[i-1][j]); } } } -
求解最优解
int isp[n]; j = c; for (i = n; i > 0; i--){ if(p[i][j]>p[i-1][j]){ //核心代码 isp[i] = 1; j = j - w[i-1]; }else{ isp[i] = 0; } }
-
矩阵链式方程-状态转移方程
m(i,j)代表最小相乘次数，熟记状态转移方程
第六章 图的搜索
图的定义：顶点的集合以及边的集合，顶点不能为空，边不能为空
-
图的搜索办法：
- 广度优先
- 深度优先
-
深度优先搜索的主要思想：
首先以一个未被访问过的顶点作为起始顶点，延当前顶点的边走到为访问过的顶点，当没有未访问的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问
-
广度优先搜索的主要思想
从根节点开始，沿着树的宽度遍历树的结点
第七章 回溯法
回溯的基本做法是搜索（深度优先）
回溯法的步骤：从根节点出发搜索解空间树
-
回溯法的基本思想：
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树，算法搜索至解空间树的任意结点时，先判断该结点是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先节点回溯，否则进入该子树，继续按深度优先策略搜索，回溯法计算问题的所有解时，要回溯到根，且根结点的所有子树都已经被搜索完成才结束
需要强调的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构
回溯法属于蛮力穷举法，时间复杂度不会太好或者太差，在最坏情况下，时间代价肯定为指数阶
在n皇后问题的可能解中，对应的解空间树有n!个叶子结点，每个叶子结点代表一种可能解，在n=4的情况下，解空间树有65个结点，24个叶子结点
虽然解空间树共有65个结点，24个叶子结点，但在实际搜索过程中，遍历操作只涉及27个结点就找到了满足条件的解，原因在于剪枝函数
图的着色问题是使用回溯法解决的
旅行商问题是使用回溯法解决的
-
教材P218-P219页4，5，6，7，8会考察，尤其关注4，5
-
第四题：n皇后问题：
#include <stdio.h> const int N=10; int a[N]; int count,n; bool check(int x,int y){ for(int i=1;i<=x;i++){ if(a[i]==y) return false; if(i+a[i]==x+y) return false; if(i-a[i]==x-y) return false; } return true; } Print(int n){ count++; printf("第%d种解",count); for(int i=1;i<=n;i++){ printf("(%d,%d)",i,a[i]); } printf("\n"); } void dfs(int row){ if(row>n) { Print(n); return ; } for(int i=1;i<=n;i++){ if (check(row,i)){ a[row]=i; dfs(row+1); a[row]=0; } } } int main(){ printf("输入n*n的棋盘数："); scanf("%d",&n); dfs(1); printf("一共有%d种解",count); return 0; } -
第五题：求子集问题：
#include<iostream> using namespace std; #define NUM 10000 int n; int c; int cw; int bestw; int w[NUM]; int x[NUM]; int r; bool flag; void backtrack(int t) { if(t>n) { if(cw==c) { for(int i=1; i<=n; i++) if (x[i]) printf("%d ",w[i]); printf("\n"); flag = false; } return; } r -= w[t]; if (cw+w[t]<=c) { x[t] = 1; cw += w[t]; backtrack(t+1); cw -= w[t]; } if (cw+r>bestw) { x[t] = 0; backtrack(t+1); } r += w[t]; } int main() { while(scanf("%d%d",&n,&c) && (n||c)) { r = 0; for(int i=1; i<=n; i++) { scanf("%d", &w[i]); r += w[i]; } cw = 0; bestw = 0; flag = true; backtrack(1); if (flag) printf("No Solution!\n"); } return 0; }
-
