【武汉理工大学】算法设计与分析总复习
本文总结了武汉理工大学算法分析与设计课程的主要知识点。
·
目录
第一章 | 算法设计基础
练习题
选择题
算法设计 Smith数问题
#include <iostream>
using namespace std;
//求该数各个项之和
int getsum(int n) {
int sum = 0;
while (n != 0) {
sum += n % 10;
n = n / 10;
}
return sum;
}
//求该数各个质因数之和
int getyinshusum(int n) {
int sum1 = 0;
for (int i = 2; i <= n; i++) {
while(n%i == 0) {
int temp = i;
while (i != 0) {
sum1 += i % 10;
i = i / 10;
}
i = temp;
n = n / i;
}
}
return sum1;
}
int main()
{
int result[500];
int n;
int flag = 0;
while (cin >> n && n != 0) {
for (int j = n + 1;; j++) {
if (getsum(j) == getyinshusum(j)) {
result[flag++] = j;
break;
}
}
}
for (int i = 0; i < flag; i++) {
cout << result[i] << endl;
}
}算法设计 最接近数问题
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int *x = new int[n];
for (int i = 0; i < n; i++)
cin >> x[i];
sort(x, x + n);
int min = x[1] - x[0];
for (int i = 1; i < n-1; i++) {
if (min > x[i + 1] - x[i])
min = x[i + 1] - x[i];
}
cout << min;
return 0;
}第二章 | 算法分析基础
知识点
O(n) 渐进上界记号
Ω(N)渐进下界记号
θ(n)渐进紧界记号
渐进复杂度结论
渐进空间复杂度
递归方程
迭代法求解递归T(n)
代入法求解递归T(n)
递归树法求解递归T(n)
主方法求解递归T(n)
练习题
选择题
第三章 | 分治法
知识点
快速排序
归并排序
二分查找
查找第k小元素
练习题
选择题
算法设计 循环左移问题
算法设计 逆序数问题
#include <iostream>
#include <algorithm>
using namespace std;
int cnt = 0;
template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end){
if (start >= end) {
return;
}
int len = end - start, mid = (len>>2) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) {
if (arr[start1] < arr[start2]) {
reg[k++] = arr[start1++];
}
else{
reg[k++] = arr[start2++];
++cnt;
}
}
while (start1 <= end1) {
reg[k++] = arr[start1++];
}
while (start2 <= end2) {
reg[k++] = arr[start2++];
}
for (k = start; k <= end; k++) {
arr[k] = reg[k];
}
}
template<typename T>
void merge_st(T arr[], const int len){
T reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
int main(int argc, const char * argv[]) {
int n;
cin>>n;
int a[n];
for (int i = 0; i < n; ++i) {
cin>>a[i];
}
merge_st(a, n);
cout<<cnt<<endl;
return 0;
}第四章 | 动态规划
知识点
斐波那契数列问题
动态规划 VS 分治法
三角最长路径问题
从上向下运用动态规划
从下向上运用动态规划
最长递增子序列
最长公共子序列
0-1背包问题
矩阵连乘问题
练习题
算法设计 拦截导弹问题
len=int(input())
height = [int(n) for n in input().split()]
result=[0]*len#存放从第n个元素开始，向后最多能取到的个数
result[len-1]=1
start=len-1
for i in range(1,len):
d=len-1-i#数组中第d个元素
#前一个元素大于最优起点元素，则最多个数加1
if height[d] >= height[start]:
result[d] = result[start]+1
start=d
#否则，向后查找第一个小于该元素的元素，在这个元素的基础上+1
else:
back=[]
for j in range(d+1,len):
if height[j] <= height[d]:
back.append(result[j]+1)
most=max(back)
result[d] = most
print(max(result))算法设计 新水果取名
#include <string>
#include <iostream>
using namespace std;
struct node
{
int pi, pj;
char data;
};
int max(int a, int b)//返回a,b中的最大值
{
int max;
if (a >= b)
max = a;
else
max = b;
return max;
}
node* LCS(char* a, char* b,int x,int y,int &length)//a,b是两个字符串序列，此函数用来求最长公共子序列,x,y是a,b的长度
{
int* *db = new int*[x];//动态规划的表格
for (int i = 0; i < x; i++)
db[i] = new int[y];
for (int i = 0; i < x; i++)//二维数组0行0列不做记录，初始化为0
db[i][0] = 0;
for (int i = 0; i < y; i++)
db[0][i] = 0;
for (int i = 1; i < x; i++)//填表
{
for (int j = 1; j < y; j++)
{
if (a[i] == b[j])
db[i][j] = db[i - 1][j - 1] + 1;
else
db[i][j] = max(db[i - 1][j], db[i][j - 1]);
}
}
int max = db[x - 1][y - 1];
length = max;
node* ch= new node[max];
//倒推求轨迹
int i = x - 1, j = y - 1,k=0;
while (i > 0 && j > 0)
{
if (a[i] == b[j])
{
ch[k].data = a[i];
ch[k].pi = i;
ch[k].pj = j;
k++;
i--; j--;
}
else
{
if (db[i][j - 1] >= db[i - 1][j])
{
j--;
}
else
i--;
}
}
return ch;
}
int main()
{
int m, n;
string fruit1, fruit2;
cin >> fruit1 >> fruit2;
m = fruit1.length();
n = fruit2.length();
char* f1 = new char[m+2];
char* f2 = new char[n+2];
f1[0] = f2[0] = '0';
f1[m + 1] = f2[n + 1] = '\0';
for (int i = 1; i < m+1; i++)
f1[i] = fruit1[i-1];
for (int i = 1; i < n+1; i++)
f2[i] = fruit2[i-1];
int number;
node* ch = LCS(f1, f2, m + 1, n + 1,number);
for (int i = 1, j = 1;i<m+1,j<n+1;)
{
for (int k = number - 1; k >= 0; k--)
{
while (i != ch[k].pi)
{
cout << f1[i];
i++;
}
while (j != ch[k].pj)
{
cout << f2[j];
j++;
}
cout << ch[k].data;
i++;
j++;
}
if (i < m + 1)
{
while (i < m + 1)
cout << f1[i++];
}
if (j < n + 1)
{
while (j < n + 1)
cout << f2[j++];
}
}
return 0;
}算法设计 机器人路径规划
#include<iostream>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
int** a = new int* [m];
for (int i = 0; i < m; i++) {
a[i] = new int[n];
}
for (int i = 0; i < m; i++)
a[i][0] = 1;
for (int i = 1; i < n; i++)
a[0][i] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
a[i][j] = a[i - 1][j] + a[i][j - 1];
}
}
cout << a[m - 1][n - 1];
for (int i = 0; i < m; i++) {
delete[]a[i];
}
delete[]a;
return 0;
}第五章 | 贪心算法
知识点
算法框架
TSP问题
部分背包问题
活动安排问题
哈夫曼编码算法
最短路径算法 Dijkstra
连通无向有权图最小生成树 Prim
最小生成树Kruskal
练习题
算法设计 畜栏问题
#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
class cow
{
public:
int l, r, number=0;
};
class lcompare
{
public:
bool operator()(cow a, cow b)
{
return a.l < b.l;
}
};
class rcompare
{
public:
bool operator()(cow a, cow b)
{
return a.r < b.r;
}
};
int main()
{
int n, ans = 0;
lcompare lcompare1;
rcompare rcompare1;
vector<cow> v1, v2;
cin >> n;
v1.resize(n);
v2.resize(n);
for (vector<cow>::iterator it = v1.begin(); it != v1.end(); it++)
cin >> it->l >> it->r;
v2 = v1;
sort(v1.begin(), v1.end(), lcompare1);
sort(v2.begin(), v2.end(), rcompare1);
for (vector<cow>::iterator it = v1.begin(); it != v1.end(); it++)
{
vector<cow>::iterator a = v2.begin();
if (!v2.empty() && it->l > a->r)
a++;
else
ans++;
}
cout << ans << endl;
}算法设计 区间覆盖问题
#include<iostream>
#include<climits>
#include<set>
using namespace std;
int main() {
int n, k, tempVal, result = 0;
set<int> mySet;//利用集合元素唯一性、有序性储存节点
cin >> n >> k;
//获取n个数字
for (int index = 0; index < n; ++index) {
cin >> tempVal;
mySet.insert(tempVal);
}
tempVal = INT_MIN;//用于记录当前放入的固定区间可覆盖的最大坐标
//贪心算法进行处理
for (auto it = mySet.begin(); it != mySet.end(); ++it) {
if (tempVal < *it) {//说明不能覆盖
result += 1;//添加固定区间的个数
tempVal = *it + k;//更新当前放入的固定区间可覆盖的最大坐标
}
}
cout << result << endl;
return 0;
}第六章 | 搜索、回溯
知识点
搜索的概念
概念
-
搜索算法是一种通用的问题求解方法：首先把问题表示转换为一个状态空间树，然后设计特定的树遍历方法在状态空间中搜索问题的答案
-
为了提高搜索的效率，在遍历状态空间时需要添加优化技术，比如剪枝策略用于尽可能避免无效搜索，启发式信息用来加速朝目标状态逼近的速度。
基于枚举策略的通用搜索
-
DFS
-
BFS
枚举 + 优化的通用搜索
-
回溯算法 = 深度优先搜索 + 剪枝策略
-
分支限界算法 = 广度优先搜索 + 剪枝策略
子集树
排列树
满m叉树
DFS基于递归的代码模板
BFS基于队列的代码模板
回溯法的概念
-
回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解
-
当搜索至树中的任一结点时，先判断该结点是否可能包含可行解，如果肯定不包含，就“回溯”尝试别的路径（剪枝策略）
-
回溯算法 = 深度优先搜索 + 剪枝策略
回溯法代码模板
//x存放解向量，记录从根结点到当前结点的必要信息
void backtrack (int t) // t是递归深度
{
if (t > n) // 递归出口，n表示递归的最大深度
output(x); // 输出问题的解
else
{ for (int i = Init(n, t);i <= Last(n, t); i++)
{ x[t] = Node(i); // 记录当前子结点相关信息
…… //其他操作
if (constraint(x) && bound(x) ){ // 约束函数与限界函数
backtrack(t + 1); // 递归调用，继续深度优先搜索
}
}
}
解空间为排列数的递归回溯
-
最坏为指数阶：解空间树是子集树时对应算法的时间复杂度为O(2n)，排列树为O(n!)。
-
一般情况下：加上剪枝策略后，回溯法的效率一般高于蛮力法。
0-1背包问题 带剪枝的递归回溯算法框架
图的m着色问题
递归框架
练习题
数列的Sum组合问题
package Backtracking;
import java.util.ArrayList;
import java.util.List;
public class LeetCode39_CombineSum {
public static void main(String[] args) {
int[] candidates = {1,2,3,4,5,6};
int target = 5;
List<List<Integer>> res = combinationSum(candidates , target);
System.out.println(res);
}
public static List<List<Integer>> combinationSum(int[] candidates , int target){
List<List<Integer>> ans = new ArrayList<>();
List<Integer> combine = new ArrayList<>();
dfs(candidates , target , ans , combine , 0);
return ans;
}
public static void dfs(int[] candidates , int target , List<List<Integer>> ans , List<Integer> combine , int idx){
if(idx == candidates.length){
return;
}
//若当前的target==0 则说明这一个 combine组合 是一个组合之一.
if(target == 0){
ans.add(new ArrayList<Integer>(combine));
return;
}
//跳过当前数
dfs(candidates , target , ans , combine , idx+1);
//选择当前数（把当前数candidates[idx]加入 combine中，然后target减去当前数，继续进行迭代。）
if(target - candidates[idx] >= 0){
combine.add(candidates[idx]);
dfs(candidates , target-candidates[idx] , ans , combine , idx);
combine.remove(combine.size() - 1);
}
}
}
算法设计 求解最小机器重量设计问题
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXSIZE 101
int n,m,d;
int w[MAXSIZE][MAXSIZE];//存储重量
int c[MAXSIZE][MAXSIZE];//存储价格
int x[2][MAXSIZE];//x[j]表示第j个商品所选取的店铺编号
int min_w=0x7fffffff;//最小的重量
int weight=0;
int price=0;
void get_w(int i){//选取第i个商品
if(i>n){
if(weight<min_w){//商品都选择完毕，如果小于当前最小值，则替换
min_w=weight;
for(int k=1;k<=n;k++){
x[0][k]=x[1][k];//x[0]保存当前最小重量的商铺
}
}
weight-=w[i-1][x[1][n]];//回溯，减去最后一件商品的相关重量和价格
price-=c[i-1][x[1][n]];
}
else{
int j;
for(j=1;j<=m;j++){
weight+=w[i][j];
price+=c[i][j];
if(price<=d){//价格小于d则递归求下一个商品
x[1][i]=j;//第i个商品在第j个店铺选取
get_w(i+1);
}
else{
weight-=w[i][j];//否则回溯
price-=c[i][j];
}
}
if(j==m+1){
weight-=w[i-1][x[1][i-1]];//循环结束再回溯一层
price-=c[i-1][x[1][i-1]];
}
}
}
int main(){
memset(w,0,sizeof(w));//置零
memset(c,0,sizeof(c));
memset(x,0,sizeof(x));
scanf("%d%d%d",&n,&m,&d);//输入初始化
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&w[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&c[i][j]);
get_w(1);
for(int k=1;k<n;k++){
printf("%d ",x[0][k]);
}
printf("%d\n",x[0][n]);
printf("%d",min_w);
return 0;
}
算法设计 求解部分和问题
#include<iostream>
using namespace std;
int x[20];
int n, k, a[20],b=0;
int sum(int num);
void find(int s);
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
find(0);
if (b == 0) {
cout << "NO";
}
return 0;
}
int sum(int num) {
int sum1 = 0;
for (int i = 0; i <= num; i++) {
sum1 = sum1 + x[i];
}
return sum1;
}
void find(int s) {
if (s < n && b != 1) {
for (int i = s; i < n&&b != 1; i++) {
x[s] = a[i];
if (sum(s) < k) {
find(i + 1);
}
if (sum(s) == k) {
cout << "YES";
b = 1;
}
}
}
}
为武汉地区的开发者提供学习、交流和合作的平台。社区聚集了众多技术爱好者和专业人士，涵盖了多个领域，包括人工智能、大数据、云计算、区块链等。社区定期举办技术分享、培训和活动，为开发者提供更多的学习和交流机会。
更多推荐
21
1- 0
已为社区贡献4条内容
所有评论(0)